Relations — Foundations of Mathematics

Definition 1.3.1. A relation on a set $$A$$ is a subset $$R$$ of the product $A\times A.$ If $$R$$ is a relation on $$A,$$ we use the notation $x\mathrel Ry$ to mean that $(x,y)\in R.$ We read it “ $$x$$ is in the relation $$R$$ to $$y.$”$

Definition 1.3.2. A relation $\sim$ on $$A$$ is an equivalence relation on $$A$$ if the following conditions hold:

$\forall x \in A \ (x\sim x)$ (reflexivity);
$\forall x,y\in A \ (x\sim y \rightarrow y\sim x)$ (symmetry);
$\forall x,y,z\in A \ ((x\sim y \land y\sim z) \rightarrow x\sim z)$ (transitivity).

Definition 1.3.3. Let a set $$A,$$ an equivalence relation $\sim$ on $$A,$$ and an element $$a$$ of $$A$$ be given. We define the equivalence class determined by $$a$$ as the set $[a]\subseteq A$ such that

\[[a] = \lbrace x\in A: x\sim a\rbrace.\]

Lemma 1.3.4. Let $a,a'\in A.$ Two equivalence classes $$[a]$$ and $$[a']$$ on $$A$$ are either disjoint or equal.

Proof. Suppose that there exists $k\in A$ such that $k\in [a]$ and $k\in [a'].$ Then $k\sim a$ and $k\sim a'$ so that $a\sim a'.$ Thus, if $l\in [a]$ then $l\sim a,$ so that $l\sim a'.$ Therefore $l\in [a'].$ Consequently, $[a]\subseteq [a'].$ By symmetry, $[a']\subseteq [a]$ as well, so that $$[a]=[a'].$$ Conversely, we suppose that there are no elements such that $k\in [a]$ and $k\in [a'].$ Then $$[a]$$ and $$[a']$$ are disjoint. $\square$

Definition 1.3.5. A collection $\mathcal P$ is a partition of $$A$$ if the following conditions hold:

$$\forall x\in \mathcal P\ (x\neq \varnothing \land x\subseteq A)$;$
$$\forall x, y\in \mathcal P\ (x\neq y\rightarrow x\cap y = \varnothing )$;$
$$\bigcup \mathcal P = A$.$

Theorem 1.3.6. Let $\sim$ be an equivalence relation on a set $$A,$$ and let $A/{\sim}$ the collection of all the equivalence classes determined by $\sim.$ Then $A/{\sim}$ is a partition of $$A.$$

Proof. From Definition 1.3.3 $[a]\subseteq A,$ and $a\in [a]$ so that $[a]\neq \varnothing$ by reflexivity. By Lemma 1.3.4, if $[a]\neq [a']$ then $[a]\cap [a'] = \varnothing.$ If $a\in A$ then $a\in [a]$ so that $a\in \bigcup A/{\sim}.$ Thus $A\subseteq \bigcup A/{\sim}.$ If $a\in \bigcup A/{\sim}$ then there exists $[a']\in A/{\sim}$ such that $a\in [a'],$ where $a'\in A.$ Since $[a']\subseteq A,$ it follows that $a\in A.$ Thus $\bigcup A/{\sim}\subseteq A.$ Consequently, $\bigcup A/{\sim} = A.$ Therefore, the collection $A/{\sim}$ is a partition of $$A.$$ $\square$

Theorem 1.3.7. There exist exactly one equivalence relation corresponding to any given partition.

Proof. Let $\mathcal P$ be any partition of a set $$A.$$ We define a relation $$R$$ on $$A$$ by

\[R = \lbrace (x,y)\in A\times A : \varphi (x,y) \rbrace \quad \text{where} \quad \varphi(x,y) : \exists P\in \mathcal P \ (x\in P\land y\in P).\]

Since $$R$$ has reflexivity, symmetry, and transitivity, $$R$$ is an equivalence relation on $$A.$$ Since $\mathcal P$ is a partition of $$A,$$ there exists exactly one element that contains $a\in A.$ Denote the unique element as $$P_a$.$ Then

\[a\mathrel Rx \iff x\in P_a.\]

Therefore $$[a]_R = P_a.$$ Let

\[A/R=\lbrace [x]_R:x\in A\rbrace.\]

If $[a]_R\in A/R$ then $[a]_R=P_a\in \mathcal P.$ Thus $A/R \subseteq \mathcal P.$ If $P\in \mathcal P,$ then, since $P\neq 0,$ there exists $a\in A$ such that $a\in P.$ Hence, $$P=P_a=[a]_R,$$ so that $P\in A/R.$ Thus $\mathcal P \subseteq A/R,$ so that $A/R = \mathcal P.$ We finally conclude that there exist equivalence relations corresponding to any given partition. After that, we show the uniqueness. Suppose that $$R_1$$ and $$R_2$$ are two equivalence relations that give rise to $\mathcal P.$ Let $a\in A,$ and define $[a]_{R_1}$ and $[a]_{R_2}$ to be the equivalence classes relative to the relation $$R_1$$ and $$R_2$,$ respectively. Then $[a]_{R_1}=P_a=[a]_{R_2}.$ Therefore $$R_1=R_2.$$ $\square$

Definition 1.3.8. Let $f\colon A\to B$ be a function. The. kernel of $$f$$ is the relation $\operatorname{ker}f$ on $$A$$ defined by

\[\operatorname{ker}f = \lbrace (x_1,x_2) \in A \times A : f(x_1)=f(x_2)\rbrace .\]

Definition 1.3.9. Let $$R$$ be a relation on a set $$A,$$ and $$S$$ a relation on a set $$B.$$ If there is a bijection $f\colon A\to B$ such that for all $x_1,x_2\in A$

\[(x_1,x_2)\in R\ \iff \ (f(x_1),f(x_2))\in S,\]

then $$(A,R)$$ and $$(B,S)$$ are called isomorphic. In this case, we call $$f$$ an isomorphism, and write

\[(A,R)\cong (B,S).\]

Note that $\cong$ is an equivalence relation on the class of relational structures.

Exercises

1. Define two ordered pairs $$(x_0,y_0)$$ and $$(x_1,y_1)$$ of $\mathbb R^2$ to be equivalent if $$y_0-x_0^2=y_1-x_1^2.$$ Check that this is an equivalence relation and describe the equivalence classes.

Solution. It satisfies the conditions described in Definition 1.3.2, so that it is an equivalence relation. Let $(a,b)\in \mathbb R^2.$ Then we define the equivalence class determined by $$(a,b)$$ as follows:

\[[(a,b)] = \lbrace (x,y)\in \mathbb R^2 : y=x^2-a^2+b \rbrace.\]

Since $$y$$ depends on $$x,$$ we can see that $$[(a,b)]$$ is a rule of assignment whose domain and image are $\mathbb R$ and $\lbrace y\in \mathbb R : y\geq -a^2+ b\rbrace$ respectively.

2. Let $$R$$ be a relation on a set $$A.$$ If $A_0\subseteq A,$ define the restriction of $$R$$ to $$A_0$$ to be the relation $R\cap (A_0\times A_0).$ Show that the restriction of an equivalence relation is an equivalence relation.

Proof. Let $$R$$ be an equivalence relation on $$A$$ and $R_0=R\cap (A_0\times A_0)$ where $A_0\subseteq A.$ Since $R\cap (A_0\times A_0)\subseteq A_0\times A_0,$ the restriction $$R_0$$ is a subset of $A_0\times A_0.$ Suppose that $a,b,c\in A_0.$ Since $(a,a)\in R$ and $(a,a)\in A_0\times A_0, (a,a)\in R_0.$ If $(a,b)\in R_0,$ then $(a,b)\in R$ so that $(b,a)\in R.$ Given $(b,a)\in A_0\times A_0,$ it follows that $(b,a)\in R_0.$ If $$(a,b)$$ and $$(b,c)$$ are elements of $$R_0,$$ then they belongs to $$R,$$ so that $(a,c)\in R.$ Since $(a,c)\in A_0\times A_0,$ $(a,c)\in R_0.$ Consequently, $$R_0$$ is an equivalence relation on $$A_0.$$ $\square$

3. Here is a “proof” that every relation $$R$$ that is both symmetric and transitive is also reflexive: “Since $$R$$ is symmetric, $$aRb$$ implies $$bRa$.$ Since $$R$$ is transitive, $$aRb$$ and $$bRa$$ together imply $$aRa$,$ as desired.” Find the flaw in this argument.

Solution. The proof assumes that $$aRb$$ for some $$b.$$ That is, symmetry and transitivity only imply $$aRa$$ for elements $$a$$ that are already related to some element $$b.$$ For example, on $A=\lbrace 1,2\rbrace,$ let $R=\lbrace (1,1)\rbrace.$ Then $$R$$ is symmetric and transitive but it is not reflexive, because $(2,2)\notin R.$

4. Let $f\colon A\to B$ be a surjective function. Let us define an equivalence relation on $$A$$ by setting $a_0 \sim a_1$ if $$f(a_0)=f(a_1).$$ Let

\[A/{\sim} = \lbrace [x] : x\in A \rbrace.\]

Show there is a bijective correspondence of $A/{\sim}$ with $$B.$$

Proof. Define $g\colon A/{\sim} \to B$ by

\[g([x]) = f(x).\]

First, we show that $$g$$ is well-defined. Suppose $$[a_0] = [a_1].$$ Then $a_0 \sim a_1,$ so by the definition of $\sim,$ we have $$f(a_0) = f(a_1).$$ Hence $$g([a_0]) = g([a_1]).$$ Therefore $$g$$ is well-defined. We now show that $$g$$ is injective. Suppose $$g([a_0]) = g([a_1]).$$ Then $$f(a_0) = f(a_1).$$ Thus $a_0 \sim a_1,$ and hence $$[a_0] = [a_1].$$ Therefore $$g$$ is injective. Finally, we show that $$g$$ is surjective. Let $b \in B.$ Since $$f$$ is surjective, there exists $a \in A$ such that $$f(a) = b.$$ Then $$g([a]) = f(a) = b.$$ Thus every element of $$B$$ lies in the image of $$g,$$ so $$g$$ is surjective. Consequently, $$g$$ is bijective, and hence there is a bijective correspondence between $A/{\sim}$ and $$B.$$ $\square$

5. Let $$S$$ be the subset of $\mathbb R^2$ defined by

\[S =\lbrace (x,y)\in \mathbb R^2 : (y = x + 1) \land (0<x<2) \rbrace.\]

Describe the equivalence relation $$T$$ on $\mathbb R$ that is the intersection of all equivalence relations on $\mathbb R$ that contain $$S.$$ Describe the equivalence classes of $$T.$$

Solution. Let $$T$$ denote the intersection of all equivalence relations on $\mathbb{R}$ that contain $$S.$$ Since every equivalence relation must be reflexive, symmetric, and transitive, $$T$$ is exactly the smallest equivalence relation on $\mathbb{R}$ containing all pairs $$(x, x+1)$$ with $$0 < x < 2.$$ Since $$S$$ contains only pairs $$(x,x+1)$$ with $$0<x<2,$$ in the graph picture, every nontrivial edge has the endpoint $$x$$ and $$x+1,$$ hence lies inside the interval $$(0,3).$$ Therefore every $x\notin (0,3)$ is immediately isolated, so

\[[x]=\lbrace x\rbrace \qquad x \in (-\infty, 0] \cup [3, \infty).\]

Once we know the relevant region is the interval $$(0,3),$$ we examine what kind of graph can be captured in $$(0,3).$$ We note that the length of an edge is short enough for us to capture two adjacent edges. Thus we find the remaining equivalence classes:

\[[x] = \lbrace x, x+1, x+2\rbrace \qquad (0 < x < 1).\]

At this stage, we explicitly record what has been covered: as $$x$$ ranges over $$(0, 1)$,$ the elements $$x$,$ $$x+1$,$ and $$x+2$$ range over $$(0, 1)$,$ $$(1, 2)$,$ and $$(2, 3)$,$ respectively. Therefore the classes cover every non-integer point in $$(0, 3)$.$ That is, only the integer points inside $$(0, 3)$$ remain, namely $$1$$ and $$2$.$ From the fact that $1\sim 2,$ but $0\not\sim 1$ and $2\not\sim 3,$ we find the last remaining equivalence class:

\[[1]=\lbrace 1,2 \rbrace.\]

Equivalently, the relation $$T$$ itself can be described as

\[\begin{aligned} T = {}& \Delta_{\mathbb R}\\ &\cup \lbrace (x,x+1),(x+1,x),(x+1,x+2),(x+2,x+1),(x,x+2),(x+2,x):0<x<1\rbrace \\ &\cup \lbrace (1,2),(2,1)\rbrace \end{aligned}\]

where $\Delta_{\mathbb R}$ is the diagonal in $\mathbb R,$ defined by

\[\Delta_{\mathbb R} = \lbrace (x,x):x\in\mathbb R\rbrace.\]