# dual Dedekind-infinity may not imply Dedekind-infinite without AC

It is written in wikipedia: https://en.wikipedia.org/wiki/Dedekind-infinite_set

It is not provable (in ZF without the AC) that dual Dedekind-infinity implies that A is Dedekind-infinite. (For example, if B is an infinite but Dedekind-finite set, and A is the set of finite one-to-one sequences from B, then "drop the last element" is a surjective but not injective function from A to A, yet A is Dedekind finite.)

A is set of all finite subsets of B. Hence it has to be infinite and of same cardinality as of A. But 'drop the last elemenet' but which element.(For this we need choosing map from [0,n] to elements of A but then it requires AC but then these two definitions become equivalent.)

And why A is Dedekind finite.

• $A$ is a set of finite sequences, not of finite subsets, so it makes sense to talk of the last element of any member of $A$: If $s\in A$, then $s=(s_0,\dots,s_n)$ for some $s_i\in B$, and "dropping the last element of $s$" results in the sequence $t_s=(s_0,\dots,s_{n-1})$. (If $n=0$ or if $s=\emptyset$, simply set $t_s=\emptyset$.) – Andrés E. Caicedo Jun 25 '15 at 5:05
• @AndresCaicedo But why A will be Dedekind finite – Sushil Jun 25 '15 at 5:09
• Also, $A$ does not have the same cardinality as $B$: The set of tuples of length $1$ is in bijection with $B$ and is a proper subset of $A$. (One needs some amount of choice to verify that if $B$ is infinite, then $A$ and $B$ are equipotent. But $B$ cannot be Dedekind finite in this case.) – Andrés E. Caicedo Jun 25 '15 at 5:09
• Yes, you need to check that $A$ is Dedekind finite. Prove the contrapositive: Check first that a set $S$ is Dedekind infinite iff there is an injection $f:\mathbb N\to S$. Use that $A$ consists of injective tuples to conclude that if we have such an $f:\mathbb N\to A$, then there is an injection $g:\mathbb N\to B$. – Andrés E. Caicedo Jun 25 '15 at 5:12
• @AndresCaicedo I have taken A to be set of injective tuples and trying to prove A Dedekind finite. But I am having problem in proving it without some choice. And thanks for pointing out and cardinality of A and B will not be same here since we are not assuming any choice – Sushil Jun 25 '15 at 5:37

You have two mistakes, as pointed by Andres in the comments.

1. The claim that for an infinite set $$A$$, the set $$B=\{X\subseteq A\mid X\text{ finite}\}$$ has the same cardinality as $$A$$ requires the axiom of choice. For a Dedekind-finite set this is most certainly false in any case (there's an injection from $$A$$ into $$B$$, and this injection is not a surjection. So if $$|A|=|B|$$, it is impossible that $$B$$ is Dedekind-finite, so $$A$$ is not either.)

2. Sets have no linear ordering in most cases. So there's no real meaning to "last element". You can talk about the set of finite sequences, but those are always Dedekind-infinite, since $$\{\langle a\rangle,\langle a,a\rangle,\langle a,a,a\rangle,\ldots\}$$ is a countably infinite subset.

However, we can show that the set of injective finite sequences is in fact Dedekind-finite, when $$A$$ is Dedekind-finite.

Now we return to your question, if $$A$$ is Dedekind-finite, and $$S$$ is the set of injective finite sequences of $$A$$, then $$B$$ is Dedekind-finite, and the operation "remove the last element" is well-defined, because the elements of $$B$$ are sequences, and no choice of ordering is needed.

• I have absolutely no idea what your comment is saying. – Asaf Karagila Jun 25 '15 at 7:27
• I'm sorry, I still have no idea what you are saying in the comment. If the answer is not visible, how can you comment on it? If there is a problem with showing parts of the answer, it's a problem on your device, it's neither a problem with my answer nor with the website. – Asaf Karagila Jun 25 '15 at 7:35
• Yes I got it when Andrews pointed it out. I'll fix it in the question. Actually I am having problem in proving: set of injective finite sequences is Dedekind-finite, when A is Dedekind-finite. – Sushil Jun 25 '15 at 7:40
• For the sequence $a_n$, write $A_n$ as the range of the sequence. Then show that $\bigcup A_n$ is an infinite subset of $A$, and conclude that it is a countable set as the union of enumerated sets. – Asaf Karagila Jun 25 '15 at 7:43
• Again, this fact when proved in ZFC only uses the axiom of choice to choose enumerations. Here we have the enumerations so no choice is needed. – Asaf Karagila Jun 26 '15 at 3:28