Skip to main content

Introduction to Proofs An Active Exploration of Mathematical Language

Jennifer Firkins Nordstrom

Section 5.4 Equivalence Relations

In many area of mathematics we care about how mathematical objects relate to each other. In Section 5.3 we used function to relate elements of two sets. In this section we define the more general concept of a relation between sets. We also look as several properties.
🔗

Subsection 5.4.1 Introduction to Relations

Definition 5.4.1.

A relation, \(R\text{,}\) on \(A\times B\text{,}\) is a set of ordered pairs in \(A\times B\text{.}\)
🔗
🔗
Simply put, a relation, \(R\) is just a subset of \(A\times B\text{.}\)
🔗
We say \((x, y)\in R\) if and only if \(x R y\). Notationally, we can either use the set \(R\) or the symbol \(R\) to describe the relation. When using \(x R y\text{,}\) we read this as “\(x\) is related to \(y\text{.}\)”
🔗

Example 5.4.2. Relation Defined by a Set.

Let \(A=\{1, 2, 3, 4\}\text{,}\) \(B=\{1, 3, 5\}\) define the relation on \(A\times B\) by
\begin{equation*} R=\{(1, 1), (1, 5), (3, 5), (2, 1), (4, 3)\}. \end{equation*}
Then \(1 R 1, 3 R 5, 4 R 3\text{,}\) for example. But 3 is not related to 1, for example.
🔗
🔗

Example 5.4.3. Relation Defined by Less Than.

We can also define relations with familiar mathematical relationships.
🔗
Let \(A=\{1, 2, 3, 4\}\text{,}\) \(B=\{1, 3, 5\}\) define the relation on \(A\times B\) by
\begin{equation*} x R y \Leftrightarrow x< y. \end{equation*}
🔗
Find the set of ordered pairs for \(R\text{.}\)
🔗
Answer.
\(R=\{(1, 3), (1, 5), (2, 3), (2, 5), (3, 5), (4, 5)\}\)
🔗
🔗
A function is a relation. Let \(f:A\rightarrow B, f(a)=b\text{.}\) Then define \(R\) by
\begin{equation*} (a, b)\in R \Leftrightarrow f(a)=b. \end{equation*}
🔗
We can see that Example 5.4.3 is not a function since an element of \(A\) can map to two different elements of \(B\text{:}\) \((1, 3), (1, 5)\text{.}\)
🔗

Example 5.4.4. A Function as a Relation.

Let \(f:\mathbb{Z}\rightarrow\mathbb{Z}\) be given by \(f(n)=n^2\text{.}\) Let \(F\) be the relation given by \(f\text{:}\)
\begin{equation*} (a, b)\in F \Leftrightarrow f(a)=b. \end{equation*}
🔗
True or false: \((1, 1)\in F\text{.}\)
🔗
Answer 1.
True
🔗
🔗
True or false: \((3, 9)\in F\text{.}\)
🔗
Answer 2.
True
🔗
🔗
True or false: \((9, 3)\in F\text{.}\)
🔗
Answer 3.
False
🔗
🔗
True or false: \((-2, 4)\in F\text{.}\)
🔗
Answer 4.
True
🔗
🔗
True or false: \((2, -4)\in F\text{.}\)
🔗
Answer 5.
False
🔗
🔗
True or false: \((1, 3)\in F\text{.}\)
🔗
Answer 6.
False
🔗
🔗
🔗
To determine if a relation is a function, we check the properties from the definition of a function, Definition 5.3.1:
  • For every \(a\in A\) there must be a \(b\in B\) related to \(a\text{.}\)
    🔗
    🔗
  • Each \(a\in A\) can only be related in one \(b\in B\text{.}\)
    🔗
    🔗
🔗
We can translate this idea into the ordered pair notation:
  • For every \(a\in A\) there must be a \(b\in B\) such that \((a, b)\in F\text{.}\)
    🔗
    🔗
  • If \((a, b)\in F\) and \((a, c)\in F\) then \(b=c\text{.}\)
    🔗
    🔗
🔗

Activity 5.4.1. A Difference Relation.

