Results 1 to 5 of 5

Math Help - a set is infinite iff there is a bijection between it and a proper subset

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    2

    a set is infinite iff there is a bijection between it and a proper subset

    I've been trying to prove that a set S is infinite if any only if there is a proper subset S' and a bijection \phi : S \longleftrightarrow S'.

    Assuming the bijection exists, it's pretty clear that S cannot be finite, and it was easy to prove this. But I'm not having much luck going the other direction:

    Assuming S is not finite, prove there exists S' \subset S with a bijection \phi : S \longleftrightarrow S'.

    Any tips?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,908
    Thanks
    1759
    Awards
    1
    How does your textbook define infinite set ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2009
    Posts
    2
    The textbook's definition is as follows:

    A set S is finite if it is empty or if there is a natural number n such that {1, 2, ..., n} and S have the same cardinality. A set that is not finite is said to be infinite.

    ... so essentially we have infinite defined as not finite.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,908
    Thanks
    1759
    Awards
    1
    Quote Originally Posted by pswoo View Post
    The textbook's definition is as follows:
    A set S is finite if it is empty or if there is a natural number n such that {1, 2, ..., n} and S have the same cardinality. A set that is not finite is said to be infinite.
    ... so essentially we have infinite defined as not finite.
    That is a definition that I do not use in my presentations of this material.
    Therefore, sad to say, I do not see a good way to do this.
    Maybe someone else here knows this approach.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    May 2009
    Posts
    27
    Here is my solution.

    We'll prove that if S is infinite, then S is in bijection with a proper subset of itself.

    This is obvious if S is countable, as if we remove one element, we still have a countable set, so we'll assume S is uncountable.

    It is true that any infinite set has a countable subset A=\{s_1,s_2,s_3\cdots\}.

    Define the bijection \phi as follows:

    Then define the bijection as follows:

    If x\notin A then \phi(x)=x .
    Otherwise, \phi(x)=s_{i+1},, where s_i=x.

    Then \phi is a bijection from S to S\smallsetminus s_1.

    I'll illustrate an example with the real numbers.

    \mathbb{R} has a countable subset, \{1,2,\cdots\}.

    Then \phi will map 1 to 2, 2 to 3, etc .. and everything else will remain fixed.

    We thus have a bijection from \mathbb{R}to \mathbb{R}\smallsetminus \{1\}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. If no proper subset of X is dense..
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 10th 2011, 07:03 AM
  2. Replies: 2
    Last Post: October 4th 2010, 04:53 PM
  3. Replies: 8
    Last Post: April 14th 2010, 10:36 AM
  4. Bijection of an infinite series
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 1st 2009, 04:34 AM
  5. Bijection in infinite sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: May 25th 2008, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum