1.1: Sets and Relations
- Page ID
- 22636
1.1.1 The Integers
Kronecker once said, "God made the integers; all the rest is the work of man." Taking this as our starting point, we assume the existence of the set
\[\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3, \ldots\}.\]
the set of integers. Moreover, we assume the properties of the operations of addition and multiplication of integers, along with other elementary properties such as the Fundamental Theorem of Arithmetic, that is, the statement that every integer may be factored into a product of prime numbers and this factorization is essentially unique.
1.1.2 Sets
We will take a naive view of sets: given any property \(p,\) we may determine a set by collecting together all objects which have property \(p .\) This may be done either by explicit enumeration, such as, \(p\) is the property of being one of \(a, b,\) or \(c,\) which creates the set \(\{a, b, c\},\) or by stating the desired property, such as, \(p\) is the property of being a positive integer, which creates the set
\[\mathbb{Z}^{+}=\{1,2,3,4, \ldots\}.\]
The notation \(x \in A\) indicates that \(x\) is an element of the set \(A .\) Given sets \(A\) and \(B,\) we say \(A\) is a subset of \(B,\) denoted \(A \subset B,\) if from the fact that \(x \in A\) it necessarily follows that \(x \in B .\) We say sets \(A\) and \(B\) are equal if both \(A \subset B\) and \(B \subset A .\)
Given two sets \(A\) and \(B,\) we call the set
\[A \cup B=\{x: x \in A \text { or } x \in B\}\]
the union of \(A\) and \(B\) and the set
\[A \cap B=\{x: x \in A \text { and } x \in B\}\]
the intersection of \(A\) and \(B .\) We call the set
\[A \backslash B=\{x: x \in A, x \notin B\}\]
the difference of \(A\) and \(B\).
More generally, if \(I\) is a set and \(\left\{A_{\alpha}: \alpha \in I\right\}\) is a collection of sets, one for each element of \(I,\) then we have the union
\[\bigcup_{\alpha \in I} A_{\alpha}=\left\{x: x \in A_{\alpha} \text { for some } \alpha\right\}\]
and the intersection
\[\bigcap_{\alpha \in I} A_{\alpha}=\left\{x: x \in A_{\alpha} \text { for all } \alpha\right\}.\]
For example, if \(I=\{2,3,4, \ldots\}\) and we let
\[A_{2}=\left\{n: n \in \mathbb{Z}^{+}, n>1, n \neq 2 m \text { for any } m \in \mathbb{Z}^{+} \text {with } m>1\right\}\]
and, for any \(i \in I, i>2\),
\[A_{i}=\left\{n: n \in A_{i-1}, n \neq m i \text { for any } m \in \mathbb{Z}^{+} \text {with } m>1\right\},\]
then \(\cap_{i \in I} A_{i}\) is the set of prime numbers.
If \(A\) and \(B\) are both sets, we call the set
\[A \times B=\{(a, b): a \in A, b \in B\}\]
the cartesian product of \(A\) and \(B .\) If \(A=B,\) we write
\[A^{2}=A \times A.\]
\(\mathbb{Z}^{2}=\{(m, n): m \in \mathbb{Z}, n \in \mathbb{Z}\}\) is the set of all ordered pairs of integers.
1.1.3 Relations
Given two sets \(A\) and \(B,\) we call a subset \(R\) of \(A \times B\) a relation. Given a relation \(R,\) we will write \(a \sim _{R} b\), or simply \(a \sim b\) if \(R\) is clear from the context, to indicate that \((a, b) \in R .\)
We say that an integer \(m\) divides and integer \(n\) if \(n=m i\) for some integer \(i .\) If we let
\[R=\{(m, n): m \in \mathbb{Z}, n \in \mathbb{Z}, m \text { divides } n\},\]
then \(R\) is a relation. For example, \(3 \sim_{R} 12\).
Consider a set \(A\) and a relation \(R \subset A^{2} .\) For purposes of conciseness, we say simply that \(R\) is a relation on \(A .\) If \(R\) is such that \(a \sim _{R} a\) for every \(a \in A,\) we say \(R\) is reflexive; if \(R\) is such that \(b \sim R a\) whenever \(a \sim _{R} b,\) we say \(R\) is symmetric; if \(a \sim_{R} b\) and \(b \sim_{R} c\) together imply \(a \sim_{R} c,\) we say \(R\) is transitive. We call a relation which is reflexive, symmetric, and transitive an equivalence relation.
Show that the relation \(R\) on \(\mathbb{Z}\) defined by \(m \sim_{R} n\) if \(m\) divides \(n\) is reflexive and transitive, but not symmetric.
Show that the relation \(R\) on \(\mathbb{Z}\) defined by \(m \sim_{R} n\) if \(m-n\) is even is an equivalence relation.
Given an equivalence relation \(R\) on a set \(A\) and an element \(x \in A,\) we call
\[[x]=\left\{y: y \in A, y \sim_{R} x\right\}\]
the equivalence class of \(x .\)
Given an equivalence relation \(R\) on a set \(A,\) show that
a. \([x] \cap[y] \neq \emptyset\) if and only if \(x \sim_{R} y\)
b. \([x]=[y]\) if and only if \(x \sim_{R} y .\)
As a consequence of the previous exercise, the equivalence classes of an equivalence relation on a set \(A\) constitute a partition of \(A\) (that is, \(A\) may be written as the disjoint union of the equivalence classes).
Find the equivalence classes for the equivalence relation in Exercise 1.1.2.