# How to be sure a contradiction is not possible?

I have written a formal proof of the theorem:

$$\forall U \exists r(\forall a(a\in r \leftrightarrow (a\in U \wedge a\notin a)) \wedge r\notin U \wedge r\notin r)$$

(Somewhat non-standard notation: & = $\wedge$, | = $\vee$)

It seems you can select a subset much like the so-called Russell Set from any set $U$ without obtaining a contradiction. How can I be certain?

Edit: Apparently you can't be certain. See my own answer below.

-
A formal proof from what basis of axioms? –  Jason DeVito Jun 25 '12 at 16:07
It's really unclear what you mean by "the Russell set." The $r$ that you are asserting here is just a subset of $U$, so it is not the "Russell set" that normally leads to any contradiction. Basically, you are saying, for any set $U$, you can find the subset $r$ of $U$ of elements which don't contain themselves. This doesn't mean the same $r$ satisfies this property for all $U$. –  Thomas Andrews Jun 25 '12 at 16:13
@Dan: I have proved that your statement is not contradictory by exhibiting a structure in which it is true. If "does not lead to a contradiction" means something other than this, you'll have to tell us what that is. –  Chris Eagle Jun 25 '12 at 16:38
@DanChristensen The only way to prove this is to prove the consistency of some set of axioms. In and of itself, there is no contradiction. –  Thomas Andrews Jun 25 '12 at 16:38
From the comments to my answer, you seem to think you have a particular contradiction you can show from this statement. If so, present that, and ask us what is wrong with the argument, don't ask us to show the consistency of your ill-defined axiomatic system. –  Thomas Andrews Jun 25 '12 at 17:20

First, the question is vague. You are saying:

I have proven a theorem $T$ in some axiom system. How do I show that $T$ does not lead to a contradiction, given that another statement, $T'$, that looks superficially similar, does lead to a contradiction.

If you want us to check your proof, which was perhaps your goal, given that you link to your proof, we'd have to know what axioms you are using. That said, the theorem you say you have proven follows pretty much directly from most axioms for set theory. Given that you haven't asked us explicitly to verify your proof, and that is a lot of work, I will not be attempting that.

Given that you have proven the theorem in some axiom system, it technically "leads to a contradiction" if and only if the original axiom system leads to a contradiction. Given your comments, you are not asking about the consistency of the original axioms, so I will skip this.

Perhaps you mean, "How do I prove this does not directly lead to a contradiction?" The only way to do that is to define "directly," which is actually fairly hard, and is impossible without some explicit axioms.

Finally, perhaps you mean "Why does $T'$ lead to a contradiction, but $T$ doesn't?" This is not a formal question, but it could be a request for clarification of the differences between the two statements that causes on to yield a contradiction but not the other.

So let's write $T'$:

$$\exists R: \forall a: a\in R \iff a\notin a$$

Why does this yield a contradiction? Because if such an $R$ exists, we can ask "Is $R\in R$?" and we get the usual contradiction: $R\in R \iff R\notin R$.

However, your statement, $T$, does not have such a paradox, because it can be rephrased as:

$$\exists R:R\notin R \land R\notin U \land (\forall a: a\in R \iff (a\in U \land a\notin a))$$

Where $U$ is some set. But the reason there is no contraction is the simple addition of that condition on $R$: $a\in U$. There is no contradiction because the requirement "$a\in U$" gives you an "out." That "out" is why the $T$ does not lead to a contradiction, but $T'$ does. It is the difference between $a\notin a$ and $a\notin a \land a\in U$. Once you have that condition, $a\in U$, you lose the contradiction.

Note that $R$ depends on $U$. An $R$ for one $U$ is not equal to the $R$ for another $U$. There is not one universal set $R$ which applies to every $U$ - the conditions, in particular, make it clear that $R\subset U$. (This was why I thought you might be confusing the difference between $\forall\exists$ nd $\exists\forall$ in my early answer - a common mistake.)

As I mentioned in the comments, you re-gain the contradiction if you assert the existence of a universal set: $\exists V:\forall a: a\in V$. But that just means that, in this axiom system, that assertion is invalid - you have essentially proven that the universal set does not exist in your axiom system (or your axiom system is inconsistent.)

But again, it is not clear what you are asking. You haven't asked a well-formed question, and most of the answers and comments posted here have been based on efforts to deduce your meaning based on common types of confusion that plague newcomers to set theory and logic. Are you looking for some formal argument? Are you looking just for clarification/elucidation? Are you looking for a review of your proof? Or are you reaching for something else that none of us have quite grasped yet?

-
I'm not sure what you are getting at, Thomas. If you postulate $\forall a (a\in r \leftrightarrow a\notin a)$, you can derive $r\notin r$. You can also derive $r\in r$. This wouldn't mean that your axioms are inconsistent, only that $r$ cannot exist. I want to know if my construction of $r$ will lead to a similar contradiction. –  Dan Christensen Jun 25 '12 at 16:50
How do you derive $r\in r$? You can't, because $r\notin U$, it is a subset of $U$. The Russell paradox occurs because you construct a set $r$ from some "universe" set $V$ which has the property, $\forall x:x\in V$. If such $V$ exists, you set $U=V$ and then the $r$ you get is necessarily in $U=V$, so your condition becomes $a\in r \iff a\notin a$. Then you asks "Is $r\in r$?" and reach a contradiction. But under the condition above, you have an "out": $r\notin U$. –  Thomas Andrews Jun 25 '12 at 17:13
Thomas, I am talking about the usual contradiction you get in the standard presentation of Russell's Paradox: From $\forall a(a\in r \leftrightarrow a\notin a)$, you obtain the contradiction $r\notin r$ and $r \in r$. There isn't usually any mention of a universal set. Perhaps I confused matters at the end by saying "my construction of $r$" in which I do refer to a universe $U$. Sorry. –  Dan Christensen Jun 25 '12 at 17:29
But you don't have $\forall a (a\in r \iff a\notin a)$. So that contradiction is easily bypassed, because your theorem states $a\in r\iff a\notin a \land a\in U$. So the standard contradiction is easily bypassed. The point is, you can't show that a particular statement "does not lead to a contradiction" without showing your entire axiom set does not lead to a contradiction. –  Thomas Andrews Jun 25 '12 at 17:32
But that notion requires a universal set because you can write $P(x)$ to be some universally true statement, like $x\notin \emptyset$ –  Thomas Andrews Jun 25 '12 at 17:47

As far as I can tell, your question is whether the theory (in the language whose only nonlogical symbol is the binary relation-symbol $\in$) consisting solely of the axiom schema of separation is consistent. This is obvious: it has the empty structure as a model. Another simple model (if your logic doesn't allow empty structures, say) is the one-element structure $\{\varnothing\}$ (with $\varnothing \in \varnothing$ defined to be false).

-
Chris, see my first comment to you above. –  Dan Christensen Jun 25 '12 at 16:34
Strictly speaking, if, after postulating the existence of $U$, I did get a contradiction from my construction of $r$, then, even if the axioms of this system were consistent, no sets would exist! (This system doesn't actually assume the existence of any sets, not even the empty set.)