CMPUT272 Lecture Notes - Lecture 20: Coimage, Cross Product, Binary Relation

45 views4 pages
November 18 2014
ETLC 2-001
Definitions wrt functons / Bender and Williamson notations
B^A: Set of all functions from A to B
f B^A f: A -> B
_n_ = {1, 2, ..., n}
So _4_^_3_ = is the set of functions from {1,2,3} -> {1,2,3,4}
{{(1,1),(2,3),(3,3)}, {...}, ...}
If a set A is finite and ordered
then the functions that are elements of B^A
can be specified with a 'one-line notation':
each function is a list of length |A| of elements of B
f _4_^_3_, f = {(1,1), (2,3), (3,3)}
in 1line, looks like: (1,3,3)
f = (1,3,3)
B^A, (set of function)
B^|A| (cross product of B to the cardinality A)
Suppose f is a function
Let f: A -> B
Image
Image(f) = Elements of B that get mapped to, {f(a)|a A}
The image of a A is f(a)
Inverse Image
For all b B, the inverse image of b is: f^-1(b)
The set of elements from a where f(a) = b
f^-1(b) = {a | a A f(a) = b}∈ ∧
f^-1(3) = {2,3}, f^-1(1) = {1}, f^-1(4) =
Coimage
The coimage of f: A -> B is the set of non-empty inverse images
of
elements of B
Coimage(f) = {f^-1(b)|b B}
coimage(f) = {{2,3}, {1}}
Binary Relations
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Definitions wrt functons / bender and williamson notations. B^a: set of all functions from a to b f b^a f: a -> b. So _4_^_3_ = is the set of functions from {1,2,3} -> {1,2,3,4} B^|a| (cross product of b to the cardinality a) Image(f) = elements of b that get mapped to, {f(a)|a a} . For all b b, the inverse image of b is: f^-1(b) The set of elements from a where f(a) = b f^-1(b) = {a | a a f(a) = b} f^-1(3) = {2,3}, f^-1(1) = {1}, f^-1(4) = . The coimage of f: a -> b is the set of non-empty inverse images of elements of b. Coimage(f) = {f^-1(b)|b b} coimage(f) = {{2,3}, {1}} Each is a subset of a^2 = a a . To visualize/represent r: incidence matrix a1 a2 a3 u an 1 if (u,n) r else 0 a1 a2 a3 w an .

Get access

Grade+20% OFF
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers