Prove equivalence relation of $S=\{1,2,3,\dots,10\}$ where $a \sim b$ if $a/b$ is a power of 2.

Question

Say $S=\{1,2,3,4,5,6,7,8,9,10\}$ and for $a, b \in S$ we have $a \sim b$ if $\frac{a}{b}$ is a power of $2$ (meaning $\frac{a}{b}= 2^m$ for some integer $m$).

Looking for a proof critique. I am still struggling with proof writing.

Here is what I have:

To prove this is an equivalence class we must show it is

• Reflexive
• Symmetric
• Transitive

Reflexive part:
We can see this is reflexive because if $a \in S$, $\frac{a}{a} = 1$ which is a power of two to the zeroth power. Also note $\frac{a}{a}=\frac{a}{a}$ and thus reflexives.

Symmetric part:\

If $a, b \in S$ then there is a $\frac{a}{b}= 2^m$ where $m \in \mathbb{Z}$. Taking this a set further $\log_{a}(\frac{a}{b})= \log_{a}(2^m)$. Then taking the log of both sides, $\log_{2}(a) - \log_{2}(b)= m$ where $m$ is an integer. This implies $\log_{2}(a)$ and $\log_{2}(b)$ are also integers. Thus $\frac{b}{a}$ since both at integers in $\log_2$, $\log_2(\frac{b}{a}) = \log_2(b) - \log_2(a) = -m$. Finally $\frac{b}{a} = 2^{-m}$

Now the transitive part:
Assume for some $a,b,c \in S$ that $\frac{a}{b}= 2^m$ and $\frac{b}{c}= 2^k$ where $k,m$ are some integers. Then if $\frac{\frac{a}{b}}{\frac{b}{c}}= \frac{2^m}{2^k}$. We would have $\frac{ab}{bc}= \frac{a}{c}=2^{m-k}$. Since $m, k$ are integers $m-k$ is in integer.

Since we've seen reflexive, symmetric and transitive property we have a relation.

Answer 1

To prove this is an equivalence class we must show it is equivalence relation (equivalence class is an object related to equivalence relation)

• Reflexive
• Symmetric
• Transitive

Reflexive part:
We can see this is reflexive because if $a \in S$, $\frac{a}{a} = 1$ which is a power of two to the zeroth power. Also note $\frac{a}{a}=\frac{a}{a}$ and thus reflexives. This part is of no use there, the first sentence proves the reflexivity.

Symmetric part:\

If $a, b \in S$ then there is a $\frac{a}{b}= 2^m$ where $m \in \mathbb{Z}$. Taking this a set further $\log_{a}(\frac{a}{b})= \log_{a}(2^m)$. Then taking the log of both sides, $\log_{2}(a) - \log_{2}(b)= m$ where $m$ is an integer. This implies $\log_{2}(a)$ and $\log_{2}(b)$ are also integers. Thus $\frac{b}{a}$ since both at integers in $\log_2$, $\log_2(\frac{b}{a}) = \log_2(b) - \log_2(a) = -m$. Finally $\frac{b}{a} = 2^{-m}$

Why do you use the logarithm? Looking at the first equality and the last one, you are just computing the inverse of $2^m$. Logarithm is an overkill here.

Now the transitive part:
Assume for some $a,b,c \in S$ that $\frac{a}{b}= 2^m$ and $\frac{b}{c}= 2^k$ where $k,m$ are some integers. Then if $\frac{\frac{a}{b}}{\frac{b}{c}}= \frac{2^m}{2^k}$. We would have $\frac{ab}{bc}= \frac{a}{c}=2^{m-k}$. Since $m, k$ are integers $m-k$ is in integer. There is a problem with $\frac{\frac{a}{b}}{\frac{b}{c}}= \frac{2^m}{2^k}$ implying $\frac{a}{c}=2^{m-k}$ check the rules for elimination in a fraction (if you struggle with this maybe you should try first with integers, for instance: $a=2$, $b=3$, $c=4$)

Since we've seen reflexive, symmetric and transitive property we have a relation. You mean an equivalence relation

Answer 2

As others have pointed out, you are proving that your relation is in fact an equivalence relation. Also, there is no need to invoke a logarithm explicitly.

Your arguments are essentially correct, if a bit wordy. The relation is defined by the existence of an integer:

$a \sim b$ in $S$ if there exists $m \in \Bbb{Z}$ such that $\displaystyle \smash{\frac{a}{b}} = 2^m$.

so for each of the three properties, where the conclusion is that a certain element in $S$ is related to another element in $S$, you must explicitly name that integer for those elements.

---

Reflexive. All you can assume is that $a \in S$. But, as you observed in your proof, $$ \frac{a}{a} = 1 = 2^0, $$ and of course $0 \in \Bbb{Z}$, so $a \sim a$.

Symmetric. Here you begin with $a \sim b$ in $S$, so there exists an $m \in \Bbb{Z}$ such that $\displaystyle \smash{\frac{a}{b}} = 2^m$. It follows that $$ \frac{b}{a} = 2^{-m}, $$ and $-m \in \Bbb{Z}$, so we've found the exponent; hence, $b \sim a$.

Transitive. Assume that $a \sim b$ and $b \sim c$ in $S$, so $$ \frac{a}{b} = 2^m \quad \text{and} \quad \frac{b}{c} = 2^n $$ for some $m, n \in \Bbb{Z}$. Now, $$ \frac{a}{c} = \frac{a}{b} \cdot \frac{b}{c} = 2^m \cdot 2^n = 2^{m+n}, $$ and $m + n \in \Bbb{Z}$, which shows that $a \sim c$. (This last part is where your most serious error lies.)