Proper Classes in ZF: No Assumptions of Choice

[Dragonfall]

I know that V, Ord and Card are proper classes because otherwise foundation, successor and Cantor's theorem would be violated respectively. But if a class is in bijection with one of them, why is that class automatically proper? If we don't assume choice, then the cardinality argument doesn't work. So let's not assume choice.

Also, suppose we adopt the anti-foundation axiom instead, why is there no set of all non-well-founded sets?

 

[Hurkyl]

I know that V, Ord and Card are proper classes because otherwise foundation, successor and Cantor's theorem would be violated respectively. But if a class is in bijection with one of them, why is that class automatically proper?

Replacement.

 

[Dragonfall]

Suppose we only consider non-well-founded sets as "sets". ie, we replace foundation with an anti-foundation axiom, remove the empty and infinity sets, and replace them "x={x}" exists or something. Is it possible to build up a set theory rich enough such that the class of all sets is a SET? This would dispense with the need for higher and higher order of classes.

 

[Hurkyl]

The only model of your axioms is one where no set exists. (If a set exists, then the empty set must exist, which fails to satisfy your axiom)


Anyways, you can randomly play with axioms, but to what end? The utility of ZFC comes from the fact it describes the naturals and mimics formal logic. If you take away those qualities...

 

[Dragonfall]

Not true, the empty set exists only because of the axiom. If instead we start with a set x={x}, it's possible to build something else out of it.

I'm not denying that ZFC is not useful or anything, I'm just saying that the fact that in ZFC (or Morse-kelley, or whatever), there are always objects which are too big to be sets, and thus you need more and more powerful theories to describe them. It'd be great if that weren't necessary.

 

[Hurkyl]

Not true, the empty set exists only because of the axiom.

If any set exists, the empty set can be constructed by restricted comprehension. Let S be any set; then we can define:
\emptyset_S = \{ x \in S \mid x \neq x \}
it's straightforward to show that \emptyset_S is, in fact, empty. Furthermore, all sets created in ths manner are equal.

 

[Dragonfall]

We could work around that by allowing atoms in our set theory. The empty set would be an atom. But that's not really my point here. I'm asking whether it is possible to build a universe of sets that is as rich as ZFC, and in which the universe of sets is a set. I'm thinking this may be possible if we only think of non-well-founded sets + the empty atom. There could be a set of all non-well-founded (and hence all) sets in this theory that is not inconsistent.

 

[Hurkyl]

If you want to insist the empty 'set' is not a set, then you will have to modify restricted comprehension appropriately. And this seems to defeat your whole idea of rejecting "higher and higher order classes", because you are putting all other sets on a "higher order" than the empty set.


And if you're going to seek out a theory with a 'set of all sets', you're going to have to find a way out of all of the classical paradoxes, such as Russell's paradox, or Cantor's proof that there is no injective function from P(S) to S.


Incidentally, one method that people use if they really want to talk about universes as if they were sets is to invoke a large cardinal axiom, so that there exists some set S such that the elements of S (often called "small sets") form a model of ZFC. In this way, you can speak of the "large set of all small sets". e.g. see http://en.wikipedia.org/wiki/Grothendieck_universe



If you're willing to go in another direction -- I believe that in constructivism, depending on what you meant by 'set', you can easily have a set of all sets. However, constructivism gives up Boolean logic. (I can't say much intrinsically about constructivism, because I'm only really familiar with the perspective given by the theory of computation. i.e. studying Turing machines)

 

[gel]

If you're willing to go in another direction -- I believe that in constructivism, depending on what you meant by 'set', you can easily have a set of all sets. However, constructivism gives up Boolean logic. (I can't say much intrinsically about constructivism, because I'm only really familiar with the perspective given by the theory of computation. i.e. studying Turing machines)

Constructivism doesn't allow for a set of all sets, because http://en.wikipedia.org/wiki/Russells_paradox#The_paradox_holds_in_intuitionistic_logic".

I'm asking whether it is possible to build a universe of sets that is as rich as ZFC, and in which the universe of sets is a set.

http://en.wikipedia.org/wiki/New_Foundations" allows for the set of all sets. I don't know a lot about it, but it avoids Russell's paradox by restricting the allowed formulas used in comprehension. The link also explains how Cantor's paradox is avoided.

 

[Hurkyl]

Constructivism doesn't allow for a set of all sets, because http://en.wikipedia.org/wiki/Russells_paradox#The_paradox_holds_in_intuitionistic_logic".

I was thinking even weaker than intuitionism: the objects are strings of symbols and the predicates are Turing machines.

If we use unrestricted comprehension, then we could define a set to be a Turing machine, and the membership relation is defined by x \in M := M(x).

(note that equality of sets is not a computable relation)

Since it's easy to tell if a string of symbols denotes a Turing machine, we clearly have a set V of sets. Since the above is just the theory of computation, it is all consistent. (relative to ZFC)