3
$\begingroup$

I appreciate any insight to this question, including suggestions for other terms to learn about first. I am self-taught with regards to set theory and not a mathematician, so my question may not be well-formed. Thank you for your patience!

To get to this question I have read numerous Wikipedia articles (set theory, ZFC, ordinal numbers, limit ordinals, etc.), spoken with some grad friends who study math, and read a paper and part of a book by Thomas Jech.

I wanted to know if there exist set theories in use that do not use an Axiom Schema of Separation. My understanding is that in response to Russell's Paradox (itself a critique of Frege) in ZF we have the Axiom Schema of Separation instead of the Axiom Schema of Comprehension (as Jech teaches in Set Theory).

I've been curious about alternative set theories and have found the Wikipedia pages for NBG (Neumann Bernays Godel) and MK (Morse-Kelley). Am I correct in thinking that both of these have something equivalent to the Axiom Schema of Separation?

I am specifically interested in the following notion: is there a set theory in use today that does not rely on the Axiom Schema of Separation to construct its existents*? It seems the power of the Axiom Schema of Separation is to get out of Russell's Paradox by assuming there exists some other set, say $Y$, that one then 'cuts' from in order to construct the set you really wanted to bring into being (say, set of all $x$ with some property).

I'm curious if there are set theories used today that don't do this move, and if so, how do they deal with Russell's Paradox? In short, I'd love a list of alternative strategies that set theories use to create new sets. (Edited after reading Asaf Karagila's kind answer.)

Thank you.

*Existent is a word borrowed from philosophy. It just means "thing that exists." As I understand ZFC, everything in it is a set, so if we were just talking about ZFC instead of "existent" I could have said "set." But, in Morse-Kelley it seems like sets and classes both exist, so I use the term "existent" instead.

$\endgroup$
  • $\begingroup$ I feel that I might not have fully understood your question, so please let me know if my answer was any help at all. $\endgroup$ – Asaf Karagila Mar 16 '15 at 23:16
  • 1
    $\begingroup$ (Also, "ur-elements" in the context of set theory usually refer to objects in the universe which do not have elements, and are not the empty set; so your use of "ur-elements" here is a bit off.) $\endgroup$ – Asaf Karagila Mar 16 '15 at 23:20
  • $\begingroup$ Hi @AsafKaragila, thank you for your response, it was very interesting. This part is the part I'm most interested in: "The solution was to just limit which instances will define sets. One way is to insist that only collections which are bounded in a pre-existing set will define sets, and this is the schema of separation." What other ways exist? And where can I read about them? Is there a list of them somewhere so I can read about all of them? Thank you! $\endgroup$ – bobo Mar 16 '15 at 23:47
  • $\begingroup$ Let me edit my answer. $\endgroup$ – Asaf Karagila Mar 16 '15 at 23:55
  • 1
    $\begingroup$ @bobo I don't see the need, for example, to build up natural numbers from induction on the null set. Peano's Axioms are really quite intuitive if looked at the right way. (See my posting, "What is a number again?" at my math blog dcproof.wordpress.com ) If even those simple axioms are too much of a leap for you, from every Dedekind-infinte set, you can extract a subset that satisfies the Peano's Axioms. Harvesting natural numbers growing in the wild! (See "Daddy, where do numbers come from?" at my blog). $\endgroup$ – Dan Christensen Mar 20 '15 at 2:25
4
$\begingroup$

Set theory is only useful if you can actually define new sets, if you can specify that certain properties define sets. Because the whole idea behind sets is to have collections of mathematical objects being "first class citizens" of the mathematical universe. In other words, sets are mathematical objects which are themselves collections of mathematical objects.

Naively it was suggested that every property, every collection we can "describe" in a reasonably consistent way, will be a set. But the many paradoxes of naive set theory show us that this is impossible, the most famous one as you point out, is Russell's paradox.

To avoid Russell's paradox we need to limit comprehension, but without some limited form of it, we're quite powerless to define sets, so we can't do much.

  1. $\sf ZFC$ and its close relative have a stronger axiom schema (and it allows us to prove strictly more, in a technical sense). Namely the replacement axiom schema, which says that if there is a function, definable with a first-order formula, then the image of a set is another set.

    This of course implies separation. In its second-order relatives, $\sf NBG$ and $\sf KM$, we need to decide what sort of replacement axioms we allow with regard to class variables. This is the key difference between these two cousins.

    So while we allow more power than just separation, we don't quite reach into the obvious paradoxes of naive set theory yet. Simply because for a contradiction to occur here, we need to find a set (which already exists) and a definable function, whose range is not a set.

  2. $\sf KP$ (Kripke-Platek) and its close relatives in fact weaken the separation axiom schema only to certain formulas. These theories are much weaker, but they still have interesting uses in recursion theory.

  3. $\sf NF$, Quine's New Foundation, a mysterious set theory whose guiding hand comes from type theory. Here we don't require subsets to be defined from pre-existing sets. Instead we require that formulas will have a certain "typed hierarchy" in the variables appearing there (stratified formulas), and this helps to put a leash on the many paradoxes.

    One peculiar example is that $\sf NF$ has a universal set. The set of all sets exists. Here we remove the issue of Russell's paradox by noting that the formula $x\notin x$ is not stratified. So it doesn't need to define a set.

It is important, however, to point out that all the modern set theories we have, at least those that are worth anything, cannot prove their own consistency, and usually we need to explicitly (or sometimes implicitly) assume they are in fact consistent; or assume even stronger theories are consistent. This means that we don't quite avoid Russell's paradox, as much as "we haven't found a contradiction yet". This comes to show that the many paradoxes of naive set theory just tell us that these collections are not necessarily sets.

My view of Russell's paradox, is that it is not at all a paradox. It is a theorem stating the following:

Theorem. If $A$ is a set, and $B=\{x\in A\mid x\notin x\}$ is a set, then $B\notin A$.

Proof. If $B\in A$, then we can ask, is $B\in B$? And then note that $B\in B\leftrightarrow B\notin B$, of course this is a contradiction. Therefore $B\notin A$.

From this we can draw some conclusions, if the set of all sets exists, then $B$ is not a set at all; or if $A$ is a set, and $x\notin x$ can be used to define a subset of $A$, then there is a subset of $A$ which is not an element of $A$.

The conclusion, if so, is that we don't quite avoid Russell's paradox, as much as tacitly assume that everything is fine, and the paradox in fact proves that a certain formulas does not define a set, but rather a proper class.

$\endgroup$
  • $\begingroup$ Hi @AsafKaragila, some questions: 1) Aren't the only existents in ZFC sets? So aren't the elements of sets also always sets? What did you mean with "Because the whole idea behind sets is to have collections of mathematical objects being "first class citizens" of the mathematical universe. In other words, sets are mathematical objects which are themselves collections of mathematical objects." 2) Does Quine's NF come from Russell's Theory of Types? $\endgroup$ – bobo Mar 17 '15 at 0:19
  • $\begingroup$ 3) I like your explanation of Russell's paradox: if the set of all set exists, then B is not a set, very cool. And I remember Jech speaking of "proper classes," so your argument makes sense. 4) Where can I read more on NF? I'm very interested in what a set theory looks like that doesn't need the Axiom Schema of Separation to make sets. 5) Where can I get an accessible intro to the difference between Axiom Schema of Separation and Axiom Schema of Replacement? 6) Is NF the only set theory you know of that doesn't use Separation/Replacement? Thank you! $\endgroup$ – bobo Mar 17 '15 at 0:19
  • $\begingroup$ (1) Yes, but the philosophy of sets is that before we had "all the natural numbers" and now we can say "all the elements of the set of all natural numbers". The collection itself is now a mathematical object for its own right. But some collections cannot be sets, that's the issue here. So you need to allow some separation, or some comprehension, but not everything; and if you remove it entirely you lose too much power. (2) I don't know too much about it. Supposedly NF and TST are equivalent, or something similar. (3) This is not a question. :-) $\endgroup$ – Asaf Karagila Mar 17 '15 at 0:23
  • $\begingroup$ (4) Let me clarify, NF does have a separation schema. But instead of saying "definable subsets of pre-existing sets are sets", it says "definable collections are sets, assuming that the formula was stratified". It is a separation schema. It just works in a completely different way, and it forces you to meddle with the logic in a far dirtier way than $\sf ZFC$. But there's separation. Again, you can't do too much without any form of separation axioms. You end up with something equivalent to a Venn diagram in statistics for psychology majors course. $\endgroup$ – Asaf Karagila Mar 17 '15 at 0:25
  • $\begingroup$ Awesome, thank you so much! If you know of any other set theories (other than NF) with alternative approaches to set creation that don't depend on "definable subsets of pre-existing sets are sets," as you put it, please let me know their names. I'm super curious on this point. Thank you very much for your help! $\endgroup$ – bobo Mar 17 '15 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.