Let \(A=\{1, 2, 3, 4\}\) and \(B=\{0, 1\}\text{.}\) Define the relation from \(A\) to \(B\) by
\begin{equation*} (x, y)\in R \iff x-y\ \text{is even}. \end{equation*}
🔗
(a)
Find the set of ordered pairs given by this relation.
🔗
🔗
(b)
Is the relation \(R\) a function?
🔗
🔗
🔗

Definition 5.4.5.

A relation on \(A\) is a relation on \(A\times A\text{.}\) We also call it a relation from \(A\) to \(A\text{.}\)
🔗
🔗

Activity 5.4.2. Divisibility by 3.

Let \(A=\{0, 1, 2, 3, 4, 5\}\text{.}\) Define the relation on \(A\) by
\begin{equation*} (x, y)\in R \iff 3 \mid (x-y). \end{equation*}
🔗
(a)
Find the set of ordered pairs given by this relation.
🔗
🔗
(b)
Is the relation \(R\) a function?
🔗
🔗
🔗

Activity 5.4.3. The Divides Relation.

Let \(A=\{0, 1, 2, 3, 4, 5\}\text{.}\) Define the relation on \(A\) by
\begin{equation*} (x, y)\in R \iff x\ \text{divides}\ y. \end{equation*}
🔗
(a)
Find the set of ordered pairs given by this relation.
🔗
🔗
(b)
Is the relation \(R\) a function?
🔗
🔗
🔗
🔗

Subsection 5.4.2 Equivalence Relations

We look at some properties of relations. In particular, we define the reflexive, symmetric, and transitive properties. We will look at how to prove whether a relation is reflexive, symmetric, and/or transitive. We then use these properties to define equivalence relations.
🔗

Definition 5.4.6.

Let \(R\) be a relation on \(A\text{.}\) Then
  • \(R\) is reflexive if for all \(x\in A\text{,}\) \(x R x\text{.}\) In ordered pair notation, \((x, x)\in R\text{.}\)
    🔗
  • \(R\) is symmetric if for all \(x, y\in A\text{,}\) if \(x R y\) then \(y R x\text{.}\) In ordered pair notation, if \((x, y)\in R\) then \((y, x)\in R\text{.}\)
    🔗
  • \(R\) is transitive if for all \(x, y, z\in A\text{,}\) if \(x R y\) and \(y R z\) then \(x R z\text{.}\) In ordered pair notation, if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
    🔗
🔗
🔗

Example 5.4.7. Reflexive, Symmetric, Transitive.

Let \(A=\{1, 2, 3\}\text{,}\) define the relation on \(A\) by
\begin{equation*} R=\{(1, 1), (2, 2), (3, 3)\}. \end{equation*}
🔗
\(R\) is reflexive since \((x, x)\in R\) for each \(x\in A\text{.}\)
🔗
\(R\) is symmetric since if \((x, y)\in R\) then \((y, x)\in R\text{.}\) Note, this property does not mean \((x, y)\in R\text{,}\) just that if a pair is in \(R\text{,}\) then the reverse is as well.
🔗
\(R\) is transitive since if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\) Note, this property can be tedious to check by hand. In this example, though, the only pairs that fit the hypothesis are pairs like \((x, y)=(1, 1), (y, z)=(1, 1)\text{,}\) so \((x, z)=(1, 1)\text{,}\) which is in \(R\text{.}\)
🔗
🔗

Example 5.4.8. Another Look at the Properties.

Let \(A=\{1, 2, 3\}\text{,}\) define the relation on \(A\) by
\begin{equation*} R=\{(1, 2), (1, 3), (2, 3)\}. \end{equation*}
🔗
\(R\) is not reflexive since \((1, 1)\notin R\text{.}\)
🔗
\(R\) is not symmetric since \((1, 2)\in R\text{,}\) but not \((2, 1)\text{.}\)
🔗
\(R\) is transitive since if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
🔗
Check: \((x, y)=(1, 2), (y, z)=(2, 3)\text{,}\) so \((x, z)=(1, 3)\text{,}\) which is in \(R\text{.}\) This is the only set of ordered pairs where the second coordinate matches the first.
🔗
🔗

Activity 5.4.4. Pratice with the Properties on a Finite Relation.

