~$_P$ is an equivalence relation in A.

Question

Prove Proposition 2.23. Use the notations defined in Definition 2.21 and 2.22.

Definition 2.21. Let A be a set and R be an equivalence relation in A. Let x $\in$ A be an arbitrary element in A. The subset of A which contains all elements which is equivalent to x is called the equivalence class of x, and is denoted by $[x]_R$. If there are no confusion, sometimes it is shorted to $[x]$. The set of equivalence classes in A under the equivalence relation R is denoted by A/R.

Definition 2.22. Given a set A and a partition P of A. Then we call the relation “being in the same partition” the relation induced by the partition. It is denoted by ~$_P$. In other words, x ~$_P$ y if and only if x and y are in the same partition.

Prop 2.23

(1) A\R is a partition of A.

(2) ~$_P$ is an equivalence relation in A.

I was able to prove the first part of prop 2.23; (1) A/R is a partition of A by proving that

$\cup$ A/R =A

A/R is pair wise disjoint

$\forall$ x $\in$ A/R (x $\neq$ 0)

But im having trouble with the second part of the proposition.

(2) ~$_P$ is an equivalence relation in A.

I understand how to go about proving if a relation is an equivalence relation im just not sure how to go about it in this instance.

Answer 1

You need to prove the following:

1. $\forall x\in A,x\sim_Px$.

2. $\forall x,y\in A,x\sim_P y\implies y\sim_p x.$

3. $\forall x,y,z\in A,x\sim_P y\,\land y\sim_P z\implies x\sim_P z.$

I don't know exactly what you mean by "not sure how to go about it in this instance", but I hope that doing the first instance will help.

Let $x\in A$. You want to show that $x\sim_P x$, which means, as wrote in definition 2.22, that $x$ is in the same parts of the partition, which is trivial because $x=x$.

Answer 2

Since $P$ is a partition on $A$ for every element $a\in A$ there exactly one element in the partition that contains $a$ as element.

This allows you to define a function $f:A\to P$ such that $a\in f(a)\in P$.

Then the relation $\sim_P$ can be described by:$$a\sim_Pb\iff f(a)=f(b)$$

This makes it easy to prove that $\sim_P$ is an equivalence relation because it is immediately obvious that we have:

• $f(a)=f(a)$ for all $a\in A$ (reflexivity)
• $f(a)=f(b)\implies f(b)=f(a)$ for all $a,b\in A$ (symmetry)
• $f(a)=f(b)\wedge f(b)=f(c)\implies f(a)=f(c)$ for all $a,b,c\in A$ (transitivity).