w2 - func&range Flashcards
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|=n and |C|=m
How many possible functions are there?
General case
Independent of other members of D (i.e., all elements of C are always available)
|D|^|c| =n^m functions
Injective (one-to-one)
Every element of D is mapped to only one of the elements in C (i.e., once one element of C is taken, cannot be used again)
* So always |D|≥|C| i.e., n>m in this case (bijective is m=n)
Hence, First element has n choices, then n−1 choices, then n−2 choices….
n(n−1)(n−2)…(n−m+1)=**n!/(n−m)! **
Surjective (onto)
(later)
**Bijective **
Same as injection but |D|=|B|=n
n∗(n−1)∗(n−2)∗(2)∗(1)=n!
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)]
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)]
Antisymmetric
Formally
Iff for any x,y∈A, then
x R y and y R x only when x=y
That is (another definition):
For all (x,y)∈R, where x≠y, we must have (y,x)∉R
////////////
Informally:
If two elements are related in both directions, they must be equal, OR
For every (x,y) set, ignoring where x is the same as y, the reverse pair (y,x) is also not in the relation
```
Example of:
=(If x=y and y=x, then x = y)
≤, ≥(If a ≤ b and b ≤ a, then c when a = b)
⊆ (if a⊆b and b⊆a, then a=b)
To test: if a(symbol)b and b(symbol)a, then it is antisymmetric if a=b
Let s={1,2,3,4,5}
Antisymmetric example: {(1,1), (2,4), (5,2), (4,2)}
~~~
Eg not of:
Add (4,2) to be NO longer antisymmetric: {(1,1), (2,4), (5,2), (4,2)}
since the reverse pair is also in the relation
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)
