Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - How many equivalent classes there are?

  1. #1
    Member
    Joined
    May 2009
    Posts
    146

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: How many equivalent classes there are?

    Quote Originally Posted by godelproof View Post
     \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 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    146

    Re: How many equivalent classes there are?

    Quote Originally Posted by FernandoRevilla View Post
    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.
    Last edited by godelproof; June 26th 2011 at 10:18 PM. Reason: mistake pointed out in #4 corrected
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: How many equivalent classes there are?

    Quote Originally Posted by godelproof View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162

    Re: How many equivalent classes there are?

    Try to show that each class contains countably many elements.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2009
    Posts
    146

    Re: How many equivalent classes there are?

    Quote Originally Posted by FernandoRevilla View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: How many equivalent classes there are?

    Quote Originally Posted by godelproof View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2009
    Posts
    146

    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
    Last edited by godelproof; June 27th 2011 at 01:18 AM. Reason: R replaced by S
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2009
    Posts
    146

    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
    Last edited by godelproof; June 27th 2011 at 02:09 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: How many equivalent classes there are?

    Quote Originally Posted by godelproof View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: How many equivalent classes there are?

    Quote Originally Posted by godelproof View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    May 2009
    Posts
    146

    Re: How many equivalent classes there are?

    Quote Originally Posted by emakarov View Post
    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!!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    May 2009
    Posts
    146

    Re: How many equivalent classes there are?

    Quote Originally Posted by FernandoRevilla View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: How many equivalent classes there are?

    Quote Originally Posted by godelproof View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    May 2009
    Posts
    146

    Re: How many equivalent classes there are?

    Quote Originally Posted by FernandoRevilla View Post
    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?)
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] conjugacy classes
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 7th 2011, 06:31 PM
  2. Distinct equivalent classes the null set
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: January 5th 2010, 12:47 PM
  3. classes
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 8th 2009, 04:28 PM
  4. Residue classes
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: September 22nd 2009, 09:29 PM
  5. Conjugation classes
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 24th 2008, 07:19 PM

Search Tags


/mathhelpforum @mathhelpforum