1
$\begingroup$

I was reading about countably infinite sets and the definition goes as, "A set is countably infinite if its elements can be put in one-to-one correspondence with the set of natural numbers"(Source: Google). Well yes, this make sense. As the set $\mathbb{N}$ is countably infinite and set which can it can create a bijection with, would end up having the same number of elements and thus they too would be countably infinite. But this would be true iff $\mathbb{N}$ is countably infinite. How would you prove that? Or is the idea of countably infinite base on some assumption that $\mathbb{N}$ is countably infinite?

$\endgroup$
  • 6
    $\begingroup$ A definition is not something that you prove. The definition of "countably infinite" then implies that $\mathbb N$ is countably infinite, because there is of course a bijection between $\mathbb N$ and itself. $\endgroup$ – Jakob Hansen Jun 17 '16 at 17:01
  • $\begingroup$ I'm not sure I'd say that we assume $\mathbb N$ is countably infinite so much as define it that way. There is some sense in this, since $|\mathbb N |$ is the smallest infinite cardinality. $\endgroup$ – Milo Brandt Jun 17 '16 at 17:01
  • 2
    $\begingroup$ The fact that $\Bbb N$ is countably infinite is trivial to prove from the definition! We need to show that the elements of $\Bbb N$ can be put into one-to-one correspondence with the elements of $\Bbb N$... $\endgroup$ – David C. Ullrich Jun 17 '16 at 17:01
  • 1
    $\begingroup$ You are confused. It is a fact that the elements of $\Bbb N$ can be put into one-to-one correspondence with the elements of $\Bbb N$. That is a proof that $\Bbb N$ is countably infinite. Because it satisfies the definition. $\endgroup$ – David C. Ullrich Jun 17 '16 at 17:06
  • 1
    $\begingroup$ What you think the definition is based on is totally irrelevant! All that matters is what the definition says. When we use the definition to show $\Bbb N$ is countably infinite we are not assuming what you say. Look, here's the proof: "The elements of $\Bbb N$ can be placed in one-to-one correspondence with the elements of $\Bbb N$, so $\Bbb N$ is countably infinite, by definition." That is the whole proof. Nowhere in that proof did I assume that $\Bbb N$ is countably infinite. $\endgroup$ – David C. Ullrich Jun 17 '16 at 17:16
3
$\begingroup$

We don't assume that $\Bbb N$ is countably infinite. We just name sets which can be put in bijection with $\Bbb N$ as countably infinite.

Then, it is a trivial consequence that $\Bbb N$ is countably infinite, as the identity function witnesses this fact.

$\endgroup$
1
$\begingroup$

That $N$ is countably infinite is not so much an assumption as it is a basic intuition. When we say a collection is countable, we are saying we can pair its items off with successive elements of $N$ because intuitively that is what counting actually is - a pairing off. And of course $N$ is infinite because intuitively, no matter how high we count, we can always count one more. So intuitively, something is countably infinite if it can be counted using all of $N$ and nothing less.

When we get to Axiomatic Set Theory, this intuition is formally embedded into the theory by postulating the Axiom of Infinity. So within the theory we can define 'countably infinite' as 'pairable with all elements of the set provided by the Axiom of Infinity'.

[so actually, your final question essentially gets to the heart of the matter]

$\endgroup$
  • 2
    $\begingroup$ What you say about the intuition behind things is correct. But this answer simply ignores the important point, which is that there is no circularity in using that definition to prove that $\Bbb N$ is countable. The reason the OP is confused is that he's thinking that this or that intuition has some relevance to the correctness of a formal proof. It does not - imo talking about the intuitive meanning of things as you do here is simply adding to the confusion. $\endgroup$ – David C. Ullrich Jun 17 '16 at 18:08

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.