- #1
Eclair_de_XII
- 1,083
- 91
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?