Does a logic with set of all sets exist?

[nonequilibrium]

Hello.

As I understand, in the classical logic it's impossible to "take", for example, the set of all sets.

I was wondering: is it possible to create a logic where that is possible by changing some of the basic postulates by which logic works? Or is it impossible for all logics?

Thank you.

 

[micromass]

Hi mr. vodka!

The answer is yes! There are set theories out there (which use the same logic), but which do allow an universal set. The most studied such a set theory is "New Foundations". See http://en.wikipedia.org/wiki/New_Foundations

 

[Hurkyl]

I don't think it takes much to think of the theory of computation (i.e. Turing machines) as providing such a thing.

For a functional version, there is also the (untyped) lambda calculus.

 

[nonequilibrium]

Hm, I don't think I know enough of the subject at hand. I'm but an undergraduate and there are no undergraduate courses in logic at my university, so my knowledge about these things is limited.

But micromass, you say "which use the same logic"; so the axioms of classical logic don't need to be modified to allow self-containing sets in a consistent way?

Or is it perhaps in those cases the notion of "set" or "containing" that is modified, instead of the rules of logic used to derive the "usual" paradox(es)?

 

[micromass]

Hm, I don't think I know enough of the subject at hand. I'm but an undergraduate and there are no undergraduate courses in logic at my university, so my knowledge about these things is limited.

But micromass, you say "which use the same logic"; so the axioms of classical logic don't need to be modified to allow self-containing sets in a consistent way?

Or is it perhaps in those cases the notion of "set" or "containing" that is modified, instead of the rules of logic used to derive the "usual" paradox(es)?

Well, you have several kinds of axioms: you have the logical axioms and you have the set theoretic axioms (usually ZF-axioms). Only the ZF-axioms need to be canged here. So yes, we essentially modify the meaning of a set. But we modify it so we can still work with it like we're used to.
I'm sure a modification of the logical axioms would work, but I'm not aware of that being done.

 

[nonequilibrium]

Interesting!

But the New Foundations isn't the "common" logic, is it? Cause as far as I've heard, the problem of self-referring sets is also solved as "you simply are not allowed to define a set that contains itself" or is that "solution" not the most common one? Anyway, let it be clear that that solution is not the one I'm interested in at the moment; I'm looking for a logic where you are allowed to play with self-referring sets, but I think you got that, so I assume New Foundations allows those sets.

How can someone in my position understand how New Foundations (or a variant) solves the Russell paradox?

 

[SW VandeCarr]

How can someone in my position understand how New Foundations (or a variant) solves the Russell paradox?

You can look up Russell's Theory of Types. The lowest type include sets of individuals; the next level of type include sets of sets; the next level, sets of sets of sets and so on. These are sometimes referred to as first, second and higher order logic. Thus we can have a set of all sets in a lower order of type which is a set the next higher order of type.

I'm not sure how the "variants" referred to but not described differ from Russell's approach. I believe they may be variants of it.

EDIT: Micromass's link to VO Quine's version is based on Russell. I think understanding Russell's approach first may make reading Quine a bit easier. Likewise for understanding the "untyped" lambda calculus.

 

[praeclarum]

Interesting!

But the New Foundations isn't the "common" logic, is it? Cause as far as I've heard, the problem of self-referring sets is also solved as "you simply are not allowed to define a set that contains itself" or is that "solution" not the most common one? Anyway, let it be clear that that solution is not the one I'm interested in at the moment; I'm looking for a logic where you are allowed to play with self-referring sets, but I think you got that, so I assume New Foundations allows those sets.

How can someone in my position understand how New Foundations (or a variant) solves the Russell paradox?

Well, if I am interpreting your comment correctly, then you are talking about the Axiom of Regularity of ZF set theory, which implies that
[itex]\neg[/itex]x[itex]\in[/itex]x

As far as NF (New Foundations) solving set theory paradoxes, Quine says that
{ x | [itex]\varphi[/itex] } (that is, the collection of all sets "x" such that [itex]\varphi[/itex]) exists (is a member of the universe) if [itex]\varphi[/itex] is stratified. For fear of explaining it incorrectly, I recommend you read the wikipedia page on stratification to gain a better understanding of it. The Russell class, which is { x | x [itex]\notin[/itex] x } cannot be constructed in NF, because x [itex]\notin[/itex] x is not stratified.

Edit: And x [itex]\notin[/itex] x is not stratified because x [itex]\in[/itex] y can only be constructed if y can take a value that is one type higher than x.

The best way I can explain it is that [itex]\varphi[/itex] is stratified if, when reduced to its atomic formulas, you can assign a type value to x, y, z, and any other variables in such a way so that whenever you have an = sign, variables on both sides are of the same type, and whenever you have x [itex]\in[/itex] y, y is of one type higher than x. This prevents circular references like Russell's paradox.

 

[Hurkyl]

As far as NF (New Foundations) solving set theory paradoxes, Quine says that
{ x | [itex]\varphi[/itex] } (that is, the collection of all sets "x" such that [itex]\varphi[/itex]) exists (is a member of the universe) if [itex]\varphi[/itex] is stratified.

If I understand what you're talking about, this is just how higher order logic works, and isn't anything specific to new foundations.