Let \(A=\{1, 2, 3\}\text{.}\) Let \(R=\{(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)\}\text{.}\)
🔗
(a)
Determine if \(R\) is reflexive.
🔗
🔗
(b)
Determine if \(R\) is symmetric.
🔗
🔗
(c)
Determine if \(R\) is transitive.
🔗
🔗
🔗

Activity 5.4.5. More Practice with a Finite Relation.

Let \(A=\{1, 2, 3, 4\}\text{.}\) Let \(R=\{(1, 1), (1, 3), (2, 2), (3, 2), (3, 3)\}\text{.}\)
🔗
(a)
Determine if \(R\) is reflexive.
🔗
🔗
(b)
Determine if \(R\) is symmetric.
🔗
🔗
(c)
Determine if \(R\) is transitive.
🔗
🔗
🔗
Checking that a relation is reflexive, symmetric, or transitive on a small finite set can be done by checking that the property holds for all the elements of \(R\text{.}\) But if \(A\) is infinite we need to prove the properties more generally.
🔗

Proving Reflexive, Symmetric, and Transitive Properties.

To prove
  • Reflexive.
    Let \(x\in A\text{.}\) Show \((x, x)\in R\text{.}\)
    🔗
    🔗
  • Symmetric.
    Assume \((x, y)\in R\text{.}\) Show \((y, x)\in R\text{.}\)
    🔗
    🔗
  • Transitive.
    Assume \((x, y), (y, z)\in R\text{.}\) Show \((x, z)\in R\text{.}\)
    🔗
    🔗
🔗
To disprove a property, find a specific counterexample.
  • Reflexive.
    Find \((x, x)\notin R\) for some \(x\in A\text{.}\)
    🔗
    🔗
  • Symmetric.
    Find \((x, y)\in R\) with \((y, x)\notin R\text{.}\)
    🔗
    🔗
  • Transitive.
    Find \((x, y), (y, z)\in R\) with \((x, z)\notin R\text{.}\)
    🔗
    🔗
🔗
🔗

Example 5.4.9. Proving Refexive, Symmetric, Transitive.

Let \(R\) be the relation on \(\mathbb{Z}\) given by \((m, n)\in R\Leftrightarrow 3\mid(m-n)\text{.}\)
🔗
Reflexive: Show \((m, m)\in R\text{.}\) Now \(m-m=0\text{,}\) and \(3\mid 0\text{.}\) So we get that \(3\mid m-m\text{.}\) Thus \((m, m)\in R\) for all \(m\in \mathbb{Z}\text{.}\)
🔗
Symmetric: Assume \((x, y)\in R\text{.}\) Then \(3\mid (x-y)\text{.}\) This implies \(x-y=3k\) for some \(k\in\mathbb{Z}\text{.}\) But then \(y-x=-3k=3(-k)\text{,}\) where \(-k\in \mathbb{Z}\text{.}\) Thus, \(3\mid (y-x)\text{.}\) Hence, \((y, x)\in R\text{.}\)
🔗
Transitive: Assume \((x, y), (y, z)\in R\text{.}\) Then \(3\mid (x-y)\) and \(3\mid (y-z)\text{.}\) This implies \(x-y=3k\) for some \(k\in\mathbb{Z}\) and \(y-z=3j\) for some \(j\in\mathbb{Z}\text{.}\) But then \(x-z=x-y+y-z=3k+3j=3(j+k)\text{,}\) where \(k+j\in \mathbb{Z}\text{.}\) Thus, \(3\mid (x-z)\text{.}\) Hence, \((x, z)\in R\text{.}\)
🔗
🔗

Activity 5.4.6. The Equals Relation.

Define the relation on \(\mathbb{R}\) by \(xRy \iff x=y\text{.}\)
🔗
(a)
Prove or disprove \(R\) is reflexive.
🔗
🔗
(b)
Prove or disprove \(R\) is symmetric.
🔗
🔗
(c)
Prove or disprove \(R\) is transitive.
🔗
🔗
🔗

Activity 5.4.7. The Less Than Relation.

