Math 360, Fall 2021, Assignment 2

No doubt many people feel that the inclusion of mathematics among the arts is unwarranted. The strongest objection is that mathematics has no emotional import. Of course this argument discounts the feelings of dislike and revulsion that mathematics induces....

- Morris Kline, Mathematics in Western Culture

Carefully define the following terms, then give one example and one non-example of each:

1. Binary relation (from $A$ to $B$).
2. Reflexive (binary relation).
3. Symmetric (binary relation).
4. Anti-symmetric (binary relation).
5. Transitive (binary relation).
6. Equivalence relation.
7. Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
8. Partition (of a set $A$).
9. $S/\sim$ (the partition arising from the equivalence relation $\sim$ on the set $S$).
10. $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
11. Function (from $A$ to $B$).
12. Domain (of a function).
13. Codomain (of a function).
14. Image (of a function).

Carefully state the following theorems (you do not need to prove them):

1. Theorem relating equivalence relations to partitions.
2. Theorem concerning the key properties of $\equiv_n$ (i.e. "$\equiv_n$ is an...").

Solve the following problems:

1. Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
2. Calculate the cardinality (i.e. the number of elements) of $\mathbb{Z}/\equiv_n$. Illustrate your calculation with a concrete example, listing the elements of $\mathbb{Z}/\equiv_n$ explicitly.
3. A binary relation which is reflexive, anti-symmetric, and transitive is called a partial ordering. Give at least one example of a partial ordering. (Hint: you may wish to ignore the word "partial," which functions here mainly as a distraction.)
4. Now looks for an example of a partial ordering which shows why we should call them partial orderings in general.

--------------------End of assignment--------------------

Solutions

Definitions:

1. Binary relation (from $A$ to $B$): A subset of the Cartesian product $A \times B$. Example: $A=\{1,2,3\},B=\{4,5\},R=\{(1,4),(3,5)\}$, $R$ is a binary relation. Non-example: $A=\{1,2,3\},B=\{4,5\},R=\{(1,2),(3,4)\}$, $R$ is not a binary relation.
2. Reflexive (binary relation): If there is a binary relation $\sim$ on set $S, \forall a \in S, a \sim a$. Example: $\sim$ on $S$, $x \sim y$ if $x = y$. $a=a \rightarrow a \sim a$, reflexive. Non-example: $\sim$ on $S$, $x \sim y$ if $x > y$. $a \ngtr a \rightarrow$ $a \not\sim a$, not reflexive.
3. Symmetric (binary relation): If there is a binary relation $\sim$ on set $S, \forall a, b \in S, a \sim b \rightarrow b \sim a$. Example: $\sim$ on $S$, $x \sim y$ if $x = y$. $a=b$ then $b=a \rightarrow b \sim a$ if $a \sim b$, symmetric. Non-example: $\sim$ on $S$, $x \sim y$ if $x > y$. $a > b, b \ngtr a \rightarrow a \sim b$ $b \not\sim a$, not symmetric.
4. Anti-symmetric (binary relation): If there is a binary relation $\sim$ on set $S, \forall a, b \in S, a \sim b \wedge b \sim a \iff a=b$. Example: $\sim$ on $S$, $x \sim y$ if $x \geqslant y$. $a \geqslant b, b \geqslant a$ then $a = b \rightarrow a \sim b, b \sim a \iff a=b$, anti-symmetric. Non-example: $\sim$ on $S$, $x \sim y$ if $x$ and $y$ have the same last digit. 1 has the same last digit as 11, 11 has the same last digit as 1, $1 \sim 11, 11 \sim 1, 1 \neq 11$, not anti-symmetric.
5. Transitive (binary relation): If there is a binary relation $\sim$ on set $S, \forall a, b, c \in S, a \sim b \wedge b \sim c \rightarrow a \sim c$. Example: $\sim$ on $S$, $x \sim y$ if $x = y$. $a=b \wedge b=c$ then $a=c \rightarrow a \sim c$ if $a \sim b \wedge b \sim c$, transitive. Non-example: $\sim$ on $S$, $x \sim y$ if $x = y + 1$. $a = b + 1, b = c + 1, a = c + 1 + 1 = c + 2 \neq c + 1 \rightarrow a \sim b \wedge b \sim c$, $a \not\sim c$, not transitive.
6. Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
7. Equivalence class: Suppose $a \in S$. the equivalence class of $S$ with respect to $\sim$ is the set of all things that are $\sim$ related to $S:[s]_{\sim} = \{t \in S | s \sim t \}$. Example: The equivalence classes of relation $\equiv_{2}$ are $\{[0]_~,[1]_~\}$. Non-Example: relation $>$ doesn't have equivalence class.
8. Partition (of a set $A$): Let $S$ be a set. A partition of $S$ is a set of subsets, where every element of $S$ belongs to exactly one subset. For example: $S = \{1, 2 ,3,4,5\}, \mathbb P = \{\{1,2\}, \{3,4\},\{5\}\}$ $\mathbb P$ is a partition of $S$. Non-example: $\mathbb k = \{\{1\}, \{3,4\},\{5\}\}$ is not a partition of $S$.
9. ${}^{S}/_\sim$: ${}^{S}/_\sim$ is the set of equivalence classes for which \(\sim\) is the relation on the set $S$. Example:\(\mathbb Z/\equiv_{m} = \{[0], [1] \cdots [m-1]\}\). Non-Example: if $R$ is a relation such that $aRb \rightarrow a<b$, then \(\mathbb Z/R\) is not an equivalence class, because if $a<b$, then \(b \nless a\), thus it is not symmetric and not an equivalence relation.
10. $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$): \(\forall a,b \in \mathbb Z, a \mod n = b \mod n \rightarrow a \equiv_n b\). Example: 13 $\equiv_{2} 1$. Non-example: $13 \not\equiv_{2} 2 $.
11. Function (from $A$ to $B$): A relation from $A$ to $B$ is said to be a function (or mapping) if every elements in $A$ is related to exactly one element in $B$. Example: $A = \{1,2\}. B = \{a,b\}, R = \{(1,a),(2,b)\}$. Non-example: $A = \{1,2\}. B = \{a,b\}, R = \{(1,a),(1,b)\}$
12. Domain (of a function): If R is a function from $A$ to $B$, we write $R: A \rightarrow B$. In this case, $A$ is the domain of $R$. Example: $A = \{1,2\}. B = \{a,b\}, R = \{(1,a),(2,b)\}, \text{dom}(R) = A$. Non-example: $A = \{1,2\}. B = \{a,b\}, R = \{(1,a),(2,b)\}, \text{dom}(R) \neq B$
13. Codomain (of a function): If R is a function from $A$ to $B$, the set $B$ is the codomain of $R$. Example: $A = \{1,2\}. B = \{a,b\}, R = \{(1,a),(2,b)\}, \text{codom}(R) = B$. Non-example: $A = \{1,2\}. B = \{a,b\}, R = \{(1,a),(2,b)\}, \text{codom}(R) \neq \{1,a\}$
14. Image (of a function): The subset of the codomain mapped to by the function. Example: $A = \{1,2\}. B = \{a,b, c\}, R = \{(1,a),(2,b)\}, \text{im}(R) = \{a,b\}$. Non-example: $A = \{1,2\}. B = \{a,b,c\}, R = \{(1,a),(2,b)\}, \text{im}(R) \neq \{a,b,c\}$

---

---

Theorems:

1. If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
2. $\equiv_{n}$ is an equivalence relation and forms equivalence classes on $\mathbb Z$. By being divided by $n$, all integers with the same remainder are in the same equivalence class.

---

---

Book problems:

12. 1. It is a function. Every elements in domain is related to exactly one element in codomain. Not one to one, because $(1,4)(2,4)$, 1 and 2 are related to the same element in codomain. It is not onto, because $\text{im}(B) \neq \text{codom}(B)$.
    2. It is a function. Every elements in domain is related to exactly one element in codomain. Not one to one, because $(1,4)(3,4)$, 1 and 3 are related to the same element in codomain. It is not onto, because $\text{im}(B) \neq \text{codom}(B)$.
    3. Not a function. In domain, element $1$ is related to $3$ different elements in codomain.
    4. It is a function. Every elements in domain is related to exactly one element in codomain. It is one to one, because $2 \rightarrow 2,1 \rightarrow 6,3 \rightarrow 4$, all elements in domain are related to different elements in codomain. It is onto $B$, because $\text{im}(B) = \text{codom}(B)$.
    5. It is a function. Every elements in domain is related to exactly one element in codomain. Not one to one, because $(1,6)(2,6),(3,6)$, 1, 2 and 3 are related to the same element in codomain. It is not onto, because $\text{im}(B) \neq \text{codom}(B)$.
    6. Not a function. In domain, element $2$ is related to $2$ different elements in codomain.
23. There is 1 possible partition of a set with 1 element: the set containing the set containing that element.
25. There are 5 possible partitions of a set with 3 element. For example, for $\{1,2,3\}$, the possible partitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}\}$.
29. $nRm$ in $\mathbb Z$ if $nm>0$. This is not an equivalence relation, because $n=0 \in \mathbb Z$, but $nn = 0(0) \not > 0$.
30. $xRy$ in $\mathbb R$ if $x \geqslant y$. This is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
31. $xRy$ in $\mathbb R$ if $|x| = |y|$. This is an equivalence relation. It is reflexive, because $|x| = |x|$. It is symmetric, because $|x| = |y| \rightarrow |y| = |x|$. It is transitive, because $|x| = |y| \wedge |y| = |z|\rightarrow |x| = |z|$. The partition would be $\{\mathbb R\}$.
33. This is equivalence relation. It is reflexive, because $n$ has the same number of digits as itself. It is symmetric, because if $n$ has the same number of digits as $m$, then $m$ has the same number of digits as $n$. It is transitive, because if $n$ has the same number of digits as $m$ and $m$ has the same number of digits as $p$, then $n$ has the same number of digits as $p$. The partition would be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.

Other Problems:

2. $\mathbb Z/\equiv_{n}$ is the set of equivalence classes, if there is the congruence modulo n relation on the set Z of integers. For congruence modulo n relation, $a \equiv b$ mod(n), $a, b \in \mathbb Z$. Every equivalence classes of congruence modulo n relation should include one element, which is the reminder of n divides any elements in this equivalence class. For example, $4 = 2n + 0$, then there is an equivalence class $[0]$ and $4$ is in the equivalence class $[0]$. So that $\mathbb Z/\equiv_{n}$ should be $\{[0], [1] \cdots [n-1]\}, (n-1$ is the largest reminder any number $\in \mathbb Z$ can be by being divided by n.) Therefore, the cardinality of $\mathbb Z/\equiv_{n}$ should be $n$, because its elements are all integers $\in [0,n-1]$.
3. Example of a partial ordering: for relation $R$ on $S$, $aRb: \{a \leq b|a,b \in S\}$.Reflexive: $a \leq a \rightarrow aRa$. Anti-symmetric: $a \leq b \rightarrow b \leq a$ then $ aRb \rightarrow bRa$ hold when $a = b$. Transitive: $a \leq b \wedge b \leq c \rightarrow a \leq c$: $aRb \wedge bRc \rightarrow aRc$.
4. Except from the example $\preceq$ in the previous answer, another relation $\sqsubseteq$ is also an example. On a set $S$, $\sqsubseteq : \{a\sqsubseteq b | a \subseteq b; a,b \in S \}$.
   
   For both relations $\preceq$ and $\sqsubseteq$, we can draw a graph, whose vertices are all elements of the set which the relation is acting on, and then we connect vertices with an arrow, which represents the relation. For example, $aRb$ will be represented as $a \rightarrow b$. All arrows between different elements will be one-headed arrows. No double-headed arrows will be found in the graph.
   
   Also, if we look at their equivalence classes, every their equivalence class contains only one element, because equivalence class requires symmetry, and their elements meet the requirements if they are the same as themselves. The set of the equivalence class contains partitions of one-element subsets of the set $S$.