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

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

 

[jbunniii]

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\}$.

 

[Tsunoyukami]

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.

 

[jbunniii]

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

 

[Tsunoyukami]

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

 

[Tsunoyukami]

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

 

[pasmith]

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.

 

[Tsunoyukami]

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?

 

[pasmith]

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.

 

[Tsunoyukami]

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?

 

[jbunniii]

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?

 

[Tsunoyukami]

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?

 

[jbunniii]

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)$.

 

[Tsunoyukami]

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\}$?

 

[jbunniii]

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

Sure, can you prove it?

 

[Tsunoyukami]

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

 

[jbunniii]

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