Talk:Russell's Paradox

From ProofWiki
Jump to navigation Jump to search

The issue isn't really allowing sets to contain themselves, it's allowing the instantiation of sets defined by any property. Assuming just unrestricted comprehension (UC), existential instantiation (EI), and universal-instantiation (UI), we can do this:

\(\displaystyle (1)\) \(\) \(\displaystyle \exists y \forall x (x\in y \leftrightarrow x \notin x)\) (UC using the property given by $x\notin x$)
\(\displaystyle (2)\) \(\) \(\displaystyle \forall x (x\in R \leftrightarrow x \notin x)\) (EI (1) y as R)
\(\displaystyle (3)\) \(\) \(\displaystyle R\in R \leftrightarrow R \notin R\) (UI (2) x as R)

This is already a contradiction, modulo some propositional logic stuff, using the $P\vee \neg P$ tautology and deriving a statement in the form $Q \wedge \neg Q$ if you want.

Using the axiom of foundation (AF), we could mess around with (3) a bit, but this won't prevent a contradiction; it's already inherent at step (1). It gets us there a different way. For example:

\(\displaystyle (4)\) \(\) \(\displaystyle \forall x (x\notin x)\) (as a consequence of AF)
\(\displaystyle (5)\) \(\) \(\displaystyle R\notin R\) (UI (4) x as R)
\(\displaystyle (6)\) \(\) \(\displaystyle R\in R\) (3 and 5)

Russel's paradox shows us that any theory containing unrestricted comprehension is already inconsistent. Adding axioms doesn't resolve inconsistency; unrestricted comprehension has to be repealed to avoid this. ZFC does this by using a restricted version of comprehension instead of this one, so that we can't justify (1) from an axiom.

-- Qedetc 19:17, 22 June 2011 (CDT)

Amended comment. How's that? Feel free to add the material on this page as another consequence of UC, on another page in the "Paradoxes" and "Naive Set Theory" categories, perhaps. --prime mover 00:24, 23 June 2011 (CDT)

I've edited it, and I'll try to justify not mentioning the axiom of foundation in it (looking back up there, it probably wasn't clear what I was complaining about):
While adding axioms can constrain the models of a theory (more things to satisfy), it actually removes constraints on proofs and lets us do more (more ways to justify statements). Because of this, since we're essentially discussing how to prevent the proof of a contradiction, it isn't right to say that the axiom of foundation is a constraint or suggest that it prevents steps in the argument.
ZFC first tries to avoid the paradox by not having a certain axiom. Then, after the problem is cut out, it carefully reinserts enough axioms to build the sets we want in order to have a worthwhile theory, hopefully not reintroducing any paradoxes.
If my claim about about adding axioms removing constraints on proofs seems fishy, remember that one way of defining valid proofs are as finite sequences $(S_1, \dots, S_k)$ of statements where each $S_i$ is either an axiom or follows from earlier statements in the sequence by a rule of inference. So, two points can be made:
1) Any valid proof using axioms from a set $A$ is also a valid proof in any larger set of axioms $A'\supseteq A$. This is because if $S_i$ is an axiom in $A$, then it is also an axiom in $A'$.
2) If $A'$ is a proper superset of $A$, then there are valid proofs using $A'$ which are not valid proofs using $A$. For example, just take any proof over $A$ and stick in an extra statement at the front which is an axiom from $A' - A$.
Together those tell us that adding axioms means we get to keep all the proofs we had, but also get some more proofs (and consequently maybe some more theorems).
--Qedetc 03:32, 24 June 2011 (CDT)

Also, I should point this out since it might be a more convincing point (I had hinted at this in the discussion page for the set of all sets):
These are equivalent:
A) The axioms of ZFC (including the axiom of foundation) are consistent.
B) The axioms of ZFC, without the axiom of foundation, but with a (certain) axiom that implies the negation of the axiom of foundation, are consistent.
Hopefully that made sense. I'll confess that I haven't actually gone through a proof of this. I'm trusting some comments in Jech and Hrbacek's set theory book. It looks like this is the content of chapter 3 of a paper by Aczel. A very skimpy wikipedia article on the axiom he uses is here. The paper is listed as a reference at the bottom.
--Qedetc 13:21, 24 June 2011 (CDT)
I wonder whether this page is trying to do too much? Perhaps all we need to do is say: "This is an antinomy arising from the comprehension principle" and leave it at that. If we then decide to put another page together which analyses all this stuff in detail (a good move IMO) then we can link to it.--prime mover 13:55, 24 June 2011 (CDT)

The comment section could probably be broken off into a broader discussion of attempts to formalize mathematical reasoning while avoiding arguments like this. I don't know enough about other systems to say much more than what I've said here unfortunately.
There are definitely some nuances hanging around all of this that would be good to ramble on about. I think the source of some confusion is that the argument in the proof on this page is extremely similar to the proof that a set of all sets can't exist in ZFC. Russell's paradox kind of has multiple uses, depending on what framework you're in. I think getting a sense of all of this requires a decent amount of discussion and links back to definitions in logic.
I don't know if it's currently overreaching; I came here having talked about a bunch of this before, and now that I've edited it, I've also conformed it to what makes sense in my head. So it seems okay to me, but that's clearly a biased view. It would be good to get comments from some other members.
--Qedetc 15:23, 24 June 2011 (CDT)
No problem with any of this, I just think it belongs on a different page. Perhaps we ought to wait for someone who knows enough about other systems to attempt to put it into whatever different contexts there are. --prime mover 16:11, 24 June 2011 (CDT)