Bijective function between an ordered pair and a scalar?

[Eclair_de_XII]

Homework Statement

"Prove that $S = \{(a, b) : a, b ∈ ℕ$ and $b ≥ 2a\}$ is denumerable."

Homework Equations

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

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?

 

[LCKurtz]

Homework Statement

"Prove that $S = \{(a, b) : a, b ∈ ℕ$ and $b ≥ 2a\}$ is denumerable."

Homework Equations

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

The Attempt at a Solution

Define $f: ℕ→S$ by $f(x)≥2x$.

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.

 

[Mark44]

Homework Statement

"Prove that $S = \{(a, b) : a, b ∈ ℕ$ and $b ≥ 2a\}$ is denumerable."

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.

 

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

 

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

 

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

 

[Eclair_de_XII]

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

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

If you were going to start counting them, what would you do?

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

 

[LCKurtz]

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

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.

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

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?

 

[Eclair_de_XII]

Let's see...

 

[LCKurtz]

Let's see...

View attachment 196061

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.

 

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

 

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

 

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

 

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

 

[Eclair_de_XII]

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

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

 

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