Note admins: THIS IS NOT A DUPLICATE to other posts (see the last sentence).

Prove that if $A$ and $B$ are Dedekind finite then so is their union, without using the concept of natural numbers or Axiom of Choice.

Of course, the result is trivial with the natural numbers, but the book from which this question is derived said this can be proven without the aid of natural numbers and Axiom of Choice (I am using Moschovakis' Notes on Set Theory, 1st edition, chapter 4, x4.25)

We are allowed to use $ZF$ Axioms.

Suppose on the contrary thay there are Dedekind finite sets $A,B$ such that $A \cup B$ is Dedekind infinite. If either $f(A) \subset A$ or $f(B) \subset B$ then we can easily create a proper injection from one set to itself (just take restriction of $f$), so assume that that is not the case.

I am not sure what to do here. A hint would be more appreciated then a full answer.

I realize that there already are many questions and answers regarding how a union of two Dedekind finite sets are still Dedekind finite, but my question is different: the difficulty here is that (1) since I am not allowed to use natural numbers, we cannot talk about a set being finite or infinte, much less list some elements or sets, and (2) we cannot use Axiom of Choice.

  • $\begingroup$ Since being Dedekind finite is defined without a reference to the natural numbers, your last comment is irrelevant. $\endgroup$ – Asaf Karagila Jul 26 '18 at 6:49
  • 1
    $\begingroup$ If A $\cup$B is Dedekind infinite, there is an injective function f : N → A $\cup$ B, but he can't make use of that. So it could be relevant. $\endgroup$ – Steve B Jul 26 '18 at 7:00
  • $\begingroup$ @Steve: And that does not use the natural numbers, how? :) $\endgroup$ – Asaf Karagila Jul 26 '18 at 9:10
  • $\begingroup$ BlueRoss: Unless you are allowed to use the axiom of choice, which you explicitly said you can't, that is a false statement. $\endgroup$ – Asaf Karagila Jul 27 '18 at 8:38

Here's a hint. Suppose f is an injection from $A \cup B$ to a proper subset.

Define $D(x) = \bigcap \{S \subset A \cup B : x \in S, f(S) \subseteq S\}$.

Choose $c \in (A \cup B) \setminus f(A \cup B)$. Let $C = D(c)$.

Show that $x \prec y$ iff $D(y) \subsetneq D(x)$ is a well-ordering of C and attempt to construct injections on $A \cap C$ and $B \cap C$ taking members of each to the next member under the well-ordering. Show that at least one of these must exist. It is onto a proper subset and so one of A and B is Dedekind-infinite.

(You might get away without fully proving the well-ordering. Showing that if $X \subset C$ is non-empty then $\exists! x \in X, X \subseteq D(x)$ may be enough.)

ETA more details.

Let's call a set $S$ f-closed if $f(S) \subseteq S \subseteq A \cup B$

Note that for any such $S$, $x \in S$ implies $D(x) \subseteq S$.

In particular, $D(x)$, $f(D(x))$, $D(f(x))$, $D(f(x)) \cup \{ x \}$ and $f(D(x)) \cup \{ x \}$ are all f-closed, for any x, which can be used to show $D(f(x)) = f(D(x))$ and $D(x) = D(f(x)) \cup \{ x \} = f(D(x)) \cup \{ x \}$. And also, for any $y \in D(x)$, $D(y) \subseteq D(x)$.

Next we need to prove: If $S$ is f-closed, non-empty and $S \subseteq D(x)$ for some x, then there exists $y \in D(x)$ such that $S=D(y)$

Suppose this fails for a particular $S$. Let $T = \{y \in D(x) : S \subsetneq D(y) \}$. If $y \in T$ then $S \subseteq D(f(y))$ (as $y \notin S$) but we can't have $S = D(f(y))$ so we must have $S \subsetneq D(f(y))$ and so $f(y) \in T$. Thus $T$ is f-closed. But $x \in T$ and so $T = D(x)$, which implies S is empty - a contradiction.

A similar argument shows that if $D(x) \neq D(f(x))$ then for any $y$,$z \in D(x)$, $D(y) = D(z)$ iff $y = z$. In particular this applies in C.

So now if $X \subseteq C$ is non-empty, let $W = \bigcup \{D(x) : x \in X \}$. This f-closed so there is a unique $m \in C$ such that $W = D(m)$. Clearly $m \in X$. Define $min(X) = m$. (This can be used to construct the full well-ordering, but it is all we need to complete the proof.)

Now try to define a function on $A \cap C$ by $g(x) = min(D(f(x) \cap A)$. If this is possible $g$ is an injection from $A \cap C$ to a proper subset. If it is not possible then for some $y \in C$, $(D(y) \cap A = \emptyset$. Then $D(y) \subseteq B \cap C$ and f restricted to $D(y)$ is an injection onto a proper subset. At least one of $A \cap C$ and $B \cap C$ must be Dedekind-infinite.

| cite | improve this answer | |
  • $\begingroup$ Very good, very good! $\endgroup$ – Asaf Karagila Jul 27 '18 at 11:52
  • $\begingroup$ Could you give another hint, either about showing that the order on C is well, or about constructing the next-member injections? $\endgroup$ – Sophie MacDonald Aug 5 '18 at 1:12
  • $\begingroup$ @Kyle MacDonald I've added some more details now. Sorry it's taken so long, I've been rather busy. $\endgroup$ – David Hartley Aug 8 '18 at 23:33

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.