Results 1 to 4 of 4

Math Help - Question involving showing there's a bijection

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Question involving showing there's a bijection

    My question is:

    Let A be a finite set with m elements, for some m\in\mathbb N. And suppose x is an object that is not a member of A.

    Prove, using the definitions, that A \cup \{x\} has m+1 elements.

    (All you are told about A is that it has m elements. You need to show that there is a bijection from \mathbb N_m_+_1 to A \cup \{x\}.)

    Any help would be appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32

    Re: Question involving showing there's a bijection

    Do you need to show there's a bijection?

    You could use induction as well. Start with the empty set (base case m=0). empty set union with {x} is {x} by definition and has 0+1 = 1 elements. so the base case is true.
    then assume P(k): "A union with {x} has m+1 elements for k \leq m"

    then prove P(k+1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Question involving showing there's a bijection

    Yeah, I need to show that there's a bijection rather than doing a proof by induction. Would you be able to help me? Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32

    Re: Question involving showing there's a bijection

    Maybe it's easier than I originally thought, maybe. Since A is a finite set, we can label the m elements a0 a1, a2 ... am

    then by definition
    A \cup \{x\}\\ has elements a0 a1, a2 ... am, x

    Let f be a bijection from A \cup \{x\}\\ to Nm+1 such that an -> n for n \leq m and x -> m+1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: April 18th 2011, 12:17 AM
  2. Replies: 1
    Last Post: March 28th 2011, 04:23 AM
  3. simple question on bijection
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 13th 2010, 09:33 AM
  4. need help showing a particular function is a bijection ((URGENT))
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 19th 2009, 11:04 PM
  5. Proof showing bijection
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2009, 01:18 AM

Search Tags


/mathhelpforum @mathhelpforum