Sets, Functions, Constructions

Section A.1 Sets, Functions, Constructions

Subsection Sets

Vague Definition A.1. Set.

The basic undefined term we will use is that of a set, which we take to be any collection of objects, not necessarily mathematical ones.

Remark A.2.

A more rigrorous description of sets can be found using the ZFC axioms for set theory, which are listed around here somewhere.

Example A.3. Empty Set.

Example A.4. Sets of Numbers.

Natural Numbers.
The set of natural numbers is denoted by \(\N=\{1,2,3\dots\}\text{.}\)
Integers.
The set of integers is denoted by \(\Z=\{\dots,-2,-1,0,1,2\dots\}\text{.}\)
Rational Numbers.
The set of rational numbers is denoted by \(\Q=\{\frac{p}{q}|p,q\in\Z,q\neq 0\}\text{.}\)
Real Numbers.
The set of real numbers is denoted by \(\R\text{,}\) and is a little trickier to define both rigorously and succinctly. Heuristically, it is the set of all numbers on the number line.
Complex Numbers.
The set of complex numbers is denoted by \(\C=\{a+bi|a,b\in\R\}\text{.}\)

Definition A.5. Set Containments.

Let \(A\) and \(B\) be sets.

The set \(A\) is a subset of the set \(B\text{,}\) denoted \(A \subseteq B\text{,}\) if \(x\in A\) implies \(x\in B\text{.}\)
The set \(A\) equals the set \(B\text{,}\) denoted \(A = B\text{,}\) if \(A \subseteq B\) and \(B \subseteq A\text{.}\)
The set \(A\) is a proper subset of the set \(B\text{,}\) denoted \(A \subset B\text{,}\) if \(A \subseteq B\) and \(A \neq B\text{.}\)

Example A.6. Power Set.

Definition A.7. Union, Intersection.

Let \(A\) and \(B\) be sets. The union of \(A\) and \(B\text{,}\) denoted \(A \cup B\text{,}\) is the set defined by

\begin{equation*} A \cup B = \{x | x\in A \text{ or } x\in B\}\text{.} \end{equation*}

The intersection of \(A\) and \(B\text{,}\) denoted \(A \cap B\text{,}\) is the set defined by

\begin{equation*} A \cap B = \{x | x\in A \text{ and }x\in B\}\text{.} \end{equation*}

Definition A.8. Family of Sets.

Let \(\cA\) be a set. The set \(\cA\) is called a family of sets if all the elements of \(\cA\) are sets. The family of sets \(\cA\) is indexed by \(I\text{,}\) denoted \(\cA = \{A_i\}_{i\in I}\text{,}\) if there is a non-empty set \(I\) such that there is an element \(A_i\in \cA\) for each \(i\in I\text{,}\) and that every element of \(\cA\) equals \(A_i\) for exactly one \(i\in I\text{.}\)

Definition A.9. Union and Intersection of Families of Sets.

Let \(\cA\) be a family of sets. If \(\cA = \{A_i\}i\in I\) is indexed by a set \(I\text{,}\) then we write

\begin{equation*} \bigcup_{i\in I}A_i = \{x | x\in A_i \text{ for some }i\in I\} \text{ and } \bigcap_{i\in I}A_i = \{x | x\in A_i \text{ for all } i\in I\} \end{equation*}

to denote the union and intersection of the sets in \(\cA\text{,}\) respectively.

Theorem A.10. Distributive Laws.

\(A \cap (\bigcup_\alpha B_\alpha ) = \bigcup_\alpha (A \cap B_\alpha )\) and \(A \cup (\bigcap_\alpha B_\alpha ) = \bigcap_\alpha (A \cup B_\alpha )\)

Theorem A.11. De Morgan’s Laws.

\(A \sm (\bigcup_\alpha B_\alpha ) = \bigcap_\alpha (A \sm B_\alpha )\) and \(A \sm (\bigcap_\alpha B_\alpha ) = \bigcup_\alpha (A \sm B_\alpha )\)

Definition A.12. Cartesian Product.

Let \(A, B,\) and \(A_\alpha\) for \(all \alpha \in J\) be sets. The Cartesian product \(A \times B := \{(a,b) | a \in A, b \in B\}\) and \(\prod_{\alpha\in J} A_\alpha := \{(a_\alpha )_{\alpha \in J} | a_\alpha \in A_\alpha\}\)

Exercise A.13. Subsets of Cartesian Products.

If \(A \subseteq G\) and \(B \subseteq H\text{,}\) then \(A \times B \subseteq G \times H\text{.}\)

Subsection Functions

Definition A.14. Function.

Let \(A\) and \(B\) be sets. A function (also called a map) \(f\) from \(A\) to \(B\text{,}\) denoted \(f : A \to B\text{,}\) is a subset \(F \subseteq A \times B\) such that for each \(a\in A\text{,}\) there is one and only one pair in \(F\) of the form \((a, b)\text{.}\) The set \(A\) is called the domain of \(f\) and the set \(B\) is called the codomain of \(f\text{.}\)

Definition A.15. Well-defined Function.

A function \(f: G \to H\) is well-defined if whenever \(g,g' \in G\) and \(g = g'\text{,}\) then \(f(g) = f(g')\text{.}\)

Remark A.16.

All functions are well-defined.

Example A.17. Commonly Encountered Functions.

Constant Map.
A constant map \(f : A \to B\) is any function of the form \(f (x) = b\) for all \(x\in A\text{,}\) where \(b\in B\) is some fixed element. When \(b=0\text{,}\) this is often called the zero map.
Identity Map.
The identity map on \(A\) is the function \(1_A : A \to A\) defined by \(1_A(x) = x\) for all \(x\in A\text{.}\)
Inclusion Map.
The inclusion map from \(S\) to \(A\) is the function \(\iota : S \to A\) defined by \(j(x) = x\) for all \(x\in S\)
Restriction.
If \(f : A \to B\) is a function, the restriction of \(f\) to \(S\text{,}\) denoted \(f|_S\text{,}\) is the function \(f|_S : S \to B\) defined by \(f|_S(x) = f (x)\) for all \(x\in S\text{.}\)
Extension Map.
If \(g : S \to B\) is a function, an extension of \(g\) to \(A\) is any function \(G : A \to B\) such that \(G|S = g\text{.}\)
Projection Map.

The projection maps from \(A \times B\) are the functions \(π_1 : A \times B \to A\) and \(π_2 : A \times B \to B\) defined by \(π_1((a, b)) = a\) and \(π_2((a, b)) = b\) for all \((a, b)\in A \times B\text{.}\) For any finite collection of sets \(A1, \dots, A p\text{,}\) projection maps

\begin{equation*} π_i : A1 \times\cdots \times A p \to A_i \end{equation*}

for all \(i\in {1, \dots, p}\) can be defined similarly.
Characteristic Map.

Let \(X\) be a non-empty set, and let \(S \subseteq X\) be a subset. The characteristic map for \(S\) in \(X\text{,}\) denoted \(χS\text{,}\) is the function \(χS : X \to {0, 1}\) defined by

\begin{equation*} χS(y) = \begin{cases} 1, & if y\in S// 0, & if y\in X - S. \end{cases} \end{equation*}

Definition A.18. Injective, Surjective, Bijective.

Let \(f: X \to Y\) be a function.

The function \(f\) is one-to-one (also called an injection and denoted \(f: X \hookrightarrow Y\)) if whenever \(x,x' \in X\) and \(f(x) = f(x')\) then \(x = x'\text{.}\)
The function \(f\) is onto (also called a surjection and denoted \(f: X ↠ Y\)) if for every \(y\) in \(Y\text{,}\) there is an \(x\) in \(X\) with \(f(x) = y\text{.}\)
The function \(f\) is a bijection if \(f\) is both one-to-one and onto.
The function \(f\) is invertible if there is a function \(g:Y \to X\) such that \(f \circ g = 1_Y\) and \(g \circ f = 1_X\text{.}\)

Exercise A.19. Surjective iff Image is Codomain.

A function \(f:A\to B\) is surjective if and only if \(f(A)=B\text{.}\)

Definition A.20. Composition.

Let \(A\text{,}\) \(B\) and \(C\) be sets, and let \(f : A \to B\) and \(g : B \to C\) be functions. The composition of \(f\) and \(g\) is the function \(g \circ f : A \to C\) defined by

\begin{equation*} (g \circ f )(x) = g( f (x)) \end{equation*}

for all \(x\in A\text{.}\)

Theorem A.21. Compositions and ’Jectivity.

Let \(a: G \to H\text{,}\) \(b: H \to K\text{,}\) and \(c: K \to L\) be functions. Then:

If \(a\) and \(b\) are one-to-one then \(b\circ a\) is one-to-one.
If \(b\circ a\) is one-to-one then \(a\) is one-to-one.
If \(a\) and \(b\) are onto then \(b\circ a\) is onto.
If \(b\circ a\) is onto then \(b\) is onto.
\(a\) is a bijection if and only if \(a\) is invertible.

Definition A.22. Image and Preimage.

Let \(f: X \to Y\) be a function.

The image of a subset \(A\) of \(X\) is \(f(A) := \{f(a) | a \in A\}\text{.}\)
The preimage of a subset \(B\) of \(Y\) is \(f\inv(B) := \{g | g \in X and f(g) \in B\}\text{.}\)
The image \(f\) is \(f(X)\text{.}\)

Theorem A.23. PAN.

If \(f: X \to Y, E \subseteq E' \subseteq Y\text{,}\) and \(E_\alpha \subseteq Y\) for all \(\alpha\text{,}\) then

\(f\inv(E) \subseteq f\inv(E')\text{.}\)
\(f\inv(\bigcup_\alpha E_\alpha ) = \bigcup_\alpha f\inv(E_\alpha )\text{.}\)
\(f\inv(\bigcap_\alpha E_\alpha ) = \bigcap_\alpha f\inv(E_\alpha )\text{.}\)
\(f\inv(E' \sm E) = f\inv(E') \sm f\inv(E)\text{.}\)

Theorem A.24. IASN.

If \(f: X \to Y, C \subseteq C' \subseteq X\text{,}\) and \(C_\alpha \subseteq X\) for all \(\alpha\text{,}\) then

\(f(C) \subseteq f(C')\text{.}\)
\(f(\bigcup_\alpha C_\alpha ) = \bigcup_\alpha f(C_\alpha )\text{.}\)
\(f(\bigcap_\alpha C_\alpha ) \subseteq \bigcap_\alpha f(C_\alpha )\text{.}\) If moreover \(f\) is injective, then \(f(\bigcap_\alpha C_\alpha ) = \bigcap_\alpha f(C_\alpha )\text{.}\)
\(f(C' \sm C) \supseteq f(C') \sm f(C)\text{.}\) If moreover \(f\) is injective, then \(f(C' \sm C) = f(C') \sm f(C)\text{.}\)

Theorem A.25. Containments of Images, Preimages.

Let \(f: X \to Y\text{.}\)

If \(A \subseteq X\text{,}\) then \(A \subseteq f\inv(f(A))\text{;}\) if moreover \(f\) is injective then \(A = f\inv(f(A))\text{.}\)
If \(B \subseteq Y\) then \(f(f\inv (B)) \subseteq B\text{;}\) if moreover \(f\) is surjective then \(f(f\inv(B)) = B\text{.}\)

Proposition A.26. Inclusions are Injective.

If \(B \subseteq A\) and \(\iota:B \to A\) is the inclusion, then \(\iota\) is an injection.

Definition A.27. Projection Map.

Let \(A_\alpha\) for all \(\alpha \in J\) be sets and let \(\beta in J\text{.}\) The projection map \(\pi_\beta : \prod_{ \alpha \in J} A_\alpha \to A_\beta\) is defined by \(\pi_\beta ((a_\alpha )_{\alpha \in J}) = a_\beta \text{ for all }(a_\alpha )_{\alpha \in J} \in \prod_{\alpha \in J} A_\alpha\) .

Definition A.28. Product Inclusion Map.

Let \(A_\alpha\) for all \(\alpha \in J\) be sets, let \(\beta \in J\text{,}\) and for each \(\alpha \in J \sm \{\beta \}\text{,}\) let \(b_\alpha \in A_\alpha\text{.}\) The associated product inclusion map \(\iota_\beta : A_\beta \to \prod_{\alpha \in J} A_\alpha\) is defined for each \(a \in A_\beta\) by \(\iota_\beta (a) := (a_\alpha )_{\alpha \in J}\text{,}\) where \(a_\beta := a \text{ and } a_\alpha := b_\alpha \text{ for all } \alpha \in J \sm \{\beta \}\text{.}\)

Theorem A.29. Properties of Projections and Product Inclusions.

Projection maps are surjections.
Product inclusion maps are injections.

Subsection Set Constructions

Subsubsection Equivalence Relations and Modular Arithmetic

Definition A.30. Equivalence Relation.

An equivalence relation \(\sim\) on a set \(X\) is a subset \(S \sse X \times X\) (where \((a,b) \in S\) is written \(a \sim b\)) that satisfies the following for all \(a,b,c\) in \(X\text{:}\)

Reflexivity.
\(a \sim a\text{,}\)
Symmetry.
\(a \sim b\) implies \(b \sim a\text{,}\) and
Transitivity.
\(a \sim b\) and \(b \sim c\) implies \(a \sim c\text{.}\)

The equivalence class of an element a of \(X\) is \([a]:= \{b | b \sim a\}\text{.}\)

The notation \(X/\sim\) denotes the set of equivalence classes, also called the quotient of \(X\) with respect to \(\sim\text{.}\)

The function \(q:X \to X/\sim\) defined by \(q(p) := [p]\) for all \(p \in X\) is called the quotient map.

Definition A.31. Partition.

A partition of a set \(X\) is a collection of nonempty disjoint subsets of \(X\) whose union is \(X\text{.}\)

Theorem A.32. EPT.

Let \(X\) be a set.

If \(\sim\) is an equivalence relation on \(G\text{,}\) then \(X/\sim\) is a partition of \(X\text{.}\)
If \(\cC\) is a partition of \(X\text{,}\) and \(T = \{(x,y) \in X \times X | x,y \text{ are in the same element of } \cC\}\text{,}\) then \(T\) is an equivalence relation on \(X\text{.}\)

Definition A.33. The Integers Modulo \(n\).

Let \(n\in\N\text{,}\) and let \(a, b\in\Z\text{.}\) The number \(a\) is congruent to the number \(b\) modulo \(n\text{,}\) denoted \(a \equiv b (mod n)\text{,}\) if \(a - b = kn\) for some \(k\in\Z\text{.}\)

For each \(n ∈ N\text{,}\) we obtain a relation on \(\Z\) given by congruence modulo \(n\text{,}\) which we call the integers modulo \(n\text{.}\)

Prev Top Next