1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that the set of all 2-element subsets of N is denumerable.

  1. Mar 10, 2014 #1
    I am having difficulty with the following Exercise due next week.

    Prove that the set of all 2-element subsets of ##N## is denumerable. (Exercise 10.12 from Chartrand, Polimeni & Zhang's Mathematical Proofs: A Transition to Advanced Mathematics; 3rd ed.; pg. 262).

    My idea so far was something like this:
    1) Notice ##N## is denumerable since the identity function is a bijective function from ##N## to ##N##.
    2) Notice that ##N x N## is denumerable since the Cartesian Product of two denumerable sets is denumerable.
    3) The set ##N x N## consists of all ordered pairs of the form ##(a,b)## such that ##a,b \in N## (ie. each ordered pair is "like" a 2-element subset)
    4) Every infinite subset of a denumerable set is denumerable.

    My difficulty lies in what I have in step (3). I have said "each ordered pair is "like" a 2-element subset" which really isn't precise enough...

    I'm not sure if my approach is entirely correct (in fact, I'm pretty sure it's not) but I feel like I'm using all the right facts necessary. Any guidance on how to approach this problem would be appreciated.
     
  2. jcsd
  3. Mar 10, 2014 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your approach is quite correct. You just need to make step 3 a bit more precise. To do this, see if you can construct a bijection between the set of 2-element subsets of ##\mathbb{N}## and a subset of ##\mathbb{N}\times \mathbb{N}##.

    The only thing to watch out for is that an ordered pair of the form ##(x,x)## won't correspond to any 2-element set, since the set ##\{x,x\}## is simply equal to ##\{x\}##.
     
  4. Mar 11, 2014 #3
    Okay, so after sleeping I have come up with what might be the next step to making (3) more precise.

    Recall the following steps.
    1) Notice that ##N## is denumerable.
    2) Notice that ##N x N## is denumerable. ##N x N = \left\{(a,b) : a,b \in N\right\}##
    3) Consider the set ##S = \left\{(a,b) : a,b\in N and b < a \right\}##. This is an infinite subset of ##N x N## and therefore is also denumerable. By constructing the set ##S## we have removed all ordered pairs of the form ##(a,a)## and any ordered pairs that are inverses of those in S. (That is, if ##(a,b), (b,a) \in N x N## we consider only ##(a,b)## because the sets ##\left\{a,b\right\}=\left\{b,a\right\}##).

    Create a table of elements in the following form:

    (1,1) (1,2) (1,3)
    (2,1) (2,2) (2,3)
    (3,1) (3,2) (3,3)

    So the set ##S## consists only of elements below the diagonal created by the ordered pairs (a,a). We can then write ##S=\left\{(2,1), (3,1), (3,2), (4,1), (4,2), (4,3),...\right\}##

    Now we construct a function ##f: N → S## defined by

    1 → (2,1)
    2 → (3,1)
    3 → (3,2)
    4 → (4,1)
    5 → (4,2)
    6 → (4,3)
    (and so on)

    Notice that this function ##f## is bijective. So we know ##S## is denumerable. (We knew this already by showing that S was a subset of N x N.)


    Before, jbunniii suggested "To do this, see if you can construct a bijection between the set of 2-element subsets of N and a subset of N×N."

    What I have done so far is constructed the desired subset of N x N. Now all I have left to do is find a bijection from ##N_{2}## (ie. the 2-element subsets of N) to N x N. Is that correct?

    EDIT: I mean a bijection from ##N_{2}## to S. Thanks to jbunniii for the correction.
     
    Last edited: Mar 11, 2014
  5. Mar 11, 2014 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It will be a bijection from ##N_{2}## to ##S##, not to ##N \times N##.
     
  6. Mar 11, 2014 #5
    Thank you, that's what I meant. I'll be working on this again shortly.
     
  7. Mar 11, 2014 #6
    Okay, so now I need to find a bijection from ##N_{2}## to ##S## where ##N_{2}## and ##S## are defined as they are above (post #3).

    First, recall that ##N_{2}## is the set consisting of all 2-element subsets of ##N##. That is, each subset is of the form ##\left\{a,b\right\}##. For each subset order the elements such that ##b<a##. That is, if we have a subset ##\left\{3,6\right\}## we instead write it as ##\left\{6,3\right\}##.

    Now we construct a function ##g:N_{2} \rightarrow S## defined by

    ##\left\{2,1\right\} \rightarrow (2,1)##
    ##\left\{3,1\right\} \rightarrow (3,1)##
    ##\left\{3,2\right\} \rightarrow (3,2)##
    ##\left\{4,1\right\} \rightarrow (4,1)##
    ##\left\{4,2\right\} \rightarrow (4,2)##
    ##\left\{4,3\right\} \rightarrow (4,3)##
    (and so on)

    This function is a bijection. Therefore ##N_{2}## and ##S## are numerically equivalent. In particular, since we know ##S## is denumerable we conclude that ##N_{2}## is denumerable.


    Is this a valid way to construct the function ##g:N_{2} \rightarrow S##? (Do I need to provide an explicit formula for the function?)

    If all of this is correct, is this a sufficient sketch of a proof (ie. posts 3 and 6 together)?
     
  8. Mar 11, 2014 #7

    pasmith

    User Avatar
    Homework Helper

    Trying to displace the fundamental convention that the order in which we list elements between braces does not matter is not a good idea.

    What you're doing is taking your bijection to be
    [tex]f: N_2 \to S : P \mapsto (\max P,\min P)[/tex]
    and it is better to say so directly, and then confirm that it is a bijection.
     
  9. Mar 11, 2014 #8
    I'm not sure I understand completely. You have defined a function that takes ##f: N_{2} to S## as I have, but you have included some additional information.

    I'm not familiar with the notation ##\mapsto## so that's probably where my I'm having difficulty. I presume that this notation allows you to provide additional constraints on the bijection between ##N_{2}## and ##S## that tells us precisely how ##f## works.

    Lastly, I'm not clear on what ##P## is. Is ##P## just some property? Does it refer to the elements of ##S## as I expect? Or is it something else entirely?
     
  10. Mar 11, 2014 #9

    pasmith

    User Avatar
    Homework Helper

    "[itex]\mapsto[/itex]" is read as "maps to". In this context it means that if [itex]P \in N_2[/itex] then [itex]f(P) = (\max P, \min P) \in S[/itex].

    [itex]P[/itex] itself contains exactly two distinct natural numbers, so one of them will be the maximum element of [itex]P[/itex] and the other the minimum.
     
  11. Mar 11, 2014 #10
    Ahh, I think I see. By defining your function in this manner you don't need to worry about the order of the order of the elements in each subset of ##N_{2}## - this map ##\mapsto## takes care of that.

    So "all that I have left to do" is show that the function defined by pasmith is bijective (ie. both injective and surjective) and then I will be done. Then does this constitute a fair sketch of the proof?

    I'm not too sure how I would show that this function is bijective; I've never done so without being given an explicit formula for ##f## such as ##f(x)=x+3##.

    To show this function is injective I must show "If ##f(x)=f(y)##, then ##x=y##. In this case, the argument of my function is a subset of ##N_{2}## so I would have to show "If ##f(\left\{a,b\right\})=f(\left\{c,d\right\})##, then ##\left\{a,b\right\}=\left\{c,d\right\}##. Is that correct?
     
  12. Mar 11, 2014 #11

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that's correct. So suppose that ##f(\left\{a,b\right\})=f(\left\{c,d\right\})##. By definition, this means that ##(\max\{a,b\}, \min\{a,b\}) = (\max\{c,d\}, \min\{c,d\}) ##. What does this imply?
     
  13. Mar 11, 2014 #12
    I presume this would imply the following:
    1) ##\max\{a,b\}=\max\{c,d\}##
    2) ##\min\{a,b\}=\min\{c,d\}##

    Then, since I know the maxs and mins are equal is this enough to conclude that {a,b}={c,d}?

    EDIT: Wait, reading that question it seems silly. Since I know that the maxs and mins are equal and the ordering of a set doesn't matter (ie. {a,b}={b,a}) I can conclude that {a,b}={c,d}. So this would show that the function is injective. (Is this correct?)

    Next I must show that the function is surjective.


    SECOND EDIT: To show a function is surjective we show that for any ##y## in the range there exists an ##x## such that ##f(x)=y##. Since our function takes a subset as the argument and returns an ordered pair ##y## is an ordered pair and ##x## is an element of ##N_{2}##.

    So we want to show for any ##(\max\{a,b\},\min\{a,b\})## there exists a ##\{a,b\}## such that ##f(\{a,b\})=(\max\{a,b\},\min\{a,b\})##. Is that correct?
     
    Last edited: Mar 12, 2014
  14. Mar 12, 2014 #13

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I think it's fine as you stated it.

    If you wanted to be more pedantic, first note that the definition of equality of sets is that they contain the same elements. Thus showing equality of ##\{a,b\}## and ##\{c,d\}## means showing that ##\{a,b\} \subset \{c,d\}## and vice versa. Since both sets have exactly two elements, showing the containment in one direction suffices. So you would need to show that ##a \in \{c,d\}## and ##b \in \{c,d\}##. To show that ##a \in \{c,d\}##, we note that ##a## is equal to either ##\min\{a,b\}## or ##\max\{a,b\}##. Therefore, blah blah...

    Not exactly. We want to show that ##f## is surjective onto the set ##S##. Thus, start with an arbitrary element of ##S##. By definition of ##S##, this element will be of the form ##(a,b)## where ##a > b##. Now you need to find an element of ##\mathbb{N}_2## that maps to ##(a,b)##.
     
  15. Mar 12, 2014 #14
    Would this element of ##\mathbb{N}_2## that maps to ##(a,b)## just be the set ##\{a,b\}##?
     
  16. Mar 12, 2014 #15

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Sure, can you prove it?
     
  17. Mar 12, 2014 #16
    I'm not sure how to "prove" this per say. I just knew I needed to find an argument for my function that would return ##(a,b)## and knew by the definition of ##f## that the argument ##\{a,b\}## satisfied this requirement. Is that valid? I am looking for an ##x## such that ##f(x)=(a,b)##. Let ##x=\{a,b\}##. Then ##f(x)=f(\{a,b\})=(\max\{a,b\},\min\{a,b\})=(a,b)## where ##a>b##.
     
  18. Mar 12, 2014 #17

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, it's fine. There isn't that much to prove. The key is that ##(\max\{a,b\},\min\{a,b\})=(a,b)## because ##a > b##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove that the set of all 2-element subsets of N is denumerable.
  1. Denumerable sets (Replies: 9)

Loading...