## ACA0, Russell's Paradox, ZF, Arithmetic

From: "andrew cooke" <andrew@...>

Date: Tue, 14 Feb 2006 10:33:40 -0300 (CLST)

I have joined the FOM mailing list -
http://www.cs.nyu.edu/mailman/listinfo/fom/

Someone there mentioned ACA0, RCA0.  ACA0 is, I think, the Axiom of
Comprehension - http://planetmath.org/encyclopedia/ComprehensionAxiom.html
- that every formula defines a set.

That article appears to imply that ZF is open to Russell's paradox.  That
is not correct.  However, my initial argument for it not being correct
(from the Regularity Axiom) is wrong.  There's a good comment here -
http://en.wikipedia.org/wiki/Axiom_of_regularity - which I'll quote:

Russell's paradox is the paradox whereby consideration of "the set of
all sets that do not contain themselves as members" leads to a
contradiction in naive set theory. Since the axiom of regularity implies
that no set contains itself as a member, it can be tempting for the
non-expert to think that the presence of the axiom of regularity in
Zermelo-Fraenkel set theory (ZF) has something to do with the way in
which ZF resolves Russell's paradox. (For example, this misconception is
perpetuated in David Foster Wallace's Everything and More.) In fact, the
contradiction of Russell's paradox is avoided because the separation
axioms in ZF are of limited power (as compared with naive set theory).
Indeed, a contradiction can only be eliminated from a theory by
weakening or removing axioms; adding the axiom of regularity (or any
other axiom) to a theory only makes it more likely that a contradiction
will be encountered. The axiom of regularity is irrelevant to the
resolution of Russell's paradox.

And if you look at the Separation Axiom then the "architect approach" is
pretty clear - "If X is a set and P is a condition on sets, there exists a
set Y whose members are precisely the members of X satisfying P".  That is
weaker than the Axiom of Comprehension given above.

Vaguely related to the above, some articles on arithmetic:

Second order arithmetic -
http://en.wikipedia.org/wiki/Second-order_arithmetic

Peano arithmetic - http://en.wikipedia.org/wiki/Peano_arithmetic

An article on Frege that is beginning to make more sense, now that I
understand more of the notation and history -
http://plato.stanford.edu/entries/frege-logic/

Andrew