cartan.math.umb.edu - User contributions [en]

Math 360, Fall 2021, Assignment 2

2021-09-21T16:38:42Z

Michael.reilly002: /* Book problems: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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)$.</li>
<li> 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)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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)$. </li>
<li> 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)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 possible partition of a set with 1 element: the set containing the set containing that element.
<li value=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\}\}$.
<li value=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$.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. This is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=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\}$.
<li value=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\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-21T16:36:30Z

Michael.reilly002: /* Book problems: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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)$.</li>
<li> 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)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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)$. </li>
<li> 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)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 possible partition of a set with 1 element: the set containing the set containing that element.
<li value=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\}\}$.
<li value=29> $nRm$ in $\mathbb Z$ if $nm>0$. This is not an equivalence relation, because $0 \in \mathbb Z, n=0 \land m = 0 \rightarrow nm \not > 0$.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. This is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=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\}$.
<li value=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\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-21T16:34:52Z

Michael.reilly002: /* Book problems: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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)$.</li>
<li> 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)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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)$. </li>
<li> 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)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 possible partition of a set with 1 element: the set containing the set containing that element.
<li value=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\}\}$.
<li value=29> $nRm$ in $\mathbb Z$ if $nm>0$. This is not an equivalence relation, because $0 \in \mathbb Z, n=0 \land m \in \mathbb Z \rightarrow nm \not > 0$.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. This is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=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\}$.
<li value=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\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Talk:Math 360, Fall 2021, Assignment 2

2021-09-21T16:31:54Z

Michael.reilly002: /* More Changes: */

== Changes (Michael Reilly) ==

Most of the changes to the definitions I did were minor grammar changes or modifying TeX formulas and markup formatting, just to make answers easier to read. The only substantive change I made was to codomain and image, because the definitions were backwards: the codomain of a function is all possible values, the image of a function are the elements of the codomain specifically mapped to.

=== More Changes: ===

I am going through the answers, and some of them were wrong. For Section 0, problem 12, the confusion between codomain and image from the definitions section carried over and several of the functions were incorrectly noted as “onto” when they were not.

I cleaned up the formatting and readability of the answers for the rest of the book questions. I thought the answer to 29 was incorrect, but it was not, I was, I am reverting it now.

Math 360, Fall 2021, Assignment 2

2021-09-21T16:29:44Z

Michael.reilly002: /* Book problems: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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)$.</li>
<li> 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)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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)$. </li>
<li> 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)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 possible partition of a set with 1 element: the set containing the set containing that element.
<li value=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\}\}$.
<li value=29> $nRm$ in $\mathbb Z$ if $nm>0$. This is an equivalence relation. It is reflexive, because $n\neq 0\rightarrow nn>0$. It is symmetric, because $nm>0 \rightarrow mn > 0$. It is transitive, because $ab>0$ implies that $a$ and $b$ are both nonzero integers that share a sign, likewise for $bc>0$, and therefore $a$ and $c$ must also share a sign and $aRc$. The partition of this equivalence relation would be the sets of nonzero integers that share a sign, $\{\mathbb Z^+,\mathbb Z^-\}$.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. This is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=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\}$.
<li value=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\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Talk:Math 360, Fall 2021, Assignment 2

2021-09-21T15:59:37Z

Michael.reilly002: /* Changes (Michael Reilly) */

Math 360, Fall 2021, Assignment 2

2021-09-21T15:57:45Z

Michael.reilly002: /* Book problems: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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)$.</li>
<li> 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)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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)$. </li>
<li> 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)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-20T17:31:31Z

Michael.reilly002: /* Definitions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-20T17:30:58Z

Michael.reilly002: /* Definitions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Talk:Math 360, Fall 2021, Assignment 2

2021-09-20T17:24:32Z

Michael.reilly002: /* Changes (Michael Reilly) */

Math 360, Fall 2021, Assignment 2

2021-09-20T17:13:07Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions==
===Definitions:===
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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:===
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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:===
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

===Other Problems:===
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-20T17:09:47Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==
Definitions:
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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.

----

----
Section 0 problems:
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

----

----
<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-20T17:08:10Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==
# 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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\}$

----

----
Theorem
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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.

----

----
Section 0 problems:
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

----

----

<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-20T17:06:56Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==
# Binary relation (from $A$ to $B$): is 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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\}$

----

----
Theorem
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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.

----

----
Section 0 problems:
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

----

----

<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Math 360, Fall 2021, Assignment 2

2021-09-20T17:06:00Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==
# Binary relation (from $A$ to $B$): is 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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\}$

----

----
Theorem
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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.

----

----
Section 0
<ol>
<li value=12>
<ol type=a>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$.</li>
<li> 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $1$ is related to $3$ different elements in codomain.</li>
<li> 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. </li>
<li> 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. </li>
<li> Not a function. In domain, element $2$ is related to $2$ different elements in codomain. </li>
</ol>
<li value=23> There is 1 partition of a set with 1 element.
<li value=25> There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
<li value=29> $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
<li value=30> $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
<li value=31> $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
<li value=33> It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.
</ol>

----

----

<ol start=2>
<li>$\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]$.</li>
<li>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$.</li>
<li>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$.
</li>
</ol>

Talk:Math 360, Fall 2021, Assignment 2

2021-09-20T15:14:44Z

Michael.reilly002: Created page with "== Changes (Michael Reilly) == Most of the changes to the definitions I did were minor grammar changes or modifying TeX formulas, just to make answers easier to read. The onl..."

== Changes (Michael Reilly) ==

Most of the changes to the definitions I did were minor grammar changes or modifying TeX formulas, just to make answers easier to read. The only substantive change I made was to codomain and image, because the definitions were backwards: the codomain of a function is all possible values, the image of a function are the elements of the codomain specifically mapped to.

Math 360, Fall 2021, Assignment 2

2021-09-20T15:11:02Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''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:==

# Binary relation (from $A$ to $B$).
# Reflexive (binary relation).
# Symmetric (binary relation).
# Anti-symmetric (binary relation).
# Transitive (binary relation).
# Equivalence relation.
# Equivalence class (of an element $a\in A$, with respect to an equivalence relation $\sim$ on $A$; also known as $\left[a\right]_\sim$).
# Partition (of a set $A$).
# $S/\sim$ (the ''partition arising from the equivalence relation $\sim$ on the set $S$'').
# $\equiv_n$ (the relation of congruence modulo a non-negative integer $n$).
# Function (from $A$ to $B$).
# Domain (of a function).
# Codomain (of a function).
# Image (of a function).

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

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

==Solve the following problems:==

# Section 0, problems 12, 23, 25, 29, 30, 31, 32, and 33.
# 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.
# 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.)''
# Now looks for an example of a partial ordering which shows why we should call them ''partial'' orderings in general.

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==
# Binary relation (from $A$ to $B$): is 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.
# 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.
# 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.
# 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.
# 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.
# Equivalence relation: A relation on $S$ which is reflexive, symmetric and transitive. Example: $xRy: x = y$. Non-example: $xRy: x = y+1$.
# 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.
# 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$.
# ${}^{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.
# $\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 $.
# 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)\}$
# 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$
# 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\}$
# 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\}$

----

----
Theorem
# If we have an equivalence relation $R$ on $A$, the equivalence classes of $R$ form a partition of $A$.
# $\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.

----

----
Section 0
# (12) a. 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. b. 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 onto $B$, because all elements in codomain $(\{4,6\})$ are in $Im(B)$. c. Not a function. In domain, element $1$ is related to $3$ different elements in codomain. d. 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 all elements in codomain $(\{2, 4,6\})$ are in $Im(B)$. e. 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 onto $B$, because all elements in codomain $(\{6\})$ are in $Im(B)$. f. Not a function. In domain, element $2$ is related to $2$ different elements in codomain.
# (23) There is 1 partition of a set with 1 element.
# (25) There are 5 partitions of a set with 3 element. For example, for $\{1,2,3\}$ petitions are $\{\{1,2,3\}\}, \{\{1,2\},3\}, \{\{1,3\},2\},\{1,\{2,3\}\},\{\{1\},\{2\},\{3\}$
# (29) $nRm$ in $\mathbb Z$ if $nm > 0$. If $n = 0, nn = 0 /ngtr 0$. Not an equivalence relation.
# (30) $xRy$ in $\mathbb R$ if $x \geqslant y$. It is not an equivalence relation. $5 \geqslant 3$ but $3 \ngeq 5$, not symmetric.
# (31) $xRy$ in $\mathbb R$ if $|x| = |y|$ is an equivalence relation. Reflexive:$|x| = |x| \rightarrow xRx$; Symmetric: if $|x| = |y|, x = \pm y, |y| = |x| \rightarrow$ if $xRy, yRx$; Transitive: $|x| = |y| \wedge |y| = |z|, x = \pm y, y = \pm z$ then $x = \pm z, |x| = |z| \ rightarrow$ if $xRy \wedge yRz$ then $xRz$. The partition should be $\{\{0\},\{1, -1\},\{2, -2\} \cdots\}$.
# (33) It is equivalence relation. Reflexive: n has the same number of digits as itself, $nRn$; Symmetric: if n has the same number of digits, k digits, as m, the m has the same number of digits, k digits as n, $nRm \rightarrow mRn$; Transitive: if n has the same number of digits, $k_{1}$ digits, as m, m has the same number of digits, $k_{2}$ digits, as p, then $k_{1}=k_{2}$, n has the same number of digits as p, $nRm \wedge mRp \rightarrow nRp$. The partition should be $\{\{n_{1} | n_{1} \in [0,9]\},\{n_{2} | n_{2} \in [10,99]\}, \{n_{3} | n_{3} \in [100,999]\} \cdots\}$.

----

----

# $\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]$.
# 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$.
# 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$.

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T21:04:56Z

Michael.reilly002: /* More Changes */

==Revisions (Michael Reilly):==

