Talk:Russell's paradox

From Wikipedia, the free encyclopedia

Archives
27 November 2002 – 16 November 2005

Contents 1 Applied Version: Chinese Lao-tzu's Tao-te-ching 2 the truth about Russell's non-paradox 3 Principles of Mathematics vs. Principia Mathematica 4 Meta-Sets 5 Original Research 6 Remove: Responses illustrated 7 Barber 8 A clarification please? 9 Falicy in "Independence from excluded middle"? 10 Arithmetic 11 keep it simple 12 An odd creature 12.1 Possible worlds 13 Fuzzy Russell 14 A closer and clearer Russell paradox by Ali nour mohammadi sharif university of tehran 15 Urban Legend 16 what?

[edit] Applied Version: Chinese Lao-tzu's Tao-te-ching

The 1st statement of Lao-tzu's book says "道可道 非常道 A describable statement doesn't hold true for all the time." a statement which is described but if not hold true all the time, it defies what it says.

Sounds a bit closer to the Liar paradox, which is related to Russell but not exactly the same thing (because it doesn't deal with sets). --Trovatore 05:47, 4 November 2005 (UTC)

[edit] the truth about Russell's non-paradox

Nice this discussion.. I think the following argument has not been stated so far:

If you say "x := 3+2" this is a definition.

If you say "x = x*x - 6" this is an equation that may have any number of solutions (in this case, it has exactly one). Some equations have no solution, or an infinite number of them. In a way we can say a definition is an equation with one unique solution.

To define a set, you would say "M = {x | A(x) }" where A is a statement. Normally, this is a definition.

However, if the statement A refers to something on the left side of the "=", the whole thing becomes an equation where M is the variable, and therefore it doesn't need to have a solution any more. For the Russel set "definition", the reference to the object M exists, though it may not be visible at the first sight. So the "definition" is simply an equation that has no solution. Fine?

lemon-head.

yes, this is the truth, thanks for stating it so clearly :)

[edit] Principles of Mathematics vs. Principia Mathematica

1903 for the former, 1910 for the latter: Principia Mathematica is really "later". Randall Holmes 06:04, 29 December 2005 (UTC)

[edit] Meta-Sets

A set which contains sets is not a set, it is a meta-set. When you define a set you stand above all the elements in existence and you group some and exclude others, and the set being defined is on a higher level than those elements and cannot be included in itself. When you define a set you take a virtual lasso which surrounds the defined elements, and a set cannot be a member of itself just as a lasso cannot surround itself. —The preceding unsigned comment was added by 60.234.145.146 (talk • contribs) 13:13, 1 March 2006.

Well, right, sort of. You're very close to the intution that underlies contemporary set theory; you're just using nonstandard language.

Going with your language for now: The point is that "meta-sets" are very important; we need them, whatever we call them. And meta-meta-sets too. And so on (a very long "and so on"; we iterate through all the finite and transfinite ordinals).

Now, a couple of things: First, we find that we don't have to start with any actual objects, and it simplifies our life a bit if we omit them. We still get one set, which is the empty set, two meta-sets, four meta-meta-sets, sixteen meta-meta-meta-sets, 65536 meta⁴-sets, and so on.

Finally, we want to consider all meta-to-the-whatever sets all together; the convenient thing to call them is just simply "sets", and henceforth we drop the "meta"s.

We've just reinvented the von Neumann universe, into which all known mathematics can be coded. --Trovatore 15:15, 1 March 2006 (UTC)

One has to be careful when abbreviating a term such that it is the same as a different term. To avoid confusion one should only abbreviate "metaⁿ-set" to "set" when it is clear from the context that it has been abbreviated. That is; M={A|A is not an element of A} should be transcribed as "The meta-set of all sets which do not contain themselves", so that it is clear that while M does not contain itself, this does not mean that it in fact does contain itself (by function of the set definition) since it is not a set, it is a meta-set. —The preceding unsigned comment was added by 60.234.145.146 (talk • contribs) 16:56, 2 March 2006.

It betrays a certain lack of humility to attempt to dictate linguistic usage to the entire mathematical world. What I'm explaining to you is the accepted terminology.

Your substantive point, on the other hand, is basically correct. The Russell paradox does not show up at all in the conception of set embodied in the von Neumann universe. That's one of the big reasons that this conception has won out over Frege's. --Trovatore 18:00, 2 March 2006 (UTC)

[edit] Original Research

Isn't most of this article original research? I doubt that anything has been published in a respectable journal which compares Russell's sets to Wikipedia articles. Ken Arromdee 16:13, 6 March 2006 (UTC)

