prove: ℕ is countably infinite

Question

Please, I need someone to help me to prove this theorem

ℕ is countably infinite.

I know how can I prove it when the set define by something, but I'm confused and don't know how do this. Thanks

What's your definition of countably infinite? In general it's that a set $X$ is countably infinite if $|X|=|\Bbb N|$, in that case it's obvious... — YoTengoUnLCD, May 01 '16 at 02:12
What's your definition of countably infinite? Usually, the definition is that a set $X$ is countably infinite if there is a bijection $X \to \mathbb{N}$, which makes this proof fairly quick. — Clive Newstead, May 01 '16 at 02:13
@alruwaytie: And presumably $A \sim \mathbb{N}$ means there is a bijection $A \to \mathbb{N}$? In which case... can you think of a bijection $\mathbb{N} \to \mathbb{N}$? — Clive Newstead, May 01 '16 at 02:16
Since the question was originally tagged [tag:rational-numbers], are you sure you didn't mean to ask for a proof of "$\mathbb Q$ is countably infinite" instead? In that case, see for example this question and the ones linked to it. — hmakholm left over Monica, May 01 '16 at 02:21

score 1 · Answer 1 · answered May 01 '16 at 02:21

One definition of a set $A$ being countably infinite is that we can find a function $f : A \to \Bbb N$ (where $\Bbb N$ is the set of natural numbers) such that $f$ is a bijection, i.e., a one-to-one and onto map. In other words, we can find a pairing between elements of $A$ and $\Bbb N$ such that each element of $\Bbb N$ is paired with a unique element of $A$, and each element of $A$ is paired with a unique element of $\Bbb N$. This is called a "one-to-one correspondence".

Now, using the above definition, you want to show $\Bbb N$ is countably infinite, right? So you need to find a function $f : \Bbb N \to \Bbb N$ that is one-to-one and onto. There is an obvious choice of function. Can you think of what it is? In other words, what should $f$ be?

prove: ℕ is countably infinite

1 Answers1