# Revised definition of “containment”: containment only refers to relationships between sets, “membership” is the term discussed in class that applied to individual elements in a set.
# Revised definition of “equality”: equality does not care about cardinality, because sets can be equal and have different cardinalities, if an element is repeated. Set equality is only concerned with whether the sets are subsets of each other (ie., all elements of each set are elements of the other set).
# revised definition of “property”: it is important to be specific that a “property” must be a true or false statement, the original definition was ambiguous.
# revised book problem (4): the instructions said specifically to list the elements of the set, the set was already described using a rule. Also, the rule that was given as an answer to this question said that all integers between -10.2 and 11.2 are included, and while that answer logically makes sense as there are integers between those values, typically integers are listed with integer bounds, so it would be $-10 \leq x \leq 11$.
# revised proof of largest set: The proof was hard to follow, and I don’t think even proved what the question asked. The proof was a proof by contradiction, but I think it followed faulty logic. The basic structure was: “Proof of Proposition P. Assume P is false. P=false creates a contradiction, therefore P is false.” Luckily, there is a much simpler proof that is based on the definition of the Power Set, which I have put there instead.

==More Changes==
# In my proof, I first assume “There is largest set is true, and S is this largest set”, then I prove that “there is a set larger than S”, therefore “S is not the largest set”, proved by contradiction that “There is a largest set S is not true”. I think it would work.
# and about equality, I found at storyofmathematics.com that “Two sets are said to be equal if they contain the same elements and the same cardinality. This concept is known as Set Equality.” I can’t remember clearly, but have we talked about not considering multisets in class?
- We have not discussed them in class yet, no. The definition I put is the definition we were given in class, where $\{1,2\} \text{ and } \{1,2,2\}$ were said to be equivalent. Maybe that definition applies to “simplified” sets, where duplicates are omitted?
# $\{1,2,2\}$ is a multi set, I remembered we talked about it in class. But I don’t remember if we should take it into consideration, or multi set is not considered in Abstract algebra? If we should, then I would agree that cardinalities don’t have to be the same.
# Perhaps “every element in any of the two sets can be found in another, then these two sets are equal” would be better
- That’s exactly what “they are subsets of each other” means, but less wordy.

Also, that’s a good idea, putting multiple solutions to each answer. I wish I had thought of that, I apologize for deleting the original answer to proof 4.

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T20:33:30Z

Michael.reilly002: /* More Changes */

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T20:33:08Z

Michael.reilly002: /* More Changes */

==Revisions (Michael Reilly):==

# Revised definition of “containment”: containment only refers to relationships between sets, “membership” is the term discussed in class that applied to individual elements in a set.
# Revised definition of “equality”: equality does not care about cardinality, because sets can be equal and have different cardinalities, if an element is repeated. Set equality is only concerned with whether the sets are subsets of each other (ie., all elements of each set are elements of the other set).
# revised definition of “property”: it is important to be specific that a “property” must be a true or false statement, the original definition was ambiguous.
# revised book problem (4): the instructions said specifically to list the elements of the set, the set was already described using a rule. Also, the rule that was given as an answer to this question said that all integers between -10.2 and 11.2 are included, and while that answer logically makes sense as there are integers between those values, typically integers are listed with integer bounds, so it would be $-10 \leq x \leq 11$.
# revised proof of largest set: The proof was hard to follow, and I don’t think even proved what the question asked. The proof was a proof by contradiction, but I think it followed faulty logic. The basic structure was: “Proof of Proposition P. Assume P is false. P=false creates a contradiction, therefore P is false.” Luckily, there is a much simpler proof that is based on the definition of the Power Set, which I have put there instead.

==More Changes==
# In my proof, I first assume “There is largest set is true, and S is this largest set”, then I prove that “there is a set larger than S”, therefore “S is not the largest set”, proved by contradiction that “There is a largest set S is not true”. I think it would work.
# and about equality, I found at storyofmathematics.com that “Two sets are said to be equal if they contain the same elements and the same cardinality. This concept is known as Set Equality.” I can’t remember clearly, but have we talked about not considering multisets in class?
- We have not discussed them in class yet, no. The definition I put is the definition we were given in class, where $\{1,2\}$ and $\{1,2,2\}$ were said to be equivalent. Maybe that definition applies to “simplified” sets, where duplicates are omitted?

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T20:32:42Z

Michael.reilly002: /* Revisions (Michael Reilly): */

==Revisions (Michael Reilly):==

# Revised definition of “containment”: containment only refers to relationships between sets, “membership” is the term discussed in class that applied to individual elements in a set.
# Revised definition of “equality”: equality does not care about cardinality, because sets can be equal and have different cardinalities, if an element is repeated. Set equality is only concerned with whether the sets are subsets of each other (ie., all elements of each set are elements of the other set).
# revised definition of “property”: it is important to be specific that a “property” must be a true or false statement, the original definition was ambiguous.
# revised book problem (4): the instructions said specifically to list the elements of the set, the set was already described using a rule. Also, the rule that was given as an answer to this question said that all integers between -10.2 and 11.2 are included, and while that answer logically makes sense as there are integers between those values, typically integers are listed with integer bounds, so it would be $-10 \leq x \leq 11$.
# revised proof of largest set: The proof was hard to follow, and I don’t think even proved what the question asked. The proof was a proof by contradiction, but I think it followed faulty logic. The basic structure was: “Proof of Proposition P. Assume P is false. P=false creates a contradiction, therefore P is false.” Luckily, there is a much simpler proof that is based on the definition of the Power Set, which I have put there instead.