Define the relation on \(\mathbb{R}\) by \(xRy \iff x < y\text{.}\)
🔗
(a)
Prove or disprove \(R\) is reflexive.
🔗
🔗
(b)
Prove or disprove \(R\) is symmetric.
🔗
🔗
(c)
Prove or disprove \(R\) is transitive.
🔗
🔗
🔗

Definition 5.4.10.

A relation that is reflexive, symmetric and transitive is an equivalence relation.
🔗
🔗
In Example 5.4.9 we proved that the relation given by \((m, n)\in R \Leftrightarrow 3\mid (m-n)\) is an equivalence relation since we proved it is reflexive, symmetric, and transitive.
🔗
In fact, the proof can easily be adapted to show \((m, n)\in R \Leftrightarrow d\mid (m-n)\) is an equivalence relation for \(d\neq 0, d\in \mathbb{Z}\text{.}\)
🔗
This is an important enough relation that it has its own notation.
\begin{equation*} m\equiv n \mod d. \end{equation*}
🔗

Definition 5.4.11.

Let \(m, n, d\in \mathbb{Z}, d>0\text{.}\) Then \(m\) and \(n\) are congruent modulo \(d\) if \(d\mid (m-n)\text{.}\) We denote congruence mod \(d\) by \(m\equiv n \mod d\).
🔗
🔗
We often just say \(m\) is congruent to \(n\) mod \(d\text{.}\)
🔗

Example 5.4.12. Congruence mod \(d\).

True or false: \(7\equiv 1 \mod 3\text{.}\)
🔗
Answer 1.
Since \(3\mid (7-1)\text{,}\) true.
🔗
🔗
True or false: \(7\equiv -2 \mod 3\text{.}\)
🔗
Answer 2.
Since \(3\mid (7+2)\text{,}\) true.
🔗
🔗
True or false: \(7\equiv -7 \mod 3\text{.}\)
🔗
Answer 3.
Since \(3\nmid (7+7)\text{,}\) false.
🔗
🔗
True or false: \(7\equiv 2 \mod 3\text{.}\)
🔗
Answer 4.
Since \(3\nmid (7-2)\text{,}\) false.
🔗
🔗
🔗
Let \(R\) be an equivalence relation on \(A\text{.}\) Let \(a\in A\text{.}\) The set
\begin{equation*} [a]=\{b\in A : b R a\} \end{equation*}
is the equivalence class of \(a\text{.}\)
🔗
Given a specific \(a\in A\text{,}\) we find the equivalence class of \(a\) by finding all the elements that are related to \(a\text{.}\) Keep in mind the equivalence class is a set, denoted \([a]\text{.}\)
🔗

Example 5.4.13. Equivalence Classes.

