How many equivalent classes there are?

**godelproof** · June 26th 2011, 08:12 AM

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

**FernandoRevilla** · June 26th 2011, 11:01 AM

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$ .

**godelproof** · June 26th 2011, 06:53 PM

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...
-----------------------------------------------

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

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

**FernandoRevilla** · June 26th 2011, 09:41 PM

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$ .

**Traveller** · June 26th 2011, 09:42 PM

Try to show that each class contains countably many elements.

**godelproof** · June 26th 2011, 10:17 PM

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?

**FernandoRevilla** · June 26th 2011, 10:38 PM

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.

**godelproof** · June 27th 2011, 12:58 AM

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$

**godelproof** · June 27th 2011, 01:04 AM

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

**FernandoRevilla** · June 27th 2011, 02:21 AM

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.

**emakarov** · June 27th 2011, 03:30 AM

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.

**godelproof** · June 27th 2011, 03:38 AM

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!!

**godelproof** · June 27th 2011, 08:14 PM

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?

**FernandoRevilla** · June 27th 2011, 10:46 PM

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?

**godelproof** · June 27th 2011, 11:34 PM

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?)

Thread: How many equivalent classes there are?

LinkBack

Thread Tools

Display

How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Re: How many equivalent classes there are?

Similar Math Help Forum Discussions

[SOLVED] conjugacy classes

Distinct equivalent classes the null set

classes

Residue classes

Conjugation classes

Search Tags