Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  BFD Oct 30 '13 at 8:03
    
@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. –  Trevor Wilson Oct 30 '13 at 16:23

3 Answers 3

up vote 12 down vote accepted

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.

share|improve this answer
    
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. –  LTS Oct 30 '13 at 10:24
2  
@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. –  Asaf Karagila Oct 30 '13 at 11:20
1  
@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. –  Trevor Wilson Oct 30 '13 at 16:18

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.

share|improve this answer

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

share|improve this answer
    
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. –  Trevor Wilson Oct 30 '13 at 16:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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