2
$\begingroup$

There is a small induction argument in the proof of the following Lemma:

enter image description here

Essentially, we want to show that you never run out of elements to choose.

My proof goes like this:

For the base case it is sufficient to note that $X \setminus \{f(0)\} = \emptyset$ implies $X=\{f(x)\}$. But then X would be finite, which is a contradiction.

The induction step essentially comes down to the same thing, i.e. assume that $Y = X \setminus \{f(0),...,f(n)\} \neq \emptyset$. Now if $X \setminus \{f(0),...,f(n),f(n+1)\} = \emptyset$, then $Y = X \setminus \{f(0),...,f(n)\} = \{f(n+1)\}$. But then $X = Y \cup \{f(n+1)\} = \{f(0),...,f(n),f(n+1)\}$, i.e. X would be finite (contradictions).

What makes me a bit uneasy is that I'm not really using the induction hypothesis.

Is my proof fine like this?

Thank you.

Edit: Adding the definition of finite as requested:

enter image description here

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ What is the precise definition of finite / infinite that you are using? $\endgroup$ Commented Oct 10, 2022 at 20:43
  • $\begingroup$ @MarkKamsma Good point, I have added this now. $\endgroup$ Commented Oct 11, 2022 at 7:48

1 Answer 1

2
$\begingroup$

As indicated in the comments, it would be helpful to know the precise definitions of "finite" and "infinite" used in the source material, and what other results have been established at this point, but a natural inductive argument here would show that the set $\{f(0),\ldots,f(n)\}$ is a finite set, in fact a finite subset of $X$, for all $n\in\mathbb{N}$, from which it follows that $X-\{f(0),\ldots,f(n)\}\ne\emptyset$ for all $n\in\mathbb{N}$.

Indeed, clearly $\{f(0)\}=\{x\}$ is a finite subset of $X$, and if $\{f(0),\ldots,f(n)\}$ is a finite subset of $X$, then so is $\{f(0),\ldots,f(n+1)\}$, since by construction $f(n+1)$ is in $X$ and adding a single element to a finite subset preserves finiteness.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer. I think I glossed over the details why $\{f(0),...,f(n)\}$ is finite for all $n \in \mathbb{N}$. But this is in fact the core of the induction argument. At this point the author has already shown that the union of two finite sets is finite. Hence, the induction step is very easy, but we are explicitly using the induction hypothesis that $\{f(0),...,f(n)\}$ is finite to show that $\{f(0),...,f(n),f(n+1)\}$ is finite. $\endgroup$ Commented Oct 11, 2022 at 7:52
  • 1
    $\begingroup$ @DerivativesGuy It looks like you fully understand what is going on, but just to fully close out the question: even though $\{f(0), \ldots, f(n)\}$ is 'obviously' finite, if you are being really precise this requires an inductive argument. The reason is that to show it is finite you need to construct a bijection with some natural number, but all that we 'obviously' have is a surjection from $n+1$ to $\{f(0), \ldots, f(n)\}$. However, if there are duplicate elements among $f(0), \ldots, f(n)$ then this surjection would not be injective and hence not a bijection. $\endgroup$ Commented Oct 11, 2022 at 10:03
  • $\begingroup$ @MarkKamsma Yes, thanks for pointing out. There is a proof in the lecture notes that shows that the union of two finite sets is finite. So, the induction step follows from the induction hypothesis and that theorem. The proof of that theorem also takes care of the problem you've mentioned, i.e. that there could be elements in both finite sets. $\endgroup$ Commented Oct 11, 2022 at 16:17

You must log in to answer this question.

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