0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Thomas Andrews Oct 29 '15 at 19:41
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Oct 29 '15 at 19:42
  • $\begingroup$ @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? $\endgroup$ – user2694307 Oct 29 '15 at 19:48
  • 1
    $\begingroup$ 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}$". $\endgroup$ – BrianO Oct 29 '15 at 19:55
  • $\begingroup$ 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. $\endgroup$ – fleablood Oct 29 '15 at 20:04
0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ That explains the proof that has been given by authors. That said, is my reasoning correct according to their finite set definition? $\endgroup$ – user2694307 Oct 29 '15 at 20:00
  • 1
    $\begingroup$ @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.) $\endgroup$ – Noah Schweber Oct 29 '15 at 20:13
  • $\begingroup$ 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}$! $\endgroup$ – Noah Schweber Oct 29 '15 at 20:15

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.