🚀 go-pugleaf

In article <Bx2ALr.3Az@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>...This may be considered disturbing in view of
>Menzel's remark that Aczel's selfmembering set theory is equiconsistent with
>ZF. But I hardly think this is a bother. I have read some and listened some to
>Aczel's theory, and it is great fun, and nice math, but it has always struck
>me as being an essentially graph-theoretic excercise, and having little to
>do with what sets "really are", in a Cantorian sense. I may be treading on
>some toes, but IMHO these selfmembered "sets" have little to do with our
>concerns here.

Ooh, ouch, you got toe number 3.  :-)

There is a foundational advantage to eschewing Aczel's cyclic-graph
view of membership (AFA or AntiFoundation Axiom) in favor of the
standard (but rarely if ever appealed to in ordinary maths) Foundation
Axiom that membership is not only an acyclic but well-founded
relation.  The advantage is that the nonexistence of a set of all sets
has a trivial proof: such an object would entail a cycle in the
membership relation, forbidden by FA.

That Russell felt obliged to give a more broadly applicable argument
suggests that FA was not held to be an evident property of sets by
mathematicians in 1905.  That it is self-evident to you now seems more
an accident of culture---your training---than of something inherent in
the notion of set.

While I'm on this topic, let me express a preference for stating the
Cantor-Russell "paradox" in its positive form: every set X has a
nonmember set, i.e. a set Y that is not a member of X.  The more usual
negative "paradoxical" form, that there is no set of all sets, follows
immediately.  Here are two proofs of the positive form, respectively
with and without FA.

1. With FA the obvious witness Y is X itself.  For if X were a set
belonging to X we would have a cycle in the membership relation.

2. Without FA, Russell subpoenas the more elusive set Y of all members
of X not members of themselves.  To see more visually than with the
usual symbol-pushing that this Y is not a member of X, picture the
restriction to X of the membership relation as a square 0-1-valued
matrix E: for any two elements x,y in X, E[x,y] = 1 just when x is a
member of y.  Every member Z of X appears exactly once as a column of
this matrix, with a 1 in just those rows W for which W is a member of
Z.  The set Y is the complement of the diagonal straightened to
vertical.  For every column Z of E, the column Y differs from Z in row
Z.  Hence Y is not a member of X, making it the desired witness.

Now what is the relationship between arguments 1 and 2?  Well, if we
announce FA *after* carrying out this construction (like producing your
discount coupon after being served) we notice that the diagonal of E is
all 0's, whence its complement is all 1's.  This means that argument 2
under FA produces X.  Hence argument 1 does not produce a different set
from argument 2, just the set that it must produce in the presence of
FA.  That is, argument 1 is what 2 simplifies to in the presence of
FA.

While this point of view may not immediately convert the reader from FA
to Aczel's AFA, it does encourage the sort of perspective from which
AFA can start to be seen as a very reasonable point of view.

For my own part I cannot imagine how I ever used to believe that FA was
an inherent property of sets.  I was simply bullied into it.

>                    Kleeneness is next to Godelness.

Dynamite .sig!
-- 
                                       |
Vaughan Pratt                          |                          ttarP nahguaV
Why do mirrors reverse words&not lettersrettel ton&sdrow esrever srorrim od yhW