# prove: ℕ is countably infinite

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 1 '16 at 2: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 1 '16 at 2:13
• A set A is countably infinite (denumerable) ⇔ A~ℕ. – haron May 1 '16 at 2:15
• @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 1 '16 at 2:16
• Take the identity function... – YoTengoUnLCD May 1 '16 at 2:16

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?