[sci.math.symbolic] Russell's set of sets which... paradox

campbell@utx1.UUCP (Tom Campbell) (07/22/87)

I would like to know if a *satisfactory explaination* has ever
been given regarding Russell's well-known set theory paradox.

For those who are not familar with it, here it is.

Let S' be a set such that S' has as its elements all and only those
sets which have the following property:   

              They do not have themselves as elements.

QUESTION: Is S' a set which does not have itself as a member?


                                    Thanks, TDC

matt@oddjob.UChicago.EDU (Matt Crawford) (07/23/87)

Ahhh!  Sci.math gets its own set of very long relativistic
scissors.  Have fun, kids.
					Matt

mojo@reed.UUCP (definition) (07/23/87)

In article <1214@utx1.UUCP> campbell@utx1.UUCP (Tom Campbell) writes:
}I would like to know if a *satisfactory explaination* has ever
}been given regarding Russell's well-known set theory paradox.
}
}For those who are not familar with it, here it is.
}
}Let S' be a set such that S' has as its elements all and only those
}sets which have the following property:   
}
}              They do not have themselves as elements.
}
}QUESTION: Is S' a set which does not have itself as a member?
}
}
}                                    Thanks, TDC


What would you consider a "satisfactory explanation"?  The only reasonable
analysis I can imagine goes to the point of saying that S' is a member of
itself iff S' is not a member of itself, then breaks down into paradox.

This is a little like asking for a satisfactory explanation of the "This
sentence is false" paradox.

	"Paradox is its own explanation"
	Nathan Tenny
	...tektronix!reed!mojo

gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/24/87)

In article <1214@utx1.UUCP> campbell@utx1.UUCP (Tom Campbell) writes:
>QUESTION: Is S' a set which does not have itself as a member?

Dunno; what's a "set"?  Is it definable in terms of categories?
(Seriously, there are MANY ways around Russell's anomaly.)

jnp@daimi.UUCP (J|rgen N|rgaard) (07/24/87)

Zermelo Fraenkels axioms for sets (should) prevent(s) sets to be defined
that way. A reference might be North Hollands Handbook of ... mathematics 
(I think it is called).

 
-- 
			Regards J|rgen N|rgaard
				e-mail: jnp@daimi.UUCP
                                or      ....{seismo!}mcvax!diku!daimi!jnp

pem@cadnetix.UUCP (Paul Meyer) (07/25/87)

[]
	Actually, the paradox as stated leads to a very significant con-
   clusion:  not everything is a set.  Modern mathematics (at least as I
   was taught it) draws a distinction between "classes" (things which
   follow the intuitive idea that a set can be anything) and "sets" (which
   obey certain rules).

	A consequence of this distinction is that S is not a set.  Thus,
   we can say that "S is the class of all sets that do not include them-
   selves as members", and thus S does not include itself because it is not
   a set, or we can say "S is the class of all classes that do not include
   themselves as members" and then give up on S as a useful thing.

	The Z-F set theory is one consistent(*) axiomitization of what a
   "set" is.  It is also powerful enough to (given patience) produce the
   entirety of classical math--that is, it demonstrates that classes that
   are not sets are not required for classical mathematics.

	Unfortunately, the only text I can recommend for this stuff is the
   one I used, written by my professor, J. Malitz.  It is a good book, but
   quite terse.  In about 100 pages it covers 3 semesters' worth of upper-
   division math, covering set theory, computability, and formal logic.
   Without Dr. Malitz's lectures I wouldn't have been able to follow it
   very well, and even with them a good 50% of the classes tended to get
   very confused.

						pem

(*) - Of course, how do we prove that it is true?  Do we use it on itself?
   If not, how do we prove that whatever we use to prove Z-F is true?  In
   short, mathematics is in some ways as great a faith decision as theism--
   except that the consequences are no where near as far-reachese) 

andy@ecrcvax.UUCP (Andrew Dwelly) (07/27/87)

Regarding this paradox, G Spencer Brown, makes an interesting comment in
his book "The laws of form" (Dutton, New York)

"Recalling Russell's connection with the Theory of Types, it was with some
trepidation that I approached him in 1967 with the proof it was
unnecessary. To my relief he was delighted. The Theory was, he said, the
most arbitary thing he and Whitehead had ever had to do, not really a
theory but a stopgap, and he was glad to have lived long enough to see
the matter resolved.

Put as simply as  I can make it the resolution is as follows....."

Spencer Brown introduces the idea of an imaginary boolean, the counterpart
of an imaginary number. He justifies this by showing that all the self
referential paradoxes "solved" by the theory of types are no worse than

			"This statement is false"

(This step is not included in the text, is it valid ?). He then draws the
readers attention to the counterpart in ordinary equation theory.

			X^2 = 0
transposing
			X^2 = -1
dividing both sides by X
			X = -1/X

which is self referential. It is common knowledge that the introduction
of imaginary numbers tidies up this kind of paradox. Hence imaginary
booleans.

The whole area of the "laws of form" seems to have not been touched since. 
Does anyone know of new applications/developments/refutations ???

				Andy

robertj@garfield.UUCP (07/27/87)

In article <744@cadnetix.UUCP> pem@cadnetix.UUCP (Paul Meyer) writes:
>[]
>	Actually, the paradox as stated leads to a very significant con-
>   clusion:  not everything is a set.  Modern mathematics (at least as I
>   was taught it) draws a distinction between "classes" (things which
>   follow the intuitive idea that a set can be anything) and "sets" (which
>   obey certain rules).


Several people have pointed out the simplest (I think) solution found to the 
Russell Paradox, that is that the object that Russell is talking about is not
a set. The version of an axiomatization which arrives at this conclusion
with which I am aquainted is the Frankel-Zermelo Axiomatization in which
class and membership are the primitive (undefined) concepts (not sets!) and
a set is defined as a class which is a *member* of another class. Classes
which are not members of other classes are not sets and we cannot talk
about their "power class" and so forth, they are proper classes. The object
Russell defined, that is the class of all sets not members of themselves,
can easily then be shown to be one of these proper classes as assuming it
to be a set leads to a contradiction, that is the Russel Paradox.

	In all fairness however it should be pointed out that Russell in
conjunction with Whitehead came up with another solution to the problem
which does not invlove just saying that the Russell Class (R) is not a set.
Russel observed that the Russell Paradox in some way arose because of
mixing levels. That is we have here a sentence that talks about sets
of seemingly simple things (eg the set of orange cats) and sets that
talk only about other sets (eg R itself). What Russell and Whitehead
did (more or less) was say that there is a hierarchy of sets, the simplest
being type zero sets which in some way correspond to things like the
set of all grey dogs and then moving on to type one sets, which deal
with type zero sets and so forth. This was called the Theory of Types.
The key point in this theory is that one could not talk about type zero
sets interchangeably with type one sets. Thus the equation $X in R$ is
ok if $X$ runs over the type zero sets but is meaningless if we put
a type one object in the place of $X$. Thus Russell resolves the paradox
by banishing the sentence $R in R$ rather than by banishing $R$.

	This description may be wrong in details but the essential idea
is there. The resolution of set theory into an infinitely ascending
hierarchy of types which cannot be arbitrarily mixed in logical statements.
As can easily be imagined this becomes quite messy eventually particularly
when compared with F-Z which has only two levels, class and set. The system
outlined by Russell and Whitehead's Principia Mathematica (which every
wants to have read but no-one has, a classic) does capture everything
that F-Z does however and I believe Godel's work was actually written
with the Principia in mind as his model of a formal system. I think it
can be fairly safely said that very few and probably no working 
Mathematician or Logician uses the system set out in Principia. 

	Lord Russell said that after he noticed his paradox he spent
ten years looking at a blank sheet of paper, then wrote Principia
and then never did another good piece of Mathematics (or logic) again.
At least he did propose a workable if cumbersome solution.

					Robert Janes

steve@hubcap.UUCP (Steve ) (07/27/87)

in article <423@ecrcvax.UUCP>, andy@ecrcvax.UUCP (Andrew Dwelly) says:
[....Spencer Brown and Lawsof Form....]
> The whole area of the "laws of form" seems to have not been touched since. 
> Does anyone know of new applications/developments/refutations ???

The AI folks have had some discussion lately.  I had a friend at Bell
Labs who used some of it in his dissertation in logic.  Try him: Robert A.
Orchard.  I think he's at CCNY now.
-- 
Steve Stevenson                            steve@hubcap.clemson.edu
(aka D. E. Stevenson),                     dsteven@clemson.csnet
Department of Computer Science,            (803)656-5880.mabell
Clemson Univeristy, Clemson, SC 29634-1906

sigrid@geac.UUCP (Sigrid Grimm) (07/27/87)

