Results 1 to 10 of 10

Math Help - cardianlity

  1. #1
    Senior Member
    Joined
    Jan 2008
    From
    Montreal
    Posts
    311
    Awards
    1

    cardianlity

    Let f be a 1-1 function from A into B with B finite. Show that A is finite.

    I was thinking along the lines of since A \stackrel{1-1}{\mapsto} B and since B=\{b_1, \ b_2,\ ..., \ b_n\}, then A can have the same number of element as B, or slightly less, given that it's 1-1. Now since we can arrange all the elements of B, we should be able to do the same for A... but I'm not too sure on how to show this.
    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 lllll View Post
    Let f be a 1-1 function from A into B with B finite. Show that A is finite.
    What definition of finite are you using?

    Is it that a set S is finite iff there is a bijection defined on it to a set of consecutive naturals with a largest element.

    If so let f_b be a bijection from B to \{1, 2, .., n\} then f_b \circ f is a bijection from A to f_b(f(A)) . Now we just need to introduce a renumbering function on f_b(f(A)) so these are consecutive integers.

    Consider:

    f_{rn}(x)=\sum_{z \in f_b(f(A))} \chi_{\{y \in f_b(f(A)),\ y\le x\}}(z)

    Where \chi_U is the indicator or charateristic function of U (that is it is 1 for any element of U and zero otherwise).

    Then :

     <br />
f_{rn}\circ f_b \circ f<br />

    is a bijection of A to a set of consecutive integers with a largest element(you will have to fill in the detailed justification of this).

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    B is finite means that there exists an injection from B into \mathbb{N}

    So A \stackrel{f}{\longrightarrow} B \stackrel{g}{\longrightarrow} \mathbb{N}

    Where f is a bijection (1-1) and g is an injection.
    Show that g \circ f is an injection and you'll prove that there exists an injection from A into \mathbb{N} and hence A is finite.

    ______________________________________________
    You can also do it by cardinalities :
    \text{B is finite } \Leftrightarrow \text{ Card}(B) < \text{Card}(\mathbb{N})

    If there is a bijection between A and B, then \text{Card}(A)=\text{Card}(B)

    Hence \text{Card}(A)< \text{Card}(\mathbb{N}) \implies \text{ A is finite}

    But this requires to know the theorems relating cardinality to bijections, injections and surjections..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Moo View Post
    Hello,

    B is finite means that there exists an injection from B into \mathbb{N}

    So A \stackrel{f}{\longrightarrow} B \stackrel{g}{\longrightarrow} \mathbb{N}

    Where f is a bijection (1-1) and g is an injection.
    Show that g \circ f is an injection and you'll prove that there exists an injection from A into \mathbb{N} and hence A is finite.
    i don't think that is specific enough. we can have infinite sets for which there are injections into \mathbb{N}. we can do it for any countable set in fact. i think the Captain's definition is more on the ball here.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2008
    From
    Montreal
    Posts
    311
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    What definition of finite are you using?

    CB
    A set A is finite if either A is the empty set, or there is a n  \ \in \ \mathbb{N} such that A \sim \{ 1,2,..., n\}.

    That's the definition from the book.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Jhevon View Post
    i don't think that is specific enough. we can have infinite sets for which there are injections into \mathbb{N}. we can do it for any countable set in fact. i think the Captain's definition is more on the ball here.
    Well, this is what my teacher said
    Do you have examples of infinite sets for which there are injections into \mathbb{N} ?
    Oh okay, there are the ones that are in bijection with \mathbb{N}...

    Then we can say "g is injective, but not surjective"
    Follow Math Help Forum on Facebook and Google+

  7. #7
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by lllll View Post
    A set A is finite if either A is the empty set, or there is a n  \ \in \ \mathbb{N} such that A \sim \{ 1,2,..., n\}.

    That's the definition from the book.
    that is the definition CaptainBlack used. the case where the set is empty does not come into play here. since we would not have any function existing in the first place were that the case
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Moo View Post
    Well, this is what my teacher said
    maybe you weren't paying attention again. we talked about this before. listen to your professors!

    Do you have examples of infinite sets for which there are injections into \mathbb{N} ?
    how about the positive even numbers with the identity function. it is an injection "into" the natural numbers since it skips all the odd integers in the naturals


    congrats on the 35th post!!!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Jhevon View Post
    maybe you weren't paying attention again. we talked about this before. listen to your professors!
    No, it was by email, so I am sure he said it

    how about the positive even numbers with the identity function. it is an injection "into" the natural numbers since it skips all the odd integers in the naturals
    Actually, there exists a bijection from the set of even numbers into the natural numbers.
    I guess it's even what you call "identity function" :
    f : 2N -> N
    2n -> n
    It may sound weird, but this is a bijection :
    - f(n)=f(m) <=> 2m=2n <=> m=n. This is an injection.
    - n in N => there exists m in 2N such that f(n)=m, namely m=2n. This is a surjection.

    Hence f is a bijection.


    This is why I added "injection but not surjection"

    congrats on the 35th post!!!
    urgh ! I forgot it again !
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Moo View Post
    No, it was by email, so I am sure he said it


    Actually, there exists a bijection from the set of even numbers into the natural numbers.
    I guess it's even what you call "identity function" :
    f : 2N -> N
    2n -> n
    It may sound weird, but this is a bijection :
    - f(n)=f(m) <=> 2m=2n <=> m=n. This is an injection.
    - n in N => there exists m in 2N such that f(n)=m, namely m=2n. This is a surjection.

    Hence f is a bijection.


    This is why I added "injection but not surjection"


    urgh ! I forgot it again !
    the identity function on the even naturals to the naturals is not a surjection. since we only map to even numbers, we miss all the odd ones. so that definition does not work. maybe your professor was talking about something else. in fact, i think you are mixing up the definition for infinite sets with finite ones. a set is infinite if there exists an injection that is not onto from the set into itself.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum