Question

(b) Let be the relation on N define by a ~ b iff there are m,n e Z+ with albm and bla". Show that is an equivalence relation. on hea infinitolo

Answer 1

Recall Some Basic Facts and definition:

1.A binary relation $\small \sim$ on a set $\small A$ is said to be an Equivalence relation on $\small A$ if it satisfies the following conditions:

1. $\small a \sim a$, for all $\small a \in A$. (reflexivity)
2. If $\small a \sim b$ then $\small b \sim a$ (symmetry)
3. If $\small a \sim b$ and $\small b \sim c$ then $\small a \sim c$ (transitivity)

2.If $\small a|b$ and $\small b|c$implies $\small a|c$.

3. If $\small a|b$ then $\small a^{m}|b^{m}$ for all $\small m \in \mathbb{Z}^{+}$

SOLUTION:

Given a relation on $\small \mathbb{N}$ defined by $\small a \sim b$ if and only if there are $\small m,n \in \mathbb{Z}^{+}$ with $\small a|b^{m}$ and $\small b|a^{n}$ .

Claim: $\small \sim$ is an equivalence relation.

1. Reflexivity:

For $\small m=n=1$ we have $\small a|a^{m}(=a)$ and $\small a|a^{n}(=a)$ for every $\small a \in \mathbb{N}$ . That is, $\small \sim$ a reflexive relation.

2. Symmetry:

If $\small a\sim b$ then there are $\small m,n\in \mathbb{Z}^{+}$ with $\small a|b^{m}$ and $\small b|a^{n}$ .

Now $\small b|a^{n}$ and $\small a|b^{m}$ implies $\small b \sim a$.    ^{[just change the character of $\small m,n$]}

So, $\small \sim$ is Symmetric relation.

3. Transitivity:

If $\small a\sim b$ and $\small b\sim c$ then there are $\small m,n,m',n' \in \mathbb{Z}^{+}$ with $\small a|b^m,b|a^n,b|c^m^',c|b^n^'$ .

now $\small b|c^m^'\implies b^m|(c^m^')^{m}\implies b^{m}|c^{mm'}$ .Also given that $\small a|b^{m}$ . These two together implies $\small a|c^{mm'}$ ___________(i)

$\small b|a^{n}\implies b^n^'|(a^n)^{n'}\implies b^{n'} | a^{nn'}$. Also given that $\small c|b^{n'}$ . these two together implies $\small c|a^{nn'}$ _______________(ii)

From (i) and (ii) we have $\small a|c^{mm'}$ and $\small c|a^{nn'}$ ,Since $\small m,n,m',n' \in \mathbb{Z}^{+}$ implies $\small mm',nn' \in \mathbb{Z}^{+}$ . This implies $\small a \sim c$.

So, $\small \sim$ is Transitive.

Thus $\small \sim$ as equivalence relation. hence proved.