3
$\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$
5
  • 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
    Commented Oct 29, 2015 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
    Commented Oct 29, 2015 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
    Commented Oct 29, 2015 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
    Commented Oct 29, 2015 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
    Commented Oct 29, 2015 at 20:04

3 Answers 3

Reset to default
3
$\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$
3
  • $\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
    Commented Oct 29, 2015 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
    Commented Oct 29, 2015 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
    Commented Oct 29, 2015 at 20:15
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$
4
  • $\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
    Commented Oct 29, 2015 at 19:53
  • $\begingroup$ @AlekosRobotis how to proof that at infinity one single natural number also finite? $\endgroup$
    – user1068412
    Commented Jun 28, 2022 at 19:15
  • $\begingroup$ Proof by contradiction(?) and induction(?) $\endgroup$
    – The Empty String Photographer
    Commented Jun 4, 2023 at 8:51
  • $\begingroup$ what's happen if N = {0}? $\endgroup$
    – Gianni
    Commented Nov 10, 2023 at 21:34
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .