0
$\begingroup$

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

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

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?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.