# proof: The set N of natural numbers is an infinite set

DEFINITION 1: A set $$S$$ is finite with cardinality $$n \in\mathbb N$$ if there is a bijection from the set $$\left\{0, 1, ..., n-1 \right\}$$ to $$S$$. A set is infinite if its not finite.

THEOREM 1: The set $$\mathbb N$$ of natural numbers is an infinite set.

Proof: Consider the injection $$f :\mathbb N \rightarrow \mathbb N$$ defined as $$f(x) = 3x$$. The range of $$f$$ is a subset of the domain of $$f$$.

I understand that $$f(x) = 3x$$ is not surjective and thus not bijective since for example the range does not contain number $$2$$. But what would happen if we were to define $$f: \mathbb N\rightarrow \mathbb N$$ as $$f(x) = x$$? It is a bijective function. Doesn't that make the set of natural numbers finite according to the definition? What am I missing can somebody please tell me?

• That proof is seemingly using another result - a set $S$ is infinite if and only if there is a in injective function $f:S\to S$ which is not onto. Did it really come immediately after that definition? – Thomas Andrews Oct 29 '15 at 19:41
• No, $f(x)=x$ is a bijection between $\mathbb N$ and $\mathbb N$, but not a bijection between $\mathbb N$ and a set of the form $\{0,1,2,\dots,n-1\}$ for some $n$. – Thomas Andrews Oct 29 '15 at 19:42
• @ThomasAndrews Yes it is from the Kenneth H. Rosen's book, 2.5 Cardinality of Sets. The definition in your comment makes it clear but how is f(x) = x is not bijective? – user2694307 Oct 29 '15 at 19:48
• The "proof" doesn't prove the theorem, given the definitions. It proves something very different (that $\mathbb{N}$ is Dedekind infinite). It takes some doing to get from that to "there is no bijection from any $\{0, \dots, n\}$ to $\mathbb{N}$, for any $n \in \mathbb{N}$". – BrianO Oct 29 '15 at 19:55
• f:N->N f(n) = n. is injective. It proves that N is finite if and only N is finite. As N does not = {0, 1,.....n -1} it isn't a proof that N is finite. For it to prove N is finite you must first assume N = {0, 1, .... n-1} for some n. i.e. you must first assume N is finite. So it's inconclusive. – fleablood Oct 29 '15 at 20:04

No. The definition of finite is $$f:\{0,1,...,n-1\}\to S$$ is bijective.

We know $$f:\mathbb N\to\mathbb N$$ via $$f(n) = n$$ is bijective, but this maps $$\mathbb N$$ onto $$\mathbb N$$. It does not map $$\{0,1,...,n-1\}$$ onto $$\mathbb N$$.

Basically, this prove $$\mathbb N$$ is finite if $$\mathbb N$$ is finite.

Here is an alternative proof. Suppose $\mathbb{N}$ were a finite set. $\mathbb{N}$ is a discrete set, so there must exist some greatest element in $\mathbb{N}$: call it $k\in\mathbb{N}$. Consider the element $k+1$. Is $k+1\in \mathbb{N}$? Yes. Is it greater than $k$? Yes. $\mathbb{N}$ has no greatest element, and is thus an infinite set.

• Yes I learned that kind of proof from propositional logic, but I wanted to work with this definition and wondered went wrong. – user2694307 Oct 29 '15 at 19:53

If there is some injection from $X$ into $X$ which is not a bijection, then $X$ is infinite; this is a good exercise. (Note that the converse is not necessarily true if the axiom of choice is not assumed.) But the emphasis is on "some" - as long as one non-surjective injection exists, $X$ must be infinite.

• That explains the proof that has been given by authors. That said, is my reasoning correct according to their finite set definition? – user2694307 Oct 29 '15 at 20:00
• @user2694307 No - read my last sentence. Knowing that there is some surjective self-injection tells you nothing - you only know the set is finite if every self-injection is surjective! (Even then, you don't know the set is finite without using the axiom of choice - all you know is that it is Dedekind finite, which is weaker.) – Noah Schweber Oct 29 '15 at 20:13
• Also, the identity map $id_\mathbb{N}$ has range $\mathbb{N}$, not $\{0, . . . , n\}$ for some $n\in\mathbb{N}$. $\mathbb{N}\not\in\mathbb{N}$! – Noah Schweber Oct 29 '15 at 20:15