Results 1 to 11 of 11

Math Help - Countability of the irrational numbers

  1. #1
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641

    Countability of the irrational numbers

    One of the excersises in my book says "Is the set of all irrational numbers countable? Justify your response"

    Here is what I said (For the sake of writing let \mathbb{I} the set of irrationals):"

    1. First let us establish that \mathbb{Z} is an infintely countable set. This is readily seen since there is a 1-1 mapping of \mathbb{N} onto \mathbb{Z} so \mathbb{N}\sim\mathbb{Z}, thus the integers are countable.

    2. Lemma: If A is a countable set and if B_n the set of all n-tuples (a_1,a_2,\cdots,a_n) where a_1,a_2,\cdots,a_n\in{A}, then B_n is countable.

    3. So realizing that the rationals may be expressed as \frac{m\in\mathbb{Z}}{n\in\mathbb{Z}}. So now since if we express every rational number as (m,n) we can show that the rationals may be expressed as a set of ordered pairs (2-tuples). We have that the rationals may be expressed as an analogue of #2 with \mathbb{Q} expressed as B_2, and since A=\mathbb{Z}, a countable set, it follows that the rationals are countable.

    4. Lemma: The set of all Real numbers is uncountable

    5. Lemma: The union of any number of infinitely countable sets is countable.

    6. Assume that \mathbb{I} is countable, That would imply that \mathbb{R}=\mathbb{Q}\cup\mathbb{I} is countable. A contradiction.

    Therefore \mathbb{I} is uncountable \blacksquare"

    Does that look alright?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    It is well known that the set for rational numbers is countable. Cantor using the diagonal argument proved that the set [0,1] is not countable. Thus the irrational numbers in [0,1] must be uncountable. So basically your steps 4, 5, & 6, form the proof.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by Plato View Post
    It is well known that the set for rational numbers is countable. Cantor using the diagonal argument proved that the set [0,1] is not countable. Thus the irrational numbers in [0,1] must be uncountable. So basically your steps 4, 5, & 6, form the proof.
    Thank you very much Plato.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    We know that |\mathbb{R}| = |\mathbb{R}\times \mathbb{R}|. Let f: \mathbb{R}\to \mathbb{R}\times \mathbb{R} be a bijection. Define A = f[\mathbb{Q}] (that is the "image of \mathbb{Q}" i.e. \{ f(x) | x\in \mathbb{Q} \}). Of course, since A\subseteq \mathbb{R}\times \mathbb{R} it is a set of ordered pairs, let B = \text{dom}(A) (that is the first coordinates in this set of ordered pairs). Since |B|\leq |A| = |\mathbb{Q}| = |\mathbb{N}| (why?) it means there is x\in \mathbb{R} such that x\not \in B since |\mathbb{N}| < |\mathbb{R}|. Therefore, C = \{ x \} \times \mathbb{R} is disjoint with A which means C\subseteq (\mathbb{R}\times \mathbb{R}) - A. But we know that |C| = |\mathbb{R}| which means |(\mathbb{R}\times \mathbb{R}) - A|\geq |\mathbb{R}| \implies |(\mathbb{R}\times \mathbb{R}) - A| = \mathbb{R}. Finally, since \mathbb{R}\times \mathbb{R} corresponds with \mathbb{R} (with this bijection f) and A corresponds with \mathbb{Q} we can "substitute" to get |\mathbb{R} - \mathbb{Q}| = |\mathbb{R}|.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    I always wonder at efforts to reinvent the wheel.
    Bertram Russell said, “If it is worth saying, then it can be said simply”.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Plato View Post
    I always wonder at efforts to reinvent the wheel.
    Bertram Russell said, “If it is worth saying, then it can be said simply”.
    "If |A| < |B| then |B-A| = |A|" can be proven but this requires choice.
    In the demonstration above choice was avoided.
    ---

    For Mathstud: If A\subseteq \mathbb{R} is not uncountable we cannot conclude it must be countable. It turns out this statement is completely independent, and we cannot show whether it is true or false! Called Continuum Hypothesis. That is something you used implicitly in your attempted proof above.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by ThePerfectHacker View Post
    "If |A| < |B| then |B-A| = |A|" can be proven but this requires choice.
    In the demonstration above choice was avoided.
    ---

    For Mathstud: If A\subseteq \mathbb{R} is not uncountable we cannot conclude it must be countable. It turns out this statement is completely independent, and we cannot show whether it is true or false! Called Continuum Hypothesis. That is something you used implicitly in your attempted proof above.
    Where in my proof did I assert anything was countable?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Mathstud28 View Post
    Where in my proof did I assert anything was countable?
    Sorry about that! I thought your said to prove |\mathbb{I}| = |\mathbb{R}|. In that case assuming \mathbb{I} is countable and arriving at countadiction is not sufficient. But that is not what the problem was asking, it was just asking to show it is uncountable. In that case you are correct.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by ThePerfectHacker View Post
    Sorry about that! I thought your said to prove |\mathbb{I}| = |\mathbb{R}|. In that case assuming \mathbb{I} is countable and arriving at countadiction is not sufficient. But that is not what the problem was asking, it was just asking to show it is uncountable. In that case you are correct.
    Whew! Jeez TPH you scared me for a second
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker View Post
    "If |A| < |B| then |B-A| = |A|" can be proven but this requires choice.
    In the demonstration above choice was avoided.
    ---
    You need qualification on what A and B are since this is not true for finite sets.

    CB
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Plato View Post
    Bertram Russell said, “If it is worth saying, then it can be said simply”.
    Just for the record, I think it's Ludwig Wittgenstein rather than Bertrand Russell who said that.

    More accurately, what Wittgenstein actually wrote (in the preface to Tractatus Logico-Philosophicus) was "Was sich überhaupt sagen lässt, lässt sich klar sagen" ("What can be said at all can be said clearly").

    Russell certainly advocated the use of plain English, as in his essay How I Write, but I can't find anywhere where he used the words quoted above.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Irrational numbers
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: September 17th 2011, 10:34 PM
  2. Irrational numbers.Why ?
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 16th 2011, 01:12 PM
  3. Replies: 1
    Last Post: March 23rd 2010, 01:55 PM
  4. Inductive Proof of Countability of Algebraic Numbers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 5th 2009, 10:04 AM
  5. Replies: 8
    Last Post: September 15th 2008, 05:33 PM

Search Tags


/mathhelpforum @mathhelpforum