# Homework Help: Bijective function between an ordered pair and a scalar?

1. Apr 19, 2017

### Eclair_de_XII

1. The problem statement, all variables and given/known data
"Prove that $S = \{(a, b) : a, b ∈ ℕ$ and $b ≥ 2a\}$ is denumerable."

2. Relevant equations
Basically, my aim is to find a bijection $f: ℕ→S$.

3. The attempt at a solution
Define $f: ℕ→S$ by $f(x)≥2x$.

Then suppose that there exist $x_1∈ℕ$ and $x_2∈ℕ$ such that $x_1≠x_2$ but $f(x_1)=f(x_2)$. Then $2x_1=2x_2$ implies that $x_1=x_2$. This produces a contradiction; so $f(x_1)=f(x_2)$ implies $x_1=x_2$. Similarly, suppose that $x_1=x_2$. Multiplying both sides by $2$ implies $f(x_1)=f(x_2)$. Therefore, $f$ is injective.

What I'm having trouble doing, is proving that an ordered pair $(a_0,b_0)∈S$ has a pre-image $a_0∈ℕ$. I'm trying to express the ordered pair as $f(a_0)=(a_0,b_0)$. Suppose that for an arbitrary $(a_0,b_0)∈S$, there exists an $a_0∈ℕ$ such that $f(a_0)=(a_0,b_0)$. I would say that there always exists a $b_0$ that is greater than $a_0$ because of the fact that the set of natural numbers has no "most" element. How would I write this formally, if this is correct?

2. Apr 19, 2017

### LCKurtz

Stop right there. You haven't defined a function to begin with. What is $f(1),~f(2),~f(3),\dots$? You have to have a formula or algorithm or something which tells you the exact values of $f(n)$ before you can even talk about whether it is 1-1 or onto.

3. Apr 20, 2017

### Staff: Mentor

Do you have a clear idea of what your set looks like? That might help you come up with a formula for your function, as LCKurtz suggests.

4. Apr 20, 2017

### Eclair_de_XII

Okay, so I redefined $f:ℕ→S$ as $f(x)=(x,2x)$ and $range(f(x))=\{(x,2x):x∈ℕ\}⊂S$. Then I proved that it was injective by contradiction. Let $x_1,x_2∈ℕ$ such that $x_1≠x_2$ and $f(x_1)=f(x_2)$. This implies that $(x_1,2x_1)=(x_2,2x_2)$, which produces a contradiction. But I ran into the problem of proving that it was surjective. Basically, I went about this through an inductive hypothesis. I basically said that $f(1)=(1,2)∈S$. Then I assumed that for some $k∈ℕ$, $f(k)=(k,2k)∈S$. I didn't exactly need induction for this, but in the end, I ended up saying that every natural number is a pre-image of some $f(x)∈S$. And since the domain of $f$ is ℕ, then there cannot be an $f(x_0)$ with no pre-image in ℕ. I think I proved only that the range of $f$ is denumerable. And I cannot say much for $S$, other than the fact that it's infinite...

5. Apr 20, 2017

### nuuskur

Whenever you can prove something directly, it is preferred to assumptions for contradictions. [unless it's an exercise meant to practice proof by contrapositive/contradiction or what have you.]

For injectivity you have to show $(x,2x) = (y,2y)$ implies $x=y$. This is immediate, because equality of ordered pairs is defined via component-wise equality. Your mapping, however fails to be surjective and that is quite obvious, as well. For $(1,3)\in S$ there is no $x\in\mathbb N$ such that $f(x) = (x,2x)=(1,3)$.

It suffices to construct injective mappings $S\to\mathbb N$ and $\mathbb N\to S$ [Cantor-Bernstein], for it is often simpler than finding an explicit bijection. You have one direction covered, now how about an injection $S\to\mathbb N$?

As for $S$ being an infinite set, if you want to be thorough, then you should prove it. A set $M$ is infinite if it contains a proper subset $M'$ such that there is a one to one correspondence between $M$ and $M'$. In this case, it's obvious the set $S$ is infinite.

You may also note that $\mathbb N\times\mathbb N$ is countably infinite i.e it's in a one to one correspondence with $\mathbb N$, therefore it would also suffice to construct a bijection $\mathbb N\times\mathbb N\to S$ or like before, construct two injections.

Last edited: Apr 20, 2017
6. Apr 20, 2017

### LCKurtz

It might help you to see a picture of your set.

The dots correspond to points in your set S. If you were going to start counting them, what would you do? That might get you started thinking about an appropriate mapping.

Last edited: Apr 20, 2017
7. Apr 20, 2017

### Eclair_de_XII

Hm, so it suffices to find two different injections? That would make this problem easier, I think. Thanks.

I guess I would draw a line through each of them?

8. Apr 20, 2017

### LCKurtz

I don't think so. One injection is trivial and you have already done it. And finding the other injection is essentially equivalent to your problem.

Describe how you would count them. Which would be number 1? Number 2? Etc. Take the picture I gave you and label the dots 1,2,3, etc. Do you understand that if you can "count" them you know your function?

9. Apr 20, 2017

### Eclair_de_XII

Let's see...

10. Apr 21, 2017

### LCKurtz

Why are you skipping over some? And there is no need for any n's. Just number all the dots you see in some sensible order as 1,2,3,4,5,6... Do it in such a way that you could keep going if the picture was larger.

11. Apr 21, 2017

### Eclair_de_XII

I didn't know in which direction to count the dots, so I just went with the function $g(a,b)=a+b-1$. If that's wrong, then here is the result of my effort, in any case.

12. Apr 21, 2017

### pasmith

It suffices to exhibit an injection $f : S \to \mathbb{N}$, as $S$ will then be (finite or) countable.

An easy way to do that is to exploit the fundamental theorem of arithmetic.

13. Apr 21, 2017

### JonnyG

It seems to be that it would be easier to generalize and prove that the 2-fold Cartesian product of two countable sets is countable, then prove that a subset of a countable set is countable.

14. Apr 21, 2017

### LCKurtz

@Eclair_de_XII No. I mean label them like this:

Doesn't that suggest a bijection between your $S$ and $N$? Now I realize that it depends on the level of sophistication required for whatever class you are taking what kind of proof they will accept. Certainly this is an informal indication of a bijection. Of course there is more work to do if you wish to find a formula for this in the form $f(n) = (?,?)$. Or you can use ideas some of the others have posted.

15. Apr 22, 2017

### Eclair_de_XII

In the end, I ended up doing this. I defined a function $f:ℕ×ℕ→ℕ$ by $f(m,n)=2^m⋅3^n$ and said that the prime factorization for each $(m_0,n_0)$ was unique. So $f$ was injective. Suffice it to say, I think I could have said that $f:ℕ×ℕ→f(ℕ×ℕ)⊂ℕ$ is bijective. And since the subset of any denumerable set is also denumerable, then I could have then said that there exists a bijection between the Cartesian product of natural numbers and a denumerable set. Thus, $|ℕ×ℕ|=|ℕ|$. I learned this in class...

16. Apr 22, 2017

### nuuskur

#16
since the subset of any denumerable set is also denumerable

Isn't denumerability the same as countable infinity? Are finite subsets countably infinite?