w2 - func&range Flashcards
(14 cards)
Injective
for any x1, x2 ∈A
s.t. x1≠ x2 : f(x1) = f(x2)
One to one (between domain and image)
Surjective
given f:A→B
for any y ∈B
there is x ∈A : y= f(x)
image=co-domain
Bijective
Bijective functions are both injective and surjective
* Also called permutation
* An inverse exists
If finite domain, and codomain is the same size = injection ⇒ surjection ⇒ bijection
what type of func can inverse be
Inverse functions exists if and only if it’s a bijection (one-to-one and onto)
Let D be the domain and C be the codomain:
f:D→C
Then the inverse is:
f^(−1):C→D
If f is a ordered pair, just reverse the pair:
{ (y,x):(x,y) belongs to f }
Let f :D→C
and |D|=m and |C|=n
How many possible functions are there?
General case|C|^|D| =n^m functions
Injective (one-to-one)n!/(n−m)!=|C|! / (|C|-|D|)!
Bijective
n!=|C|!
Reflexivity
Properties of Binary relations
R is reflective if R(a,a) for all a∈A
eg ≤ and ≥ (e.g., 3≤3, 5≥5)
NOT eg [< and > (e.g., 2<2 is false)]
Symmetry
Properties of Binary relations
R is symmetric if for any x,y∈A, then R(x,y)⇒R(y,x)
=(e.g., if x=y then y=x)
NOT eg [<, ≤, >, ≥, ⊆, ⊂, ⊃, ⊇ (e.g., 3<4 does not emply 4<3)]
Transitivity
If for all x,y,z∈A, then R(x,y) and R(y,z)⇒R(x,z)
= (If x=y and y=z, then x=z)
≤, ≥. (If a≤b and b≤c, then a≤c)
NOT EG OF [≠ (e.g., 1≠2 and 2≠1, but 1=1, violating transitivity)]
Transitive closure
conditions for TC to be met
Transitive closure can occur if condition 1 is met:
1. if x R y then x R^+ y
* MEANING: every direct relationship in R is automatically included in R^+
* e.g., If a→b is in R, then a→b is also in R^+
AND, either (2) or (3) is also met .
2. if x R^+ y and y R z then x R^+ z
* MEANING If you have a path from x to y in R^+ and a direct step from y to z in R, add a shortcut x→z to R+
* Using existing paths + new paths
* e.g., Suppose a→b is in R^+, and b→c is in R.
Then a→c is added to R+
3. if x R y and y R+ z then x R+ z
* MEANING: If you have a direct step from x→y in R and a path from y → z in R^+, add a shortcut x→z to R+
(Using new paths + existing paths)
* e.g., Suppose a→b is in R, and b→c is in R+. Then a→c is added to R+
~~~
The TC contains all pairs in R (by 1), so
* R^((1) )=R: Direct pairs (e.g., x→y)
* R^((2) ): paris connected by two steps (e.g., x→y→z)
R^((3) ): paris connected by three steps```
In graph theory, it tells us if A is connected to C (that is, if A→B→C, then A→C)
Equivalence relation
Equivalence when it is: Reflexive, symmetric and transitive
Equivalence classes
Let R be an equivalence relation on set A
i.e., R⊆A×A s.t. R is reflexive, symmetric, transitive
The equivalence class of A under R is a subset of X⊆A in which
1. Whenever x,y ∈X we have x R y
* That is, all members of X are equaivalent to each other (all elements in the equivalence class are related to each other)
* Reflexivity: every element is related to itself (x R x)
* Symmetry: If x R y then y R x
* Transitivity: if x R y and y R z then x R z
2. There are no x∈X, z∉X s.t. x R z
* i.e., all members of X are equialent to each other and no member of X is equivalent to anything in A \X
Or in simpler terms: No element in the equivalence class is related to any element outside of it
grouping when they are same
Counting n-ary relations on finite sets
what is |P(A×B)|
Counting A×B
Remembering that
binary relation∈A×B
We can then say
number of possible binary relation = number of subsets of A×B
Remember P(A) gives all the possible subsets of A
So P(A×B) gives all the possible subsets of A×B
Hence, P(A×B)=2^|A×B| =2^(|A|∗|B| )
Compostion of relation
What is R o S
S∘R= {(x,z): ∃y s.t. xRy and ySz}
look from right to left
Informally:
If R = (a,b) and S = (c,d)
Copy c, then copy b such that a=d. Repeat for each element of a and d
We can see it like S(c,d)R(b,a) == (c,a)
What is position and iterated compsition
Let f:A→B and g:B→C
g◦f:A→C
g◦f(x)=g(f(x))
iterated composition:
if f :A→A
f∘f :A→A is defined for all x∈A by f∘f=f(f(x))
We can write f^((n) ) for n copies of f :A→A
(only if domain=CoDomain)
f^((n) )=f∘f∘f∘…∘f
Where there are n copies of f
