Eli
- Understand explanations and definitions.
- Test your understanding by solving a problem.
- Understand questions that require proofs before attempting them.
- Be able to provide a synopsis of definitions, propositions, lemmas, theories, theorems, and the likes.
Sets
The common set notations are $\cap$, $\cup$, $\uplus$, $\sqcap$, and $\in$ that we may encounter in this chapter.
We use the notation
\begin{align}\nonumber
B = \{a \in A | \dots \ ({\rm conditions \ on} \ A) \dots \}
\end{align}
to represent the subset $B$ of the set $A$.
The cardinality or order of a set $A$ is denoted by $|A|$, and if $A$ is a finite set, the cardinality of $A$ is simply the number of elements in it.
The cartesian product of two sets $A$ and $B$ is the collection of ordered pairs of elements from $A$ and $B$ given by
\begin{align}\nonumber
A\times B = \{(a,b)|a\in A, \ b \in B \}.
\end{align}
- A set $A$ is a subset of the set $B$ denoted by $A\subseteq B$ or $B\supseteq A$ if every element of $A$ is in $B$.
- $A\subset B$ or $B \supset A$ implies $A \subseteq B$ but $A \ne B$.
- Every set is a subset of itself. Thus, a set $A$ is a subset of itself, similarly an empty set $\emptyset$.
- If $A$ is any set, then $A$ is the improper subset of $A$. Any other subset of $A$ is a proper subset of $A$.
The following are notations for some common sets of numbers:
- $\mathbb{Z} = \{0, \pm 1, \pm 2, \pm 3 \}$ is used to denote the set of integers.
- $\mathbb{Q} = \{ a/b \ | \ b \ne 0, \ a,b \in \mathbb{Z} \}$ denotes the set of rational numbers (or rationals).
- The set of all decimal expansions, written as $\mathbb{R} = \{d_1d_2d_3 \dots d_n.a_1a_2a_3 \dots a_n \}$ represents real numbers (or reals).
- $\mathbb{C} = \{a+bi \ | \ a, b \in \mathbb{R}, \ i^2 = -1 \}$ denotes the set of complex numbers.
- $\mathbb{Z}^{+}$, $\mathbb{Q}^{+}$, $\mathbb{R}^{+}$, and $\mathbb{C}^{+}$ are used to denote the sets of positive elements of $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$, respectively.
- $\mathbb{Z}^{*}$, $\mathbb{Q}^{*}$, $\mathbb{R}^{*}$, and $\mathbb{C}^{*}$ are the sets of non zero members of $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$.
- $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ have the same cardinality. How ?
- $\mathbb{Z}$ and $\mathbb{Z}^{+}$ have the same cardinality.
The notation $f: A \rightarrow B$ is used to denote a function/mapping $f$ from $A$ to $B$. Here, the words function and mapping can be used interchangeably.
We denote by $f(a)$ the value of $f$ at $a$.
Domain and Codomain
Consider the notation $f: A \rightarrow B$ as previously defined:
- the set $A$ is called the domain of $f$;
- the set $B$ is called the codomain of $f$.
When we say $f$ is well defined, we mean $f$ is unambiguously defined.
Range/Image and Preimage/Inverse
The set
\begin{align}\nonumber
f(A) = \{b\in B \ | \ b = f(a), \ a \in A \}
\end{align}
is a subset of the set $B$, called the range or image of $f$ or the image of $A$ under $f$.
We can simply write the image of $A$ under $f$ as
\begin{align}\nonumber
f(A) = \{f(a) | a \in A \}.
\end{align}
For each subset $C$ of $B$, the set
\begin{align}\nonumber
f^{-1}(C) = \{a \in A \ | \ f(a) \in C \}
\end{align}
(consisting of the elements of $A$ mapping into $C$ under $f$) is called the preimage or inverse image of $C$ under $f$.
One-to-one and Onto Mappings
Let $f: A \rightarrow B$:
- $f$ is one-to-one (i.e., $f$ is injective or an injection) if whenever $a_1 \ne a_2$, we have $f(a_1) \ne f(a_2)$.
- $f$ is onto (i.e., $f$ is surjective or is a surjection) if for all $b \in B$ there is some (at least one) $a\in A$ such that $f(a) = b$, that is the image of $f$ (the image of $A$ under $f$) is all of $B$.
- $f$ is bijective or is a bijection if it is both injective and surjective. If such a bijection $f$ exists from $A$ to $B$ , we say that $A$ and $B$ are in bijective correspondence.
- The function $f$ is onto $B$ if the range of $f$ is $B$.
- Two sets $A$ and $B$ have the same cardinality if there exists a one-to-one function mapping (correspondence) from $A$ onto $B$.
The function mapping $f: \mathbb{R} \rightarrow \mathbb{R}$, where $f(x) = x^2$ is not one-to-one because $f(2) = f(-2) = 4$, but $-2 \ne 2$. Also, $f$ is not onto $\mathbb{R}$ because the range is the proper subset of $\mathbb{R}$, that is the range is only the set of all nonnegative numbers in $\mathbb{R}$.
The Composite Map
If $f:A \rightarrow B$ and $g:B \rightarrow C$, then the composite map $gof: A \rightarrow C$ is defined by
\begin{align}\nonumber
(gof)(a) \rightarrow g(f(a)).
\end{align}
A composite function is a step-wise application. Here is an illustration:
Example 1
Evaluate $fog$ and $gof$, given the following functions:
- $g(x) = 2x+2$.
- $f(x) = x^2 + 1$.
Let's calculate $fog$:
\begin{align}\nonumber
\begin{split}
fog(x) & = f(g(x)) = f(2x + 2)\\
& = (2x + 2)^2 + 1 \\
& = (4x^2 + 8x + 4) + 1 \\
& = 4x^2 + 8x + 5.
\end{split}
\end{align}
Let's calculate $gof$:
\begin{align}\nonumber
\begin{split}
gof(x) & = g(f(x)) = g(x^2 + 1) \\
& = 2(x^2 + 1) + 2 \\
& = 2x^2 + 2 + 2 \\
& = 2x^2 + 4.
\end{split}
\end{align}
As we can see, $fog = 4x^2 + 8x + 5$ and
$gof = 2x^2 + 4.$
Left and Right Inverses
Again, suppose $f: A \rightarrow B$:
- $f$ has a left inverse if there is a function $g: B \rightarrow A$ such that $gof: A \rightarrow A$ is the identity map on $A$, that is, $(gof)(a) = a$ for all $a \in A$.
- $f$ has a right inverse if there is a function $g: B \rightarrow A$ such that $fog: B \rightarrow B$ is the identity map on $B$, that is, $(fog)(b) = b$ for all $b \in B$.
Let $f:A \rightarrow B$:
- The map $f$ is injective if and only if $f$ has a left inverse.
- The map $f$ is surjective if and only if $f$ has a right inverse.
- The map $f$ is a bijection if and only if there exists $g:B \rightarrow A$ such that $fog$ is the identity map on $B$ and $gof$ is the identity map on $A$.
- If $A$ and $B$ are finite sets with the same number of elements, i.e., $|A| = |B|$, then $f: A \rightarrow B$ is bijective if and only if $f$ is injective if and only if $f$ is surjective.
Let $A$ be a nonempty set:
Binary relations
Given two sets $A$ and $B$, a binary relation $R$ from $A$ to $B$ is a subset of $A \times B$, written as $R \subseteq A\times A$, where $A \times B$ denotes the Cartesian product of $A$ and $B$.
A binary relation on a set $A$ is a subset of the Cartesian product of $A$ with itself, that is, a subset of $A \times A$. This is a collection of ordered pairs, where each pair consists of two elements from the set $A$.
More specifically, a binary relation $R$ on a set $A$ is a subset $R$ of $A\times A$, symbolically written as $R \subseteq A \times A$. We write $a R b)$ or $a \sim b$ ($a$ is related to $b$) if $(a, b) \in R.$
Binary relations can be represented in various ways. For example, they can be expressed as a set of ordered pairs, or as a matrix with rows and/or columns representing the elements of A, and so on.
Binary relations can describe various types of relationships between elements of a set. The relation $\sim$ on a set $A$ is said to be:
- Reflexive Relation if every element of $A$ is related to itself. That is, if $a \sim a$ for all $a \in A$. In other words, a binary relation $R$ on $A$ is reflexive if for every element $a \in A$, $(a, a) \in R$.
- Symmetric Relation if $a \sim b$ implies $b \sim a$, $\forall \ a,b \in A$. In other words, a binary relation $R$ on $A$ is symmetric if for every pair $(a, b) \in R$, the pair $(b, a) \in R$.
- Transitive Relation if $a \sim b$ and $b \sim c$ implies $a \sim c$, $\forall \ a, b, c \in A$. In other words, a binary relation $R$ on $A$ is transitive if for every three arbitrary elements $a, b, c \in A$, if $(a, b), (b, c) \in R$, then $(a, c) \in R$. This means if $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$.
A relation is said to be an equivalence relation if it is reflexive, symmetric and transitive.
Equivalence classes
If $\sim$ defines an equivalence relation on $A$, then the equivalence class of $a\in A$ is defined to be
\begin{align}
[a] = \{x \in A | x \sim a\}.
\end{align}
- Elements of the equivalence class of an element $a$ are said to be equivalent to $a$.
- If $C$ is an equivalence class, any element of $C$ is a representative of the class $C$.
A partition of a set $A$ is a collection of nonempty subsets of $A$ such that every element of $A$ is in exactly one of the subsets. Symbolically,
A partitions of a set $A$ is any collection $\{A_i | i \in I\}$ of nonempty subsets of $A$, where $I$ is an index set, such that
- $A = \cup_{i \in I} A_i$, and
- $A_i \cap A_j = \emptyset$ for all $i,j \in I$ with $i \neq j$.
Proposition 2
Let $A$ be a nonempty set:
- If $\sim$ defines an equivalence relation on $A$, then the set of equivalence classes of $\sim$ form a partition of $A$.
- If $\{A_i | i\in I \}$ is a partition of $A$, then there is an equivalence relation on $A$ whose equivalence classes are precisely the sets $A_i$, where $i \in I$.
