MHB Intuitive Proof: $\omega \times \omega$ is Countable

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Set
AI Thread Summary
The discussion centers on proving that the set $\omega \times \omega$ is countable by establishing a bijection with $\omega$. The intuitive proof involves defining a function that maps pairs of natural numbers to single natural numbers, demonstrating both injectivity and surjectivity. The function $J(m,n) = T(m+n) + n$ is shown to be one-to-one and onto, confirming that every pair of natural numbers corresponds uniquely to a natural number. The participants also explore the relationship between this proof and other methods of demonstrating the countability of $\omega \times \omega$. This establishes a clear understanding of the countability of the Cartesian product of natural numbers.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Proposition:
The set $\omega \times \omega$ is equinumerous with $\omega$, i.e. the set $\omega \times \omega$ is countable.

"Intuitive Proof"

$$\mathbb{N}^2=\{ (n,m): n,m \in \mathbb{N} \}$$

View attachment 3825

$$1 \mapsto a_{11}$$
$$2 \mapsto a_{12}$$
$$3 \mapsto a_{31}$$
$$4 \mapsto a_{22}$$
$$5 \mapsto a_{13}$$
$$6 \mapsto a_{14}$$
$$7 \mapsto a_{23}$$
$$\ \ \ \ \cdots \cdots \\ \ \ \ \ \cdots \cdots \\ \ \ \ \ \cdots \cdots$$Could you explain me the intuitive proof? (Thinking)
 

Attachments

  • set_theory.png
    set_theory.png
    7.3 KB · Views: 97
Physics news on Phys.org
This process gives every pair of natural numbers a single natural number and vice versa: e.g., (1, 3) corresponds to 5. This correspondence is a bijection.
 
So do we know that it is an injection because we pair each natural number to a diferent pair of natural numbers?
Also do we know that it is a surjection because there are both infinitely many natural numbers and pairs of natural numbers, so for each pair there will be a single element that we can correspond to the pair? (Thinking)
 
Yes, pretty much.
 
Then it is given the following proof:

We define recursively the function $T: \omega \to \omega$ as follows:

$T(0)=0 \ \ \ \ \ T(n+1)=T(n)+n=1$

which has the following properties:

  • it is strictly increasing
  • it is 1-1
  • show that $(\forall y \in \omega) (\exists x \in \omega) (T(x) \leq y<T(x+1))$
We define the function $J(m,n)=T(m+n)+n (\langle m,n \rangle=m,n)$.

We will show that $J$ is 1-1 and surjective, i.e. $J: \omega \times \omega \overset{\text{surjective}}{\longrightarrow} \omega$.
  • $J$ is 1-1.

    Let $\langle m,n \rangle \neq \langle k,l \rangle , m,n,k,l \in \omega$.

    First case: $m+n=n+k$

    If we had $J(m,n)=J(k,l)$ then $T(m+n)+n=T(k+l)+l \rightarrow n=l$ and since $m+n=k+l$ we have that $m=k$ that implies that $\langle m,n \rangle= \langle k, l \rangle$, contradiction.
    Thus $J(m,n) \neq J(k,l)$.Second case: $m+n \neq k+l$

    We suppose without loss of generality that $m+n<k+l$. Then $m+n+1 \leq k+l$ and so $T(m+n+1) \leq T(k+l)$.

    We have that $J(m,n)=T(m+n)+n<T(m+n)+n+1=T(m+n+1) \leq T(k+l)<T(k+l)+l=J(k,l)$

    Thus, $J(m,n) \neq J(k,l)$.
  • Show that $J$ is surjective.
Is this proof related to the other proof? Do we have the same correspondance?
 
Last edited:
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
15
Views
2K
Replies
3
Views
2K
Replies
18
Views
1K
Replies
9
Views
2K
Replies
2
Views
3K
Replies
3
Views
2K
Replies
1
Views
2K
Back
Top