Extraordinary Sets

3 March 2010

Wednesday


Zermelo built upon the work of Georg Cantor, who was one of the great intellectual revolutionaries of all time.

Usually in this forum I write for an intelligent general audience assuming no particular background other than an interest in the world. Today I’m going to write about a topic in set theory and I will assume a certain familiarity with the concepts of set theory. If set theory isn’t your thing, I appreciate that and I hope you’ll come back tomorrow for something different. But from the hints I’ve dropped about my admiration for Georg Cantor (for example, recently in Salto Mortale) the careful reader (if I have any) will already have guessed my interest in this area.

A little-known concept in set theory is that of what are sometimes called extraordinary sets, which are sets that have infinite descending membership chains. In other words, an extraordinary set is a set with a element that is a set that has an element, and so forth, ad infinitum. In most familiar forms of set theory there are no extraordinary sets, as they are ruled out ab initio by an axiom of foundation. This is one way to prevent the possibility of the paradoxes of self-membership, but in my opinion this simply is a case of throwing out the baby with the bathwater. While we do eliminate one kind of paradoxical set in this way, we also eliminate a lot of potentially interesting sets that are neither paradoxical nor contradictory.

It has occurred to me that sets could be extraordinary in three ways:

(1) a set has an infinite descending membership chain,

(2) a set has an infinite ascending membership chain, and

(3) a set has both infinite ascending and descending membership chains.

Now, we know that (2) is a part of orthodox set theory, as this is nothing other than Zermelo’s infinite set. I find this interesting as this schematic approach puts Zermelian set theory, at least in so far as the strategy it employs to secure an infinite set, in the context of extraordinary sets. One familiar axiom of infinity, viz. “(F) \/x\/y(x in y & /\z(z in y => zU{z} in y)” is usually associated with VNB and results in an ordinal infinite set in so far as it iterates the set theoretical equivalent to ordered pairs. Zermelo’s axiom is simpler, yielding the empty set embedded in an infinitude of brackets.

Postulating only that there is at least one set with an infinite descending membership chain — (1) above — is sufficient to secure a beginning for the cumulative hierarchy. In What is Mathematical Logic? (by Crossley, et al.), Chap. 6, pp. 62-63, the only rationale given for the axiom of foundation is the elimination of infinite descending membership chains, and the only rationale given for this is the elimination of the possibility of self-membership. (Cf. also Foundations of Set Theory, by Fraenkel, et al., North Holland Pub, Chap. II, sec. 5. I highly recommend this latter book; it is well written and easy to understand.) Now whether self-membership must be construed as constituting an infinite descending membership chain I consider an open philosophical question, but I will grant the point for purposes of argument. In any case, this seems to me a minor matter that could be dealt with within the context of an axiom which would postulate at least one set with an infinite descending membership chain.

In what follows I will use “(Ex)” for the existential quantifier, “(Ax)” for the universal quantifier, “⊂” for the membership relation, and “≠” for non-identity (with a few other obvious symbols).

Suppose we have an axiom like:

1* (Ex)(Ay)(y x . (Ez)(z y) . x≠y≠z)

…which I take to mean that there is a set which contains elements which themselves all contain a set.

or, more simply,

2* (Ex)(Ay)(Ez)(y x → z y . x≠y≠z)

…meaning that every element has an element in at least one set.

By replacing E’s above with A’s we have a more radical formulation in which every set is infinitely embedded.

Putting the matter schematically puts Zermelian set theory in a different perspective, and I can take this shift in perspective further. From the trichotomy of infinite sets above we can move directly to a numerical model, specifically the number line, where (1) is associated with infinities in the small, and (2) is associated with infinities in the large. For example, for (1) we may pair left brackets with the series ¼, 3/8, 7/16 . . . , and right brackets with ¾, 5/8, 9/16 . . ., and for (2) we may pair left brackets with the negative integers and right brackets with the positive integers. (To make the correspondence more obvious we could do it all within one interval, with the same kind of convergent series, representing (2) instead by left brackets at ¼, 1/8, 1/16, . . . , and right brackets at ¾, 7/8, 15/16, . . .) In this way we can demonstrate a one-to-one correspondence between these two methods of infinitely embedded sets, and from this I conclude (1) is as good a way as the orthodox (2) for jump-starting infinite sets. But don’t ask me to prove this in an axiomatic setting, because the whole question here is what axioms we ought to use for set theory.

This creates an immediate intuitive connection between the ZF infinite set postulated by the axiom of infinity and the infinity of the natural numbers. In any case, this provides a way of going immediately to object-formalism without detouring through the linguistic formalism of a logical or axiomatic system — object-formalism being really just another form of appealing to arithmetical intuitions, but don’t tell that to dedicated metamathematicians. (Note: Object formalism is the formalization of the mathematical object itself rather than the formalization of the language in which the mathematical object is mentioned, which is the traditional method of applying logic to mathematical reasoning. The paradigmatic example of object formalism is Gödel’s arithmetization of syntax. Here, numbers go proxy for objects.)

I assume that a set with an infinite descending membership chain doesn’t need to be parlayed into an infinite set because it already is a set with an infinite number of elements, sort of like a mirror image of a set with an infinite ascending membership chain, which is the orthodox introduction of infinite sets into axiomatic set theory. The mirror image pairing I suggested above demonstrates a thoroughgoing parallelism between the infinite set in ZF and an infinite set with an infinite descending membership chain. Therefore, if ZF’s axiom of infinity guarantees an infinite set, then I hold that the negation of the axiom of foundation (in certain forms) can guarantee an infinite set where it allows a set with an infinite descending membership chain.

The notion of sets with infinite descending membership chains is not new. However, I don’t know that anyone has suggested the correspondence between Zermelo’s infinite set and sets with infinite descending membership chains. As I mentioned before, they have been called extraordinary sets (I think this in Introduction to Axiomatic Set Theory by Jean-Louis Krivine, but I can’t find my copy and am still looking for the reference), and more recently they have been called non-well-founded sets by Peter Aczel (in a book of the same title), sometimes also called hypersets by those who have developed Aczel’s theory (like Jon Barwise — Barwise and Etchemendy’s book The Liar applies hypersets to the liar paradox; they don’t bother to rule out loops). The “non-well-founded” refers to the axiom of foundation, which in Aczel’s theory is strongly negated by the anti-foundation axiom (AFA). Also, hypersets may contain cyclical membership chains, which would justify self-membership, and put it in the same category as infinite descending chains though distinguishing the two (which I consider an acceptable response to what I called an open philosophical question above).

With this sanction of recent tradition, professionals in set theory might find this an acceptable option for jump-starting the cumulative hierarchy. Although the literature on hypersets recognizes elements of type zero, i.e., individuals (what Zermelo called “urelemente” and banished from his set theory), they don’t do without the empty set, and they don’t try to generate the cumulative hierarchy from hypersets. But I don’t see any objection in principle to doing so. The simplest solution is to admit individuals, which means having an axiom stating that there is at least one individual. Somewhere I remember reading that Russell early on considered an axiom like this but rejected it because he thought mathematics had no business assuming anything about the world, and presumably an individual is part of the furniture of the universe. This is a philosophical question, and an interesting one, but not part of set theory proper, at least as I understand it.

. . . . .

signature

. . . . .

Grand Strategy Annex

. . . . .

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: