3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Actually I was trying to use the definition given in wikipedia: "In mathematics, a set A is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset B of A is equinumerous to A." $\endgroup$ – Paramar May 8 '13 at 18:11
  • $\begingroup$ Paramar, equinumerous means that there is a bijection, in particular it means an injection. $\endgroup$ – Asaf Karagila May 8 '13 at 18:15
  • $\begingroup$ I know.I understood the proof you gave here, that is why I accepted it, thank you $\endgroup$ – Paramar May 8 '13 at 18:30
  • $\begingroup$ You're welcome. $\endgroup$ – Asaf Karagila May 8 '13 at 18:31
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\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.