Results 1 to 6 of 6

Math Help - uncountable

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

    uncountable

    Prove that if a set  S is countably or uncountably infinite, then there is a proper subset  T \subset S and a bijection  f: S \to T .

    Consider the case in which the set is countably infinite. Then  \text{card}(S) = \aleph_0. Then there is a set  T such that  \text{card}(T) < \text{card}(S) . And so there is an injective function  f: T \to S . Then  f: S \to T is an injection and also a surjection which implies that it is a bijection.

    Consider case in which  S is uncountably infinite. Then  \text{card}(S) > \aleph_{0} . Suppose that  T is a set such that  \text{card}(S) > \text{card}(T) > \aleph_{0} .


    Now how do I proceed?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by particlejohn View Post
    Prove that if a set  S is countably or uncountably infinite, then there is a proper subset  T \subset S and a bijection  f: S \to T .

    Consider the case in which the set is countably infinite. Then  \text{card}(S) = \aleph_0. Then there is a set  T such that  \text{card}(T) < \text{card}(S) . And so there is an injective function  f: T \to S . Then  f: S \to T is an injection and also a surjection which implies that it is a bijection.

    Consider case in which  S is uncountably infinite. Then  \text{card}(S) > \aleph_{0} . Suppose that  T is a set such that  \text{card}(S) > \text{card}(T) > \aleph_{0} .


    Now how do I proceed?
    What definition are you using for an infite set?

    It looks to me as though what you are trying to prove is the Dedekind's definition of an infinite set.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    170
    Quote Originally Posted by CaptainBlack View Post
    What definition are you using for an infite set?

    It looks to me as though what you are trying to prove is the Dedekind's definition of an infinite set.

    RonL
    A set  S is said to be uncountably infinite if  \aleph_{0} < \text{card}(S) .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by particlejohn View Post
    Prove that if a set  S is countably or uncountably infinite, then there is a proper subset  T \subset S and a bijection  f: S \to T .
    A set is finite if it is equiponent to a natural number. A set is infinite if it is not finite (no seriously, that is how we define it). If A is finite then there is no proper subset B with |A| = |B|. Thus, if A has a proper subset equiponent to it then it means A is infinite. We may wonder if A is a set such that it is has a proper subset equiponent to it, then is it infinite (this property is Dedekind infinite)? Phrased more differently are infinite sets equivalent to Dedekind infinite sets? With the Axiom of Choice this is true. Let A be an infinite set. And let a\in A. Then since |A| > |\{ a\}| it means |A - \{ a\}| = |A|. Thus, B = A - \{ a\}\subset A is equipotent to A.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by particlejohn View Post
    Prove that if a set  S is countably or uncountably infinite, then there is a proper subset  T \subset S and a bijection  f: S \to T .
    Here is one way to proceed.

    Since S is infinite, it contains a countable subset E. Define f on E by f(e_i) = e_{i+1} \text{ and } f(x) = x elsewhere. Then f is one-to-one but e_1 is not in its range.
    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 awkward View Post
    Since S is infinite, it contains a countable subset E.
    By the way, in case you are interested this uses the Axiom of Choice.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cantor set is uncountable
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 6th 2009, 12:14 AM
  2. uncountable set
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 20th 2009, 10:45 AM
  3. [SOLVED] uncountable subset is itself uncountable
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 3rd 2009, 11:30 AM
  4. Replies: 4
    Last Post: October 11th 2008, 02:42 PM
  5. N^N is uncountable
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 22nd 2008, 02:34 AM

Search Tags


/mathhelpforum @mathhelpforum