-5
$\begingroup$

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)$$

See: http://www.dcproof.com/SeparationAxiom.htm

(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.

  • 3
    A formal proof from what basis of axioms?2012-06-25
  • 1
    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$.2012-06-25
  • 0
    @JasonDeVito Like the notation, the axioms are somewhat non-standard. The axioms of logic used are based a form of natural deduction of the kind implicit in most undergraduate mathematics textbooks. The only axiom of set theory I use is a subset axiom like the Axiom of Separation in ZF.2012-06-25
  • 0
    It's clear that the theory consisting solely of separation is consistent. For example, $\{ \varnothing \}$ is a model of it.2012-06-25
  • 0
    @ThomasAndrews Yes, the $r$ would, of course, depend on $U$. I only meant to suggest similarities to the Russell Set.2012-06-25
  • 0
    @ChrisEagle Sorry, I didn't mean to suggest there aren't other set-theoretic axioms in this system. I meant that the only set-theoretic axiom *used in this proof* is a subset (or separation) axiom.2012-06-25
  • 0
    @Dan: Then what is your actual question? It's axiom systems that are or are not contradictory, not proofs.2012-06-25
  • 0
    @ChrisEagle I want to show that the existence of this subset $r\subset U$ does not lead to a contradiction in the same way that the existence of the Russell Set does.2012-06-25
  • 2
    @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.2012-06-25
  • 2
    @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.2012-06-25
  • 3
    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.2012-06-25
  • 0
    @ThomasAndrews I was able to obtain $r\notin U$ and $r\notin r$. I was wondering if I could also get $r\in r$. If that is possible, it would mean big trouble for not only for the system I use here, but for ZF theory as well.2012-06-25
  • 0
    Of course there might be a contradiction in ZF. However what if *your* proof software is to blame?2012-06-26
  • 0
    @AsafKaragila The subset (separation) axiom in my system is meant to be identical to that in ZF. And the other axioms and rules used there are just those commonly used in mathematics textbooks. So, if an inconsistency did arise, it should be fairly simple to determine whether it was a result of a software problem, or whether it was a deeper problem that would also arise in a purely ZF implementation.2012-06-26
  • 0
    @Dan: Be forewarned, every software has bugs. Not every bug is easy to spot.2012-06-26
  • 0
    @AsafKaragila The specs for every axiom and rule are fairly simple. That is the beauty of any formal system. It should be easy to manually verify every line of a proof if some inconsistency is discovered.2012-06-26
  • 0
    And if the proof is $100,000$ steps long? What if there is a memory leak at the $60,000$-th step. Can you trace through that manually and see? If so, you are wasting your time with math software. I am sure every software developing organization would hire you for ridiculous amounts of money.2012-06-26
  • 0
    @AsafKaragila If you can write it, I can verify it. I ask only that you try to break it down into a series of smaller proofs of not more than about 1,000 lines each. (Anyway, there's that moderator again! Gotta go.)2012-06-26
  • 1
    Let me just finish this discussion with the remarked that if I could write a proof for the inconsistence of ZF, I would probably submit it as a dissertation and skip all those years of extensive study instead. Good for me, I cannot write such proof so I can spend a few more years as a student meddling with ZF.2012-06-26

3 Answers 3

3

I'll rewrite my answer.

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?

  • 0
    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.2012-06-25
  • 0
    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$.2012-06-25
  • 0
    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.2012-06-25
  • 1
    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.2012-06-25
  • 0
    And any discussion of the Russell set that does not first talk about the idea of "the set of all sets" is misleading you. The notion that the Russell set ought to exists springs from the intuition that such a universal set exists. If such a universal set exists, your theorem does, indeed, yield contradiction, because setting $U$ to be that universal set is what yields the contradiction.2012-06-25
  • 0
    As I understand, the notion that the Russell Set ought to exist springs from the notion that a set exists simply because we can describe it, that is, for every 1-ary predicate $P$ there exists $\{x \mid P(x)\}$ It doesn't require any notion of a universal set.2012-06-25
  • 2
    But that notion requires a universal set because you can write $P(x)$ to be some universally true statement, like $x\notin \emptyset$2012-06-25
  • 0
    Again, a statement that leads to a contradiction need not be the result of inconsistent axioms. Proof by contradiction is a standard method of proof. (No further comment. Moderator getting antsy!)2012-06-25
  • 0
    It does if you've proven the statement in the axiom system you say you have proven the statement in.2012-06-25
  • 0
    But I haven't proven the existence of $r$. (Last comment for sure -- don't want to "chat".)2012-06-25
  • 1
    I think you might want to start considering the possibility that the word you are writing don't actually mean what you think they mean. I'm not trying to be snide, but the initial question is vague (how do I show a theorem I've proven doesn't lead to a contradiction the way an unrelated statement leads to a contradiction?) Several people have tried to guide you into clarifying your question, using common understanding of what you might be trying to ask, but you seem to be missing the plot. Were you just asking us to check your proof?2012-06-25
2

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).

  • 0
    Chris, see my first comment to you above.2012-06-25
0

If it's not bad form to answer your own question...

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.)

Bottom line, we have no proof that such a contradiction is impossible. Such a contradiction would be problematic not only for the system I use here, but for the standard ZFC set theory as well. With over a century of extensive research behind the ZFC theory, however, such a contradiction seems highly unlikely.

Thanks all for your, ummm.... patience.