# Thread: How many equivalent classes there are?

1. ## How many equivalent classes there are?

$\forall a, b \in \mathbb{R}$, $a\sim b$ iff $a$ and $b$ differ in finitely many digits. (So for example $3.14\sim 502.441$ but $3.14\nsim \pi$). Then this equivalent relation $\sim$ partitions $\mathbb{R}$ into different equivalent classes. How many equivalent classes there are?

2. ## Re: How many equivalent classes there are?

Originally Posted by godelproof
$\forall a, b \in \mathbb{R}$, $a\sim b$ iff $a$ and $b$ differ in finitely many digits. (So for example $3.14\sim 502.441$ but $3.14\nsim \pi$). Then this equivalent relation $\sim$ partitions $\mathbb{R}$ into different equivalent classes. How many equivalent classes there are?
The relation is not well defined (depends on the decimal expansion of $x\in\mathbb{R}$). For example $1=0.999\ldots$ so, $0.999\ldots \not\sim 1$ and $1\sim 1$ .

3. ## Re: How many equivalent classes there are?

Originally Posted by FernandoRevilla
The relation is not well defined (depends on the decimal expansion of $x\in\mathbb{R}$). For example $1=0.999\ldots$ so, $0.999\ldots \not\sim 1$ and $1\sim 1$ .
Thanks for the reply. I knew that. But by my definition $0.999\ldots \not\sim 1$. What you have is $1=0.999\ldots$, NOT $0.999\ldots \sim 1$. I don't really see anything inconsistent with the definition...
---------------------------------------------
Well, maybe I was wrong and it IS ill-defined (but I'd like to know why?). If that is the case, let me define it this way: $\forall a,b \in \mathbb{R}$, $a\sim b$ iff $a$ and $b$ differ in finitely many digits or a (b) ends in ...999... and b (a) ends in ...000...
-----------------------------------------------

Edit: Red. sorry for that conspicuous mistake. Corrected in red.

4. ## Re: How many equivalent classes there are?

Originally Posted by godelproof
Well, maybe I was wrong and it IS ill-defined (but I'd like to know why?). If that is the case, let me define it this way: $\forall a,b \in \mathbb{R}$, $a\sim b$ iff $a$ and $b$ differ in finitely many digits or $a=b$.
It is also ill defined. Choose for example $a=0,\;b=1=0.999\ldots$ .

5. ## Re: How many equivalent classes there are?

Try to show that each class contains countably many elements.

6. ## Re: How many equivalent classes there are?

Originally Posted by FernandoRevilla
It is also ill defined. Choose for example $a=0,\;b=1=0.999\ldots$ .
Thanks. I've correct that mistake in red letters. But you haven't explained to me why is the original definition ill-defined?

7. ## Re: How many equivalent classes there are?

Originally Posted by godelproof
But you haven't explained to me why is the original definition ill-defined?
I have explained it. The relation is ill defined in $\mathbb{R}$ . You can define a well defined equivalence relation in $S=\{(a_n)_{n\geq 0}:a_n\in\{0,1,\ldots,9\}}\}$ in the following way: $(a_n)\sim (b_n)$ iff $a_n=b_n$ except for a finite number of terms. I suppose this is what you meant. If you have seen the problem in a book, please transcribe it.

8. ## Re: How many equivalent classes there are?

Let me use FernandoRevilla's definition in #7. Please check if there's any problem with the following proofs:

1. Any equivalent class contains countable elements.

Proof: Let $E$ be the set of all equivalent classes of $S$ in #7. Choose any ${E}_{x}\in E$ and $x\in {E}_{x}$.

$\forall y\in S$ and $y\sim x$ $\Longrightarrow$ $\exists {N}_{y}\in \mathbb{N}$ such that ${y}_{n}={x}_{n},\ \forall n>{N}_{y}$. Hence $y \in {\bigcup}_{k=0}^{\infty}{a}^{k}$, where ${a}^{0}=x$ and ${a}^{k}=\{({a}_{0},{a}_{1},...,{a}_{k-1},{x}_{k},{x}_{k+1},{x}_{k+2},...)|{a}_{i} \in \{0,1,...,9\}\}$ for $k\geq 1$. Since $y\sim x$ was arbitary, we have ${E}_{x}\subseteq {\bigcup}_{k=0}^{\infty}{a}^{k}$. Since ${a}^{k}$ is countable for any $k$, we proved that ${E}_{x}$ is countable.
Q.E.D.
-------------------------------------------------------------------------------

2. $|E|>{\aleph}_{0}$.

Proof:

(1) If $|E|<{\aleph}_{0}$, then E contains finite elements ${E}_{1},{E}_{2},...,{E}_{n}$. Now because S is uncountable and $S={\bigcup}_{i=1}^{n}{E}_{i}$, some ${E}_{i}$ must contain uncountably many elements, i.e., $|{E}_{i}|>{\aleph}_{0}$ for some i. Contradiction to proof in 1.

(2) If $|E|={\aleph}_{0}$, then $E={\{{E}_{i}\}}_{i=0}^{\infty}$. Define $B={\{{x}^{i}\}}_{i=0}^{\infty}$, where ${x}^{i}\in {E}_{i}$ for all i. Now we derive a contradiction by constructing $y \in S$ but $y \notin {E}_{i}$, $\forall i$ as follows:

define $f(i,j)={2}^{i}(2j+1)-1$, then clearly $f(i,j)$ is a bijection from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$. Construct y by choosing ${y}_{f(i,j)} \in \{0,1,...,9\}/{x}_{j}^{i}$ for $i=0,1,2,...$ and $j=0,1,2,...$ (Or by the Cantor's diagonal method, if you prefer). Clearly $y \notin {E}_{i}$, $\forall i$. Which is a contradiction. Q.E.D.
------------------------------------------------------------------------------

3. $|E|\leq |S|$

Proof: Choose from each element ${E}_{x}$ of $E$ an $x \in {E}_{x}$. Let the set of all such x's be $D$. Clearly $|D|=|E|$. But $D \subseteq S$. Hence $|D| \leq |S|$. Hence $|E|\leq |S|$. Q.E.D.

-------------------------------------------
Edit: all $\mathbb{R}$ is replaced by $S$

9. ## Re: How many equivalent classes there are?

It is easy to see that $|S|=|\mathbb{R}|$, so:

is ${\aleph}_{0}<|E|\leq |\mathbb{R}|$ all we can say about $|E|$?

Can we show that $|E|=|\mathbb{R}|$, without assuming ${\aleph}_{1}=|\mathbb{R}|$?

----------------------------------------
Edit: Bold font

10. ## Re: How many equivalent classes there are?

Originally Posted by godelproof
1. Any equivalent class contains countable elements.

Proof: Let $E$ be the set of all equivalent classes of $S$ in #7. Choose any ${E}_{x}\in E$ and $x\in {E}_{x}$.

$\forall y\in S$ and $y\sim x$ $\Longrightarrow$ $\exists {N}_{y}\in \mathbb{N}$ such that ${y}_{n}={x}_{n},\ \forall n>{N}_{y}$. Hence $y \in {\bigcup}_{k=0}^{\infty}{a}^{k}$, where ${a}^{0}=x$ and ${a}^{k}=\{({a}_{0},{a}_{1},...,{a}_{k-1},{x}_{k},{x}_{k+1},{x}_{k+2},...)|{a}_{i} \in \{0,1,...,9\}\}$ for $k\geq 1$. Since $y\sim x$ was arbitary, we have ${E}_{x}\subseteq {\bigcup}_{k=0}^{\infty}{a}^{k}$. Since ${a}^{k}$ is countable for any $k$, we proved that ${E}_{x}$ is countable. Q.E.D.
That is right. Now, I have no time so, I'll review the rest as soon as possible.

11. ## Re: How many equivalent classes there are?

Originally Posted by godelproof
Thanks for the reply. I knew that. But by my definition $0.999\ldots \not\sim 1$. What you have is $1=0.999\ldots$, NOT $0.999\ldots \sim 1$. I don't really see anything inconsistent with the definition...
In case this is still not clear: If two objects are equal, then one of them can be replaced by the other in any proposition without changing the truth value of this proposition. (Sometimes this is even taken as the definition of equality.) So here we have

1 ~ 1 (*)

and 1 = 0.999... Replacing the second occurrence 1 in (*) by an equal object 0.999... we get

1 ~ 0.999...

which is false, unlike (*).

Ill-defined definitions typically happen when they involve choosing a representative. Some rational numbers have two decimal expansions, and choosing one or the other gives different results with respect to ~; hence ~ is ill-defined.

I agree with Fernando that considering $\{0,\dots,9\}^\mathbb{N}$ instead of $\mathbb{R}$ is probably the most reasonable approach here.

12. ## Re: How many equivalent classes there are?

Originally Posted by emakarov
In case this is still not clear: If two objects are equal, then one of them can be replaced by the other in any proposition without changing the truth value of this proposition. (Sometimes this is even taken as the definition of equality.) So here we have

1 ~ 1 (*)

and 1 = 0.999... Replacing the second occurrence 1 in (*) by an equal object 0.999... we get

1 ~ 0.999...

which is false, unlike (*).

Ill-defined definitions typically happen when they involve choosing a representative. Some rational numbers have two decimal expansions, and choosing one or the other gives different results with respect to ~; hence ~ is ill-defined.

I agree with Fernando that considering $\{0,\dots,9\}^\mathbb{N}$ instead of $\mathbb{R}$ is probably the most reasonable approach here.
That was crystal clear! Thank you!!

13. ## Re: How many equivalent classes there are?

Originally Posted by FernandoRevilla
That is right. Now, I have no time so, I'll review the rest as soon as possible.
Thanks, it's OK if you have no time. But what do you say about #9?

14. ## Re: How many equivalent classes there are?

Originally Posted by godelproof
It is easy to see that $|S|=|\mathbb{R}|$, so: is ${\aleph}_{0}<|E|\leq |\mathbb{R}|$ all we can say about $|E|$?

Out of curiosity: Are you trying to prove the Continuum Hypothesis?

15. ## Re: How many equivalent classes there are?

Originally Posted by FernandoRevilla
Out of curiosity: Are you trying to prove the Continuum Hypothesis?
Is that a joke?
Ok... what I meant was this: Can we conclude $|E|=|\mathbb{R}|$ without CH. (With CH we can of course conclude it; but perhaps for this particular problem we can conclude it without CH, too: not by my proofs there of course. Am I right about that?)

Page 1 of 2 12 Last