==More Changes==
# In my proof, I first assume “There is largest set is true, and S is this largest set”, then I prove that “there is a set larger than S”, therefore “S is not the largest set”, proved by contradiction that “There is a largest set S is not true”. I think it would work.
# and about equality, I found at storyofmathematics.com that “Two sets are said to be equal if they contain the same elements and the same cardinality. This concept is known as Set Equality.” I can’t remember clearly, but have we talked about not considering multisets in class?
- We have not discussed them in class yet, no. The definition I put is the definition we were given in class, where $\{1,2}\}$ and $\{1,2,2}\}$ were said to be equivalent. Maybe that definition applies to “simplified” sets, where duplicates are omitted?

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T19:42:50Z

Michael.reilly002: /* Revisions (Michael Reilly): */

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T18:07:40Z

Michael.reilly002:

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T17:56:18Z

Michael.reilly002: /* Revisions (Michael Reilly): */

User talk:Michael.reilly002

2021-09-13T17:36:06Z

Michael.reilly002: Blanked the page

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T17:35:26Z

Michael.reilly002:

Talk:Math 360, Fall 2021, Assignment 1

2021-09-13T17:34:57Z

Michael.reilly002: Created page with "== Revisions (Michael Reilly): # Revised definition of “containment”: containment only refers to relationships between sets, “membership” is the term discussed in cla..."

== Revisions (Michael Reilly):

# Revised definition of “containment”: containment only refers to relationships between sets, “membership” is the term discussed in class that applied to individual elements in a set.
# Revised definition of “equality”: equality does not care about cardinality, because sets can be equal and have different cardinalities, if an element is repeated. Set equality is only concerned with whether the sets are subsets of each other (ie., all elements of each set are elements of the other set).
# revised definition of “property”: it is important to be specific that a “property” must be a true or false statement, the original definition was ambiguous.
# revised book problem (4): the instructions said specifically to list the elements of the set, the set was already described using a rule. Also, the rule that was given as an answer to this question said that all integers between -10.2 and 11.2 are included, and while that answer logically makes sense, there are integers between those values, typically integers are listed with integer bounds, so it would be $-10 \leq x \leq 11$.
# revised proof of largest set: The proof was hard to follow, and I don’t think even proved what the question asked. The proof was a proof by contradiction, but I think it followed faulty logic. The basic structure was: “Proof of Proposition P. Assume P is false. P=false creates a contradiction, therefore P is false.” Luckily, there is a much simpler proof that is based on the definition of the Power Set that is definitional and doesn’t require proof by contradiction, which I have put there instead.

User talk:Michael.reilly002

2021-09-13T17:06:46Z

Michael.reilly002:

What's wrong with my answer?

Which answer was yours? I changed a few of them.

Math 360, Fall 2021, Assignment 1

2021-09-13T16:55:09Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''By one of those caprices of the mind, which we are perhaps most subject to in early youth, I at once gave up my former occupations; set down natural history and all its progeny as a deformed and abortive creation; and entertained the greatest disdain for a would-be science, which could never even step within the threshold of real knowledge. In this mood of mind I betook myself to the mathematics, and the branches of study appertaining to that science, as being built upon secure foundations, and so, worthy of my consideration.''

: - Mary Shelley, ''Frankenstein''

==Read:==

# Section 0.

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

# Containment (of sets).
# Equality (of sets).
# Property.
# Ordered pair.
# Cartesian product (of two sets).

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

# Russell's paradox (this is not really a theorem, but it is an important fact).
# Basic counting principle (relating the size of $A\times B$ to the sizes of $A$ and $B$).

==Solve the following problems:==

# Section 0, problems 1, 2, 3, 4, 5, 6, 7, 8, and 11.
# Prove that for any set $S$, it must be the case that $\emptyset\subseteq S$. ''(Hint: begin with "Suppose not. Then by the definition of set containment, there must be some member of $\emptyset$ which is not a member of $S$. But...".)''
# Now suppose $S$ is any set with $S\subseteq\emptyset$. Prove that $S=\emptyset$. ''(Hint: use the previous result together with the definition of set equality.)''
# The previous two exercises show that $\emptyset$ is the "smallest of all sets." Is there a "largest of all sets?" (For more information on this question as well as on Russell's Paradox and its resolutions, see [https://en.wikipedia.org/wiki/Universal_set Wikipedia: Universal Set].)

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==