• That's one section.
• The purpose of an enyclopedia is to explain; examples are useful. WP:OR is intended to stop novel interpretations; unless the analogy is wrong, this is not novel, merely good writing.
• It is self-reference, which is also deprecated; it should be possible to mirror this article anywhere without reference to WP as such. I have made a stab at fixing this. Septentrionalis 17:20, 6 March 2006 (UTC)

I was just looking through the 'no original research' policy (WP:OR), and it has a very broad definition of 'original research'.

Regardless of whether the article violates the "No original research" policy, I'm fairly sure it violates the Citation/Verifiability policy. The only place that I could find any references was the history section. The whole article needs to be fully referenced or it violates the policy. For example, the "Independance from excluded middle" section (which I believe is incorrect, see below) doesn't give any information on where that opinion/argument can be found in a reputable publication.

I should mention here that I am new to Wiki editing, so I apologise if I have made a mistake or broken etiquette in some way. Could a more experienced editor please take a look and venture an opinion about this? If there are others who think that this article content is questionable, perhaps a dispute template should be included at the top of the article. DonkeyKong the mathematician (in training) 05:12, 2 May 2006 (UTC)

[edit] Remove: Responses illustrated

remote it Full Decent 04:03, 28 March 2006 (UTC)

[edit] Barber

The barber is a woman.

[edit] A clarification please?

From the article: "ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it assumes that for any given set and any definable property, there is a subset of all elements of the given set satisfying the property. The object M discussed above cannot be constructed like that and is therefore not a set in this theory".

Excuse my ignorance, but could somebody describe to a non-mathematician how exactly this addition of a "given set" removes the paradox and why M cannot be constructed this way? It's not that obvious to me... let's take a trivial case, and say that this "given set" is M itself, and the property is . The subset of M satisfying the property P(A) is again M, i.e. the paradoxical set itself.

The phrasing of the excerpt above doesn't seem to preclude choosing M as the "given set". In fact the only reason I came to this article was hoping to find out how formal set theories eliminate this paradox, yet it was only briefly mentioned and I wasn't able to fully understand it from the short description above. --Grnch 17:23, 20 April 2006 (UTC)

The ZFC version of the axiom of comprehension (axiom of separation, axiom of subsets, Aussonderung; these are just different names), says "for every set x and every formula φ, there is a set y consisting of exactly the elements z of x such that φ(z) holds". So to use this axiom to prove the existence of a y having the properties you want, you first have to prove the existence of the relevant x. So if you try to use this to prove the existence of the Russell set, you simply can't get started; you have to prove M exists before you can prove M exists. The discussion I've given you is slightly imprecise but it's the basic idea; hope it helps. --Trovatore 17:34, 20 April 2006 (UTC)

