GTX0 NewestRepliesHottestMy Active
NIFE UpdatesRoadmapRequests | HelpDiscuss Game Worlds

Proving Something is Independent of our Axioms (Basic Idea for a Talk)
Posted: Posted November 21st, 2013
Edited February 8th, 2015 by Yeano

My university has a mathematics colloquium called the "Student Colloquium" which is run by students with student presenters and only students attend. It's a nice way for students to get practice giving talks.

I am thinking about perhaps giving a talk on how to prove that something is independent of our axioms (for example - how would anyone even begin to go about proving that the Axiom of Choice is independent from ZF set theory.)

Tell me if this sounds like a good outline for the talk.

Begin with an introduction about how we know certain statements are independent of our axioms - for example the Axiom of Choice and the Continuum Hypothesis.

Then I would introduce First Order Logic. Explain what a language, theory, proof, interpretation, and model are.

As a nice example, I would use the following theory, G, which I would call the Theory of Groups, having the following axioms:

(G1) [math](?x)(?y)(?z)((xy)z = x(yz))[/math]

(G2) (?x)(xe = ex = x)

(G3) (?x)(?y)(xy = yx = e)

With our language consisting of e, times, and equals (with of course a bunch of constants at our disposal).

I would then illustrate how truth is not really in the axioms, but is more in the interpretation of the language.

I would give an interpretation of our language being the set of integers under multiplication, and show how some of our axioms are false in this interpretation.

I would then give an interpretation of the integers under addition, and show how our axioms are true in this interpretation, and explain that this means that our interpretation is a model of the theory G.

Next, I would discuss how this initially seems counter-intuitive! We can only claim something is true if we can prove it true, but here I am claiming that truth is in the model, not in the proof.

I would then rectify this conundrum by explaining the idea behind the Completeness Theorem, and how it connects proof with truth (being that a statement is provable in a theory K if and only if it is true in every model of K).

I would then go back to my theory G, The Theory of Groups, and make the claim that the following statement is independent of G:

(A) (?x)(?y)(xy = yx)

Now, most people would assume this statement is false, but recall that truth is in the model, not the axioms.

I would show an abelian group, which means that (A) is true in some model of G, and I would show a non-abelian group, demonstrating that (A) is false in some model of G.

By way of the Completeness Theorem, this shows that neither (A) nor (A) is provable in G, and thus, is independent from G.

Now, we could extend our theory G by adding the (A) as an axiom, and we would still have a consistent theory (The Theory of Abelian Groups, AG), and we could also extend G by adding (A) as an axiom, and we would still have a consistent theory (The Theory of Non-Abelian Groups, NG). Of course, the models of these theories would be different from each other! There would be models of G which are not models of AG and models of G which are not models of NG. And of course, since truth is in the models, we are essentially restricting what is true about our theory in general.

I would then very quickly mention that this is the basic technique used to prove that a statement is independent of a set of axioms - finding a model in which it is true and one in which it is false. Now, the models that Godel and Cohen used to prove that the Axiom of Choice and the Continuum Hypothesis are independent of ZF are much, much more complicated than what we did, but it's the same basic idea. It's just the details you need to show it are a lot more difficult.

What do you think?

There are 3 Replies

I would go to that talk. Sounds like you've put a lot of thought into this.

Posted November 21st, 2013 by EN

Thanks, EN.

Posted November 23rd, 2013 by Yeano

I'm stickying this thread because maybe it needs further attention. Another read.

I removed the old sticky thread on what we're interested in since it's gone and Xhin hasn't resurrected it in many months.

Posted June 21st, 2014 by The Fly
Site Rules | Complaints Process | Give Feedback Facebook Page
GTX0 © 2009-2019 Xhin GameTalk © 1999-2008 lives on