# Containment: Set A is contained in set B if each element in A is also an element in B. This is also the definition of a subset. For example: $ \{1,2\} \subseteq \{1,2,5\}$, $\{1,2,3\} \not\subseteq \{1,2,5\}$.
# Equality: two sets are equal if they are mutually subsets of each other. If there are two sets $A \textrm{ and } B$. $A \subseteq B \wedge B \subseteq A \Leftrightarrow A = B$
# Property: a statement that must be able to be evaluated as true or false about an object. For example $\{ x| x \textrm{ is even } \wedge x \leqslant 8\}$. However, "x is almost an integer" is not a property, as it is not well-defined.
# Ordered Pair: two associated objects, the order of which is significant. In an ordered pair $(a,b), a \textrm{ is the first element and } b \textrm{ is the second}. (a,b) \neq (b,a) \textrm{ if } a \neq b.$ For example, $(1,2) = (1,2) \textrm{ because } 1 = 1, 2=2$ and $(1,2) \neq (2,1) \textrm{ because } 1 \neq 2, 2 \neq 1.$
# Cartesian Product of Two Sets: $\textrm{if } A, B \textrm{ are two sets:}$ $A \times B = \{(a,b) | a \in A \wedge b \in B\}$. For example, $\{1,2\} \times \{3,4\} = \{(1,3),(1,4),(2,3),(2,4)\}$. As a non-example, $\{1,2\} \times \{3,4\} \neq \{(1,2),(3,4)\}$
#Russell's paradox: if $R \textrm{ is a set and } R = \{x|x \neq x \}$, can one say $R \in R$ or not? Assume that $R \in R, \textrm{ then } R \notin R \textrm{ according to set R's property. However, if } R \notin R, \textrm{ according to R's property, } R \in R$ which creates paradox.
#Basic Counting Principle: if there are a elements in set A and b elements in set B, there should be $a \times b$ pairs (or elements) in the set which represents Cartesian Product of set A and B. $|A \times B| = |A| \times |B|$, $(|A|$ is the cardinality of set A).

----
Section 0

# $\{x \in \mathbb R | x^{2} = 3\}$ $ x \in R \rightarrow x \textrm{ are elements contained in the real number set}$, $x^{2} = 3 \rightarrow \textrm{ elements in the real number set which have their square } = 3 $. $x^{2} = 3$, $x = \pm \sqrt{3}$, therefore, this set is $\{\sqrt{3} , -\sqrt{3} \}$
# $\emptyset$
# $\{1,2,3,4,5,6,10,12,15,20,30,60\}$
# $\{m \in \mathbb Z | m^{2} - m < 115\}$, m are all integers. $m^{2} - m < 115 \rightarrow m^{2} - m - 115 < 0$, $m = -10.24 \textrm{ and } m = 11.24 \textrm{ when } m^{2} - m - 115 < 0$, $ (m^{2} - m - 115)' = 2m - 1 = 0, m = \frac{1}{2}, m^{2} - m - 115 < 0 \textrm{ when } m = \frac{1}{2}$. Therefore, $-10.24 < m < 11.24$, the set is $\{-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$
# Not well-defined, because "large number" is not unique value.
# $\emptyset$
# $\emptyset$
# Not well-defined, because "almost an integer" is not unique value.
----
Solve Problems

# Suppose that $\emptyset \nsubseteq S$, $\exists a \in \emptyset \wedge a \notin S$. However, $\forall a, a \notin \emptyset$. Therefore, $\forall a \notin S, a \notin \emptyset$. Proved by contradiction that $\forall S, \emptyset \subseteq S$
# Suppose that $S \subseteq \emptyset \wedge S \neq \emptyset$, which means that $\emptyset \nsubseteq S$. From the previous proof, we know that $\forall S, \emptyset \subseteq S$. $ \emptyset \subseteq S \wedge S \subseteq \emptyset$ Proved by contradiction that $\forall S \subseteq \emptyset, S = \emptyset$.
# Suppose S is the largest set in the whole mathematical world. S should have a power set, the power set $P(S) \textrm{of} S$. Power sets $P(S)$ always have higher cardinality than the set $S, \forall S$. $P(S) > S$, proved by contradiction that S is not the largest set. There is no largest set.

----

Section 0

1, {-√3,√3}

2, ∅

3, {-60,-30,-20,-15,-12,-10,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,10,12,15,20,30,60}

4, {-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11}

5, Not well defined

6, ∅

7, ∅

8, Not well defined

11, {(a,1),(a,2),(a,c),(b,1),(b,2),(b,c),(c,1),(c,2),(c,c)}

Problem 2:

Containment def:
We say A ⊆ B (read A is contained in B) whenever each element of A is also an element of B.

Solution 1:
So it's also true that not single element of A is not an element of B.
∅ don't have any elements, so it's true that ∅ is contained in S.

Solution 2:
Suppose that ∅ ⊈ S, then there is an element of ∅ that is also an element of S.
But the ∅ don't have any elements, so it's false that there is an element of ∅ that is also an element of S.
Thus, it's true that ∅ ⊆ S.

Problem 3:

Containment def:
We say A ⊆ B (read A is contained in B) whenever each element of A is also an element of B.

Solution 1:
So it's also true that not single element of A is not an element of B.
∅ don't have any elements, so if S ⊆ ∅ then not single element of S is not an element of ∅, which means S don't have any elements.
Thus, S = ∅.

Solution 2:
Suppose that S ≠ ∅, then there is at least one element in S.
But then S ⊈ ∅, so it’s false that there is at least one element in S.
Thus, S = ∅.

Problems 4:

The power set of a set is defined as all possible subsets of that set. The power set of a set has a strictly larger cardinality than that of the original set. Therefore, the power set of any “largest possible set” A has a larger cardinality than A by definition, and A is not the largest possible set.

<center><big>'''--------------------End of Solution--------------------'''</big></center>

