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

• Tsunoyukami
In summary, to prove that the set of all 2-element subsets of ##N## is denumerable, we can follow these 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\}##, which is an infinite subset of ##N x N## and therefore denumerable.4) Construct a function ##f: N → S## defined by mapping each element in ##N## to
Tsunoyukami
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.

Tsunoyukami said:
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.
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\}##.

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:
Tsunoyukami said:
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?
It will be a bijection from ##N_{2}## to ##S##, not to ##N \times N##.

Thank you, that's what I meant. I'll be working on this again shortly.

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)?

Tsunoyukami said:
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\}##.

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
$$f: N_2 \to S : P \mapsto (\max P,\min P)$$
and it is better to say so directly, and then confirm that it is a bijection.

pasmith said:
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
$$f: N_2 \to S : P \mapsto (\max P,\min P)$$
and it is better to say so directly, and then confirm that it is a bijection.

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?

Tsunoyukami said:
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.

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

$P$ itself contains exactly two distinct natural numbers, so one of them will be the maximum element of $P$ and the other the minimum.

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?

Tsunoyukami said:
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?
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?

jbunniii said:
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?

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:
Tsunoyukami said:
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?)
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...

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?
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)##.

jbunniii said:
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)##.

Would this element of ##\mathbb{N}_2## that maps to ##(a,b)## just be the set ##\{a,b\}##?

Tsunoyukami said:
Would this element of ##\mathbb{N}_2## that maps to ##(a,b)## just be the set ##\{a,b\}##?
Sure, can you prove it?

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##.

Tsunoyukami said:
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##.
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##.

## What is a "denumerable" set?

A denumerable set is a set that can be put into a one-to-one correspondence with the set of natural numbers (N). This means that the elements of the set can be counted and listed in a specific order.

## What is the set of all 2-element subsets of N?

The set of all 2-element subsets of N is a set that contains all possible combinations of two natural numbers. For example, the set contains subsets such as {1,2}, {2,3}, {3,4}, etc.

## Why is it important to prove that this set is denumerable?

Proving that this set is denumerable allows us to understand the size and structure of the set. It also helps us understand the properties and characteristics of denumerable sets in general.

## How can we prove that the set of all 2-element subsets of N is denumerable?

We can prove this by constructing a one-to-one correspondence between the set of all 2-element subsets of N and the set of natural numbers. This can be done by listing the subsets in a specific order and assigning a unique natural number to each subset.

## What are some real-life examples of denumerable sets?

Some real-life examples of denumerable sets include the set of positive integers, the set of even integers, and the set of decimals between 0 and 1. These sets can all be counted and put into a one-to-one correspondence with the set of natural numbers.

• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
728
• Calculus and Beyond Homework Help
Replies
4
Views
653
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Calculus and Beyond Homework Help
Replies
16
Views
3K
• Calculus and Beyond Homework Help
Replies
3
Views
742
• Calculus and Beyond Homework Help
Replies
1
Views
4K
• Calculus and Beyond Homework Help
Replies
8
Views
2K