# How do we know that we'll never prove a contradiction in Math

I know that we can prove a contradiction in naive set theory.

Let D be a set of all sets that don't contain itself. Say D does not contain D. Then D contains D. That means D contains itself. A contradiction. Hence, D contains D. But that means D doesn't contain itself. That means D doesn't contain D again. But we presume D contains D. So another contradiction. Because either D contains itself and D does not contain itself is false, we're pretty much stuck.

So, set theory is pretty much upgraded to kingdom come to prevent this so called contradiction. I am still unsure how after so much upgrade the contradiction is gone.

How do we know that there will be no contradiction for group or other theory? How do I know if that from some axioms like commutative, associative, have identity, etc. suddenly I found out that A is a group and not a group or something like that.

Note: The problem with one contradiction is if you can proof one you can proof anything. Say I want to proof 1=0. Say 1 is not 0. Now, let Z be a set of all sets that doesn't contain it self. Yada yada yada... Contradiction. Hence, 1=0. The sun also rises in the west (at least for the last 300 years)

-
The contradiction from naive set theory I think you are trying to demonstrate is Russell's Paradox, which defines a set $R$ to be the collection of all sets $x$ such that $x \notin x$ holds. Then it can be shown that $R \in R$ iff $R \notin R$. (You have worded it slightly incorrectly in the second paragraph.) –  Arthur Fischer Mar 14 '12 at 10:53
Yea. Russel's paradox. I am trying to pull that out my self. I think there should be a bracket on my proof. But it's essensialy the Russel's paradox. Axioms are true in a very different sense than physics laws is true. I want to know how mathematicians see that difference. –  Jim Thio Apr 2 '12 at 7:58
A set $D$ that doesn't contain itself is not contradictory. In the usual axiomatization of set theory, all sets are of this form. What is contradictory is the existence of a set of all sets that do not contain themselves. –  Michael Greinecker Apr 8 '12 at 12:00
Oh ya. Thanks for pointing that out. Yes it's russel's paradox. –  Jim Thio Apr 10 '12 at 2:53

The contradiction you mention is not limited to set theory: consider the statement "this statement is false". If it is true then it is false, and if it is false then it is true.

Does this imply that language is contradictory? No. What it does is to show that you cannot expect every sentence to have a truth value.

In a similar way Russell's Paradox, as your contradiction is known, only shows that you cannot go happily saying "let $D$ be a set such that this and that" and always expect it to make sense. "Naive" set theory was indeed naive.

Regarding the strength of math as a whole, the lack of formal proofs of consistency is not ideal; but there are so many connections between diverse areas and even between abstract math and real-world experience that it is very unlikely that a hidden contradiction would be there lurking to come up to the light and make the whole bulding crumble.

-
Not sure I agree with your conclusion. The same could have been said of mathematics prior to Russell's proof. –  Patrick Mar 14 '12 at 17:46
Of course. But what problem did Russell's Paradox cause? What theorems had been proven that were shown contradictory by the paradox? The only role played by Russell's Paradox is to show that one has to be careful with the definition of set. Exactly the same way that one has to be careful with the definition of "statement" in logic. –  Martin Argerami Mar 14 '12 at 18:16
I know what you're driving at and I more or less agree. But if there is a contradiction, then it's very easy to prove that every statement is both true and false. So from that standpoint, all the proved theorems were shown to be false (as well). –  Patrick Mar 17 '12 at 21:26
you proof one contradiction and you can proof anything. –  Jim Thio Apr 2 '12 at 8:03
Very good answer. So now we have Martin's paradox. Let B = "This statement is false". Is B true? –  Jim Thio Apr 2 '12 at 8:06

This really isn't an answer to the question posed, but a response that is much too long for a comment.

You (Jim Thio) state that, "[S]et theory is pretty much upgraded to kingdom come to prevent this so called contradiction." I would argue that almost the opposite happened.

Cantor's original definition of a set was as followed (translated from the original German by someone other than myself):

By a set we mean any collection $M$ into a whole of definite, distinct objects $m$ (which are called the elements of $M$) of our perception or of our thought.

This definition (and the implicit set construction principles) are about as wide ranging and general as possible. Any sort of collection of objects you can think has mathematical existence as a set. Cartesian products are sets. Unions of sets are sets. There is a set of all ordinals. And finally there is a set of all sets, and the various "subsets" of this are sets.

What Russell's Paradox (and others, such as Berry's Paradox) showed is that far from being able to posit the existence of sets with abandon, one has to be careful about set existence/construction principles. The various axiomatizations of set theory are then a description of the sorts of sets that one can posit into existence (this includes the operations we can perform on sets to yield another set).

So while modern axiomatizations are undoubtedly more complicated than the naive conception of a set, what it comes down to is a restriction of the sorts of collections that may rightly be called sets. On the bright side, these axiomatizations imply that virtually any collection that you meet in the various areas of mathematics are sets. We may then ignore the particulars of the axiomatizations when constructing, say, the set of extreme points of a convex subset of a topological vector space, or the set of all smooth functions $\mathbb{R} \to \mathbb{R}$.

As a final note (and something actually connected to the specific question asked), I recommend that you seek out a paper by the late George Boolos entitled "Gödel's Second Incompleteness Theorem Explained in Words of One Syllable". The first page gives a very brief and readable account of why -- unless our conception of mathematics becomes drastically different -- we cannot know that we are free of contradictions.

-

To be more precise than LLLLL, we cannot prove in ZFC (for example) that ZFC itself will not result in a contradiction; or if we could, this would show that ZFC is inconsistent. This is Gödel's Incompleteness Theorem.

But say we have a logic system where an is axiom encoded to look like "ZFC is consistent", then this logic system will "prove" that ZFC is consistent. But is this new logic system consistent...? You begin to see the problem.

-
Your answer first was confusing because you are referring to LLLLL (the person who answered here) and ZFC (I assume you are referring to Zermelo–Fraenkel something?). Always appreciate others answers as well. –  Kirthi Raman Mar 14 '12 at 12:27

We don't. In fact, we cannot know, we know that we cannot know, and we have a proof that we can never prove there is no inconsistency. We'd have to use some external reasoning apparatus to assert that math is consistent. But then we wouldn't be able to prove that old math plus new apparatus is consistent. We'd have to add that as a new axiom, and then...

This is known as Gödel's Incompleteness Theorem.

-
+1 for everyone. This is the most direct answer. Thanks. By a suspended user. Yea Godel shows up several times. –  Jim Thio Apr 2 '12 at 8:04

If there is a model, then there is no contradiction. So that is how we know there is no contradiction for group theory: because there is a group.

-
But what if there is a contradiction in how we deduce things, in how we do mathematics? What if group theory is inconsistent and the reason we assume it works is because our inconsistency proves everything, including group theory's consistency (which is false)? –  Asaf Karagila Apr 10 '12 at 6:55