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, TDCmatt@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!jnppem@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