2 Sets and Functions Flashcards
Definition 2.1:
Sets
A collection of things, called its elements. π₯βπ΄ := π₯ is an element of the set π΄.
Definition 2.5:
Subsets
Let π΄ and π΅ be sets.
- π΄ is a subset of π΅ (π΄βπ΅) if every element of π΄ also lies in π΅.
- π΄ is empty if π΄ has no elements, i.e. πβπ΄ is never true.
Lemma 2.8
There can only be one
If π΄ is empty, then π΄βπ΅ for any set π΅. In particular, there is precisely one empty set, denoted β .
Definition 2.9:
Power set
For any set π΄, the power set, denoted P(π΄), is the set of all subsets of π΄. Thus π΅βP(π΄)βΊπ΅βπ΄.
i.e. B an element of P(A) iff B is a subset of A
Definition 2.12:
Cardinality of a finite set
Let π΄ be a set containing only finitely many elements. The cardinality of π΄, denoted |π΄|, is the number of elements in π΄.
Definition 2.17:
Unions, intersections and differences
Given sets π΄ and π΅
- union π΄βͺπ΅ = {π₯β£π₯βπ΄ or π₯βπ΅};
- intersection π΄β©π΅ = {π₯β£π₯βπ΄ and π₯βπ΅} = {π₯βπ΄β£π₯βπ΅} = {π₯βπ΅β£π₯βπ΄}
- difference π΄βπ΅={π₯βπ΄β£π₯βπ΅}
- In the special case where π΅βπ΄, the difference π΄βπ΅ is called the complement of π΅ in π΄.
Definition 2.20
Cartesian product
The Cartesian product of sets π΄1,β¦,π΄π for some πβ₯1 is π΄1Γβ―Γπ΄π = { (π1,β¦,ππ) β£ ππβπ΄π for π=1,β¦,π }.
E.g. For π΄={1,3} and π΅={4,5},
π΄Γπ΅={(1,4),(1,5),(3,4),(3,5)}.
Definition 2.20
Cartesian powers
The Cartesian powers of a set π΄ are defined to be π΄^π = { (π1,β¦,ππ) β£ ππβπ΄ for π=1,β¦,π }.
E.g. For π΄={1,3},
π΄^2={(1,1),(1,3),(3,1),(3,3)}.
Definition 2.23
Function
Given sets π΄ and π΅, a function (also called a map) π:π΄βπ΅ is a rule that assigns to every element πβπ΄, a unique element π(π)βπ΅.
We call π΄ the domain of π and π΅ the codomain of π.
Definition 2.25:
Graph of a function
Given a function π:π΄βπ΅, the graph of π is the subset of π΄Γπ΅ given by Graph(π) = { (π,π)βπ΄Γπ΅ β£ π=π(π) }.
Definition 2.28:
Identity map
Let π΄ be a be set.
The identity map idπ΄ is the map whose domain and codomain both equal π΄, and where idπ΄(π)=π for all πβπ΄.
Definition 2.28:
Composition
Let π΄,π΅,πΆ be sets.
Given functions π:π΄βπ΅ and π:π΅βπΆ, their composition (πβπ):π΄βπΆ, which we read as βπ follows πβ, is the function given by (πβπ)(π)=π(π(π)) for πβπ΄.
We do not consider πβπ, unless the codomain of π and the domain of π coincide.
Definition 2.30:
Function spaces
Let π΄ and π΅ be sets. The set of functions from π΄ to π΅ is denoted π΅^π΄ = {functions π΄βπ΅}.
Equivalently, π΅^π΄ = {πΊβπ΄Γπ΅ β£ πΊ is the graph of a function π:π΄βπ΅}
The vertical line test (check if it is a function).
Definition 2.33:
Image of a function
Let π:π΄βπ΅ be a function. The image of π, denoted Im(π), is the subset of π΅ given by
Im(π) = {πβπ΅ β£ π=π(π) for some πβπ΄} = {π(π) β£ πβπ΄}.
Definition 2.34:
Injective
If whenever π,πβ²βπ΄ satisfy π(π)=π(πβ²), it follows that π=πβ².
If there is a solution, then it is unique.
For π:βββ, horizontal line cuts graph of π in at most 1 point.
Definition 2.34:
Surjective
If for all πβπ΅, there exists πβπ΄ such that π=π(π). i.e. Im(π)=π΅.
Every π can be written as a function of π.
Definition 2.34:
Bijective
If π is both injective and surjective.
A unique solution exists for all πβπ΅.
For π:βββ, horizontal line cuts graph of π in exactly 1 point.
Definition 2.41:
Left-inverse
Let π:π΄βπ΅ and π:π΅βπ΄ be functions.
Then π is a left inverse of π if πβπ=idπ΄.
Definition 2.41:
Right-inverse
Let π:π΄βπ΅ and π:π΅βπ΄ be functions.
Then π is a right inverse of π if πβπ=idπ΅.
Definition 2.41:
Two-sided inverse
Let π:π΄βπ΅ and π:π΅βπ΄ be functions.
Then π is a two-sided inverse of π if πβπ=idπ΄ and πβπ=idπ΅.
Definition 2.53:
Finite set
A set π΄ is finite if π΄=β or if there exists πββ and a bijective map π:{1,β¦,π}βπ΄.
The cardinality of π΄ is defined to be 0 when π΄=β , and it is |π΄|:=π when there is a bijective map π:{1,β¦,π}βπ΄.
Definition 2.61:
Countable sets
The set π΄ is countably infinite if there is a bijection π:ββπ΄.
π΄ is countable if π΄ is finite or countably infinite.
Definition 2.62 preface:
Binary relation
A binary relation βΌ on a set π΄ is a property that any given pair of elements of π΄ (π,πβπ΄) either satisfy (πβΌπ), or they do not satisfy (πβπ).
A binary relation βΌ is determined completely by the set {(π,π)βπ΄Γπ΄β£πβΌπ} of pairs that satisfy the relation.
A binary relation on a set π΄ is a subset of π΄Γπ΄ (comprising the pairs (π,π) for which πβΌπ).
Definition 2.62:
Equivalence relation
A binary relation βΌ on a non-empty set π΄ is an equivalence relation if it is reflexive (R), symmetric (S) and transitive (T).
Definition 2.62:
Reflexive
βΌ is reflexive if
for πβπ΄, we have π(π)=π(π), so πβΌπ
Definition 2.62:
Symmetric
βΌ is symmetric if:
πβΌπ β πβΌπ for all π,πβπ΄.
for π,πβπ΄, if π(π)=π(π), then π(π)=π(π).
Definition 2.62:
Transitive
βΌ is transitive if:
(πβΌπ and πβΌπ) β πβΌπ for all π,π,πβπ΄.
Definition 2.64:
Equivalence classes
Let βΌ be an equivalence relation on π΄.
For each πβπ΄, the equivalence class of π is [π] = { π₯βπ΄ β£ π₯βΌπ }.
Let π΄/βΌ = { [π] β£ πβπ΄ } denote the set of equivalence classes.
[π] is the set of elements in π΄ where π₯βΌπ.
Definition 2.67:
Partition of a set
A partition of a set π΄ is a set of pairwise disjoint non-empty subsets of π΄ whose union is π΄.
i.e. a set {π΄_π}(πβπΌ) of non-empty subsets π΄_πβπ΄ such that π΄=β(πβπΌ)π΄_π and (π΄_π)β©(π΄_π)=β for all π,πβπΌ with πβ π.
Definition 2.71:
The set of permutations on π letters
For πββ, a bijective map π:{1,β¦,π}β{1,β¦,π} is called a permutation on π letters.
Let π_π denote the set of all permutations on π letters.
Definition 2.75:
Cyclic permutations
For π<π, an π-cycle in ππ is a permutation πβππ that cyclically permutes π elements of {1,β¦,π} and fixes the remaining elements. We write π = ( π,π(π),β¦,π^(πβ1)(π) ).
Definition 2.75:
Transpositions
A 2-cycle (permutation).
Definition 2.78:
Even and odd permutations
A permutation is [odd/even] if it can be written as the composition of an [odd/even] number of transpositions.
Definition 2.79:
Sign of a permutation
Let sign:ππβ{1,β1} be the function defined by sending a permutation π whose π orbits are cycles of lengths π1,β¦,ππ to
sign(π) = (β1)^[ (π1β1)+(π2β1)+β―+(ππβ1) ].