Project: More on Equivalence Classes

David M. Clark and W. Ted Mahavier

( Chapter 3: W. Ted Mahavier < E.L. May < K.M. Shannon ¹ )

If each of \(X\) and \(Y\) is a person, then the relation \(X < Y\) indicates that the notes originated with \(Y\) and were subsequently modified by \(X\text{,}\) who takes full responsibility for the current version. While \(Y\) is credited with the genesis of the notes, s/he makes no claim to the accuracy of the current version which may or may not reflect her/his original version.

Section Project: More on Equivalence Classes

Problem 8.24.

Suppose \(R\) is an equivalence relation on the set \(A\text{.}\) Prove that the set of all equivalence classes defined by \(R\) form a partition of \(A\text{.}\)

Problem 8.25.

We might think of two compound sentences in propositional logic to be “equivalent” if they have the same truth tables. For example, the truth table below shows that every implication \(p\rightarrow q\) is equivalent to its contrapositive \(\lnot q \rightarrow \lnot p\text{.}\)

Table 8.26. 1 is True; 0 is False


\(p\)	\(q\)	\(p\rightarrow q\)	\(\lnot q \rightarrow \lnot p\)

0	0	1	1

0	1	1	1

1	0	0	0

1	1	1	1

Let \(\A\) be the (infinite) set of all compound sentences in propositional logic that can be constructed using the sentence variables \(p\) and \(q\) and the connectives \(\lnot\text{,}\) \(\land\text{,}\) \(\lor\) and \(\rightarrow\text{.}\) For \(a,b \in A\) we say that \(a\equiv b\) if \(a\) and \(b\) have the same truth table.

Show that \(\equiv\) is an equivalence relation.
List of as many non-equivalent compound sentences as you can.
How many different equivalence classes are there?

Problem 8.27.

Let \(\mathbf S = \{a,b,c,d,e,f,g,h\}\text{,}\) let \(\mathbf T = \{a,b,c\}\) and let \(\A\) be the set of all (\(2^8\)) subsets of \(\mathbf S\text{.}\) For \(X,Y \in \A\text{,}\) we define \(X R Y\) if \(X\) and \(Y\) have the same intersection with \(\mathbf T\text{.}\) Determine if \(R\) is an equivalence relation and if so, describe the equivalence classes.

Problem 8.28.

Let \(\A = \{0,1\}^5\) be the set of 32 different five-tuples of 0s and 1s, that is, all sequences \((a,b,c,d,e)\) where \(a,b,c,d,e\in\{0,1\}\text{.}\) For \(x,y \in \A\text{,}\) define \(x R y\) to mean that \(x\) and \(y\) have the same number of 1s. Show that \(R\) is an equivalence relation and write down all the members of each of the different equivalence classes.

Problem 8.29.

Let \(n\) is a positive integer and let \(\A = \{0,1\}^n\) be the set of all \(n\)–tuples of 0s and 1s. For \(x,y \in \A\text{,}\) again define \(xR y\) to mean that \(x\) and \(y\) have the same number of 1s. How many different equivalence classes does \(\A\) have?