How many equivalent classes there are?

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

Re: How many equivalent classes there are?

Quote:

Originally Posted by

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

The relation is not well defined (depends on the decimal expansion of $\displaystyle x\in\mathbb{R}$). For example $\displaystyle 1=0.999\ldots$ so, $\displaystyle 0.999\ldots \not\sim 1$ and $\displaystyle 1\sim 1$ .

Re: How many equivalent classes there are?

Quote:

Originally Posted by

**FernandoRevilla** The relation is not well defined (depends on the decimal expansion of $\displaystyle x\in\mathbb{R}$). For example $\displaystyle 1=0.999\ldots$ so, $\displaystyle 0.999\ldots \not\sim 1$ and $\displaystyle 1\sim 1$ .

Thanks for the reply. I knew that. But by my definition $\displaystyle 0.999\ldots \not\sim 1$. What you have is $\displaystyle 1=0.999\ldots$, **NOT** $\displaystyle 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: $\displaystyle \forall a,b \in \mathbb{R}$, $\displaystyle a\sim b$ iff $\displaystyle a$ and $\displaystyle b$ differ in finitely many digits or a (b) ends in ...999... and b (a) ends in ...000...

-----------------------------------------------

I'd like to hear your opinion. Thanks in advance(Happy)

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

Re: How many equivalent classes there are?

Quote:

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: $\displaystyle \forall a,b \in \mathbb{R}$, $\displaystyle a\sim b$ iff $\displaystyle a$ and $\displaystyle b$ differ in finitely many digits or $\displaystyle a=b$.

It is also ill defined. Choose for example $\displaystyle a=0,\;b=1=0.999\ldots$ .

Re: How many equivalent classes there are?

Try to show that each class contains countably many elements.

Re: How many equivalent classes there are?

Quote:

Originally Posted by

**FernandoRevilla** It is also ill defined. Choose for example $\displaystyle 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?

Re: How many equivalent classes there are?

Quote:

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 $\displaystyle \mathbb{R}$ . You can define a well defined equivalence relation in $\displaystyle S=\{(a_n)_{n\geq 0}:a_n\in\{0,1,\ldots,9\}}\}$ in the following way: $\displaystyle (a_n)\sim (b_n)$ iff $\displaystyle 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.

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 $\displaystyle E$ be the set of all equivalent classes of $\displaystyle S$ in #7. Choose any $\displaystyle {E}_{x}\in E$ and $\displaystyle x\in {E}_{x}$.

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

Q.E.D.

-------------------------------------------------------------------------------

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

Proof:

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

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

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

------------------------------------------------------------------------------

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

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

-------------------------------------------

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

Re: How many equivalent classes there are?

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

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

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

----------------------------------------

Edit: Bold font

Re: How many equivalent classes there are?

Quote:

Originally Posted by

**godelproof** **1.** Any equivalent class contains countable elements.

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

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

Re: How many equivalent classes there are?

Quote:

Originally Posted by

**godelproof** Thanks for the reply. I knew that. But by my definition $\displaystyle 0.999\ldots \not\sim 1$. What you have is $\displaystyle 1=0.999\ldots$, **NOT** $\displaystyle 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 $\displaystyle \{0,\dots,9\}^\mathbb{N}$ instead of $\displaystyle \mathbb{R}$ is probably the most reasonable approach here.

Re: How many equivalent classes there are?

Quote:

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 $\displaystyle \{0,\dots,9\}^\mathbb{N}$ instead of $\displaystyle \mathbb{R}$ is probably the most reasonable approach here.

That was crystal clear! Thank you!!

Re: How many equivalent classes there are?

Quote:

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?

Re: How many equivalent classes there are?

Quote:

Originally Posted by

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

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

Re: How many equivalent classes there are?

Quote:

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 $\displaystyle |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?)