It does help, thanks. I guess I took the meaning of "for any given set" a bit too broadly (since the domain of allowable values wasn't explicitely stated), whereas it only applies to sets definable in ZFC. I appreciate the quick response. --Grnch 18:06, 20 April 2006 (UTC)

Well, actually it applies to all sets, definable or not. What I was arguing is that the proof of the contradiction doesn't go through, when unrestricted comprehension is replaced by separation.

I think you may need to get a clearer understanding of distinctions like syntax/semantics, provability/truth, definability/existence. By the way your original question talks about "how formal set theories eliminate this paradox"; I think that's a misimpression. It's not the formality per se that resolves the paradox, but rather a different conception of set, the one from which the von Neumann universe arises. --Trovatore 18:19, 20 April 2006 (UTC)

[edit] Falicy in "Independence from excluded middle"?

I think that the author of the "Independance from excluded middle" passage has made a mistake.

... Often, as is done above, showing the absurdity of such a proposition is based upon the law of excluded middle, by showing that absurdity follows from assuming P true and from assuming it false. Thus, it may be tempting to think that the paradox is avoidable by avoiding the law of excluded middle, as with Intuitionistic logic. On the contrary, assume P iff not P. Then P implies not P. Hence not P. And hence, again using our assumption in the opposite direction, we infer P. So we have inferred both P and its negation from our assumption, with no use of excluded middle. ...

This argument appears to make use of the same reasoning as the earlier examples. At first I thought that none of the earlier arguments really used the law of excluded middle, but then I realized that this argument (quoted) implicitly uses the law of excluded middle.

This argument goes: "...assume P iff not P. Then P implies not P..." The reasoning is fine so far...

"... Hense not P..." This is where the reasoning is flawed, since we have not assumed P, so the fact that P => ~P does not assist us, and thus we cannot conclude ~P.

In other words, since we are not assuming the law of excluded middle, it is possible to assume that neither P nor ~P are true (is it correct to talk about truth in this context?).

Thus the fact that we can show both P and ~P to be self contradictory does not lead to a paradox, since without the law of excluded middle, they can both be false at the same time. DonkeyKong the mathematician 04:05, 2 May 2006 (UTC)

No, P and ¬P can't exactly be false at the same time for an intuitionist; it's just that neither has to be true. (P → ¬P)→¬P is valid in intuitionistic logic. Intuitionistically, you should think of A → B as meaning "I have a way of transforming any proof of A into a proof of B", and think of ¬A as meaning "I have a way of transforming any proof of A into a proof of false". Now if you have a way of turning a proof of P into a proof of ¬P, and you also have a proof of P, then you can put them together to get a proof of P∧¬P, which then gives you a proof of false. Thus you can turn a proof of P into a proof of false; that proves ¬P. --Trovatore 05:38, 2 May 2006 (UTC)

Just the same, you have a point about the passage as written. The deduction of ¬P from P ↔ ¬P is valid, but the deduction of P from the same assumption, as far as I can tell, is not; what you actually get by the same argument is ¬¬P. But this does give us a contradiction, namely ¬P∧¬¬P. And of course from that you can deduce P, because ex falso quodlibet is intuitionistically valid. But the paragraph should be corrected. --Trovatore 18:07, 2 May 2006 (UTC)

Okay, I'm totally out of my depth with this stuff, so I'll just have to take your word for it. Anyway, I think we need an expert on the topic to help us out with this. DonkeyKong the mathematician (in training) 01:31, 19 June 2006 (UTC)

The passage as I found it was correct, although it seems to me you can, in fact, deduce P directly rather than using indriect proof a second time to get ¬¬P. I amended it to try to make the key step clear, let me know if it is still unclear (or if I have made it incorrect). 192.75.48.150 14:36, 19 June 2006 (UTC)

[edit] Arithmetic

The article says that arithmetic is "incomplete". I checked Completeness and Arithmetic but found no explanation: in what way is arithmetic incomplete? MrHumperdink 21:22, 7 May 2006 (UTC)

Thanks for catching that: The flat statement "arithmetic is incomplete", as contextualized (or more to the point not contextualized) in the article, is pretty meaningless. The probable intended meaning is that any (computably enumerable) axiomatization of arithmetic must be incomplete; that is, if you write down any finite list of first-order axioms for arithmetic (or more generally, an infinite list capable of being produced, in principle, by a fixed computer program), then there must be a statement of arithmetic that can neither be proved nor disproved from your list of axioms, or else the list is inconsistent (in which case every statement can be both proved and disproved). See Gödel's incompleteness theorems. Be warned that the article is in pretty bad shape (though listed, inexplicably, as a "good article"). --Trovatore 21:35, 7 May 2006 (UTC)

Thanks for your quick response! So, in layman's terms (if that's possible - calculus is clear as water compared to some of this stuff), arithmetic, by definition, has some property that can neither be proven nor disproven... I understand the idea, I suppose, but what would a "statement of arithmetic" be? MrHumperdink 00:23, 8 May 2006 (UTC)

