Proving Independence of Axioms by Exhibiting Models Which Don't Satisfy Our Intuition - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:53:05Z http://mathoverflow.net/feeds/question/34767 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34767/proving-independence-of-axioms-by-exhibiting-models-which-dont-satisfy-our-intui Proving Independence of Axioms by Exhibiting Models Which Don't Satisfy Our Intuition David Corwin 2010-08-06T13:52:41Z 2010-08-16T18:04:13Z <p>I recently saw the proof of the independence of ZF (with allowance for multiple empty sets) and AC. The proof constructed the model based on a set theory generated by infinitely many empty sets and then restricted this model to those with a hereditary finite basis (HFB). However, this model did not seem to conform to my intuition about set theory. Rather, it seemed like an odd construction which is <em>not</em> what I think of as the theory of sets, yet which did in fact formally satisfy all the axioms of ZF as well as negation of AC. Although we may have proved that the ZF axioms do not imply choice, I do not feel at all convinced that AC does not have to be true in set theory. Rather, although what I'm about to say is imprecise, I feel that in any model of set theory which is actually like our intuitive notion of set theory, AC should be true.</p> <p>Similarly, at <a href="http://mathoverflow.net/questions/21367/proof-that-pi-is-transcendental-that-doesnt-use-the-infinitude-of-primes" rel="nofollow">this thead</a>, one constructed a model of arithmetic (without induction) in which $\pi$ is rational. However, I know the integers very well, and even though this model satisfied the axioms of the integers, these were intuitively clearly not the integers.</p> <p>My question is, I feel that with my of these independence proofs, if you precisely identify the notion we're talking about (like the integers, set theory), then these pathological models don't exist. Maybe it means these axioms aren't sufficient - are there any better sets of axioms? Or maybe it means that we should be focusing on particular models rather than theories in general (as in, a different philosophy of doing mathematical logic)? I'm trying to understand whether there's a way to precise-ify things so that any independence proof we do really shows that something is independent of the actual thing we're considering (not some set of axioms which happen to conform to that thing). This is guided in part by the intuition that if we really know which mathematical object (or collection of objects) we are talking about, then in some sense, any statement should simply either be true or false.</p> http://mathoverflow.net/questions/34767/proving-independence-of-axioms-by-exhibiting-models-which-dont-satisfy-our-intui/34774#34774 Answer by Carl Mummert for Proving Independence of Axioms by Exhibiting Models Which Don't Satisfy Our Intuition Carl Mummert 2010-08-06T15:18:27Z 2010-08-06T15:18:27Z <p>You have run into one of the main themes of contemporary logic: the difference between "truth in the standard model" and "provability". This is an extremely deep issue, so I'm sure other people will also have something to say about it. </p> <p>The difficulty with focusing only on standard models rather than on theories in general is that essentially the only way to convince someone else that the standard model has some property is to prove it, and then you're back to the problem of choosing axioms. For example, the reason you know &pi; is transcendental is because you recognize certain axioms that are true in the standard model and which allow you to prove &pi; is transcendental. If someone else did not already believe &pi; is transcendental, you would try to convince them by getting them to accept the axioms you used to prove it. </p> <p>In some cases, we can make a set of axioms that completely describes a standard model. For example, there are complete axiomatizations of Euclidean geometry, which allow you to prove any statement in the language of geometry that is true about the standard Euclidean plane model and disprove any statement false on it.</p> <p>But for other models, like the standard model of the natural numbers, there are theorems that show we can never find an effective, complete, consistent axiomatization. The axiom systems we use to study these models are called "essentially incomplete". For these models, it isn't clear in what sense you could make the underlying concept (e.g. "natural number") precise enough to eliminate independence results. </p> <p>That being said, one nice property of models in classical logic is that any sentence in the language of the model is either true in the model or false in the model. So there is no concept of independence from a model. The downside is that for models like the standard natural numbers, it takes stronger and stronger axiom systems to determine more and more true statements about the model. </p> http://mathoverflow.net/questions/34767/proving-independence-of-axioms-by-exhibiting-models-which-dont-satisfy-our-intui/34776#34776 Answer by Andreas Blass for Proving Independence of Axioms by Exhibiting Models Which Don't Satisfy Our Intuition Andreas Blass 2010-08-06T15:25:33Z 2010-08-06T15:25:33Z <p>I'm inclined to agree that "if you precisely identify the notion we're talking about (like the integers, set theory), then these pathological models don't exist." The problem is that it's not so easy to precisely identify such structures. </p> <p>The usual approach to precisely identifying a structure is to write down its essential properties, the axioms governing it. To make use of such axioms, we need to derive consequences from them, and here we find ourselves in a dilemma. On the one hand, there is a perfectly clear notion of logical deduction in the context of first-order logic. On the other hand, the L"owenheim-Skolem-Tarski theorem guarantees that, in the context of first-order logic, there will be unintended models of the axioms (as long as the intended model was infinite). So first-order logic does not accomplish what is wanted.</p> <p>So let's use second- (or higher-)order logic insterad. (Here you can quantify over subsets of the structure, and those quantified variables are assumed to really range over <em>all</em> subsets, not just, say, definable ones.) Now structures like the integers and the reals can be uniquely specified. But there is no complete deductive system for second-order logic. (More precisely, the set of valid second-order sentences is not recursively enumerable.) Furthermore, the intended meaning of second-order quantifiers depends on the general notion of "set," which is one of the concepts that we were hoping to precisely specify.</p> <p>So the bottom line, in my opinion, is that, while we might want to build mathematics on the basis of unique specifications of the relevant structures, it simply can't be done, at least not if we want the specifications to contain actual information about the structures (as opposed to just saying "I mean the genuine integers, you know") and to be able to deduce the logical consequences of that information.</p>