## SectionProject: More on Equivalence Classes

###### Problem8.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{.}$

###### Problem8.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{.}$

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.

1. Show that $\equiv$ is an equivalence relation.

2. List of as many non-equivalent compound sentences as you can.

3. How many different equivalence classes are there?

###### Problem8.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.

###### Problem8.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.

###### Problem8.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?