First, a little background. Frege’s logicist program is quite different from what is done in analytic philosophy today, and from what is done in ‘foundations’ today. In particular, Frege opposes the use of mathematical axioms. Instead, he wants to say mathematics (although his book on the subject covered only arithmetic, he indicated a plan for future books to cover all of existing mathematics) is just fancy logic. All you need to do, he says, is recognize the principles of logic (giving basic logical principles) and mathematics will, in a sense, pop out. Basic logical principle 5 is supposed to be the basic rule of thought (again, or of reality, I’m not sure what he held here) that justifies the use of sets in mathematics (there was not yet a distinction between classes and sets, that is part of ZF). It is phrased as : the value-range of a function f is the same as that of a function g iff for every x, f(x)=g(x). This implies that, in philosophical terms, for every sense there is an extension, and an object is in the extension of the characteristic predicate iff it has the sense of the predicate. Today, we recognize this as having the same theory as an unlimited axiom of comprehension - that is, for any description, you can form the set of objects meeting that description. It is from here that Russell derives Russell’s paradox by describing ‘things which are not elements of themselves.’
In ZF, it is believed that we capture the intuitions and things Frege wanted without the paradox by the subset axiom - for any set S and a predicate, you can form the subset of S whose elements are st they make the predicate true. This is sometimes referred to as the axiom of limited comprehension, and is what allows the distinction between sets (objects that may be worked with mathematically) and classes (which are simply descriptions without extensions.)
Thanks again! The Wikipedia article refers to a set such as “the set of all non-squares,” but I’m immediately thinking, “What is the universe of discourse?!” Is the difference between a set and a class basically that the universe of discourse (or whatever the analog may be in math) is delineated or defined, while for classes it is not? It seems that if the universe of discourse if clearly defined a set could not contain itself in the first place. This has been bothering me for several weeks.
Well, those are logically possible. What I was pointing out is that there are some things we can say in language that appear normal and well-formed, but actually are incoherent or logically impossible. (Interestingly, if you write a visual representation of the statement, “There is a website that links to every site that does not link to itself,” you get an infinite series of frames that looks like what you see when you face two mirrors at each other. Same with other paradoxes like, “This sentence is false” and “If this sentence is true, Santa Claus exists.”)
Sorry, I was completely unclear. This question have nothing to do with Russel’s paradox or even paradoxes in general. The square rectangle, or circular oval, is a semi-classic object oriented modeling problem (in programming).
That would make your answer even more interesting. =) Implementing a class hierarchy some programmers try to think in concepts of “contracts”. Each subclass has to promise not to break any contracts of it’s superclass. Let’s say you’re developing a drawing program with some vector shapes. When you add the square shape it’s easy to think like: “A square is a Rectangle which is a Shape”. Rectangle sets up a contract that it should have four sides and right-angles. It also makes sense to add to the contract that when the length of one side is changed, the length of its opposite side is also changed, but not the two other sides. A square, naturally has to violate that contract…
The approach that says that by defining the universe, you can simply outlaw self-membership, is actually the approach that Russell took to Russell’s paradox. Like Frege, Russell was in the logicist project, and hence wanted to preserve as much of Frege as possible. It is Russell that Godel addressed in his famous theorem, although it turned out to apply to formalism a la Hilbert as well. There have been two problems with Russell’s theory of types, the first being Godel’s theorem just mentioned, the other (more fatal as a mathematical approach) is that is outlaws much of actually existing mathematics.
In axiomatic mathematics, on the other hand, such as ZF, the universe of discourse is simply those things that come into existence through the axioms. It turns out, though, that axiom sets have multiple models, hence we don’t know certain things about the universe (put Platonically. For a formalist, they just describe multiple universes.) For the purpose of making a set, though, it doesn’t matter what the universe of discourse is. Some sets come from axioms, and the universe is irrelevant. Others come from other sets, and all those operations are absolute. It doesn’t matter what universe you’re working in if you say A is the subset of B st…all that matters is what is in B. The set of all non-squares only really makes sense out of the naturals, or the integers - out the reals, what do you mean by square?
A class, though, is in mathematics treated as non-existent. As math is actually done, proper classes (sets are also classes, but existent ones) are formed by taking all or most of the universe. For instance, every ordinal is a set - but the group of all the ordinals, while it can be described {x:x is an ordinal} is not specified by any axiom to exist. Thus, we treat it as simply a predicate, and do not assume that the collection it implies actually exists. This doesn’t exactly solve philosophical problems, it does let us do math without them getting in our way.
That’s quite a relief, as that’s how I wanted to think about it.
Right, just definitions and axioms.
Great, no need to bother with that then. But about Gödel now, Wikipedia says in one of its articles about Truth,
This implies that “true,” since Gödel, means something other than “provable from the axioms.” Yet as I understand, the Gödel sentence G in a consistent formal theory T is
G = “G is not provable in T”
Isn’t the idea that G is true but not provable? If so, what is the new notion of true?
Correct, although the = there needs explanation. In any case, here’s the idea. The deductive system used in math can be proven to be both consistent and complete, so if you have a group of axioms and they imply something, then you can prove that thing. What Godel showed to be incomplete is an system of axioms for mathematics - in particular, any useful axiom system. Godel himself was a Platonist, and so he described things this way - there is a real mathematical universe, somewhere, where math happens. We attempt to create an axiomatic system such that, through deduction, we can prove all and only those things that are true in that universe. Here’s an easy way - just make every true statement into an axiom. That works, but we then have an undecidable axiom system. On the other hand, if you want a useful axiom system, it won’t do what you say. Either it will prove everything, or it will fail to prove some true fact about mathematics.
So what does a non-Platonist make of this? It’s harder to describe. From my point of view, axioms define structures (the same as the formalist notion) and we construct axioms to make a mathematical structure model a structure that exists somewhere else - either a thought pattern, or a physical system, or whatever. We want it to model it precisely, and Godel shows that it cannot - there will be facts about the real system that cannot be proven with the axioms, or else the axioms will prove false things about the system. I call my position an Aristotelian position, to distinguish it from the Platonists.
What of a pure formalism? I have no idea what a pure formalist makes of Godel’s theorem. That’s probably why there are so few of them since Godel.
Aren’t those two the same thing? (Logical implication and provability)
But what does “true” mean if not “provable”? OK, from a Platonist perspective I see, but what does a Platonist think of as truth?
Yeah, usually right. (I could make a haphazard mathematical system just for fun, or in hopes it might someday be useful.)
Now this is interesting. I suppose the examples would be things similar to the halting problem?
My apprehension about Gödel’s theorem has been, where is truth being defined, and isn’t truth a norm of assertion? If (1) truth is a norm of assertion (i.e., a statement automatically asserts its own truth by its very fact of being a statement rather than just a free-floating utterance), and if (2) what is true is defined to be simply that which follows from the axioms, then
G = “G is not provable in T”
G = “G is true, and G is not provable in T” [by (1)]
G = “G is provable in T, and G is not provable in T” [by (2)]
Which seems like just a normal contradiction. So either (1) doesn’t hold, (2) doesn’t hold, or the theorem doesn’t hold. Since the theorem has been widely accepted, I can only assume there is broad agreement that either (1) or (2) doesn’t hold. Yet what I’ve looked at seems to indicate there is much debate on such issues. That’s what’s weird.
By logical implication, we mean “Whenever A is true in a structure, then B is true in a structure.” By provable, we mean “can write a formal deduction whose first line is A, every line is an axiom or the result of applying laws of inference to previous lines, and whose last line is B.” We can certainly construct a deductive calculus that is not complete - just take out all the laws of inference.
A Platonist (in math) thinks that a sentence is true just in case the proposition expressed by that sentence (using modern terminology to describe Platonic thought) is a statement that has no counterexamples in the “universe of mathematics” - which is among the forms. Modern Platonists tend not to mention forms, though.
Sure, you could, and attempts have been made to do so - but it turns out that any such attempt tends to model a system of thought, since it’s hard to break out of the way your mind works. Now, some systems - set theory, for instance - were developed to model a system of thought, but turned out later to have physical applications as well (Dr. Long might have something to say on this.)
The fact is, though, that whatever you were hoping to model, it turns out your system has other models that are not similar to it. This is the source of the Skolem paradox.
The halting problem is a corollary of Godel’s theorem in recursion, so yes. It seems to most of us (some would disagree) that before you run the program, it is true or false that it will halt in a finite amount of time. Yet the answer is not computable. This is just Godel’s theorem translated into the language of recursion. How would someone disagree? You could hold that anything not computable is indeterminate - until we run it, there is no answer. On the other hand, a formalist can simply deny that theory of recursion has much at all to do with computers running actual programs.
Even if a statement automatically asserts its own truth - I’d say asserts the truth of its proposition, but whatever - the sentence can be wrong about that, too. Consider the sentence “5 has no successor in the natural numbers.” It asserts its own truth, but it’s wrong about that. Next, it simply isn’t true that to assert your own truth is to assert your own provability. 2 is incorrect. Finally, even if I followed your argument, it would turn out that G is a contradiction, hence a false statement - but then it’s provable.
It seems to me that there are “laws of inference” that are inherent, or simply are, by virtue of how we define the terms. Given A → B and B → C, I don’t think it makes sense to state that without a special law of inference we cannot conclude that A → C. (Is that what you’re saying?) Of course that’s fine in the case where we want to model a special kind of “logic” that only shares the common word but isn’t strictly related to logical reasoning.
If this is in debate, then how do you state the following, which seems to imply that truth is something other than provability (but what?)?
Even kids understand that “You’re not not fat” just means “You’re fat” without a proof, and a proof could add nothing to their understanding or certainty. Adults understand more, and seasoned mathematicians even more. If you told a hyper-intelligent being the ZF axioms and certain definitions, and then later told him an advanced theorem based on those axioms and theorems, he might say, “You already told me that.” So it seems from point of view of a sufficiently intelligent creature, to speak of a theorem as “provable” would be as irrelevant as telling a kid it’s provable that “not not fat” means “fat.” In other words, it seems it’s only our human limitations that make us use a word like “provable” instead of simply “follows from premises.”
Uh oh, another paradox. I’m addicted to these things lately. Will have to check it out.
I’ll have to think about that one for a while.
Yeah, so like “A and ~A” it’s a false statement (I’d say that since it’s a contradiction, it doesn’t follow from any non-contradictory premises).
In Human Action, Mises wrote something to the effect that all mathematical theorems were already contained in the axioms. For reasons I mentioned above (the point of view of a hyper-intelligent being), it seems that provable just means “follows from premises.” So - and this is really what I’m hoping to figure out - if “true” doesn’t mean “follows from premises” then what does it mean? I know there are many theories of truth, but if that debate were at play Gödel’s theorem wouldn’t be so widely accepted.
If “provable” just means “follows from the premises,” then we have
G = “G follows from the premises of T, and G does not follow from the premises of T”
So G is a contradiction and hence false, meaning - I propose - that G does not follow from the premises (since a contradiction can’t follow from non-contradictory premises/axioms).
Well, this is precisely the point of coming up with deductions. When we describe a formal deduction, we are talking about something that can be carried out mechanically. Picture having a computer do it - which is precisely why there are so many applications to recursion theory, by the way. (In fact, my professor wrote a text where he presents the entire proof of Godel’s theorem in the language of recursion, rather than logic.) Now, one would hope that the rules of inference we program into the computer match up well with what really happens. But the computer doesn’t know or care about meaning - I can just as easily tell the computer that if it sees A->B on one line, and A on another, then it may conclude -B on a third, as I can anything useful. So if I did that, I’d be able to prove false things, and unable to prove true things. This would be (for our purposes) a poor deductive system, since one can’t mess up logical implication in the same way. The universe follows certain rules, and it doesn’t care what we program. So if it is the case that A implies B, and A happens, B will happen, even if we’ve proved something different. So showing that a certain deductive system is complete and consistent is precisely showing that the rules selected to characterize the system do the same things as the rules operative in the real world. This is not obvious at all times, especially the completeness. Frege, after all, came up with a rule that he believed did model how things happen in the real world which was inconsistent (basic logical principle 5.)
So, once we’ve designed a good deductive system, we will be assured that whenever some situation models the axiom set S, and if T can be proven from S, that the same situation models T. This is completeness and consistency of the deductive system.
Godel’s incompleteness proof, on the other hand, is about completeness of a set of axioms. Essentially, he wants to ask if it is possible to come up with a set of axioms which completely characterize the particular universe of mathematics (remember, he’s a Platonist) and yet are decidable - we know what’s in the set and what isn’t. It turns out we can’t.
Truth is something other than provability. The Platonist sees truth as expressing a proposition that correctly describes things in the forms. I see truth as expressing a proposition that correctly describes things in our world. A formalist sees truth as irrelevant, but does not regard provability as irrelevant, hence must see them as different. (Formalism, as I mentioned earlier, is not really taken seriously since Godel.) Everyone agrees about what provability is, though, relative to a deductive system and set of axioms. To see that provability and truth cannot necessarily coincide, consider the empty set of axioms. Nothing is provable from the empty set of axioms (formally) but certainly some things are true. More generally, changing the axiom set changes what is provable, but cannot change what is true.
Well, sure, to be provable is to follow from the axioms. But the point of Godel’s proof is that there are things not entailed by the axioms which are nonetheless true - for any decidable set of axioms of sufficient complexity. Considering your example, either double negation is really true, or it isn’t. It turns out it is. In natural language, we use a pretty good deductive system psychologically (it’s terrible linguistically though. Lots of languages use double negation to emphasize a point rather than to express a positive. A linguist once said in a speech that while the use of the double negative is split between languages, there is no language in which a double positive expresses a negative. An audience member said “yea, sure.”) and so certain things become common sense to us, relative to language. That’s not helpful in math.
This one is a bit harder. There is a theorem in set theory (LST) showing that if a set S of axioms has a model M, then it has a countable submodel N. Yet among the axioms, one could include a statement like “the universe is not countable” which would nonetheless has a countable model. This is called the Skolem paradox. It’s not really a paradox, though, in that it isn’t problematic once you understand how functions work.
Well, I’m not saying that such a position is correct, but you can at least see where it comes from.
Right, and further, any two contradictions are logically equivalent. (To see why, notice that from a contradiction, with standard logic, we can prove anything at all:
A and ~A
A
A or B (anything true can be “or’ed” with anything else
B (since either A or B, and we have ~A)
This is true for either one, so they have the same theory, so they are logically equivalent.
That’s exactly what provable means. True means satisfied by the universe or model or structure under discussion. Consider again your example - it is, let’ say, true that a particular program P will not halt, but there is no way to prove it in a finite amount of time (including running it.)
The second translation there is incorrect. G says “G is not provable” so G says “G is true and not provable” so G says “G is true and does not follow from the axioms.”
You seem to be implying that there is no pure math, or that any math system will necessarily be limited to the creator’s biases. Can’t one just create a random set of axioms, check for consistency, and then have a new field of mathematics (though perhaps not useful or interesting)?
Again, what if the math is totally fanciful and corresponds to nothing (known) about the world? (Although in the first place I’m not sure that any math describes the real world - for instance, I’ve never seen the number “5” / but then again, what do we mean by “real world” if not our mental models based on what we are sensing.)
Thanks, that sounds interesting.
In each of the above, you’re using the idea that truth is different from what follows from the premises. Of course true just means whatever the speaker intends it to mean, but for example I might ask how you know what the world is like, other than by making assumptions based on what sensations present themselves to you. Since those assumptions would be premises as well, I arrive at the notion that true would be most aptly used to describe just what follows from the premises.
Yeah, agreed.
I do think the notion makes sense for (real-world) mechanical operations. I am just not sure how you mean to say that math corresponds to the real world, or how Gödel can be a Platonist given that one could make, for example, two different geometries with conflicting axioms.
I don’t see where I’ve implied that. Everything I’ve said about mathematics proper is entirely consistent with Platonism, which is the ultimate in a “pure math” is it not? On your last question, checking for consistency is not so easy. In fact, Godel’s second theorem is that we cannot operate within a system to prove its own consistency. So what we do is relative consistency proofs - assuming ZFC is consistent, so is ZFC with CH, for instance.
Such math can exist, although I’m not quite sure just what would help you to set up the axioms. In such a system, we’d have plenty of provable statements, but I maintain they would not be true.
You’ve said many times that in math, true means follows from the premises. I’ve told you that it does not, but your reply has continued to be “yes it does.” I really don’t know what else to say on the subject. I am a practicing mathematician, not a philosopher, so I don’t regularly delve into philosophical issues, although they interest me. I can tell you, as a working mathematician, that almost none of us think this. If that doesn’t help, consider reading any text on philosophy of math, or mathematical logic. I recommend Leary’s A Friendly Introduction to Mathematical Logic to start with.
Even in physical reality, we have examples of Riemann and Euclidean geometries, so I don’t see why there couldn’t be both flat and curved surfaces in the mathematical universe. Reaching further, though, certainly a Platonist has to admit that one can make axioms (or rules of inference) that do not relate to what happens in the universe of mathematics. When you do that, you make a game that has no relation to anything true, and your conclusions are “provable from the axioms” yet not true. I don’t see why this is problematic. This, in fact, is what I’ve said throughout - that one can make useful (true) axioms, or not. This is the point of the debate between Hilbert and Frege. References on that debate are easily available, if you’re interested, and might shed light on some of these questions.
All right, I think I see what you’re saying now. It looks like there is a broader philosophical question underlying this, and that my tentative position on the matter disagrees with most mathematicians working in the field. I would be very interested to read more on this subject. I will check out the Leary book for starters.
My contention is that everything is a “game” so to speak, in the sense of “the map is not the territory,” so I can see now that this is a deeper question touching on epistemology and/or a theory of mind, and why it might not be of much interest to a practical mathematician. Still, this conversation made the issue much clearer for me. Thank you.
The reason I have taken an interest in this is mostly because of Adam Knott’s attempt to extend the strict version of Mengerian/Misesian praxeology, wherein it became apparent to me that there are some far-reaching philosophical issues that may need to be resolved. Can I ask what your specialization is, and how pure/applied your focus is?
I may be a bit out of my depth, as I said, because I explore these issues as a mathematician, not a philosopher, although I have some background in philosophy. I do appreciate that there are issues and so forth, but also, remember that I myself have positions on larger philosophical issues which I am not making explicit here - because they are also the positions that most mathematicians hold, and so to describe what mathematicians do, I have no need to open that can of worms. The Leary book is a great place to start to understand how mathematicians actually work with and view these concerns. Another book you might consider is Frege’s Foundations of Arithmetic. It’s not at all how we think, but it shows where we started. Reading that before Leary would be good - Leary covers Hilbert through Godel, roughly (although he puts in more computer science) so seeing the first attempt first, to understand the difference between logicism and formalism, would be good. The Oxford book on philosophy of math is also full of readings. You can buy this book for under $40, and it’s available at most college libraries. It includes Russell’s letter to Frege, as well as the Frege/Hilbert letters I mentioned.
I’m pretty sure I don’t understand your contention. That the map is not the territory, I think, is exactly what I’ve been saying, and I thought you were arguing opposite that point.
I have three areas of interest - chaos/complexity, math education, and logic. My current research program is in logic, more narrowly reverse mathematics, and more narrowly still, the reverse mathematics of certain theorems in set theory. Reverse mathematics, as the name suggests, is math in reverse. Rather than beginning with axioms and deriving conclusions, we ask people in other fields - either within math or in applied fields - what theorems they need to do their work, and then we attempt to discover minimal axiom sets that make this true. Philosophically, we are asking just how far from ideal a structure/universe can be and still exhibit nice properties. My interests are largely pure, in the sense that I do not look at how math is used in other fields. On the other hand, my goal is application, but of a different sort. Rather than looking for “how can this formula be used here?” I look at how other structures - biological, economic, political, etc. exhibit patterns that can be seen in mathematical structures, then look for isomorphisms so that math can be used to give some answers over there. This is still considered pure math.
I don’t, actually I do but they’re password protected. They can be found in the Oxford book, or a google search.