3
$\begingroup$

I have proven that if $X $ is a finite set and $Y$ is a proper set of $X$, then does not exist $f:X \rightarrow Y $ such that $f$ is a bijection.

I'm pretending to show that the naturals is an infinite set. Let $P=\{2,4,6...\} $. So, by contraposity i just have to show that $f: \mathbb{N} \rightarrow P$, given by $f(n)=2n$, is actually a bijection.

Logically speaking (my book), i have yet constructed only the natural numbers, its addition and multiplication.

By far, i have shown that $f$ is injective. But in order to prove that $f$ is a surjection, how can i do that without using the usual: "Take any $y\in P$. Given $x=\frac{y}{2}$ ..."? Because $x$ is actually a rational number given in a "strange form", which I yet didn't construct.

$\endgroup$
1
$\begingroup$

You are not using the definition of even number.

Definition 1 (Even number). We say that a natural number $n$ is an even number if $n=2k$ for some natural number $k$.

In order to prove that $f\colon P\to\mathbb N$ is a surjection, let $y\in P$. Now we need to find some $x\in\mathbb N$ such that $f(x)=2x=y$. But such $x$ exists by Definition 1 as desired.

Definition 2 (Surjective functions). A function $f$ is surjective if every element in $Y$ comes from applying $f$ to some element in $X$: $$\text{For every }y\in Y\text{, there exists }x\in X\text{ such that }f(x)=y.$$

$\endgroup$
1
$\begingroup$

The function $f$ you gave is surjective onto its image, and this image is a proper subset (can $2n=1$ be realized by some $n \in\mathbb{N}$?).

By the fact that there is a bijection $f: \mathbb{N} \to 2\mathbb{N}$, and $2\mathbb{N}$ is a proper subset of $\mathbb{N}$, it follows that $\mathbb{N}$ cannot be finite.

Showing there is a bijection $f: \mathbb{N} \to \mathbb{N}$ doesn't do much, because such a bijection does not contradict the theorem you've mentioned.

$\endgroup$
  • $\begingroup$ Yes, i've edited my post. But how can i actually show that $f$ from the naturals to the even naturals is a bijection? $\endgroup$ – math.h Jan 9 '17 at 0:18
  • 1
    $\begingroup$ If $m$ is even, then $m=2n= f(n)$. This shows surjectivity, and you've already shown injectivity. $\endgroup$ – Hayden Jan 9 '17 at 0:35
  • $\begingroup$ Thank you. Now it is really clear for me. $\endgroup$ – math.h Jan 9 '17 at 0:37

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.