Chapter 1 Section 1 Allufi chapter 0 problems and solutions

1.2)Prove that if $\sim$ is a relation on S, then the corresponding family $P_{\sim}$ defined in 1.5 is indeed a partition of S: That is, its elements are non-empty disjoint, and their union in S.

Proof:

Recall $[a] := \{b \in S : b \sim a\}$ and $P_{\sim} := \{ [a] : a \in S\}$.
$\bigcup_{[a] \in P_{\sim}} [a] = \bigcup_{a \in S} [a] = S$, since for each $a \in S$ we have atleast $a \sim a$, so each element in S is in some equivalence relation. This also covers all equivalence relations. Also, for all $a \in S$, $[a] \subset S$.

Since $a \sim a$ for all $a \in S \implies [a] \neq \emptyset$ for any $[a] \in P_{\sim}$ as atleast $a \in [a]$.

Suppose that $[a]$ and $[b] \in P_{\sim}$ such that $q \in [a]\ and\ [b]$.

This means $q \sim a$ and $q \sim b \implies a \sim q$ and $q \sim b \implies a \sim b \implies [a] \subset [b]$. The other inclusion is similiar. Thus, $[a] = [b]$.



1.3)Given a partition $\mathcal{P}$ on a set S, show how to define a relation $\sim$ on S such that $\mathcal{P}$ is the corresponding partition.

Proof:

Suppose that $\mathcal{P}$ is a partition on the set S. That is $\mathcal{P}$ is a collection of disjoint subsets of S, whose union is all of S.

Define the following relation:
$s_1 \sim s_2 \iff s_1 \ and \ s_2$ belong to the same set in $\mathcal{P}$. We have to verify that this relation that we defined is an equivalence relation; moreover, it gives $\mathcal{P}$ as a partition.

$s_1 \sim s_1 \forall \ s \in S$, since it belong to some $U_{s_1} \in \mathcal{P}$ as the elements of $\mathcal{P}$ cover S, so there must exist atleast one $U$ such that U contains $s_1$. We denote it by $U_{s_1}$.  Suppose that $s_1 \sim s_2$, then it is obvious that $s_2 \sim s_1$ by definition of how we defined this relation.

Suppose that $s_1 \sim s_2$ and $s_2 \sim s_3$, then $s_1$ and $s_2 \in U_1$ for some $U_1 \in \mathcal{P}$. Similiarly, $s_2, s_3 \in U_2$ for some $U_2 \in \mathcal{P}$. By the fact that $\mathcal{P}$ is a parition $U_1 = U_2$ because, otherwise $U_1 \cap U_2 \neq \emptyset$ and $U_1 \neq U_2$, which contradicts the fact that $\mathcal{P}$ is a partition for S.

We have to show now that $P_{\sim} = P$. Suppose that $[a] \in P_{\sim}$, then $b \in [a] \iff b \ and \ a$ is in some set $U \in \mathcal{P}$. Moreover, this U is unique as the elements of $\mathcal{P}$ are disjoint. This means $[a] = U$ for some $U \in \mathcal{P}$. This mean $[a] \in \mathcal{P}$. The other inclusion is trivial.

1.4) How many different equivalence relation maybe defined on the set $\{1,2,3\}$ ?
Answer:

Mainly this question is asking how many different partitions for $\{1,2,3\}$.
Therefore, we have to count how many unique subsets are possible. Here is one way to do it.
We have the following types of subsets for S.
Type 1) $\{\star \}$.
Type 2)$\{\star ,\star \}$.
Type 3)$\{\star ,\star ,\star \}$.

To construct a subsets, whose union cover S and is disjoint. Then, we have that if we choose which type we want. If we choose type 1, then there is only one possibility. That is $P_1 = \{ \{1,2,3\} \}$.  If we choose type 2, then the other element in the set must be of type 1, so we for each type 2 we have 3 possibilities, since once we choose a type 2, then the other subset can't be of type 2 or 3. Hence it must be of type 1.  More concretely we have:

$$P_2 = \{ \{1\},\{2,3\}\ ,\ P_3 = \{ \{2\},\{1,3\},\ or \ P_4 = \{ \{3\},\{1,2\} \}.$$

Finally, if we choose two singeleton, then we must choose our third element to be a singleton.
That is, $$P_5 = \{ \{1\},\{2\},\{3\} \}.$$

Thus, there are 5 different equivalence relation on the set $\{1,2,3\}$.

1.5)Give an example of a relation that is reflexive and symmetric, but not transitive. What happens if you attempt to use this relation to define a partition on the set.

Answer:

Fix a particular set S. The hint provides the answer that we are looking for. Suppose that $\mathcal{P}$ is composed of collection of subsets of S, whose union is all of S, such that atleast two of the elements of $\mathcal{P}$ are not disjoint. That is there exists $U_1,U_2 \in \mathcal{P}$, such that $U_1 \neq U_2$ and $U_1 \cap U_2 \neq \emptyset$.


Define a relation $\sim$ on S as follows:

$s_1 \sim s_2 \iff s_1,\ s_2$ belong to the same set of $\mathcal{P}$.  That is there exists $U \in \mathcal{P}$ such that $s_1,\ s_2 \in U$.

Claim: $\sim$ is reflexive, symmetric, but not transitive.

It is obvious that $\sim$ is reflexive and symmetric. Since there exists $U_1,U_2 \in \mathcal{P}$ such that $U_1 \cap U_2 \neq \emptyset$. Therefore there exists $q_1 \in U_1 \cap U_2$. Since $U_1 \neq U_2 \implies$
$$\exists\ q_2 \in U_1 \ : q_2 \notin U_2.$$
$$\exists\ q_3 \in U_2 \ : q_3 \notin U_1.$$

Then, $q_2 \sim q_1$ and $q_2 \sim q_3$, but $q_2 \not\sim q_3 \implies \sim$ isn't transitive.

If we try to use $\sim$ to define a partition we would get that the partition elements are not disjoint, but they are non-empty and covers S.

1.6: Define a relation $\sim$ on the set $\mathbb{R}$ of real numbers by setting $a \sim b \iff b - a \in \mathbb{Z}$. Prove that this is an equivalence relation, and find a compeling description for $\mathbb{R}/ \sim$. Do the same for the equivalence relation $\approx$ on the plane $\mathbb{R} \times \mathbb{R}$ defined by declaring $(a_1,a_2) \approx (b_1,b_2) \iff b_1 - a_1 \in \mathbb{Z} \ and \ b_2 - a_2 \in \mathbb{Z}$.

Proof:

First we shall prove that this is an equivalence relation. $a \sim a$, since $a - a = 0 \in \mathbb{Z} \implies \sim$ is reflexive.  Suppose $a \sim b \implies a - b \in \mathbb{Z}$. This means that $a - b = c$ for some $c \in \mathbb{Z} \implies (b - a) = - (a - b) = -c \in \mathbb{Z}$. Therefore, $b \sim a$. Thus, $\sim$ is symmetric.

Finally, suppose that $a \sim b$ and $b \sim c \implies a - b \in \mathbb{Z} \ and \ b - c \in \mathbb{Z}.$ Thus, $a - b = d$ and $b - c = m$ for $d,m \in \mathbb{Z}$.

Here, if we take the unit interval $[0,1]$ we can see that every element of $\mathbb{R}$ is in an equivalence class of this interval, and 0 is identified to 1. Thus, $\mathbb{R}/ \sim$ represents a circle.

For the relation $\approx$ it follows same logical pattern as for $\sim$. This relation represents the Torus.