13
$\begingroup$

Are there any infinite sets that have a lower cardinality than the natural numbers? Is there a proof of this?

$\endgroup$
  • $\begingroup$ No; the cardinality of the natural numbers, usually $\omega$ is the least infinite cardinal. By definition, if the cardinality of a set $S$ was "lower" than that of the naturals(don't know the exact technical term), then there would be an injection between $S$ and the naturals, but not otherwise, so $S$ cannot be countably-infinite. $\endgroup$ – BFD Oct 30 '13 at 8:03
  • 1
    $\begingroup$ @BFD What you say is true, but then to answer the question you need to argue that every set $S$ that satisfies your equivalent conditions ($S$ injects into $\mathbb{N}$ but not vice versa, or equivalently $S$ injects into $\mathbb{N}$ but is not countably infinite) is actually finite, that is, it has the same cardinality as some natural number. Some argument is required here as in Asaf's answer. $\endgroup$ – Trevor Wilson Oct 30 '13 at 16:23
11
$\begingroup$

No there are none. If $A$ has cardinality of at most the natural numbers, we may assume that it is a subset of the natural numbers.

One can show that a subset of the natural numbers is either bounded and finite, or unbounded and equipotent to the natural numbers themselves.

$\endgroup$
  • 2
    $\begingroup$ But why couldn't there exist a set whose power set is the same cardinality as the set of natural numbers? I just don't understand why the natural numbers must be the smallest infinity when there are infinitely many infinities. $\endgroup$ – user85798 Oct 30 '13 at 10:24
  • 2
    $\begingroup$ @Oliver: Because if there is an injection from $A$ into $\Bbb N$ then take its range, which is equipotent with $A$. Now we can show that a subset of $\Bbb N$ is either finite or equipotent with $\Bbb N$ itself. If it is finite then its power set is finite; if it is countably infinite then its power set is uncountable. Therefore $\Bbb N$ is not equipotent with any power set, not has an infinite cardinal strictly smaller than itself. $\endgroup$ – Asaf Karagila Oct 30 '13 at 11:20
  • 1
    $\begingroup$ @Oliver Note that Asaf's answer doesn't have anything to do with the existence of infinitely many infinite cardinals, and indeed the question and answer can both be formulated in a fragment of set theory consistent with "every set is countable" because the power set axiom is irrelevant. $\endgroup$ – Trevor Wilson Oct 30 '13 at 16:18
  • 1
    $\begingroup$ How can one "show that a subset of the natural numbers is either bounded and finite, or unbounded and equipotent to the natural numbers themselves"? This answer simply assert the answer to the question without explaining it at all. $\endgroup$ – tparker Sep 20 '17 at 15:11
  • $\begingroup$ @tparker: Recursion. $\endgroup$ – Asaf Karagila Sep 20 '17 at 15:14
4
$\begingroup$

Every set $X$ that has cardinality at most that of $\mathbb{N}$, i.e. such that $X$ injects into $\mathbb{N}$, is either finite or has the same cardinality as $\mathbb{N}$ by the argument in Asaf's answer.

Moreover assuming the Axiom of Choice or even just a weak fragment thereof, every set $X$ that does not have cardinality at least that of $\mathbb{N}$, i.e. such that $\mathbb{N}$ does not inject into $X$, is finite by the argument in user103567's answer.

However, perhaps it is worth pointing out that it is consistent with $\mathsf{ZF}$ set theory, which is like the usual theory $\mathsf{ZFC}$ but without the Axiom of Choice, that there are infinite sets $X$ whose cardinality is incomparable with that of $\mathbb{N}$; i.e. neither $X$ nor $\mathbb{N}$ injects into the other.

Such pathological sets would be infinite and Dedekind finite: see here for the definitions.

$\endgroup$
3
$\begingroup$

Let $A$ be a infinite set.

Choose a element $a_1\in A$, then $A-a_1$ is still infinite.

....

Choose a element $a_n\in A$, then $A-a_1-a_2-\dots-a_n$ is still infinite.

Since $A$ is infinite, we can do this infinite times(countable), then we get a subset of $A$,i.e.,$\{a_1,\dots,a_n,\dots\}$, which shows that we have constructed a one to one mappi

$\endgroup$
  • 1
    $\begingroup$ This could be a good answer if you finished the last sentence. Note that this argument uses (some amount of) the Axiom of Choice whereas Asaf's answer doesn't. On the other hand, it has the advantage of applying to sets that are not known to inject into $\mathbb{N}$, which Asaf's answer doesn't. $\endgroup$ – Trevor Wilson Oct 30 '13 at 16:01
  • $\begingroup$ "Choose" is the fatal word in this argument. $\endgroup$ – Matemáticos Chibchas Jun 29 '17 at 17:24
  • $\begingroup$ No, choosing an element from a set doesn't require Axiom of Choice, or it is implied by ZFC axioms(without Axiom of Choice). See math.stackexchange.com/questions/132717/… for details. $\endgroup$ – user103567 Jul 13 '17 at 16:41

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.