In article <6160@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>In article <1214@utx1.UUCP> campbell@utx1.UUCP (Tom Campbell) writes:
>>QUESTION: Is S' a set which does not have itself as a member?
>
>Dunno; what's a "set"?  Is it definable in terms of categories?
>(Seriously, there are MANY ways around Russell's anomaly.)

Doesn't it really somehow depend upon what philosophy you adhere to ?

:-)

gcs@mundoe.mu.oz (Geoff Smith) (07/28/87)

In article <423@ecrcvax.UUCP> andy@ecrcvax.UUCP (Andrew Dwelly) writes:
>Regarding this paradox, G Spencer Brown, makes an interesting comment in
>his book "The laws of form" (Dutton, New York)
>
>"Recalling Russell's connection with the Theory of Types, it was with some
>trepidation that I approached him in 1967 with the proof it was
>unnecessary. To my relief he was delighted. The Theory was, he said, the
>most arbitary thing he and Whitehead had ever had to do, not really a
>theory but a stopgap, and he was glad to have lived long enough to see
>the matter resolved.
>
>Put as simply as  I can make it the resolution is as follows....."
>

The dates of the Bertrand Russell are 1872-1970. In the year 1967
he became 95 years old. He was, of course, a great man in various
ways, but - how can one put this kindly - his sense of mathematical
judgement may not have been as acute as it once had been. This is
one possible explanation for these alleged remarks about
_Laws_of_Form_ - if they are in fact an accurate reflection on his
thoughts at the time.

Another possible explanation might be Russell's good-manners.

Incidentally, the title _Laws_of_Form_ rather echoes George Boole's
_Laws_of_Thought_ (1854). Modest eh?

Spencer-Brown claimed to have solved the four-colour problem back in
the sixties. Despite being given every chance to explain himself
he was unable to convince the mathematical establishment of the
correctness of his methods. Need one say more?

Geoff Smith,Maths Dept,Univ of Melbourne and sometime of Bath,UK

drw@cullvax.UUCP (Dale Worley) (07/29/87)

campbell@utx1.UUCP (Tom Campbell) writes:
> I would like to know if a *satisfactory explaination* has ever
> been given regarding Russell's well-known set theory paradox.

Perhaps the best way to phrase the solution is as a consequence of a
really very subtle principle of modern mathematics:  "There are
syntactically well-formed sentences, which nonetheless don't mean
anything."  A particular example of this is "the set of all x's which
have property P(x)" -- this phrase denotes a set for only certain
properties P, and "non-self-membership" isn't one of them.

The earliest example that I know of is from the Scholastic philosophy
(Midaeval Catholic, about 1300?):  "Can God make a stone so large that
he can't lift it?"  The solution, of course, is that there can be no
such stone.

Dale
-- 
Dale Worley	Cullinet Software		ARPA: cullvax!drw@eddie.mit.edu
UUCP: ...!seismo!harvard!mit-eddie!cullvax!drw
From the Temple of St. Cathode of Vidicon:

dhesi@bsu-cs.UUCP (Rahul Dhesi) (07/30/87)

In article <1404@cullvax.UUCP> drw@cullvax.UUCP (Dale Worley) writes:
>campbell@utx1.UUCP (Tom Campbell) writes:
[about paradoxes]
>The earliest example that I know of is from the Scholastic philosophy
>(Midaeval Catholic, about 1300?):  "Can God make a stone so large that
>he can't lift it?"  The solution, of course, is that there can be no
>such stone.

Assumption:  God is all-powerful.

Conclusion:  God *can* make a stone that he can't lift.  Then he *can*
lift it.  For being all-powerful means having the ability to violate
the rules of logic, for the rules of logic exist only because God
allows them to;  therefore God can suspend the rules.

If you disagree, it is because your concept of a supreme being (a being
who can do anything provided he abides by your axioms) is different
from mine (a being who can do anything, including changing my axioms to
suit his purpose).

Followups disccouraged, because of the danger of this degenerating into
a reigious debate.  Enough to say that supreme beings are in general
poor subjects for discussion in the same breath as mathematics and
logic.
-- 
Rahul Dhesi         UUCP:  {ihnp4,seismo}!{iuvax,pur-ee}!bsu-cs!dhesi

ladkin@kestrel.ARPA (Peter Ladkin) (07/30/87)

In article <3830@garfield.UUCP>, robertj@garfield.UUCP writes:
> [..] Frankel-Zermelo Axiomatization in which
> class and membership are the primitive (undefined) concepts (not sets!) and
> a set is defined as a class which is a *member* of another class.

(Fraenkel's name is normally spelt with two e's)

I think you are talking about the von Neumann-Goedel-Bernays formulation
of set theory, otherwise known as NBG.

In ZF set theory, every object is a member of some other object, namely
its singleton (follows from pairing). 

ZF avoids the paradox also by using layering, except that the layering
is in the semantics rather than the syntax. The layering is obtained
by iterating the power set operation, starting with the empty set.
A set's rank is the index of the least layer in which it appears.
There are some subtleties if you don't include the axiom of choice.

peter ladkin
ladkin@kestrel.arpa

jvh@clinet.FI (Ville Heiskanen) (08/03/87)

In article <902@bsu-cs.UUCP> Rahul Dhesi writes:
>Conclusion:  God *can* make a stone that he can't lift.  Then he *can*
>lift it.  For being all-powerful means having the ability to violate
>the rules of logic, for the rules of logic exist only because God
>allows them to;  therefore God can suspend the rules.
>
>If you disagree, it is because your concept of a supreme being (a being
>who can do anything provided he abides by your axioms) is different
>from mine (a being who can do anything, including changing my axioms to
>suit his purpose).

Ok. So assume a generic all-powerful Meta-being (to steer clear of religious 
arguments):
  
Now: Can he formulate rules he cannot suspend? Your posting mentioned that he
certainly could do what he wanted with your axioms, but what about his own?
And saying that this Meta-being would not deal in axioms and rules of logic
at all (being above it all) will not help either. After all, this guy IS
ALL-POWERFUL, so playing with rules of logic should be childsplay...
  
And another little glitch: How does a Meta-being allow rules of logic to exist

To me it would seem, that the act of allowing requires at least one previous
formulation of logic: "There exists *rules of logic*, for which: (formulations
to suit this Meta-beings wishes)". Well, who said that life was easy... Even
for Meta-beings :-)
  
Any which-way you look at it, you're bound to get a serious sprain of the
cogitative faculty...

ags@j.cc.purdue.edu (Dave Seaman) (08/03/87)

In article <902@bsu-cs.UUCP> dhesi@bsu-cs.UUCP (Rahul Dhesi) writes:
>In article <1404@cullvax.UUCP> drw@cullvax.UUCP (Dale Worley) writes:
>>campbell@utx1.UUCP (Tom Campbell) writes:
>[about paradoxes]
>>(Midaeval Catholic, about 1300?):  "Can God make a stone so large that
>>he can't lift it?"  
>
>Assumption:  God is all-powerful.
>
>Conclusion:  God *can* make a stone that he can't lift.  Then he *can*
>lift it.  For being all-powerful means having the ability to violate
>the rules of logic, for the rules of logic exist only because God
>allows them to;  therefore God can suspend the rules.

I hesitated to respond to this because I am not interested in starting a
religious debate, but there is something to be said here that lies in the
realm of logic rather than religion.  It is especially appropriate to the
ongoing discussion about paradoxes.

As others have pointed out, the true meaning of a paradox is that it is
time to re-examine your assumptions.  Russell's paradox, for example, means
you have to be careful about what you call a set.

The stone paradox can be formulated as follows:  Assume x is an omnipotent
being.  Let P(x) be the statement, "x can make a stone so big that x can't
lift it."  Is P(x) true, or is it false?  A little thought shows that it is
neither.

What do we conclude from the contradiction?  There must be something wrong
with the original assumption that there exists an omnipotent being.
Therefore no such being can exist.  Notice that I have never said that
there is any particular thing that x cannot do, or that there is any stone
that cannot exist.  It is x itself that cannot exist.
-- 
Dave Seaman	  					
ags@j.cc.purdue.edu

dhesi@bsu-cs.UUCP (Rahul Dhesi) (08/04/87)

In article <4901@j.cc.purdue.edu> ags@j.cc.purdue.edu.UUCP (Dave Seaman) writes:
[continuing a discussion of a paradox:]

>The stone paradox can be formulated as follows:  Assume x is an omnipotent
>being.  Let P(x) be the statement, "x can make a stone so big that x can't
>lift it."  Is P(x) true, or is it false?  A little thought shows that it is
>neither.
>
>What do we conclude from the contradiction?  There must be something wrong
>with the original assumption that there exists an omnipotent being.
>Therefore no such being can exist.

Let me throw this at you:  

     Omnipotent Being n. A being with the power to invalidate any or
     all possible sets of axioms.

Now try again.
-- 
Rahul Dhesi         UUCP:  {ihnp4,seismo}!{iuvax,pur-ee}!bsu-cs!dhesi

hansw@cs.vu.nl (Hans Weigand) (08/04/87)

Expires:

Sender:

Followup-To:

Distribution:


In article <4901@j.cc.purdue.edu> ags@j.cc.purdue.edu.UUCP (Dave Seaman) writes:
>(..)
>The stone paradox can be formulated as follows:  Assume x is an omnipotent
>being.  Let P(x) be the statement, "x can make a stone so big that x can't
>lift it."  Is P(x) true, or is it false?  A little thought shows that it is
>neither.
>
>What do we conclude from the contradiction?  There must be something wrong
>with the original assumption that there exists an omnipotent being.
>Therefore no such being can exist.  (..)

I agree with you that P(x) has no reasonable truth-value.
However, your conclusion is not warranted, since you confuse
logic and ontology. What is the false assumption of the Liar
Paradox? There is none, but its property of self-referenence
makes it hard to manage for logic. This does not prove that
there are no liars, etc, only that our logic falls short.

The intentional object "a stone that x can't lift" is logically
self-contradictory, given the assumption, just as "round squares"
are. Therefore, in the world as we construct it (through our
definitions and logic) such a thing cannot exist. Then it is
useless to make ontological predications about such a thing
(woruber man nicht sprechen kann, daruber soll man schweigen,
Tractatus Wittgenstein). However, you think you can say
something about it, because your omnipotent being is allowed to
violate the logical norms.

What your argument says, then, is that the concept of an
omnipotent being may lead to logical paradoxes if we
assume the omnipotent being may violate the logical norms.
This seems pretty much a tautology. The moral of this may be:
beware of logic when it refers (negatively) to its own principles.
However, I do not see what ontological conclusion can be drawn from this.

For a more extensive treatment of the power and limitations of logic,
I may draw your attention to the works of the great Medieval mathematician
and theologian Nicolaus Cusanus, in particular "De Docta Ignorantia"
(Learned Ignorance). Kant will probably do also.

-
Hans Weigand
Vrije Universiteit, Amsterdam

ags@j.cc.purdue.edu (Dave Seaman) (08/04/87)

In article <918@bsu-cs.UUCP> dhesi@bsu-cs.UUCP (Rahul Dhesi) writes:
  [ regarding the stone paradox ]
>Let me throw this at you:  
>
>     Omnipotent Being n. A being with the power to invalidate any or
>     all possible sets of axioms.
>
>Now try again.

But of course.  I know what omnipotent means, and my proof depends on it.
I grant you that an omnipotent being could invalidate all possible sets of
axioms IF IT EXISTED.  But the proof shows that it doesn't, and it does so
without denying the being's ability to do any particular thing, including
denying axioms.

You may, of course, claim that there is an omnipotent being who has
presented us with a logic that appears to work in all cases that we can
verify, but which does not apply to herself.  The argument then reduces to
"either there is no omnipotent being, or all of logic (and all of
mathematics) is just an illusion."  Obviously the continuation of that
argument does not belong in sci.math.
-- 
Dave Seaman	  					
ags@j.cc.purdue.edu

cameron@elecvax.eecs.unsw.oz (Cameron Simpson "Life? Don't talk to me about life.") (08/07/87)

In article <1404@cullvax.UUCP> drw@cullvax.UUCP (Dale Worley) writes:
>campbell@utx1.UUCP (Tom Campbell) writes:
[about paradoxes]
>(Midaeval Catholic, about 1300?):  "Can God make a stone so large that
>he can't lift it?"  

I saw a really nice response to this reading:
	"He would not."
Of course, it doesn't solve anything except in practical terms, but
it was esthetically pleasing.
	- Cameron Simpson

The book was "The Isle of the Dead" by Roger Zelazny.
This article is *not* worth a followup.

ronald@csuchico.UUCP (08/10/87)

In article <1404@cullvax.UUCP> drw@cullvax.UUCP (Dale Worley) writes:
>campbell@utx1.UUCP (Tom Campbell) writes:
[about paradoxes]
>(Midaeval Catholic, about 1300?):  "Can God make a stone so large that
>he can't lift it?"  

Hey Tom,

	"Do you still beat your wife?"
	Same diff, get it?

-- 
Ronald Cole				| uucp:     ihnp4!csun!csuchic!ronald
AT&T 3B5 System Administrator		| PhoneNet: ronald@csuchico.edu
@ the #_1_ party school in the nation:	| voice     (916) 895-4635
California State University, Chico	"It's O.K." -Hal Landon Jr., Eraserhead