Math 360, Fall 2021, Assignment 1

2021-09-13T16:38:37Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''By one of those caprices of the mind, which we are perhaps most subject to in early youth, I at once gave up my former occupations; set down natural history and all its progeny as a deformed and abortive creation; and entertained the greatest disdain for a would-be science, which could never even step within the threshold of real knowledge. In this mood of mind I betook myself to the mathematics, and the branches of study appertaining to that science, as being built upon secure foundations, and so, worthy of my consideration.''

: - Mary Shelley, ''Frankenstein''

==Read:==

# Section 0.

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

# Containment (of sets).
# Equality (of sets).
# Property.
# Ordered pair.
# Cartesian product (of two sets).

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

# Russell's paradox (this is not really a theorem, but it is an important fact).
# Basic counting principle (relating the size of $A\times B$ to the sizes of $A$ and $B$).

==Solve the following problems:==

# Section 0, problems 1, 2, 3, 4, 5, 6, 7, 8, and 11.
# Prove that for any set $S$, it must be the case that $\emptyset\subseteq S$. ''(Hint: begin with "Suppose not. Then by the definition of set containment, there must be some member of $\emptyset$ which is not a member of $S$. But...".)''
# Now suppose $S$ is any set with $S\subseteq\emptyset$. Prove that $S=\emptyset$. ''(Hint: use the previous result together with the definition of set equality.)''
# The previous two exercises show that $\emptyset$ is the "smallest of all sets." Is there a "largest of all sets?" (For more information on this question as well as on Russell's Paradox and its resolutions, see [https://en.wikipedia.org/wiki/Universal_set Wikipedia: Universal Set].)

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==

# Containment: Set A is contained in set B if each element in A is also an element in B. This is also the definition of a subset. For example: $ \{1,2\} \subseteq \{1,2,5\}$, $\{1,2,3\} \not\subseteq \{1,2,5\}$.
# Equality: two sets are equal if they are mutually subsets of each other. If there are two sets $A \textrm{ and } B$. $A \subseteq B \wedge B \subseteq A \Leftrightarrow A = B$
# Property: a statement that must be able to be evaluated as true or false about an object. For example $\{ x| x \textrm{ is even } \wedge x \leqslant 8\}$. However, "x is almost an integer" is not a property, as it is not well-defined.
# Ordered Pair: two associated objects, the order of which is significant. In an ordered pair $(a,b), a \textrm{ is the first element and } b \textrm{ is the second}. (a,b) \neq (b,a) \textrm{ if } a \neq b.$ For example, $(1,2) = (1,2) \textrm{ because } 1 = 1, 2=2$ and $(1,2) \neq (2,1) \textrm{ because } 1 \neq 2, 2 \neq 1.$
# Cartesian Product of Two Sets: $\textrm{if } A, B \textrm{ are two sets:}$ $A \times B = \{(a,b) | a \in A \wedge b \in B\}$. For example, $\{1,2\} \times \{3,4\} = \{(1,3),(1,4),(2,3),(2,4)\}$. As a non-example, $\{1,2\} \times \{3,4\} \neq \{(1,2),(3,4)\}$
#Russell's paradox: if $R \textrm{ is a set and } R = \{x|x \neq x \}$, can one say $R \in R$ or not? Assume that $R \in R, \textrm{ then } R \notin R \textrm{ according to set R's property. However, if } R \notin R, \textrm{ according to R's property, } R \in R$ which creates paradox.
#Basic Counting Principle: if there are a elements in set A and b elements in set B, there should be $a \times b$ pairs (or elements) in the set which represents Cartesian Product of set A and B. $|A \times B| = |A| \times |B|$, $(|A|$ is the cardinality of set A).

----
Section 0

# $\{x \in \mathbb R | x^{2} = 3\}$ $ x \in R \rightarrow x \textrm{ are elements contained in the real number set}$, $x^{2} = 3 \rightarrow \textrm{ elements in the real number set which have their square } = 3 $. $x^{2} = 3$, $x = \pm \sqrt{3}$, therefore, this set is $\{\sqrt{3} , -\sqrt{3} \}$
# $\emptyset$
# $\{1,2,3,4,5,6,10,12,15,20,30,60\}$
# $\{m \in \mathbb Z | m^{2} - m < 115\}$, m are all integers. $m^{2} - m < 115 \rightarrow m^{2} - m - 115 < 0$, $m = -10.24 \textrm{ and } m = 11.24 \textrm{ when } m^{2} - m - 115 < 0$, $ (m^{2} - m - 115)' = 2m - 1 = 0, m = \frac{1}{2}, m^{2} - m - 115 < 0 \textrm{ when } m = \frac{1}{2}$. Therefore, $-10.24 < m < 11.24$, the set is $\{-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$
# Not well-defined, because "large number" is not unique value.
# $\emptyset$
# $\emptyset$
# Not well-defined, because "almost an integer" is not unique value.
----
Solve Problems

