Useful Tools on Sets and Functions

Section 1.2 Useful Tools on Sets and Functions

“The excellence of a thing related to its proper function.”
―Aristotle

Subsection 1.2.1 Properties of Sets

Theorem 1.2.1. Distributive laws.

\(A \cap (\cup_\alpha B_\alpha ) = \cup_\alpha (A \cap B_\alpha )\) and \(A \cup (\cap_\alpha B_\alpha ) = \cap_\alpha (A \cup B_\alpha )\)

Theorem 1.2.2. De Morgan's laws.

\(A\setminus (\cup_\alpha B_\alpha ) = \cap_\alpha (A\setminus B_\alpha )\) and \(A\setminus (\cap_\alpha B_\alpha ) = \cup_\alpha (A\setminus B_\alpha )\)

Template to prove two sets are equal

Definition 1.2.3. Power Set.

The power set \(\cP (S)\) of a set \(S\) is the set of all subsets of \(S\text{.}\)

Discussion of standard mathematical conventions for notation Notation for indices: \(i,j,k,m,n\) for finite or countably many indices, \(\alpha,\beta,\dots \) for arbitrarily many indices. Notation for sets, elements of sets, and sets of sets: Small letters \(a,b,c,p,q,x,y,z\) for elements of sets, capital letters \(A,B,C,X,Y,Z\) for sets, calligraphic capital letters \(\cB,\cC,\cT,\cU \) for collections of sets.

Subsection 1.2.2 Properties of functions

Definition 1.2.4.

For a function \(f: G \to H\text{,}\) the set \(G\) is the domain, the set \(H\) is the codomain.

Template to define a function

Template to prove two functions are equal

Definition 1.2.5.

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 1.2.6.

All functions are well-defined.

Definition 1.2.7.

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

