Results 1 to 5 of 5

Math Help - Infinte Sets

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    Infinte Sets

    Some notations:
    J_n = \{x|x \in N, 1\leq x \leq n\}
    For any two sets A,B; A \cong B \Rightarrow there exists a bijection between A and B

    I have read following two definitions of infinite sets:

    1. Set S, is finite if S \cong J_n for some n \in N. If a set is not finite, it is infinite.

    2. Set is infinite if there exits a proper subset of S, say S' such that S \cong S'

    Problem: I want to prove the equivalence of these two definitions.
    My Attempt: I have to demonstrate both Part 1 and Part 2 below -

    Part 1: To prove, if S \cong S' \Rightarrow there exists no n \in N such that S \cong J_n

    Outline of my attempt
    1. Let S \cong J_n for some n \in N
    2. Prove S' \cong J_m where m<n
    3. Assume S \cong S'
    4. Now we have J_n \cong S \cong S' \cong J_m \Rightarrow J_n \cong J_m, m<n. This leads to a contradiction if you apply pigeon-hole principle. Hence assumption in step 3 is not valid and we are done.

    Problem I am facing: Step 2 above. How do I prove it formally. I know it sounds so much true from intuition but how do I show it in the language of formal mathematics.

    Part 2: To prove, if there doens't exist any n \in N such that S \cong J_n \Rightarrow there exists a proper subset of S, S', where S \cong S'
    Problem I am facing: Don't even know how to start with this one?

    Also is my approach to this question correct, or there are other ways to do it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello aman_cc
    Quote Originally Posted by aman_cc View Post
    ...
    2. Prove S' \cong J_m where m<n
    ...

    Problem I am facing: Step 2 above. How do I prove it formally. I know it sounds so much true from intuition but how do I show it in the language of formal mathematics.
    I'm not sure about Part 2, but can't you say something like this for Part 1, Step 2?

    Suppose that f : S\mapsto J_n and f:S'\mapsto J_m where m \le n. We must prove m < n.

    S' is a proper subset of S \Rightarrow \exists p \in S for which p \notin S'

    Then f(p)\notin f(S'), for otherwise f^{-1}\Big(f(p)\Big) \in S'.

    Further
    \forall r \in S'

    S' \subset S \Rightarrow r \in S

    \Rightarrow f(S')\subseteq f(S)
    But we have now found a f(p) \in f(S) for which f(p) \notin f(S'). Hence f(S') = J_m is a proper subset of f(S)=J_n \Rightarrow m < n.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Grandad View Post
    Hello aman_ccI'm not sure about Part 2, but can't you say something like this for Part 1, Step 2?

    Suppose that f : S\mapsto J_n and f:S'\mapsto J_m where m \le n. We must prove m < n.

    S' is a proper subset of S \Rightarrow \exists p \in S for which p \notin S'

    Then f(p)\notin f(S'), for otherwise f^{-1}\Big(f(p)\Big) \in S'.

    Further
    \forall r \in S'

    S' \subset S \Rightarrow r \in S

    \Rightarrow f(S')\subseteq f(S)
    But we have now found a f(p) \in f(S) for which f(p) \notin f(S'). Hence f(S') = J_m is a proper subset of f(S)=J_n \Rightarrow m < n.

    Grandad
    Hi Grandad - Thanks. I have not been able to follow some of your conclusions.
    I am going to list them
    1.  f:S'\mapsto J_m . Why should that be?

    2. m \le n . Again why can't m>n?

    3. "Hence is a"
    We never showed f(S') = Jm

    I know all the above are trivial, but problem I am having is to put them formally. Apologies, but with my limited understanding, I think we still have some holes to plug, though I fully follow the idea you are proposing.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    Some notations:
    J_n = \{x|x \in N, 1\leq x \leq n\}
    For any two sets A,B; A \cong B \Rightarrow there exists a bijection between A and B

    I have read following two definitions of infinite sets:
    1. Set S, is finite if S \cong J_n for some n \in N. If a set is not finite, it is infinite.

    2. Set is infinite if there exits a proper subset of S, say S' such that S \cong S'
    It is really difficult to ‘jump in’ the middle of any development of finite/infinite sets.
    We do not know what theorems you have at hand.
    Generally, we would know these for finite sets.
    If S is a finite set and J_n=\{1,2,\cdots,n\} then:
    1) if there is an injection f:S\mapsto J_n then |S|\le n.
    1) if there is a surjection g:J_n\mapsto S then |S|\le n.

    There also a powerful theorem that applies to all sets:
    There is an injection f:A\mapsto B if and only if there is a surjection g:B\mapsto A.
    With those we show that no finite set bijects with a proper subset of itself.


    The second definition is known as Dedekind Infinite.
    If J=\mathbb{Z}^+ then \left( {\forall n} \right)\left[ {J\backslash J_n } \right] is also infinite.
    Do you see how you might use this to show equivalence with the first definition.
    Last edited by Plato; November 22nd 2009 at 03:46 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Plato View Post
    It is really difficult to ‘jump in’ the middle of any development of finite/infinite sets.
    We do not know what theorems you have at hand.
    Generally, we would know these for finite sets.
    If S is a finite set and J_n=\{1,2,\cdots,n\} then:
    1) if there is an injection f:S\mapsto J_n then |S|\le n.
    1) if there is a surjection g:J_n\mapsto S then |S|\ge n.

    There also a powerful theorem that applies to all sets:
    There is an injection f:A\mapsto B if and only if there is a surjection g:B\mapsto A.
    With those we show that no finite set bijects with a proper subset of itself.


    The second definition is known as Dedekind Infinite.
    If J=\mathbb{Z}^+ then \left( {\forall n} \right)\left[ {J\backslash J_n } \right] is also infinite.
    Do you see how you might use this to show equivalence with the first definition.
    Thanks Plato.
    I think you meant -
    if there is a surjection g:J_n\mapsto S then |S|\le n.

    Well I guess I need to be comfortable with all the concepts you mentioned before I go any further.

    So, if I may ask one question - the two theorems you said

    1) if there is an injection f:S\mapsto J_n then |S|\le n.
    1) if there is a surjection g:J_n\mapsto S then |S|\le n.

    I trust both of them follow directly from pigeon-hole principle. Or, there is something more basic required?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Metric spaces, open sets, and closed sets
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 16th 2011, 06:17 PM
  2. Replies: 9
    Last Post: November 6th 2010, 01:47 PM
  3. Countable infinte or uncountable infinite
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2010, 03:39 AM
  4. Is this an infinte set?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: December 12th 2009, 12:24 PM
  5. Replies: 2
    Last Post: March 8th 2009, 06:29 PM

Search Tags


/mathhelpforum @mathhelpforum