Re: Another Inconvenient Truth

On Aug 14, 12:37 pm, MoeBlee <jazzm...@xxxxxxxxxxx> wrote:
Where did you read this argument? I'd like to look over the actual
wording of it from your source.

MoeBlee

OK, so obviously the proof is flawed. Virgil already pointed this
out -- actually, I was trying to reconcile yet another so-called
"crank's" logic (Russell Easterly) as rigorous, and Virgil
realized that what I was doing was wrong.

The mistake I made was that I confused the above proof with a
very similar one. Let us consider the concepts of infinite and
Dedekind infinite once more. We already know that these concepts
are equivalent in ZFC. But in the biconditional

forall x(x infinite iff x Dedekind infinite)

one direction can be proved without the Axiom of Choice, which is
needed only for the other direction. What I was trying to do
was prove the direction which does not require Choice.

Searching on the Internet for reliable sources (which included a
Google Books search on set theory texts), what I actually see
is a proof in ZF of:

forall x(x finite implies x Dedekind finite)

This is in fact the Pigeonhole Principle for finite sets. (Many
"cranks" would like to extend the Pigeonhole Principle to
infinite sets as well.) It is usually proved by induction on
the cardinality of the finite set x, and it definitely does
not require the Axiom of Choice.

Now we expect the logical contrapositive of the above:

forall x(x Dedekind infinite implies x infinite)

to be a theorem of ZF as well. It is provable, but what I wrote
is not the correct proof. And so I couldn't find a proof of
the above theorem without appealing to the contrapositive.

So what did I post, and where did it come from? It turns out
that what I was posting was actually a different proof I found
at the site metamath.org (a site to which I've seen you make
references before). The actual proof was that the existence
of a set that was a proper subset of its own union is
equivalent in ZF-Infinity to the Axiom of Infinity. The
symbolic metamath proof is given as well as a plain English
proof written by an earlier member of this newsgroup:


(As posted to sci.logic on 30-Oct-96, with annotations added.)

Theorem: The statement "There exists a non-empty set that is a subset
of its union" implies the Axiom of Infinity.

Proof: Let X be a nonempty set which is a subset of its union; the
latter
property is equivalent to saying that for any y in X, there exists a z
in X
such that y is in z.

Define by finite recursion a function F:omega-->(power X) such that
F_0 = 0 (See inf3lemb 4380.)
F_n+1 = {y<X | y^X subset F_n} (See inf3lemc 4381.)
Note: ^ means intersect, < means \in ("element of").
(Finite recursion as typically done requires the existence of omega;
to avoid this we can just use transfinite recursion restricted to
omega.
F is a class-term that is not necessarily a set at this point.)

Lemma 1. F_n subset F_n+1. (See inf3lem1 4383.)
Proof: By induction: F_0 subset F_1. If y < F_n+1, then y^X subset
F_n,
so if F_n subset F_n+1, then y^X subset F_n+1, so y < F_n+2.

Lemma 2. F_n =/= X. (See inf3lem2 4384.)
Proof: By induction: F_0 =/= X because X is not empty. Assume F_n =/
= X.
Then there is a y in X that is not in F_n. By definition of X, there
is a
z in X that contains y. Suppose F_n+1 = X. Then z is in F_n+1, and
z^X
contains y, so z^X is not a subset of F_n, contrary to the definition
of
F_n+1.

Lemma 3. F_n =/= F_n+1. (See inf3lem3 4385.)
Proof: Using the identity y^X subset F_n <-> y^(X-F_n) = 0, we have
F_n+1 = {y<X | y^(X-F_n) = 0}. Let q = {y<X-F_n | y^(X-F_n) = 0}.
Then q subset F_n+1. Since X-F_n is not empty by Lemma 2 and q is the
set of \in-minimal elements of X-F_n, by Foundation q is not empty, so
q
and therefore F_n+1 have an element not in F_n.

Lemma 4. F_n proper_subset F_n+1. (See inf3lem4 4386.)
Proof: Lemmas 1 and 3.

Lemma 5. F_m proper_subset F_n, m < n. (See inf3lem5 4387.)
Proof: Fix m and use induction on n > m. Basis: F_m proper_subset F_m
+1
by Lemma 4. Induction: Assume F_m proper_subset F_n. Then since F_n
proper_subset F_n+1, F_m proper_subset F_n+1 by transitivity of proper
subset.

By Lemma 5, F_m =/= F_n for m =/= n, so F is 1-1. (See inf3lem6
4388.)
Thus the inverse of F is a function with range omega and domain a
subset
of power X, so omega exists by Replacement. (See inf3lem7 4389.)
Q.E.D.


When one clicks on the theorem, one sees the list of axioms used in
the proof, and Choice is not among them.

So I confused the above proof with what I was trying to prove. Still,
it appears that the only way to prove that some hypothesis is
equivalent to the Axiom of Infinity in ZF-Infinity is to show that
the hypothesis implies the existence of some set which can be
enumerated by the natural numbers and then using the Axiom Schema
of Replacement. You mentioned in another thread about trying to
prove Infinity equivalents in Z-Infinity (i.e., without using the
Replacement schema), but as you point out, it's probably impossible.

.

Loading