# Suppose that $\emptyset \nsubseteq S$, $\exists a \in \emptyset \wedge a \notin S$. However, $\forall a, a \notin \emptyset$. Therefore, $\forall a \notin S, a \notin \emptyset$. Proved by contradiction that $\forall S, \emptyset \subseteq S$
# Suppose that $S \subseteq \emptyset \wedge S \neq \emptyset$, which means that $\emptyset \nsubseteq S$. From the previous proof, we know that $\forall S, \emptyset \subseteq S$. $ \emptyset \subseteq S \wedge S \subseteq \emptyset$ Proved by contradiction that $\forall S \subseteq \emptyset, S = \emptyset$.
# Suppose S is the largest set in the whole mathematical world. S should have a power set, the power set $P(S) \textrm{of} S$. Power sets $P(S)$ always have higher cardinality than the set $S, \forall S$. $P(S) > S$, proved by contradiction that S is not the largest set. There is no largest set.

----

Section 0

1, {-√3,√3}

2, ∅

3, {-60,-30,-20,-15,-12,-10,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,10,12,15,20,30,60}

4, {-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11}

5, Not well defined

6, ∅

7, ∅

8, Not well defined

11, {(a,1),(a,2),(a,c),(b,1),(b,2),(b,c),(c,1),(c,2),(c,c)}

Problem 2:

Containment def:
We say A ⊆ B (read A is contained in B) whenever each element of A is also an element of B.

Solution 1:
So it's also true that not single element of A is not an element of B.
∅ don't have any elements, so it's true that ∅ is contained in S.

Solution 2:
Suppose that ∅ ⊈ S, then there is an element of ∅ that is also an element of S.
But the ∅ don't have any elements, so it's false that there is an element of ∅ that is also an element of S.
Thus, it's true that ∅ ⊆ S.

Problem 3:

Containment def:
We say A ⊆ B (read A is contained in B) whenever each element of A is also an element of B.

Solution 1:
So it's also true that not single element of A is not an element of B.
∅ don't have any elements, so if S ⊆ ∅ then not single element of S is not an element of ∅, which means S don't have any elements.
Thus, S = ∅.

Solution 2:
Suppose that S ≠ ∅, then there is at least one element in S.
But then S ⊈ ∅, so it’s false that there is at least one element in S.
Thus, S = ∅.

Problems 4:

Set A is "the largest set of all sets". Set S is any set of all sets. Then A ⊈ S.
Suppose not A ⊈ S, then A ⊆ S.
If A ⊆ S, then |S| ≥ |A|, which means A is not "the largest set of all sets".
Thus, there is not set A that is "the largest set of all sets".

<center><big>'''--------------------End of Solution--------------------'''</big></center>

Math 360, Fall 2021, Assignment 1

2021-09-13T16:26:34Z

Michael.reilly002: /* Solutions: */

__NOTOC__
''By one of those caprices of the mind, which we are perhaps most subject to in early youth, I at once gave up my former occupations; set down natural history and all its progeny as a deformed and abortive creation; and entertained the greatest disdain for a would-be science, which could never even step within the threshold of real knowledge. In this mood of mind I betook myself to the mathematics, and the branches of study appertaining to that science, as being built upon secure foundations, and so, worthy of my consideration.''

: - Mary Shelley, ''Frankenstein''

==Read:==

# Section 0.

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

# Containment (of sets).
# Equality (of sets).
# Property.
# Ordered pair.
# Cartesian product (of two sets).

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

# Russell's paradox (this is not really a theorem, but it is an important fact).
# Basic counting principle (relating the size of $A\times B$ to the sizes of $A$ and $B$).

==Solve the following problems:==

# Section 0, problems 1, 2, 3, 4, 5, 6, 7, 8, and 11.
# Prove that for any set $S$, it must be the case that $\emptyset\subseteq S$. ''(Hint: begin with "Suppose not. Then by the definition of set containment, there must be some member of $\emptyset$ which is not a member of $S$. But...".)''
# Now suppose $S$ is any set with $S\subseteq\emptyset$. Prove that $S=\emptyset$. ''(Hint: use the previous result together with the definition of set equality.)''
# The previous two exercises show that $\emptyset$ is the "smallest of all sets." Is there a "largest of all sets?" (For more information on this question as well as on Russell's Paradox and its resolutions, see [https://en.wikipedia.org/wiki/Universal_set Wikipedia: Universal Set].)

<center><big>'''--------------------End of assignment--------------------'''</big></center>

==Questions:==

==Solutions:==

# Containment: Set A is contained in set B if each element in A is also an element in B. This is also the definition of a subset. For example: $ \{1,2\} \subseteq \{1,2,5\}$, $\{1,2,3\} \not\subseteq \{1,2,5\}$.
# Equality: two sets are equal if they are mutually subsets of each other. If there are two sets $A \textrm{ and } B$. $A \subseteq B \wedge B \subseteq A \Leftrightarrow A = B$
# Property: a statement that must be able to be evaluated as true or false about an object. For example $\{ x| x \textrm{ is even } \wedge x \leqslant 8\}$. However, "x is almost an integer" is not a property, as it is not well-defined.
# Ordered Pair: two associated objects, the order of which is significant. In an ordered pair $(a,b), a \textrm{ is the first element and } b \textrm{ is the second}. (a,b) \neq (b,a) \textrm{ if } a \neq b.$ For example, $(1,2) = (1,2) \textrm{ because } 1 = 1, 2=2$ and $(1,2) \neq (2,1) \textrm{ because } 1 \neq 2, 2 \neq 1.$
# Cartesian Product of Two Sets: $\textrm{if } A, B \textrm{ are two sets:}$ $A \times B = \{(a,b) | a \in A \wedge b \in B\}$. For example, $\{1,2\} \times \{3,4\} = \{(1,3),(1,4),(2,3),(2,4)\}$. As a non-example, $\{1,2\} \times \{3,4\} \neq \{(1,2),(3,4)\}$
#Russell's paradox: if $R \textrm{ is a set and } R = \{x|x \neq x \}$, can one say $R \in R$ or not? Assume that $R \in R, \textrm{ then } R \notin R \textrm{ according to set R's property. However, if } R \notin R, \textrm{ according to R's property, } R \in R$ which creates paradox.
#Basic Counting Principle: if there are a elements in set A and b elements in set B, there should be $a \times b$ pairs (or elements) in the set which represents Cartesian Product of set A and B. $|A \times B| = |A| \times |B|$, $(|A|$ is the cardinality of set A).

----
Section 0

# $\{x \in \mathbb R | x^{2} = 3\}$ $ x \in R \rightarrow x \textrm{ are elements contained in the real number set}$, $x^{2} = 3 \rightarrow \textrm{ elements in the real number set which have their square } = 3 $. $x^{2} = 3$, $x = \pm \sqrt{3}$, therefore, this set is $\{\sqrt{3} , -\sqrt{3} \}$
# $\emptyset$
# $\{1,2,3,4,5,6,10,12,15,20,30,60\}$
# $\{m \in \mathbb Z | m^{2} - m < 115\}$, m are all integers. $m^{2} - m < 115 \rightarrow m^{2} - m - 115 < 0$, $m = -10.24 \textrm{ and } m = 11.24 \textrm{ when } m^{2} - m - 115 < 0$, $ (m^{2} - m - 115)' = 2m - 1 = 0, m = \frac{1}{2}, m^{2} - m - 115 < 0 \textrm{ when } m = \frac{1}{2}$. Therefore, $-10.24 < m < 11.24$, the set is $\{-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$
# Not well-defined, because "large number" is not unique value.
# $\emptyset$
# $\emptyset$
# Not well-defined, because "almost an integer" is not unique value.
----
Solve Problems

# Suppose that $\emptyset \nsubseteq S$, $\exists a \in \emptyset \wedge a \notin S$. However, $\forall a, a \notin \emptyset$. Therefore, $\forall a \notin S, a \notin \emptyset$. Proved by contradiction that $\forall S, \emptyset \subseteq S$
# Suppose that $S \subseteq \emptyset \wedge S \neq \emptyset$, which means that $\emptyset \nsubseteq S$. From the previous proof, we know that $\forall S, \emptyset \subseteq S$. $ \emptyset \subseteq S \wedge S \subseteq \emptyset$ Proved by contradiction that $\forall S \subseteq \emptyset, S = \emptyset$.
# Suppose S is the largest set in the whole mathematical world. S should have a power set, the power set $P(S) \textrm{of} S$. Power sets $P(S)$ always have higher cardinality than the set $S, \forall S$. $P(S) > S$, proved by contradiction that S is not the largest set. There is no largest set.

----

Section 0

1, {-√3,√3}

2, ∅

3, {-60,-30,-20,-15,-12,-10,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,10,12,15,20,30,60}

4, {m ϵ Z | -10.2 < m < 11.2}

5, Not well defined

6, ∅

7, ∅

8, Not well defined

11, {(a,1),(a,2),(a,c),(b,1),(b,2),(b,c),(c,1),(c,2),(c,c)}

Problem 2:

Containment def:
We say A ⊆ B (read A is contained in B) whenever each element of A is also an element of B.

Solution 1:
So it's also true that not single element of A is not an element of B.
∅ don't have any elements, so it's true that ∅ is contained in S.

Solution 2:
Suppose that ∅ ⊈ S, then there is an element of ∅ that is also an element of S.
But the ∅ don't have any elements, so it's false that there is an element of ∅ that is also an element of S.
Thus, it's true that ∅ ⊆ S.

Problem 3:

Containment def:
We say A ⊆ B (read A is contained in B) whenever each element of A is also an element of B.

Solution 1:
So it's also true that not single element of A is not an element of B.
∅ don't have any elements, so if S ⊆ ∅ then not single element of S is not an element of ∅, which means S don't have any elements.
Thus, S = ∅.

Solution 2:
Suppose that S ≠ ∅, then there is at least one element in S.
But then S ⊈ ∅, so it’s false that there is at least one element in S.
Thus, S = ∅.

Problems 4:

Set A is "the largest set of all sets". Set S is any set of all sets. Then A ⊈ S.
Suppose not A ⊈ S, then A ⊆ S.
If A ⊆ S, then |S| ≥ |A|, which means A is not "the largest set of all sets".
Thus, there is not set A that is "the largest set of all sets".

<center><big>'''--------------------End of Solution--------------------'''</big></center>