Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following is an exercise in Just/Weese:

Show in ZF that the following are equivalent for every set $A$:

(a) There is no injection $f: \omega \to A$

(b) Every injection $f: A \to A$ is a surjection

Can you tell me if my proof is correct? Thank you!


(b) $\rightarrow $ (a): Assume $\lnot$ (a) and let $f: \omega \hookrightarrow A$ be an injection. Then $A$ is infinite hence (by corollary 13 on page 49) there exists a map $g: A \to A$ that is injective but not surjective.

(a) $\rightarrow $ (b): Assume $\lnot$ (b) and let $f: A \to A$ be injective but not surjective. Let $a_0 \in f(A)^c$. Then the following map is an injection: define $g: \omega \to A$ as $g(\varnothing) = a_0$ and $g(n) = f(g(n-1))$.

To see that $g$ is injective assume $g(n) = g(m)$ for $n > m$. Then $g(n-1) = g(m-1)$ and so on, until $g(n-m) = g(\varnothing) = a_0$. But the empty set is the only element mapping to $a_0$ hence $n-m = \varnothing$ and hence $n = m$.

Edit

enter image description here

share|improve this question
1  
What is "corollary 13 on page 49"? –  William Dec 3 '12 at 13:21
add comment

1 Answer 1

This approach misses the point of Dedekind-finiteness being different than finiteness without choice. It is possible to have infinite Dedekind-finite sets.

The idea is that if there is an injection $f\colon\omega\to A$ then we can define the following function: $$g(a) = \begin{cases} f(n+1) & \exists n\in\omega. f(n)=a\\ a & \text{otherwise}\end{cases}$$ And it can be shown that $g$ is injective but certainly not surjective, $f(0)\notin\operatorname{rng}(g)$.


Besides the above point, which I think is amiss when a book aspires to talk about AC later on, the first proof seems fine; and the second part of the proof you gave is fine too.

Just to give it a final touch, you might want to prove that these two are equivalent to the additional characterization:

$A$ is Dedekind-finite if and only if whenever $B\subsetneqq A$, $|B|<|A|$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.