Consider the equivalence relation \(m\equiv n \mod 3\text{,}\) on \(\mathbb{Z}\text{.}\)
  1. Find \([0]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 0.
    🔗
    Answer.
    \([0]=\{0, 3, -3, 6, -6, \ldots\}=\{3k : k\in \mathbb{Z}\}\)
    🔗
    🔗
  2. Find \([1]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 1.
    🔗
    Answer.
    \([1]=\{1, 4, -2, -5, 7, 10, \ldots\}=\{3k+1: k\in \mathbb{Z}\}\)
    🔗
    🔗
  3. Find \([2]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 2.
    🔗
    Answer.
    \([2]=\{2, 5, -1, -4, -7, \ldots\}=\{3k+2: k\in \mathbb{Z}\}\)
    🔗
    🔗
  4. Find \([3]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to 3.
    🔗
    Answer.
    \([3]=\{0, 3, -3, 6, -6, \ldots\}=\{3k : k\in \mathbb{Z}\}\)
    🔗
    🔗
  5. Find \([-1]\text{,}\) the set of elements in \(\mathbb{Z}\) equivalent to -1.
    🔗
    Answer.
    \([-1]=\{2, 5, -1, -4, -7, \ldots\}=\{3k+2: k\in \mathbb{Z}\}\)
    🔗
    🔗
🔗
🔗
We can notice a few things from this last example. We can see that some of our equivalence classes are the same. In particular, \([0]=[3]\) and \([2]=[-1]\text{.}\) In fact, there are only three distinct equivalence classes, \([0], [1], [2]\text{,}\) any other equivalence class will equal one of these.
🔗
A few other things to notice, distinct equivalence classes are disjoint--they have no elements in common. Also, \([a]\) contains \(a\text{.}\) Furthermore, the equivalence classes \([0], [1], [2]\) partition the integers.
🔗

Definition 5.4.14.

A set of subsets of a set \(B\text{,}\) \(\{A_1, A_2, \ldots, A_n\}\text{,}\) is a partition of \(B\) if
  1. \(\bigcup_{i=1}^nA_i=B\text{,}\)
    🔗
    🔗
  2. \(A_i\cap A_j=\emptyset\) whenever \(i\neq j\text{.}\)
    🔗
    🔗
🔗
🔗
What this really says is that a set of subsets will be a partition of \(B\) if the union of the subsets is all of \(B\text{,}\) and the subsets are pairwise disjoint.
🔗

Example 5.4.15. Partition.

Let \(B=\{1, 2, 3, 4, 5, 6\}\text{.}\) Then let \(A_1=\{1\}, A_2=\{2, 4, 6\}, A_3=\{3, 5\}\text{.}\) We can see that \(\{A_1, A_2, A_3\}\) is a partition of \(B\) since \(A_1\cup A_2\cup A_3=B\) and the subsets have no elements in common, hence they are disjoint.
🔗
Now if we let \(A_1=\{1, 2, 3, 4\}, A_2=\{2, 3, 4, 5, 6\}\text{.}\) We can see that \(\{A_1, A_2\}\) is not a partition of \(B\) since \(A_1\cap A_2=\{2, 3, 4\}\neq\emptyset\text{.}\)
🔗
🔗

Example 5.4.16. More Equivalence Classes.

Let \(N(A)\) be the number of elements in \(A\text{.}\)
🔗
Consider the equivalence relation \(A R B \Leftrightarrow N(a)=N(B)\text{,}\) on \(\mathcal{P}(\{1, 2, 3\})\text{.}\)
🔗
This is the relation where two subsets of \(\{1, 2, 3\}\) are related if they have the same number of elements. You can check that this is an equivalence relation.
  1. Find \([\emptyset]\text{,}\) the set of elements in \(\mathcal{P}(\{1, 2, 3\})\) equivalent to \(\emptyset\text{.}\)
    🔗
    Answer.
    \([\emptyset]=\{\emptyset\}\text{,}\)
    🔗
    🔗
  2. Find \([\{1\}]\text{.}\)
    🔗
    Answer.
    \([\{1\}]=\{\{1\}, \{2\}, \{3\}\}\text{,}\)
    🔗
    🔗
  3. Find \([\{1, 2\}]\text{.}\)
    🔗
    Answer.
    \([\{1, 2\}]=\{\{1, 2\}, \{2, 3\}, \{1, 3\}\}\)
    🔗
    🔗
  4. Find \([\{1, 2, 3\}]\text{.}\)
    🔗
    Answer.
    \([\{1, 2, 3\}]=\{\{1, 2, 3\}\}\)
    🔗
    🔗
🔗
🔗
Once again, the distinct equivalence classes are disjoint--they have no elements in common. Furthermore, the equivalence classes \([\emptyset], [\{1\}], [\{1, 2\}], [\{1, 2, 3\}]\) partition the power set by size of the subset.
🔗

Activity 5.4.8. An Absolute Value Relation.

Define the relation on \(\mathbb{R}\) by \(xRy \iff |x|=|y|\text{.}\)
🔗
(a)
Prove \(R\) is an equivalence relation.
🔗
🔗
(b)
Find \([0]\) and \([-5]\text{.}\)
🔗
🔗
🔗

Activity 5.4.9. Equivalence Mod 5.

Recall that \(n \equiv m\ \text{mod}\ 5\iff 5\mid (m-n)\text{.}\)
🔗
(a)
Prove the relation \(nRm \iff n \equiv m\ \text{mod}\ 5\) is an equivalence relation on \(\mathbb{Z}\text{.}\)
🔗
🔗
(b)
Find \([0]\) and \([2]\text{.}\)
🔗
🔗
🔗

Activity 5.4.10. A Partition Relation.

Let \(S=\{1, 2, 3, 4, 5, 6\}\text{.}\) Let \(A_1=\{1, 2, 3\}, A_2=\{4\}, A_3=\{5, 6\}\text{.}\)
🔗
(b)
Define the relation on \(S\text{,}\) \(xRy \iff\) \(x\) and \(y\) are in the same subset of the partition. Is \(1 R 3\text{?}\) Is \(2 R 4?\) Is \(5 R 5?\)
🔗
🔗
(c)
Show \(R\) is reflexive, symmetric and transitive.
🔗
🔗
(d)
Find \([1]\text{,}\) the equivalence class of 1.
🔗
🔗
(e)
Do you think this particular partition matters? Could we define this relation on any partition of any set and still have it be reflexive, symmetric and transitive?
🔗
🔗
🔗
There is an important connection between equivalence classes and partitions, as we see in the next two theorems.
🔗
Conversely, as we saw in Activity 5.4.10, if we have a partition \(\{A_1, A_2, \ldots, A_n, \ldots\}\) of \(A\) and define the relation \((a, b)\in R \Leftrightarrow a\) and \(b\) are in the same subset \(A_i\text{,}\) then \(R\) is an equivalence relation. We call this the equivalence relation induced by the partition.
🔗
We leave the details of the proof of Theorem 5.4.18 as an exercise.
🔗
The proof of Theorem 5.4.17 follows directly from the next two Lemmas.
🔗

Proof.

Since we want to show the sets are equal, we will show \([a], [b]\) are subsets of each other.
🔗
Show \([a]\subseteq [b]\text{.}\) Let \(x\in [a]\text{.}\) Then by defintion of equivalence class, \(x R a\text{.}\) We assumed \(a R b\text{.}\) By the transitive property, \(x R b\text{.}\) Thus, \(x\in [b]\text{.}\)
🔗
Show \([b]\subseteq [a]\text{.}\) Let \(x\in [b]\text{.}\) Then by defintion of equivalence class, \(x R b\text{.}\) We assumed \(a R b\text{.}\) By the symmetric property, \(b R a\text{.}\) By the transitive property, \(x R a\text{.}\) Thus, \(x\in [a]\text{.}\)
🔗
🔗
Lemma 5.4.19 really says that if two elements are related in an equivalence relation, they the must have the same equivalence class. You can check this with the above examples. Note, we needed the symmetric and transitive properties to prove this lemma.
🔗
Before proving the lemma, note that we are trying to prove an “or” statement. A common technique is to assume one part is false and show the other part is true. This technique comes from the logical equivalence \(p\vee q\equiv \neg p\rightarrow q\text{.}\)
🔗

Proof.

Assume \([a]\cap[b]\neq \emptyset\text{.}\) We want to show \([a]=[b]\text{.}\) Since \([a]\cap[b]\neq \emptyset\text{,}\) there exists \(x\in [a]\cap[b]\text{.}\) This means \(x R a\) and \(x R b\text{.}\) By the symmetric property, \(a R x\text{.}\) By the transitive property, since \(a R x\) and \(x R b\text{,}\) we have \(a R b\text{.}\) By Lemma 5.4.19, \([a]=[b]\text{.}\)
🔗
🔗
Lemma 5.4.20 really say that two equivalence classes are either disjoint or exactly the same.
🔗
Theorem 5.4.17 follows since, by the reflexive property, \(x R x, \forall x\in A\) means every element is in an equivalence class. Thus, the union of the equivalence classes is all of \(A\text{.}\) By Lemma 5.4.20 distinct equivalence classes are disjoint. Thus, we have a partition of \(A\text{.}\)
🔗

Exercises Exercises

1.
Define the congruence modulo 3 relation, \(T\text{,}\) on \(\mathbb{Z}\) by
🔗
\begin{equation*} m\ T\ n \iff 3\mid (m-n). \end{equation*}
🔗
  1. Is \(10\ T\ 1\text{?}\) Is \(1\ T\ 10\text{?}\) Is \((2, 2)\in T\text{?}\) Is \((8, 1)\in T\text{?}\)
    🔗
    🔗
  2. List five integers \(n\) such that \(n\ T\ 0\text{.}\)
    🔗
    🔗
  3. List five integers \(n\) such that \(n\ T\ 1\text{.}\)
    🔗
    🔗
  4. List five integers \(n\) such that \(n\ T\ 2\text{.}\)
    🔗
    🔗
🔗
2.
Define the relation, \(S\text{,}\) on \(\mathbb{Z}\) by
🔗
\begin{equation*} m\ S\ n \iff 5\mid (m^2-n^2). \end{equation*}
🔗
  1. Is \(1\ S\ (-9)\text{?}\)
    🔗
    🔗
  2. Is \(2\ S\ 13\text{?}\)
    🔗
    🔗
  3. Is \(2\ S\ (-8)\text{?}\)
    🔗
    🔗
  4. Is \((-8)\ S\ 2\text{?}\)
    🔗
    🔗
🔗
3.
Let \(A=\{3, 4, 5\}\) and \(B=\{4, 5, 6\}\) and let \(S\) be the “divides” relation. That is, for all \((x, y)\in A\times B\text{,}\)
\begin{equation*} x\ S\ y \iff x\mid y. \end{equation*}
Find the set of ordered pairs in \(S\text{.}\)
🔗
🔗
4.
Let \(G\) be the relation on \(\mathbb{R}\) defined by
\begin{equation*} x\ G\ y\iff xy\geq 0. \end{equation*}
🔗
  1. Determine if \(G\) is reflexive. Justify your answer.
    🔗
    🔗
  2. Determine if \(G\) is symmetric. Justify your answer.
    🔗
    🔗
  3. Determine if \(G\) is transitive. Justify your answer.
    🔗
    🔗
🔗
5.
Let \(D\) be the relation on \(\mathbb{Z}^+\) defined by
\begin{equation*} m\ D\ n\iff m\mid n. \end{equation*}
🔗
  1. Determine if \(D\) is reflexive. Justify your answer.
    🔗
    🔗
  2. Determine if \(D\) is symmetric. Justify your answer.
    🔗
    🔗
  3. Determine if \(D\) is transitive. Justify your answer.
    🔗
    🔗
🔗
6.
Let \(F\) be the relation on \(\mathbb{R}\times \mathbb{R}\) defined by
\begin{equation*} (x_1, y_1)\ F\ (x_2, y_2)\iff x_1=x_2. \end{equation*}
🔗
  1. Determine if \(F\) is reflexive. Justify your answer.
    🔗
    🔗
  2. Determine if \(F\) is symmetric. Justify your answer.
    🔗
    🔗
  3. Determine if \(F\) is transitive. Justify your answer.
    🔗
    🔗
🔗
7.
Define the relation \(R\) on \(\mathbb{Z}\) by
\begin{equation*} m\ R\ n \iff 5\mid(m-n). \end{equation*}
🔗
  1. Prove or disprove \(R\) is reflexive.
    🔗
    🔗
  2. Prove or disprove \(R\) is symmetric.
    🔗
    🔗
  3. Prove or disprove \(R\) is transitive.
    🔗
    🔗
🔗
8.
Let \(X=\{a, b, c\}\) and \({\cal P}(X)\) be the power set of \(X\text{.}\) Define the relation \(L\) on \({\cal P}(X)\) by
\begin{equation*} A\ L\ B \iff \text{ the number of elements in $A$ is less than the number of elements in $B$.} \end{equation*}
🔗
  1. Prove or disprove \(L\) is reflexive.
    🔗
    🔗
  2. Prove or disprove \(L\) is symmetric.
    🔗
    🔗
  3. Prove or disprove \(L\) is transitive.
    🔗
    🔗
🔗
9.
Let \(X\) be a nonempty set and \({\cal P}(X)\) be the power set of \(X\text{.}\) Define the “subset” relation \(S\) on \({\cal P}(X)\) by
\begin{equation*} A\ S\ B \iff A\subseteq B. \end{equation*}
🔗
  1. Prove or disprove \(S\) is reflexive.
    🔗
    🔗
  2. Prove or disprove \(S\) is symmetric.
    🔗
    🔗
  3. Prove or disprove \(S\) is transitive.
    🔗
    🔗
🔗
🔗
🔗
🔗
PrevTopNext