1
$\begingroup$

Consider the set:

$$I_n = \{p\in \mathbb{N}; 1<p\le n\}$$

My book says that a set is finite when it's not empty or when there exists, for some $n\in \mathbb{N}$, a bijection: $$\phi: I_n\to X$$

Then, it defines an infinite set as a set that is not finite. This can be understood as:

a set $X$ is infinite when it's not empty and for all $n\in \mathbb{N}$, there isn't any bijection $\phi: I_n \to X$

Later, my teacher gave a list of exercises, in which one of them is:

Prove that a set $X$ is infinite iff it's no empty neither has a bijection $f: I_n \to X$ no matter which $n\in \mathbb{N}$

Well, I know that:

$\to$ if there isn't a surjective function $f: I_n \to X$, then there isn't also a bijective function $f: I_n\to X$, because bijectivity is surjectivity with injectivity, and by the definition, this set is not finite, that is, infinite.

$\leftarrow$ well, since $X$ is infinite, then it's not finite, which means that there isn't any bijective function from $I_n$ to $X$, so I know that this function must be either only injective, only surjective, or none of them. I must prove now that surjectivity must always fail, but I can't see anymore assumptions to use here. Intuitively I know that there can't possibly exist a surjective function from $I_n$ to an infinite set because all members of $I_n$ must be mapped to a unique element in $X$, but there are infinite elements in $X$. Could someone help me?

$\endgroup$
0
$\begingroup$

Using the definition of your book, proving your teacher exercice is a simple tautology.

$\leftarrow$ Since there isn't a bijection $f: I_n \rightarrow X$ then $X$ is not finite, i.e. $X$ is infinite.

$\rightarrow$ Since $X$ is infinite, then it's not finite, which means that there isn't any bijective function from $I_n$ to $X$.

Your proof would end here.

But what you DO want to prove is that there is no surjective $f: I_n \rightarrow X$.

First things first: We can define a injective $f': I_n \rightarrow X$ for every $n \in \mathbb{N}$. Using induction:

  • For $n=2$ the set $I_n$ has one single element, so $f'$ must be injective (in order to be a function). Since $X$ is non-empty, the function $f'$ exists (and isn't surjective);
  • Now assume your function $f'$ is injective for some $n$. Since $X$ is infinite, $f'$ isn't surjective, so there is a $x \in X$ such that doesn't exists $m \in I_n$ such that $f'(m)=x$. Define $f'': I_{n+1} \rightarrow X$ as $f''(i)=f'(i)$ for all $i \in I_n$ and $f''(n+1) = x$.

So now supose you have a surjective $f$ for some $n$. Then we can define a injective function $g: X \rightarrow I_n$ associating for every $x \in X$ one of the elements of the pre-image $f^{-1}(x)$. By the Schröder–Bernstein theorem this would mean there is a bijection $h: I_n \rightarrow X$ (since we have proven that exists a injective $f': I_n \rightarrow X$ for every $n \in \mathbb{N}$). And so we conclude such a surjective function $f$ cannot exist.


PS: I'm asking myself why the book did not include the number $1$ on the definition of $I_n$.

$\endgroup$

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.