Not exactly a "property that can't be proven or disproven", but rather that for any fixed set of axioms (subject to the technical stipulations I won't repeat), there's some true statement about arithmetic that's not captured by those axioms. A "statement about arithmetic" is a statement that talks about the natural numbers, using the usual operations and relationships (addition, multiplication, less than). So for example the infinitude of primes is a statement of arithmetic; it says: For every natural number n, there is a larger natural number m, such that m is not the product of natural numbers k and p, both bigger than 1. --Trovatore 03:23, 8 May 2006 (UTC)

[edit] keep it simple

M is already defined. If it includes itself,first you have defined a different set, secondly you have a self referencing object which never should have been allowed. Example: M={A,B} the original. M={A,B,M} a different set and one that cannot be resolved/expanded (what's in M?). M={A,B,M}, M={A,B,{A,B,M}}, M={A,B,{A,B,{A,B,M}}}, the infinite process again. An object can't be in two mutually exclusive sets. A thing can't be listed and unlisted. I've seen the references to the qualifiers x is not x,and you wonder where is reason? phyti--jun 05 2006

[edit] An odd creature

Some months ago I created the article List of every Wikipedia list that does not contain itself. This is in the spirit of part of the discussion in this article, the more precise in the self-reference. In any case, it simply redirects here; it might be something like a slight easter egg on Wikipedia, but please leave it be (it may not be a brillant joke, but it's worth a couple tens of bytes in the WP database.

Updating my userpage, an odd little self-reference occurred to me: List of every Wikipedia list that contains more items than this list. I know this is a digression from article discussion, but I'm trying to get a handle on exactly what kind of creature this hypothetical article is. It's not quite a Russell paradox, nor quite a Curry paradox.

Here's the issue, in case it's not immediately obvious: whether or not this list is "a problem" depends on the world external to its definition. If the world is certain ways, it's a perfectly ordinary collection. If the world is other ways, it's a paradox. Let's demonstrate:

• Suppose Wikipedia contains ten lists: five of them list 3 items each; five of them list 20 items each. No problem at all arises here, we just put the five big lists on the new list (bringing Wikipedia to eleven lists total, one of them containing five items).

• On the other hand, suppose Wikipdedia contains ten list: four of them list 3 items each; six of them list 5 items each. Now we have a problem. If we include the 5-items lists, this list has 6 items, and all the 5-item lists must be removed. If we leave off the 5-item lists, this list has zero items, and all the 5-item lists must be added (we might initially add the 3-item lists as well, but taking them off once this grows creates no special problem).

Is there a well-known name for logical/empirical paradoxes of this sort? I.e. ones that are only contingently paradoxical? LotLE×talk 06:32, 20 June 2006 (UTC)

[edit] Possible worlds

Hmm... There are plenty of stable states that this list could take. ie. say thre were 4 lists of 3 items, and 10 lists of 15 items, we'd be fine. To me this seems rather ordinary, "paradoxically" speaking... consider the "list of points at which lines ax+b and cx+d intersect?" depending on the state of a b c and d, we could have many solutions, one solution, or no solution... which seems to be exactly the same sort of outcome as this list you've just proposed. A good mathemetician might be able to generalize it with a formula, or failing that there's always computer assisted exhaustion to fall back on. - Rainwarrior 13:04, 20 June 2006 (UTC)

Certainly, there are many states of the world, or "possible worlds" where the paradox does not arise. In fact, I'm pretty sure that in a measure theoretic sense, the measure of the set of possible worlds where the paradox does arise is zero. Nonetheless, one can easily find an enumerably infinite set of "problem" possible worlds. Let's call worlds that are paradoxical in the described sense "L-paradoxical". The second part of this is almost immediate, by a trivial variation of the prior example:

• Suppose Wikipedia contains ten lists: four of them list 3 items; five of them list 5 items; one of them, BIG, lists "many" items. For every value of N > 5, the possible world described is L-paradoxical. That is, BIG must surely be included in "LoeWltcmittl". But if we try to put all the 5-item lists in LoeWltcmittl, we get a problem. So there's a countable infinity of problems. (and infinitely many other families of "problem worlds" are easy to construct).

The measurement thing is slightly more involved, but not too much. Basically, a possible world (down to homomorphism) is defined by a set of ordered pairs of natural numbers: <NumMembers, SizeOf>. That is, a (homomorphic equivalence class of) world(s) is described by the number of lists of each size that are in it. For example: "4 3-item; 5 5-item; 1 20-item". So described, some worlds are L-paradoxical, and others are not. Notice that the possible worlds are enumerable.

• We can consider all the worlds ranked by total size: worlds of 1 list (or whatever size), worlds of 2 lists, etc. If a world of size M has an "instability point"—that is, a number of items in LoeWltcmittl that would create an L-paradox—that point must be some number ≤ M. If every list in the world contains more items than M, no instability is possible. However, since M is some particular finite number, the measure of M-sized worlds in which no list is as short as M is exactly 1 (natural numbers keep going up, after all, any initial segment is measure 0).

In practical terms, one might be surprised to find billion, or trillion, or googleplex length lists on Wikipedia, but formally there is no size bound. Of course, some practical system, like WP that has an extreme bias towards "small" lists (for any value of small; say, N < number of particles in the universe) is likely to be L-paradoxical with measure greater than zero.

But all of that is not really what I was asking. My original point was that it is interesting that a construct is not just empty, or just undefined in a simple way, in some possible worlds; rather the construct is paradoxical in some possible worlds... but perfectly ordinary in other possible worlds. In some worlds (infinitely many, in fact), LoeWltcmittl cannot contain any particular number of items (including zero), and yet it gives a precise inclusion criterion for any particular possible member.

I'm familiar with paradoxes that are paradoxical by their actual form, i.e. in every possible world. But it is somewhat novel to me to have stumbled on a paradox that is, as I say, contingently paradoxical. Of course, I'm sure someone has thought of this type of thing before... so I was just hoping to learn that this was already known as, e.g. "Jones' Paradox". LotLE×talk 19:14, 20 June 2006 (UTC)

Well, it's an interesting construction to say the least. I've been reading List of paradoxes lately (that's how I ended up here), and so far I don't think anything has been "contingent". Mind you, paradox doesn't always mean "self contradicting", it more often has the sense "unintuitive but true" (ie. the Monty Hall problem is considered a paradox). (How come you created a sub-heading on the talk page for my reply? O_o?) - Rainwarrior 03:39, 21 June 2006 (UTC)

Arguably, particular instances of Curry's paradox are contigently paradoxical when their consequents are contigent. For instance the sentence "If this sentence is true, then Santa Claus exists" would be unproblematic if Santa Claus really did exist (which he does), the sentence is simply true. 192.75.48.150 18:25, 21 June 2006 (UTC)

I thought the "paradox" part of it was that you can prove anything to be true regardless of whether or not it is true... but perhaps our definitions of "paradox" differ. Is a paradox merely some form of contradiction? I thought we call Curry's paradox a paradox not because it is self referential or has a contradiction, but because it is an unusual or unexpected consequence of systems of logic. - Rainwarrior 01:33, 22 June 2006 (UTC)

I thought about 192.75.48.150's comparison some. There is a slightly different pattern to it when the consequent in Curry's paradox is already true. For example:

If <this line> then Haskell Curry exist(ed)

But in the actual world, the consequent is true, so:

If <this line> then TRUE

Which means that <this line> is going to come out TRUE, regardless of the value of <this line>. I.e. 'FALSE → TRUE' and 'TRUE → TRUE'. But in particular, since <this line> is the implication, it turns out true. We don't exactly prove some false (or self-contradictory) consequent; but what we do is follow the same reasoing that is normally the fallacy of Affirmation of the consequent. Just by having a true consequent, we manage to prove the antecedant: that's a slightly different no-no that proving a false consequent, but it's still a no-no.

So the kind of contingency suggested is still quite a bit different than that in the "L-paradox". In that, some possible worlds are entirely clear sailing, while no case of Curry's paradox is problem-free. LotLE×talk 03:20, 22 June 2006 (UTC)

[edit] Fuzzy Russell

I realized that Russell's paradox can be resolved if you use fuzzy sets, then you can just say that the set of all sets that don't contain themselves contains itself halfway.--SurrealWarrior 19:19, 12 July 2006 (UTC)

At first I was going to disagree, but after thinking about it, I think it might work. That's kind of weird... if there's a 50% chance that it contains itself (a, with a value of 1.0) and a fifty percent chance that it doesn't (b, with a value of 0.0), and (a) implies (b) and (b) implies (a) as the problem's definition, resolution of these implications brings it to the same state: 0.5 * 1.0 + 0.5 * 0.0 = 0.5, so any further resolution will again reach the same state, whereas using any other value than 50% will cause it to oscillate. ... Weird. - Rainwarrior 19:28, 12 July 2006 (UTC)

[edit] A closer and clearer Russell paradox by Ali nour mohammadi sharif university of tehran

we say that sets A1,A2,...,An is a chain of set A1 if A(i+1) be in A(i) for i=1,2,...,n-1 and chain can be infinite(in this case each Ai has an infinite chain). Let B=set of All sets that have no infinite chain ,so B has no infinite chain. so B is in B ,but in this case B has the infinite chain BBBB... And this is Paradox. --213.217.57.212 17:53, 17 July 2006 (UTC)onourmohammadi@yahoo.com

[edit] Urban Legend

There is an urban legend, at least at my undergraduate school, that several mathematicians killed themselves after hearing about Russell's Paradox. Probably not true, but there aren't many good urban legends about math. Has anyone else heard this?

[edit] what?

Russell's paradox came to be seen as the main reason why set theory requires a more elaborate axiomatic basis than simply extensionality and unlimited set abstraction. The paradox drove Russell to develop type theory and Ernst Zermelo to develop an axiomatic set theory which evolved into the now-canonical Zermelo–Fraenkel set theory.

not that my english is that bad but....is that english?--Lygophile 09:26, 13 November 2006 (UTC)

Seems OK to me. Any particular trouble with it? EdC 09:42, 17 November 2006 (UTC)