Dedekind Finite set contains Dedekind Finite subsets

Question

I would be grateful for some help in proving: If a set is Dedekind Finite then every subset of it must be Dedekind finite too. I tried a reductio ad absurdum way of thinking but I can't seem to find anything absurd. Thanks in advance

Answer 1

That slightly depends on how your define Dedekind-finite sets.

One definition is this: $A$ is Dedekind-finite if and only if $A$ does not have a countably infinite subset.

Now it's obvious.

If you prefer to still use the original definition, that a set is Dedekind-finite if and only if every self injection is a bijection it is not much harder either.

Suppose $A$ is Dedekind-finite and $B$ is a subset of $A$. Let $f\colon B\to B$ be a self-injection, we extend it to $F\colon A\to A$ by declaring: $$F(a)=\begin{cases}f(a)& a\in B\\a& a\notin B\end{cases}.$$

Since $f$ is an injection we have to have that $F$ is an injection as well. By Dedekind-finiteness, $F$ is surjective, but clearly if $a\notin B$ then $F(a)\notin B$ either, therefore $f$ must be surjective as well. Thus $B$ is Dedekind-finite as well.

One can also argue by a similar argument towards a contradiction by making the same extension of $f$, only taking $f$ to be from $B$ into a proper subset of $B$, then concluding that the extension is an injection from $A$ into a proper subset of $A$.

Answer 2

The easiest way is to note that a set $X$ is Dedekind finite iff there is no injection $\omega \to X$.

Answer 3

Another approach using the definition of Dedekind-infinite and proof by contrapositive:

Let $X\subset Y$.

Let $X$ be infinite. We will show that $Y$ must also be infinite.

By Dedekind-infinity, we have $X'\subsetneqq X$ and bijection $f:X\rightarrow X'$.

Construct $Y'=\{a\in Y :a\in X' \vee a\notin X)$

Show $Y'\subsetneqq Y$

Similar to Asaf, construct function $g:Y\rightarrow Y'$ such that

$g(a)=\begin{cases}f(a)& a\in X \\a& a\notin X\end{cases}$

Show that $g$ is a bijection and hence $Y$ is infinite. (Requires an examination of several cases and sub-cases.)

Thus, if $X$ is infinite then $Y$ is infinite.

From the contrapositive, if $Y$ is finite then $X$ is finite.