The function \(f\) is one-to-one (also called an injection and denoted \(f: X \into 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 \onto 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{.}\)

Theorem 1.2.8.

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

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

Example 1.2.9.

Definition 1.2.10.

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 of \(f\) is \(f(X)\text{.}\)

Example 1.2.11.

Theorem 1.2.12. PAN = “Preimages are nice”.

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

\(f\inv(E) \sse f\inv(E')\text{.}\)
\(f\inv(\cup_\alpha E\alpha ) = \cup_\alpha f\inv(E_\alpha )\text{.}\)
\(f\inv(\cap_\alpha E_\alpha ) = \cap_\alpha f\inv(E_\alpha )\text{.}\)
\(f\inv(E'\setminus E) = f\inv(E')\setminus f\inv(E)\text{.}\)

Theorem 1.2.13. IASN = “Images are sometimes nice”.

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

\(f(C) \sse f(C')\text{.}\)
\(f(\cup \alpha C_\alpha ) = \cup \alpha f(C_\alpha )\text{.}\)
\(f(\cap_\alpha C_\alpha ) \sse \cap_\alpha f(C_\alpha )\text{.}\) If moreover \(f\) is injective, then \(f(\cap_\alpha C_\alpha ) = \cap_\alpha f(C_\alpha )\text{.}\)
\(f(C'\setminus C) \supseteq f(C')\setminus f(C)\text{.}\) If moreover \(f\) is injective, then \(f(C'\setminus C) = f(C')\setminus f(C)\text{.}\)

Theorem 1.2.14.

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

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

Subsection 1.2.3 Constructions of new sets from old ones, and the associated functions

Subsubsection Subsets

Definition 1.2.15.

Let \(A\) be a set. A subset of \(A\) is a set of some (possibly none, possibly all, possibly neither) of the elements of \(A\text{.}\)

Definition 1.2.16.

Let \(B \sse A\text{.}\) The inclusion map is the function \(i:B \to A\) defined by \(i(b) = b\) for all \(b \in B\text{.}\)

Proposition 1.2.17.

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

Subsubsection Product sets

Definition 1.2.18.

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

Example 1.2.19.

Definition 1.2.20.

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

Definition 1.2.21.

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

Example 1.2.22.

Theorem 1.2.23.

Projection maps are surjections.
Product inclusion maps are injections.

Lemma 1.2.24.

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

Axiom 1.2.25. Axiom of Choice.

If \(A_\alpha \ne \es \) for all \(\alpha \in J\text{,}\) then \(\prod_{\alpha \in J} A_\alpha \ne \es \text{.}\)

Subsubsection Quotient sets and equivalence relations

Definition 1.2.26.

An equivalence relation \(\sim \) on a set \(X\) is a subset \(S\) of \(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{:}\)

Reflexive.
\(a \sim a\text{,}\)
Symmetric.
\(a \sim b\) implies \(b \sim a\text{,}\) and
Transitive.
\(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 equivalence map.

Example 1.2.27.

Definition 1.2.28.

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

Proposition 1.2.29.

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{.}\)

Example 1.2.30.

Theorem 1.2.31.

Let \(f: X \to Y\) be a function, and let \(\sim = \{(p,p') \in X \times X | f(p) = f(p')\}\text{.}\) Then \(\sim \) is an equivalence relation on \(X\text{.}\)

Theorem 1.2.32. FBT = Function Building Theorem for quotient sets.

Let \(\sim \) be an equivalence relation on a set \(X\text{,}\) and let \(f: X \to Y\) be a function satisfying the property that whenever \(x,x' \in X\) and \(x \sim x'\) then \(f(x) = f(x')\text{.}\) Then:

There is a well-defined function \(g:X/\sim \to Y\) defined by \(g([x]) = f(x)\) for all \([x]\) in \(X/\sim \text{;}\) that is, \(g \circ q = f\text{,}\) where \(q\) is the equivalence map.
If \(f\) is onto, then \(g\) is onto.
If \(f\) also satisfies the property that whenever \(x,x' \in X\) and \(f(x) = f(x')\) then \(x \sim x'\text{,}\) then \(g\) is one-to-one.

Example 1.2.33.

Template for proving a well-defined function with domain \(X/\sim \text{.}\)

Example 1.2.34.

Definition 1.2.35.

Let \(X\) be a set and let \(S\) be a subset of \(X \times X\text{.}\) The equivalence relation on \(X\) generated by \(S\) is the intersection of all of the equivalence relations on \(X\) that contain \(S\text{.}\)

Subsection 1.2.4 Cardinality

Definition 1.2.36.

A set \(X\) is finite if there is a bijection \(X \to \{1,\dots,n\}\) for some natural number \(n\text{,}\) or \(X\) is empty. In this case the number \(n\) is called the cardinality of \(X\text{.}\)
A set \(X\) is infinite if \(X\) is not finite. A set \(X\) is countable if there is an injection \(X \into \N \text{.}\)

Theorem 1.2.37.

Let \(X\) be a set.

The following are equivalent:
1. \(X\) is finite.
2. There is an onto function \(\{1,\dots,n\} \onto X\) for some \(n \in \N \text{.}\)
3. There is a one-to-one function \(X \into \{1,\dots,n\}\) for some \(n \in \N \text{.}\)
The following are equivalent:
1. \(X\) is infinite.
2. There is an onto function \(X \onto \N \text{.}\)
3. There is a one-to-one function \(\N \into X\text{.}\)
The following are equivalent:
1. \(X\) is countable.
2. There is an onto function \(\N \to X\text{.}\)
3. There is an injection \(X \into \N \text{.}\)

Theorem 1.2.38.

The class of finite sets is closed under: subsets, intersections, finite unions, and finite products.
The class of countable sets is closed under: subsets, intersections, countable unions, and finite products.

Example 1.2.39.

Subsection 1.2.5 Upper and lower bound properties of \(\N\) and \(\R\)

Definition 1.2.40.

An upper bound for a subset \(A \sse \R \) is a real number \(r \in \R \) satisfying \(a \leq r\) for all \(a \in A\text{.}\)
A lower bound for a subset \(A \sse \R \) is a real number \(s \in \R \) satisfying \(s \leq a\) for all \(a \in A\text{.}\)

Definition 1.2.41.

Least upper bound property of \(\R \).
If \(A \sse \R \) and \(A\) has an upper bound, then \(A\) has a least upper bound.
Greatest lower bound property of \(\R \).
If \(A \sse \R \) and \(A\) has a lower bound, then \(A\) has a greatest lower bound.

Theorem 1.2.42. Archimedean property of \(\N \).

\(\N \) has no upper bound in \(\R \text{.}\)