There was an interesting discussion about mathematical constructions in the comment thread on my post about the professor who doesn't like infinity, and I thought it was worth turning it into a post of its own.
In the history of this blog, I've often talked about the idea of "building mathematics". I've shown several constructions - most often using something based on Peano arithmetic - but I've never really gone into great detail about what it means, and how it works.
I've also often said that the underlying theory of most modern math is built using set theory. But what does that really mean? That's the important question, and the subject of this post.
Math is based on formal reasoning. A formal reasoning system consists of two parts: a logic - that is, a mechanical, symbolic inference system; and a model - a set of objects that our inference system can reason about. The objects are described by a basic set of axioms that form the basis of what we know about the objects. Everything else - everything else, will be done by defining things in terms of those basic objects, and inferring things from the definitions - and the meanings that they get from the axioms of the basic objects that underly the definitions.
In modern math, we typically work by using first order predicate logic as our inference system, with sets (defined by the Zermelo-Fraenkel axioms) as their basic objects.
Often, when you ask someone who dislikes the axiomatic approach to math how to do math without axioms, they'll say "with definitions". That answer is a copout. Definitions can be one of two things: they can be axioms, under a different name. Or they can be true definition, which rely on the underlying formal reasoning system - including its axioms.
The difference, in my jargon here, between a "true definition" and an "axiom" is that a definition defines objects in terms of something else; an axiom is foundational. While that distinction might seem to be splitting hairs, it's actually quite important. An axiom system has the responsibility of establishing the validity of everything built upon it. If an axiom scheme contains any kind of inconsistency or error, then everything that you do in the formal system - every theorem, every proof, is invalid. True definitions, on the other hand, rely on an axiom scheme for their validity. A definition doesn't have the strong requirement of validity that the axiom scheme does: you define things in terms of the consistent underlying basis, and so long as you build your construction in terms of the things provided by the axioms and the logic, your definitions will necessarily be consistent.
One of the subtle points of this - and one of the things that is commonly misunderstood - is how you build things in an axiomatic formal system like FOPL+ZF Set theory. When you're building something in a formal system, you need to make a distinction between the thing that you're building, and the things that you're building it with. You define the set of objects, properties, and operations that you're interested in studying in terms of the underlying system. You can show the validity of your construct by proving the correctness of its essential properties in terms of the underlying construction. But you always keep that clear line distinguishing between the construction and the elements.
So - let's look at an example. We generally build the natural numbers from Z-F sets. We say that 0=∅, 1={0}={∅}, 2={0,1}={{∅},∅}, and so on. Using the usual Peano arithmetic construction, we can say that for any integer, it has a unique successor. We show that in set theory by showing how, given a number in set theoretic representation, we can construct its successor: given a number n, s(n) = n ∪ {n}. By doing that, we've defined the successor operation in terms of set theory. And we can prove the property that each number has a unique successor, by using the ZF-axioms to show that for any set N which is a set-theoretic representation of a natural number, that there is exactly one set N' such that N'=S(N).
It's important to note that it's not the case that we can arbitrarily use set theoretic operations on our set theoretic numbers, and have the result be meaningful. We can define a set difference operator - but set difference of numbers M and N won't necessarily be a valid number. When we're working in terms of the construction of natural numbers using sets, we can only use the operations that we defined in the construction. The set theory is providing us with a tool for proving the validity of our construction.
My favorite metaphor for this is (obviously, given my interests) computer languages. When you write a program in a computer language, you're writing in terms of abstractions that are very different from the natural abstractions of the real machine on which the program is executed. For example, a few months back, I wrote a bunch of articles about programming in Haskell. In Haskell, you work in terms of functions, without any idea of mutable state. The computer hardware has no concept of a function. But you can write a compiler that implements Haskell functions in terms of the primitive, mutable-state-based machine language. All of Haskell becomes executable by that translation. But if you were to take a Haskell program, look at the primitive representation of a function, and perform some change to it that makes perfect sense in terms of the machine language, you could end up with something that breaks Haskell - that makes the program crash.
That's exactly the same idea as building things in math. You define them (implement them) in terms of a low level formal system (machine language), and then build theorems (programs) in terms of the high-level constructions that you've built. But if you break the abstraction, you can get into trouble.
Comments
The problem with construction, of course, is that you run the risk of your construction having properties that the abstract thing that you're trying to model doesn't.
Using your favourite analogy, this is a real problem for programming languages, too. Languages used to be defined by implementation, that is, whatever the reference implementation does is what any conforming implementation should do too.
We now know that's a bad idea. And while the ZF construction of natural numbers is very pretty, I've never been entirely convinced that it's a good idea either. Yeah, it satisfies the Peano axioms. But you wouldn't prove a theorem about natural numbers using the construction, because you always run the risk that your theorem is a consequence of the construction, rather than of the Peano axioms.
Posted by: Pseudonym | November 4, 2007 6:05 PM
Excellent post. What I find interesting is the question of how mathematics relates to the "real world," the reason that we can build bridges and skyscrapers using something that is ultimately, logically reducible to a particular collection of ideas about sets and a way of combining those ideas into bigger ideas.
Related to this issue, and the topic of your post is the question of the historical development of the particular system of mathematical ideas we've inherited today. Surely the first mathematicians did not start at what we today recognize as the root or source of all mathematics, so in a certain sense the history of mathematics is upside down relative to its logical structure.
Posted by: Dave | November 4, 2007 6:18 PM
wait for it......
wait...
wait...
wait...
LONGEST POST EVAR!!!!!
Posted by: douchebag | November 5, 2007 1:02 AM
I think that is less perplexing if we look at fields such as physics, where the search for more fundamental theories (by necessity) is explicit.
Also the case for constructions mentioned in the first comment has a strengthened connotation when looking at other fields. There constructions are supported by the application context of the model. For example, path integrals which have a physical interpretation works fine in practice, yet there is a theoretical problem to define a measure.
Posted by: Anonymous | November 5, 2007 5:11 PM
path integrals
Posted by: Torbjörn Larsson, OM | November 5, 2007 5:13 PM
Pseudonym,
If the ZF construction satisfies the PA axioms, then any results proven must be consistent with the axioms. You won't run into any properties of the ZF sets which are not properties of the natural numbers. Although, with just the idea that ZF satisfies PA, it does not rule out the idea that there are properties of the natural numbers which are not properties of the sets (I actually believe this is not a problem, but I could not tell you exactly why, at the moment).
I would, indeed, like to know your alternative to the FOL+ZF approach.
The problem with a set theoretic basis to math is that it requires a logic in order to implement it. The problem with a logical basis to set theory is that it requires a theory of sets to implement it. The accepted basis for math is completely circular.
Add to this the fact that any system which satisfies the PA axioms has sentences which are true, but cannot be proven (Godel, of course), and math starts to look like a bunch of BS (along with ZF (based on PA axioms) and FOL (based on ZF)). Then science starts to look like a bunch of BS. And reality starts to look like a bunch of BS.
Your reality has no basis in reality. Run along now, children.
Posted by: the liar | November 6, 2007 12:32 PM
*Set theory is required for FOL because there has to be a set of objects to quantify over (For all x... There exists a y...). Set theory needs FOL for its axiomatic construction, as was talked about in the article above.
Posted by: liar liar pants on fire | November 6, 2007 12:37 PM
I must admit some surprise at, over the last few weeks, seeing exactly how many people find set theory so controversial :/
Or is it just the same guy with different usernames?
Posted by: Coin | November 6, 2007 3:36 PM
Mark, I'm curious as to your thought re: category theory and its relationship to
FOL+ZF.
Posted by: radar | November 7, 2007 12:54 AM
The Incompleteness Theorems really do not suggest as much a BS factor for mathematics as Liar seems to indicate. Proof of course has a very specific notion in the context of mathematical logic.
Posted by: Shawn O'Hare | November 7, 2007 2:46 AM
[You won't run into any properties of the ZF sets which are not properties of the natural numbers.]
What a lie. Mark actually already indicated something about this. The ZF sets for natural numbers each contain each previous number as an element and as a subset of the set. A natural number x... as in the basic counting numbers... doesn't have all smaller natural numbers as elements of x. In other words, if we start counting 1, 2, 3, 4... we conceive of a sequence. But, we don't conceive of 2 as a subset and as an element of 3.
[The problem with a set theoretic basis to math is that it requires a logic in order to implement it. The problem with a logical basis to set theory is that it requires a theory of sets to implement it. The accepted basis for math is completely circular.]
Ummm... maybe... but this claim needs more backing to it. Of course with this sort of reasoning one can use a different theory of logic or a different theory of sets to implement a different logic and get a different math. So, I actually end up liking your idea, but that doesn't mean I think such has a rational basis.
[Add to this the fact that any system which satisfies the PA axioms has sentences which are true, but cannot be proven (Godel, of course)...]
Umm... well now you have to get into philosophical ideas about the nature of truth. Techincally speaking, as I understand it, Godel's theorems end up saying that any system which satisifies either the PA axioms of the ZFC axioms has propositions/sentences which come out formally undecideable. Does that mean we have true, unprovable statements in formal mathematical systems? Not necessarily.
If we take the concept 'true' and 'provable' as identical, then we have mathematical statements which come out neither true nor false, according to Godel's reasoning. Or to state it differently, Godel showed that any mathematical system sufficient to derive Peano arithmetic (or anything stronger) necessarily has statements where the classical truth set {T, F} doesn't apply, and we need at least the truth set {T, U, F}. At least, that's how I understand such.
If we have other concepts of 'true', then there may exist true, yet unprovable statements in maths... but I don't know what concept of 'truth' gets used here (I assume the idea of correspondence with reality doesn't work)... Can you elucidate what concept of 'truth' you mean to use?
[Then science starts to look like a bunch of BS.]
I don't see this. Science rarely makes used of two-valued logic, and even when it does rely on such heavily usually ways around two-valued logic exist or can get worked out. Case-in-point: Newton's mathematical model for gravity. If we applied two-valued logic to it, it would come out false. But, scientifically speaking it still comes as useful for scientifically modeling and explaining enough scientific phenomena that basically every introductory physics textbook goes over it.
Posted by: Doug | November 7, 2007 3:58 AM
Doug:
That is *not* what I said. I think you're having some serious trouble understanding the idea of a construction, and the distinction between the constructed abstractions, and the underlying mechanism used to implement those abstractions.
If you build a model of the natural number in set theory, what you're doing is building an abstraction describing numbers using set-theoretic definitions. If you work entirely in that abstraction, then any results that you derive from it using the underlying set theoretic axioms will be valid in the defined systems.
The problem is when you *break* the abstraction. "Subset" isn't a concept defined for a number in the constructed abstraction of natural numbers - so if you break the abstraction, and insist on using the primitive set theoretic operations on the abstract construct of numbers as if they weren't numbers, then you can get results that don't make sense in the context of numbers.
I can construct the set of integers using natural numbers. It's easy: if natural number N is greater than 0, and N is even, then it represents the integer NZ=-N/2; if N is odd, then NZ=1+(N-1)/2.
Then, I define the integer operators, in terms of my construction. There's +Z, -Z, etc., each of which I define in terms of the basic + and - operators on natural numbers. Now I've got an implementation of integers. If I only use +Z and -Z, then any result I can derive using my abstraction will be valid - even though under the covers, I'm doing it in terms of the primitive natural number operators. When I see "-1", it's actually represented as "2". When I see the integer 27, it's actually represented by the natural number 53.
If I work in terms of the abstraction, I can't see that representation. I see the number 27. If I add 27Z+Z-3Z, then I'll see the result 24Z - even though under the covers, I've actually done something using the natural numbers 53 and 6. My result isn't 59 - it's 24Z, which is represented by 47.
Posted by: Mark C. Chu-Carroll | November 7, 2007 9:48 AM
Doug you apparently have no idea what you are talking about. Both the work of Gödel and Tarski very clearly show that "truth" and "provabilty" within any formal language or system are seperate non equivalent concepts. What Gödel's first theorem actually states is that in any formal system rich enough to contain arithmetic there are true aritmetical statements that cannot be proved in that system.
Sorry but there is no other honest way to express this, both of these statements is pure unadulterated crap. They are so way of the mark that I have no idea what I could write to correct them except to say that the formal argumentation in all classical science including Newton's theory of Gravity is based on two valued logic and nothing else!
Posted by: Thony C. | November 7, 2007 12:12 PM
[A natural number x... as in the basic counting numbers... doesn't have all smaller natural numbers as elements of x. In other words, if we start counting 1, 2, 3, 4... we conceive of a sequence. But, we don't conceive of 2 as a subset and as an element of 3.]
Okay, okay, yeah. But the thing is, the containment relation in set theory is isomorphic to the greater than relationship among natural numbers. You're right that there are some properties which aren't technically shared, but they are translated through isomorphism. So there aren't any properties of the ZF sets which do not have equivalent properties of the natural numbers.
[Of course with this sort of reasoning one can use a different theory of logic or a different theory of sets to implement a different logic and get a different math.]
Hmmm, I'm not quite sure what you mean. For any "different math" which is based on set theory, that set theory will need to be built with a logic which can quantify over sets (otherwise it cannot talk about the objects of the language, which simply makes no sense). If it can quantify over sets, there must be a preexisting set theory there. Now, I suppose this could be a different set theory, but that one needs a logical base, which needs a set theoretical base, etc., etc... So it makes the most sense to stick with the one set theory (usually ZF or ZFC (with the axiom of choice) or some variation) and the one logic (usually first-order predicate logic) to lift each other up. But this is circular, and problematic. It cannot be avoided.
[Techincally speaking, as I understand it, Godel's theorems end up saying that any system which satisifies either the PA axioms of the ZFC axioms has propositions/sentences which come out formally undecideable. Does that mean we have true, unprovable statements in formal mathematical systems? Not necessarily.]
If we accept a semantics with more than two truth values, you are correct. But this gets us into some sticky situations, although it is a legitimate "way out".
[If we have other concepts of 'true', then there may exist true, yet unprovable statements in maths... but I don't know what concept of 'truth' gets used here (I assume the idea of correspondence with reality doesn't work)... Can you elucidate what concept of 'truth' you mean to use?]
The important attribute of the theory of truth which I was advocating is merely a two-valued {T, F} semantics. I don't know where you get the idea that this is not standard. Much, much, much of generally accepted mathematics makes use of proof by contradiction. This is impossible using three truth values, as you advocate. You are really going against the grain there, not that people (intuitionists, constructivists) don't do that.
If you assume something to be true, then prove that leads to a contradiction, you are now forced to put it in your "U" territory, until it can be proven false. Last I checked, it cannot be untrue that it is raining, and "unfalse" that it is raining at the same time. So I'm unsure how you say the two-valued semantics is not supported by correspondence with reality. I assume you are referring to the "correspondence theory of truth", but my understanding is that that theory actually goes against 3 or more valued logics.
[Science rarely makes used of two-valued logic, and even when it does rely on such heavily usually ways around two-valued logic exist or can get worked out.]
It is really only a very recent thing, to my knowledge, that people have played with 3+ valued semantics/logics. (From wikipedia on "multi-valued logic": The later logicians until the coming of the 20th century followed Aristotelian logic, which includes or implies the law of the excluded middle.) The law of the excluded middle is the rule that (p or not-p) is true of any p in the system, i.e. every statement is either true or false; there is no "middle", or your "U" value.
Now this is a very recent addition to logic. There are probably almost zero scientists who have gotten around to using it, and that certainly does not include Newton! As for the scientists who do use it, they would be radical thinkers, much like the intuitionist and constructivist mathematicians and logicians are. I am aware that many computer scientists find use in playing with fuzzy logic (where there are infinitely many truth values, not just two or three), but this is not relevant.
So, basically, it is pretty well accepted that Godel's sentence, which basically boils down to "This sentence cannot be proven," is either true (and it can't be proven), or false (in which case it can be proven, and the PA axioms are inconsistent). Which leads most who have any faith in arithmetic to conclude there are sentences which are true but cannot be proven (in fact, infinitely many).
And the whole system is built on the circular logic-built-on-set-theory-built-on-logic mess. And science is built on mathematics. And our knowledge of reality is built on science (and our senses/intuitions...do you trust those?).
So, basically, everything is quite muddled. I kind of like it that way, so I hope you can come to believe that, too.
[The Incompleteness Theorems really do not suggest as much a BS factor for mathematics as Liar seems to indicate. Proof of course has a very specific notion in the context of mathematical logic.]
A lot of people say this, and it is tempting to believe. How far the extent of Godel's proof's implications go is an interesting topic, and I would like O'Hare to expand upon his point. The best case I see is drawing a parallel with quantum mechanics and saying, yeah, all this weird stuff could happen on the quantum level, but it really doesn't happen in the world we see, so it is irrelevant to us in "our world". But the fact is that math is what we use to describe the world, and that math has extremely weird properties (much like quantum mechanics!).
To me, it doesn't make sense to ignore the quirks of our most thorough knowledge of the most basic features of our reality, or our conception of it. These things, to me, are like studying God. (But we have evidence that these exist...)
Posted by: Liar 2.0 | November 7, 2007 4:51 PM
Mark,
[That is *not* what I said.]
I didn't say you said such. I said "Mark actually already indicated something about this." In other words, if you interpret your statement "We say that 0=∅, 1={0}={∅}, 2={0,1}={{∅},∅}, and so on." in a certain way, then your statement indicates or implies such.
[I can construct the set of integers using natural numbers. It's easy: if natural number N is greater than 0, and N is even, then it represents the integer NZ=-N/2; if N is odd, then NZ=1+(N-1)/2.]
But does your construction have different properties than that of the normal conception of natural numbers? Look, we'd have to specify what we mean by 'property' here. If 'property' means a characteristic attributed to a mathematical concept, then such a construction of integers has different properties than that of natural numbers.
[Now I've got an implementation of integers.]
To some degree, I'd say yes. But, your construction ends up having different conceptual characteristics to it than the normal concept of integers. So, in terms of our mental behavior, normal integers work out differntly to some degree than such a construction.
[When I see "-1", it's actually represented as "2".]
Alright, well that's actually a good example. With the regular conception of integers, we can apply a unary operator '-' on a subset of the integers to generate the rest of the integers. As far as I can see, with the even/odd construction there doesn't end up existing a similar unary operator. So, the constructions end up behaving differently in some respect.
Thony,
[Both the work of Gödel and Tarski very clearly show that "truth" and "provabilty" within any formal language or system are seperate non equivalent concepts. What Gödel's first theorem actually states is that in any formal system rich enough to contain arithmetic there are true aritmetical statements that cannot be proved in that system.]
You've already started interpreting at some level. Maybe not in the level or way in which I think you have, but at some level.
It actually states
"Proposition VI: To every w-consistent recursive class c of formulae there correspond recursive class-signs r, such that neither v Gen r nor Neg (v Gen r) belongs to Flg(c) (where v is the free variable of r)."
http://www.vusst.hr/~logika/undecidable/godel.htm
"Informally, Gödel's incompleteness theorem states that all consistent axiomatic formulations of number theory include undecidable propositions (Hofstadter 1989). This is sometimes called Gödel's first incompleteness theorem, and answers in the negative Hilbert's problem asking whether mathematics is "complete" (in the sense that every statement in the language of number theory can be either proved or disproved). Formally, Gödel's theorem states, "To every omega-consistent recursive class kappa of formulas, there correspond recursive class-signs r such that neither (v Gen r) nor Neg(v Gen r) belongs to Flg(kappa), where v is the free variable of r" (Gödel 1931)."
http://mathworld.wolfram.com
/GoedelsIncompletenessTheorem.html
I don't see anything about the nature of truth here, but rather about class signs. In other words, one can formulate class signs for such theories which don't come out provable nor disprovable. It doesn't say anything about true class signs, so far as I see. I don't see Godel talking about truth in his preface. He says "It may therefore be surmised that these axioms and rules of inference are also sufficient to decide all mathematical questions which can in any way at all be expressed formally in the systems concerned. It is shown below that this is not the case, and that in both the systems mentioned there are in fact relatively simple problems in the theory of ordinary whole numbers4 which cannot be decided from the axioms."
http://www.vusst.hr/~logika/undecidable/godel.htm Again, I see him talking about decidability, not truth.
Lastly, notice that I said what Godel's thoerem might say IF we took true and provable as equivalent concepts. Now, you say that Godel's theorems basically say that they don't qualify as equivalent concepts in formal systems. In other words, you seem to assert that we can't *conceive* them in terms of each other in a formal system. So, as far as I can see, you turn Godel into a psychologist of possible thought instead of a mathematician or a meta-mathematician.
[They are so way of the mark that I have no idea what I could write to correct them except to say that the formal argumentation in all classical science including Newton's theory of Gravity is based on two valued logic and nothing else!]
First off REAL argumentation in sciences takes place in human language and human thinking. Simply put, neither human language nor human thinking operates exclusively according to two-valued logic, and only uses two-valued logic in a trivial sense so far as we can see.
Second, assuming Newton's theory of gravity to operate in a two-valued logical system, it either comes out true or false. Well, its gotten falsified already, and consequently it can't come out true. So, logically, it comes out false. Of course it still gets taught in basic science and physics textbooks, so if you really promoted two-valued logic in science, you would logically want people to rewrite basically all basic physics textbooks. You also logically want people to completely get rid of the model where electrons orbit atoms. Also, get rid of statements which come out usually, or partially true in science or similar matters, such as "leaves are green in the summer," or "electrons behave like waves instead of particles" (and the converse). After all, in two-valued logic there exists only 'true' and 'false', and statements like 'electrons behave like waves' comes out having counter-examples if assumed either 'true' or 'false'. But, 'electrons behave like waves' comes out as permissible scientifically speaking, so at least in QM two-valued logic doesn't get used exclusively. Not to mention quantum-logic or modeling of quantum mechanics using multi-valued logic by people such as Reichenbach in books alredy 50 plus years old.
Additionally, there already exists books like "Fuzzy Logic in Chemistry" and "Fuzzy Logic in Geology." I didn't talk about "classical" science, nor deigned to define such in an almost circular manner. I talked about science.
Lastly, it doesn't really come hard to criticize ideas "way off the mark" (so far as I can tell). We can all criticize religious ideas we find "way off the mark".
Posted by: Doug | November 7, 2007 5:28 PM
In case my post with the references cited doesn't post, hopefully this will post.
Mark,
[That is *not* what I said.]
I didn't say you said such. I said "Mark actually already indicated something about this." In other words, if you interpret your statement "We say that 0=∅, 1={0}={∅}, 2={0,1}={{∅},∅}, and so on." in a certain way, then your statement indicates or implies such.
[I can construct the set of integers using natural numbers. It's easy: if natural number N is greater than 0, and N is even, then it represents the integer NZ=-N/2; if N is odd, then NZ=1+(N-1)/2.]
But does your construction have different properties than that of the normal conception of natural numbers? Look, we'd have to specify what we mean by 'property' here. If 'property' means a characteristic attributed to a mathematical concept, then such a construction of integers has different properties than that of natural numbers.
[Now I've got an implementation of integers.]
To some degree, I'd say yes. But, your construction ends up having different conceptual characteristics to it than the normal concept of integers. So, in terms of our mental behavior, normal integers work out differntly to some degree than such a construction.
[When I see "-1", it's actually represented as "2".]
Alright, well that's actually a good example. With the regular conception of integers, we can apply a unary operator '-' on a subset of the integers to generate the rest of the integers. As far as I can see, with the even/odd construction there doesn't end up existing a similar unary operator. So, the constructions end up behaving differently in some respect.
Thony,
[Both the work of Gödel and Tarski very clearly show that "truth" and "provabilty" within any formal language or system are seperate non equivalent concepts. What Gödel's first theorem actually states is that in any formal system rich enough to contain arithmetic there are true aritmetical statements that cannot be proved in that system.]
You've already started interpreting at some level. Maybe not in the level or way in which I think you have, but at some level.
It actually states
"Proposition VI: To every w-consistent recursive class c of formulae there correspond recursive class-signs r, such that neither v Gen r nor Neg (v Gen r) belongs to Flg(c) (where v is the free variable of r)."
"Informally, Gödel's incompleteness theorem states that all consistent axiomatic formulations of number theory include undecidable propositions (Hofstadter 1989). This is sometimes called Gödel's first incompleteness theorem, and answers in the negative Hilbert's problem asking whether mathematics is "complete" (in the sense that every statement in the language of number theory can be either proved or disproved). Formally, Gödel's theorem states, "To every omega-consistent recursive class kappa of formulas, there correspond recursive class-signs r such that neither (v Gen r) nor Neg(v Gen r) belongs to Flg(kappa), where v is the free variable of r" (Gödel 1931)."
I don't see anything about the nature of truth here, but rather about class signs. In other words, one can formulate class signs for such theories which don't come out provable nor disprovable. It doesn't say anything about true class signs, so far as I see. I don't see Godel talking about truth in his preface. He says "It may therefore be surmised that these axioms and rules of inference are also sufficient to decide all mathematical questions which can in any way at all be expressed formally in the systems concerned. It is shown below that this is not the case, and that in both the systems mentioned there are in fact relatively simple problems in the theory of ordinary whole numbers4 which cannot be decided from the axioms."
Again, I see him talking about decidability, not truth.
Lastly, notice that I said what Godel's thoerem might say IF we took true and provable as equivalent concepts. Now, you say that Godel's theorems basically say that they don't qualify as equivalent concepts in formal systems. In other words, you seem to assert that we can't *conceive* them in terms of each other in a formal system. So, as far as I can see, you turn Godel into a psychologist of possible thought instead of a mathematician or a meta-mathematician.
[They are so way of the mark that I have no idea what I could write to correct them except to say that the formal argumentation in all classical science including Newton's theory of Gravity is based on two valued logic and nothing else!]
First off REAL argumentation in sciences takes place in human language and human thinking. Simply put, neither human language nor human thinking operates exclusively according to two-valued logic, and only uses two-valued logic in a trivial sense so far as we can see.
Second, assuming Newton's theory of gravity to operate in a two-valued logical system, it either comes out true or false. Well, its gotten falsified already, and consequently it can't come out true. So, logically, it comes out false. Of course it still gets taught in basic science and physics textbooks, so if you really promoted two-valued logic in science, you would logically want people to rewrite basically all basic physics textbooks. You also logically want people to completely get rid of the model where electrons orbit atoms. Also, get rid of statements which come out usually, or partially true in science or similar matters, such as "leaves are green in the summer," or "electrons behave like waves instead of particles" (and the converse). After all, in two-valued logic there exists only 'true' and 'false', and statements like 'electrons behave like waves' comes out having counter-examples if assumed either 'true' or 'false'. But, 'electrons behave like waves' comes out as permissible scientifically speaking, so at least in QM two-valued logic doesn't get used exclusively. Not to mention quantum-logic or modeling of quantum mechanics using multi-valued logic by people such as Reichenbach in books alredy 50 plus years old.
Additionally, there already exists books like "Fuzzy Logic in Chemistry" and "Fuzzy Logic in Geology." I didn't talk about "classical" science, nor deigned to define such in an almost circular manner. I talked about science.
Lastly, it doesn't really come hard to criticize ideas "way off the mark" (so far as I can tell). We can all criticize religious ideas we find "way off the mark".
Posted by: Doug | November 7, 2007 5:29 PM
[But the thing is, the containment relation in set theory is isomorphic to the greater than relationship among natural numbers.]
In some respect, perhaps. But, in general that doesn't hold for the containment relationship. After all,
{2, 4} is contained in {2, 4, 6}, but {2, 4, 6} is not greater than {2, 4}.
[So there aren't any properties of the ZF sets which do not have equivalent properties of the natural numbers.]
Define 'property'.
[For any "different math" which is based on set theory, that set theory will need to be built with a logic which can quantify over sets (otherwise it cannot talk about the objects of the language, which simply makes no sense).]
One could use a fuzzy logic with fuzzy quantifiers to construct a fuzzy set theory.
[If we accept a semantics with more than two truth values, you are correct. But this gets us into some sticky situations, although it is a legitimate "way out".]
What 'sticky situations' do you foresee? Oh... and it looks like you've disagreed with Thony who says "Doug you apparently have no idea what you are talking about." Nice truth-speaking there, liar.
[The important attribute of the theory of truth which I was advocating is merely a two-valued {T, F} semantics.]
Oh... well if you define truth in terms of such a semantics, sure.
[I don't know where you get the idea that this is not standard.]
It comes out standard enough in practice, but not explicitly so. I'd prefer that most people who use this sort of assumption about truth state such upfront. It works out like the parallel postulate of Euclidean geometry in that if you reject it you can get different logics. So, ignoring such as an assumption comes out significant.
[Much, much, much of generally accepted mathematics makes use of proof by contradiction. This is impossible using three truth values, as you advocate.]
No, it's not, and I'll show this via example. It comes out as impossible for all three-valued logics taken together. But, for specific three-valued logics it can hold. For instance, let's say that our truth value set comes as {0, 1/2, 1}. Contradiction states a^c(a)=0 (where c(a) indicates the complement or negation of a). Use the max(0, a+b-1) operator for '^', and 1-a for c(a). Well, b=c(a), so we have
max(0, a+c(a)-1)=max(0, a+1-a-1)=max(0, 0)=0. If use
min(1, a+b) for 'v', then a v c(a)=1, as
min(1, a+c(a))=min(1, a+1-a)=min(1, 1)=1. So, for a three-valued logic (or really any-valued logic) with those operators for intersection and union, proof by contradiction still holds. There exist other multi-valued logics where POC and POEM hold.
[Last I checked, it cannot be untrue that it is raining, and "unfalse" that it is raining at the same time.]
Suppose we have a few raindrops here and there. Then it rains a little over some space, while it doesn't rain at all over some other space. Last time I checked I noticed that a rain of a hurricane worked very differently than a light shower of rain which worked differently than a sunny day with no clouds in the sky.
[I assume you are referring to the "correspondence theory of truth", but my understanding is that that theory actually goes against 3 or more valued logics.]
I don't think it specifies such actually.
[Now this is a very recent addition to logic. There are probably almost zero scientists who have gotten around to using it, and that certainly does not include Newton!]
Formally, as in a mathematical development of such, it comes out quite recent. But, if we take science as "the science of thinking", then I suspect that people have used non-two valued ways of thinking for quite some time. Although, admittedly such engages in mind-reading to a high degree, so I don't know how to prove it. Then again, since the other position also engages in mind-reading heavily, someone with the other view can't prove it. So, I state my opinion.
[So, basically, it is pretty well accepted that Godel's sentence, which basically boils down to "This sentence cannot be proven," is either true (and it can't be proven), or false (in which case it can be proven, and the PA axioms are inconsistent).]
You mean that many people *accept* that it says such. But does Godel say that? Did Goedel really mean to say that? After all, we KNOW that Goedel went on and did some work in multi-valued logic. "Kurt Gödel in 1932 showed that intuitionistic logic is not a finitely-many valued logic, and defined a system of Gödel logics intermediate between classical and intuitionistic logic; such logics are known as intermediate logics."
Wikipedia article on multi-valued logic (the page seems not to post when I post citations).
So what would Goedel say his own theorem says in informal language? I'm not deciding here.
[And science is built on mathematics.]
Don't forget about the Einstein quote ""As far as the laws of mathematics refer to reality, they are not certain, as far as they are certain, they do not refer to reality." I've never seen an uncertain statement in two-valued logic, have you?
I think you and I actually have somewhat similar view liar.
Posted by: Doug | November 7, 2007 6:08 PM
Doug:
You're demonstrating exactly what I mean by "not understanding the idea of a construction".
In my construction of the integers from the naturals, there is a unary minus - defined in exactly the way that unary minus is normally defined for the integers: -X = 0-X;
but since we're working in the construction, we don't use the primitive natural number "-"; we use the "-" from the construction - that is, "-Z".
That's the point of a construction. A construction is a closed world, built on a well-understood substrate.
Like I keep saying, you can think of it like a computer language. Or for an example that's maybe closer to home: you're reading text that I've written to you. It's english text, made up of letters and spaces and punctuation. You understand it as english. It is english. But it's implemented as UTF-8, an encoding of the letters and symbols into numbers. Really, when you see an "A", it's the number 65. But you never see that when you're reading it: you read it inside the construction of the characters using numbers. And in fact, than number 65 isn't really the number 65. It's really a byte - a sequence of eight 1s and 0s: 01000001. And really, it's not a sequence of 0s and 1s - it's a sequence of electrical charges inside of a circuit. At each level, a construction is built on top of the lower level. And then you work in the construction, which depends on what's beneath it. When I'm reading and writing text on the computer, I *never* stop and think "Gosh, I can divide the letter A by two by doing a right-shift on it".
If I use the natural numbers to construct the integers, what I'm doing is using a well-understood, proven-sound system, and using it as a basis for implementing a new abstraction. When I talk about integers, I'm talking about its closed world, the construction of the integers. In the construction, I'm only dealing with constructed integers and the operations on constructed integers. The construction is like the interpreter - it's there, it's filling a necessary role - but when I'm looking at the construction and its properties, I need to stay inside the construction.
Posted by: Mark C. Chu-Carroll | November 7, 2007 6:27 PM
[In my construction of the integers from the naturals, there is a unary minus - defined in exactly the way that unary minus is normally defined for the integers: -X = 0-X]
Your definiton here makes '-' binary, and NOT unary, since you're defined it in terms of two symbols '0' and 'X'. Look, I could start with JUST the ordered set {1, 2, 3...}. Now, take the unary operation '-' on this ordered set, and we'll have reversed order {... -3, -2, -1}. I need NOT have a concept of a '0' in order to form this set. I think I could practially define '-' as the unary operation on all less-to-greater ordered subsets of natural numbers which reverses their order. Maybe that definition doesn't work out as sufficient though, I just thought of it (although I doubt I thought of such first or someone else hasn't tried a similar definiton before... but I know of no sources offhand). Maybe you have a unary operation and I've missed it, but I certainly don't see it from your definition in terms of a binary operation.
[That's the point of a construction. A construction is a closed world, built on a well-understood substrate.]
Maybe, but historically speaking and in terms of mathematical education it simply didn't happen that negative numbers came from the closed world of the natural numbers. In fact, people rather constantly objected to negative numbers, since others formed them in terms of something other than their closed world of natural numbers. In other words, they objected to negative numbers, because they took positive numbers, introduced a '-' operator on them, and then found out that closure no longer held for '-' on the positive numbers. So, this sort of emphasis on closure ends up inviting, or at least has historically done so, rejecting of other sorts of mathematical objects.
Second, I suspect I don't agree that a construction works out as a closed world, or at least I doubt the usefulness of closed mathematical worlds. Let's say I talk about a set such as {2, 3} with the operation '*' of concatenation, as in 2*3=23. Now, suppose I ask, is {2, 3} a semigroup? According to technical definitions, I can NOT properly call ({2, 3}, *) a semigroup, since closure doesn't hold. But, this misses the point I, and I suspect others, would want to ask. I want to ask 'does associativity hold for concatenation? Does order affect the results for concatenation?' Techincally speaking, I have to extend
{2, 3} to an infinite closed set before I can properly evaluate whether order affects the results for concatenation. But, practially speaking I don't have to do this to figure it out. I can merely state that x*y=xy from the definition of '*', and then write (a*b)*c=ab*c=abc and a*(b*c)=a*bc=abc. Consequently, I have sufficient reason to declare that I know that concatenation works associatively (or that order doesn't affect the results of concatenation). No, I don't have a full proof, but I do have the main part of a full proof, and some might even say I have a partial proof. With an overemphasize on closure here I don't have sufficient to declare concatenation associative, since I didn't start with a closed set.
[You understand it as english. It is english.]
I don't see how English qualifies as a closed set (over what operation? conversation?). In fact, since English has historically borrowed MANY words from other languages, and continues to do so as it evolves, I would say that the 'operation' of conversation implies English as a non-closed set. I certainly don't see how English qualifies as a 'closed world' since it continues to evolve and act with other languages.
[If I use the natural numbers to construct the integers, what I'm doing is using a well-understood, proven-sound system, and using it as a basis for implementing a new abstraction.]
I don't perceive, nor conceive, how *soundness* has gotten proven to the natural numbers.
[When I talk about integers, I'm talking about its closed world, the construction of the integers. In the construction, I'm only dealing with constructed integers and the operations on constructed integers. The construction is like the interpreter - it's there, it's filling a necessary role - but when I'm looking at the construction and its properties, I need to stay inside the construction.]
This won't tell you how the construction relates to the "outside" mathematical world. For example, remaining in the integer construction won't tell you about the rational construction. Staying strictly inside the integer construction won't tell you that the operation '*' for non-zero integers has an inverse operation '/' among a richer construction. Staying inside such a construction won't tell you that one can form richer constructions, as one has to see what happens when closure doesn't hold to find/invent richer constructions. In other words, staying inside a construction won't lead to new maths.
Posted by: Doug | November 7, 2007 11:24 PM
Doug, your ability to miss the point so consistently, and at such length, is an example to us all.
Mark is showing you how you can start with, in this case, the natural numbers, and construct the integers, defining not only the objects (integers) but also the operators (+z, -z) for the construction. The constructed -z is not the - of the natural numbers. You seem to be misunderstanding what he means by "closed world". "Closed world" means that you can't use the raw - of the naturals on a constructed integer as if it were the constructed -z operator; that would be breaking the construction. Now, we could use our constructed set of integers and use them to construct a new set of objects, the rationals. And in the rationals, we would define a new set of operators, +r and -r. Using the integer -z operator on objects in the rationals would break the construction, just as using the natural - operator on objects in the integers would break the construction.
In short, "closed world" means you can't use the raw operators of the substrate level on objects on the constructed level. It doesn't mean that you can't construct a higher level. it doesn't forbid you constructing the rationals from the integers.
Posted by: Stephen Wells | November 8, 2007 5:39 AM
If there's no such thing as the empty set, and I can hardly think of a better candidate for non-existence, then it's hard to see how to get the ZF ball rolling. That's not to mention any ontological scruples we might have about the existence of sets. I mean, here is my computer in front of me. Is {my comupter} also in front of me? And furthermore is {{my computer}, my computer} here before me? And also {{{my computer}, my computer}, {my computer}, my computer}? And so on?
And one is a philosopher for doubting these things? I would think it would take a philosopher to believe them! Of course, I believed wholeheartedly in sets when I was indoctrinated (to put it provocatively) in mathematics classes and have only developed doubts in studying the philosophical foundations of mathematics. That is not to say that I now reject set theory altogether, but rather that I think that the naive platonistic conception of sets is misleading. Certainly, assuming the existence of the ZF sets as a domain of interpretation over which to model the Peano Axioms now has no more appeal to me than simply assuming the existence of the numbers themselves.
Indeed, it seems in a way more plausible to think that the number zero exists, as a form in Plato's heaven perhaps (though current philosophers are more subtle in their metaphysics of abstract objects), than to think that something as bizarre as the empty set exists. Should we say that it is impossible that nothing exist because the empty set exists and it is a thing? One direction in recent philosophy of math has gone in developing an alternative to the ZF, VN, etc. style set theoretical constructions of models for the Peano Axioms is to return to Frege.
Frege got into trouble, famously, with his Basic Law V, which leads to Russell's Paradox. However, some modern commentators have noted that in Frege's logicist development of arithmetic he only uses Basic Law V to prove Hume's Principle, then derives arithmetic from that. Here is Hume's Principle:
(The number of Fs = The number of Gs) iff (F is equinumerous to G)
Hume's Principle provides an implicit definition of "number". On the left hand side of the biconditional is an equality sign that is flanked by objects (as indicated by the use of the definite article "the"). On the right had side is a relation of equinumerosity (defined in second order logic in terms of 1-1 correspondence) that holds between concepts. The Neo-Fregeans take Hume's Principle to be an analytic truth. Much of the philosophical debate has been over the analytic status of Hume's Principle. From this analytic truth we are able to derive the existence of numbers themselves as objects.
They are, to be sure, quite abstract objects. Leading Neo-Fregeans Bob Hale and Crispin Wright call them "shadows cast by our language". One might think of abstract objects such as numbers on analogy with The King in chess, not this or that particular token but the type itself. The King is a shadow cast by the rules of chess. Now, maybe you find this implausible or problematic. There's plenty of work to be done and many are skeptical that the Neo-Fregeans can deliver a foundation for mathematics based only on logic and definitions like Hume's Principle. Or maybe you think that definitions can't bring objects, no matter how shadowy, into existence. I sometimes think that. However, none of this seems any less plausible than thinking that the empty set exists. Even if one gives a similarly shadowy account of its existence, why would you interpret "0" to be it? Sure, ZF gives a model for the Peano Axioms, but so does the sequence of natural numbers. So I guess my point after all this rigamaroll is why not interpret the Peano Axioms over the natural numbers themselves?
Ok, I've said a lot and some of it I'm not so sure of, but here's some final thoughts that I'm similarly not so sure of. This is a loose account of some ideas Prof Gregory Landini is developing in the math logic course I'm presently enrolled in. For ease of exposition I'll stop doubting the existence of sets for a moment, though I think that what I have to say next can be stated in 2nd order logic without an ontology of sets as long as one is comfortable with heterogeneous functions. The empty set is a set with nothing in it. It has cardinality zero. Every set with nothing in it is extensionally equivalent to the empty set: e.g., the set of things not equal to themselves, the set of square circles, etc. The set containing the empty set is a set of cardinality one, but it is not extensionally equivalent to every equinumerous set. For example, the set {my computer} also has cardinality one, but is not extensionally equivalent to the set containing the empty set. What I'm driving at is that the ZF constructions give us exemplars of extensions of concepts (e.g., the concept "being the empty set or being the set containing the empty set") that satisfy higher order cardinality concepts (e.g., the second order concept "being a concept that exactly two-many things exemplify"). Why should we think of numbers as these or those particular exemplars of a cardinality concept and not as the cardinality concept (i.e., quantifier concept) itself?
Posted by: Jeremy Shipley | November 8, 2007 11:32 AM
Doug: "I've never seen an uncertain statement in two-valued logic, have you?"
Here is an uncertain statement in two-valued logic: There is intelligent life in the universe outside of earth. The statement is either true or false. We just don't know which. Here is another, perhaps more controversial, example: Every even integer greater than 2 is the sum of two primes. Here's another: The number f blades of grass on the pentacrest is odd. There are countless examples of statements that are either true or false, but we don't know which.
You seem to be confusing the epistemological status of knowledge and knowability with the semantic status of truth and falsity.
(This isn't to say I don't think that many-valued logics may have their place; e.g., in dealing with statements involving so-called "fuzzy" predicates like "bald". See the Sorites paradoxes, for example).
Posted by: Jeremy | November 8, 2007 11:46 AM
WRT to uncertain statements in two-valued logic - I think that the most interesting things are not really uncertain, but they are unprovable while clearly being true.
The classic example of this comes from Gödel: "This statement cannot be proven." Properly stating it takes a bit of trickiness - but it ends up working out. It's clear that
you can't produce a proof of the statement. And yet, for it to be false, you'd need to show of proof that it is true. So you can see that it is true, in some deep sense of the word "true"; but it's not provable. So it *does* lie in a kind of uncertain realm: true, but not provable within the constraints of a formal system. This, in turn, shows that you can't equate truth and provability. To be geeky, the set of true statements is a superset of the set of provable statements.
Posted by: Mark C. Chu-Carroll | November 8, 2007 11:53 AM
Mark. The sense in which the Godel sentence is true is not just some intuitive sense as suggested by your "you can see that it is true". Hopefully someone will correct me if I am wrong since I'm working through the details of this stuff for the first time, but isn't the Godel sentence true in the well-defined sense of truth in terms of satisfaction developed by Tarski. Here's how I've been understanding it. Tarski gave "true" and "provable" different senses. Godel showed they have differing extensions, if arithmetic number theory is consistent.
Posted by: Jeremy | November 8, 2007 2:46 PM
Stephen Wells,
You may speak correctly about me missing Mark's point within what I write. However, I more think that Mark's point doesn't come as sufficient for what I think he wants to argue: the adequacy of (crisp) set theory. Look, even if techincally speaking one can derive much-to-all of maths from (crisp) set theory, that doesn't mean it works out as sufficient as a basic philosophy of math.
[In short, "closed world" means you can't use the raw operators of the substrate level on objects on the constructed level.]
So, 'closed world' places a restriction on how we use operators. I have a problem with exactly that, as I've indicated it leads us to think that using operators to study maths leads to invalid perspectives, or at least it did with the rejection of negative numbers.
Jeremy,
[Is {my comupter} also in front of me? And furthermore is {{my computer}, my computer} here before me? And also {{{my computer}, my computer}, {my computer}, my computer}? And so on?]
*laughs* yeah that does seem ridiculous, but according to set theory it those sets "exist" as much as the natural numbers.
[Why should we think of numbers as these or those particular exemplars of a cardinality concept and not as the cardinality concept (i.e., quantifier concept) itself?]
Maybe I should scream at this one. Look, let's suppose we regard numbers as the cardinality concept, or as you put it the quantifier concept. Then, for infinite sets, any 'there all' quantifier ends up getting interpreted as an infinite number. It also works out that such an infinite number works out as equivalent with all other infinite numbers for the infinite set in question. One can talk about infinite numbers in terms of non-standard analysis, but infinity+1 does not equal infinity+2 there, so your cardinality=quantifier proposal fails here. For the 'there exists' quantifier, we would have to assign a number to 'there exists'. You might naively think assigning '1' will work. However, the 'there exists' quantifier doesn't say 1, it says *at least* 1. So, let's say we have a set like
{1, 2, 3, 4, 5}, and I want to know if there exists x>2 for this set. Well, there does exist *at least* one x such that x is greater than 2, so the 'there exists' quantifier works. But, if I interpret the the 'there exists' quantifier as '1 x', then the 'there exists' quantifier comes out incorrect since 3 xs exist here.
Lastly, if we consider quantifiers such as 'most', 'almost all', 'very few', etc. we would have to assign a unique natural number or infinity to each of these quantifiers, since the classical cardinality concept permits only those types of cardinalities (as far as I see it). Well, these quantifiers don't have precise, unique natural numbers assignable to them accurately. We need more than just one number, and numbers other than natural numbers to approximate the meaning of such quantifiers numerically, and indicate our 'numerization' of those quantifiers as contextual (which is fine... but not so necessary with crisp cardinality).
Jeremy,
["I've never seen an uncertain statement in two-valued logic, have you?"
Here is an uncertain statement in two-valued logic: There is intelligent life in the universe outside of earth. ]
Hmm... I think you've got me there. Well... maybe not though, because I doubt that the term 'intelligent' actually happens within two-valued logic. Really, I'd state that as a non-two-valued statement, as I think intelligence comes in degrees and in enough cases talking of someone/something coming as either 'intelligent' or 'not-intelligent' comes out quite silly. So, I could reject your example here.
Still, I can see your possible point, and I think need to rephrase that. Given perfect or complete information, I've never seen an uncertain statement in two-valued logic. That's the thing, in non-classical logic, one can literally have all the information in and statements still come out uncertain.
[Here is another, perhaps more controversial, example: Every even integer greater than 2 is the sum of two primes.]
Given the complete set of all natural numbers (perfect information), a small infinite set, this comes as certainly true or false. The problem comes as finding a mathematical system which allows us to view such a set completely with respect to primality.
[The number f blades of grass on the pentacrest is odd.]
How do interpret 'blades of grass'? Does some grass which stands 5 feet high count as much as a 'blade' as a piece of grass which I've just cut? I don't feel certain that statement comes out in two-valued logic.
[There are countless examples of statements that are either true or false, but we don't know which.]
The Goldbach Conjecture comes out as a good example. But, I can actually modify that statement somewhat to say "even numbers are the sum of two primes." I can claim this as partially true. Well, I know that in millions of cases this statement works out true, since computer programs have verified such. Of course, you could retort that this comes out as an infinitesimally small number of cases, since no matter how many millions of cases we have, there always exist a countable infinity of cases where such a conjecture might not hold, as we haven't checked a countable infinity of cases. So, my claim of such a statement as "even numbers are the sum of two primes" working as 'partially true' doesn't work out as significant whatsoever, even if it doesn't have a degree of truth of 0.
[(This isn't to say I don't think that many-valued logics may have their place; e.g., in dealing with statements involving so-called "fuzzy" predicates like "bald". See the Sorites paradoxes, for example).]
Well, of course they have application here. But, you can also use them to deal with paradoxes like the liar paradox. To use a variant of it, if someone says "this statement is false," then if we take it as true, then the statement comes out false. But, if taken as false, then the statement comes out true. Or symbolically T->F and F->T. Of course, that's a big problem for classical logic (maybe one can use a theory of types to resolve it). But, with fuzzy logic one can solve it much more simply. One just assumes that if P->Q and Q->P we have logically equinvalent truth values. So, we have T=F. In other words we have an equilibrium of truth values. Given the standard 1-a for complementation, then we have the liar paradox indicating that such a statement has truth value of 1/2, as a=1-a, when a=1/2 ONLY. Most philosophers seem to think that people like Epimenides meant these statements more as a way to show the inadequacy of two-valued logic, rather than to challenge two-valued logic to develop new solutions to problems... so I would maintain that the 'fuzzy logic' solution goes more along with the original spirit of these paradoxes than something like the theory of types.
Mark,
[So it *does* lie in a kind of uncertain realm: true, but not provable within the constraints of a formal system. This, in turn, shows that you can't equate truth and provability.]
It got done for thousands of years, and people still do so. Do you think such a 'proof' will dictate to them what they can and can't do in formal systems, when they already have acted otherwise? Second, I don't see how it shows you can't equate truth and provability. Again, that consists of an *interpretation* (not to say it qualifies as a bad one). If you guys really think that Godel's statement says something about truth and provability, then you would literally have the ability to demonstrate *from the text* that Godel's proposition VI says that. Has anyone done that here? Has anyone come close? Until you've done that, all you've indicated that many people interpret Godel's proposition VI as saying that. There's the paper:
http://www.vusst.hr/~logika/undecidable/godel.htm
Posted by: Doug | November 8, 2007 3:07 PM
Mysticism: believing in something you can't prove. So, if the *hypothesis* that Godel's proposition VI says that there exist arithmetical truths for formal systems like that of PM and ZFC which come as 'true, yet not provable', then one becomes a mystic by accepting such a system as PM or ZFC or a similar formal system. Yeah... I don't think so.
Posted by: Doug | November 8, 2007 3:12 PM
I'd also argue that non-two-valued statements exist within pure mathematics, such as "the difference between 1 and 2 is about the same as the difference between 3 and 5," or "the difference between 3 and 4 is much, much smaller than the difference between -1 and 10^600."
Posted by: Doug | November 8, 2007 3:34 PM
Jeremy:
Yes, you are correct - I was trying to give an intuitive explanation, rather than get into the details - since we're already having enough trouble with the details of what we're actually talking about.
Posted by: Mark C. Chu-Carroll | November 8, 2007 3:48 PM
Doug. Your points are reasonable enough on the two-valued logic matter, especially since I conceded some ground on fuzzy predicates. However, I could certainly give some kind of operational definition of "blade of grass" to clarify any ambiguity you'd like and the blades of grass example will come out. Or if you'd like, try grains of sand on a beach. The point is that what is true and what is known (or certain or proven, etc.) can come apart. . . There is much more to be said here than can be said in blog comments so I'm not going to pursue this further, but you might check out Fitch's paradox of knowability.
Setting that aside because it would take a dissertation to defend either of our views, I wonder what you'd say to the following point. Even many-valued logics are two-valued in the following way: Propositions are either not at all true or at least little bit true. Consider baldness. It's a plenty fuzzy predicate, but certainly some of us are not at all bald. Or to take the blades of grass up. Perhaps you're convinced that there are borderline cases that are not clearly countable as blades, but certainly if I'm sitting in the pentacrest you won't count me!
Moving on. . . I think that you misunderstood me on the point about cardinality concepts. Maybe I shouldn't have used the term "quantifier concept". However, I wasn't suggesting anything like the view that you criticized. Certainly, I'm well aware of how existential quantification works. However, we can use existential and universal quantification to make a schema into which we can truthfully put only those concepts that there are exactly one thing of:
(there exists x) (Fx and (for all y) (if Fy then x=y))
Comprehend that schema as a second order concept. That's the sort of thing I have in mind as a cardinality concept. I called it a "quantifier concept" because it expresses the property "there are one-many Fs" in terms of a quantificational structure. I certainly didn't have in mind that that was simply (there exists x)(Fx).
Anyhow, I'm still a little sketchy on all of this so. . . yeah.
Posted by: Jeremy | November 8, 2007 3:49 PM
So, if the *hypothesis* that Godel's proposition VI says that there exist arithmetical truths for formal systems like that of PM and ZFC which come as 'true, yet not provable', then one becomes a mystic by accepting such a system as PM or ZFC or a similar formal system.
There is a critical-- but common-- misunderstanding here. (One can catch Roger Penrose making the same error in a different context.) Godel does not say this inability to prove is a limitation of PM or ZFC. He says anything capable of expressing the arithmetic found in PM has this limitation. The limitation is present for ZFC and PM and also any potentially more "powerful" systems. This will include, for example, fuzzy set theory, since normal ZFC can be easily constructed within fuzzy ZFC.
Now, it's worth noting that there are systems which can prove some of the statements about ZFC which ZFC cannot prove about itself. But these systems don't escape Godel's cage either; these systems may be able to prove ZFC's unprovable statements about ZFC, but the cost is the higher-order systems make it possible to make statements about the higher-order systems which those systems cannot themselves prove. You can't escape incompleteness, you can only alter where the incompleteness pops up-- unless you're willing to go the other direction and accept the Pyhrric victory of adopting a system which is too weak to allow those operations which are necessary for Godel's theorem to hold.
The problem you identify comes not in "accepting such a system as PM or ZFC or a similar formal system", but in attempting to accept a meaningful formal system at all. But of course it is only in a formal system that we can make demands like "statements which are true should be provable" in the first place...
Posted by: Coin | November 8, 2007 5:17 PM
[The point is that what is true and what is known (or certain or proven, etc.) can come apart]
Well put.
[I'm not going to pursue this further, but you might check out Fitch's paradox of knowability.]
Thanks for the tip.
[Setting that aside because it would take a dissertation to defend either of our views, I wonder what you'd say to the following point. Even many-valued logics are two-valued in the following way: Propositions are either not at all true or at least little bit true.]
I consider your statement here mostly true (true of most multi-valued logics), but not all of them. If we have a neutrosophic logic, where truth values can work out infinitesimally larger than 0, yet not 0 (using non-standard analysis), then there exist propositions which don't work all true, nor 'a little bit' true, as for any 'little bit of truth' given the proposition in question can have truth value smaller than that little bit, but not 0. Maybe you want to say I've equivocated on the use of 'little bit' here. Fine. I can say you equivocated on the use of 'two-valued', since you've used it outside of the context {T, F} or something equivalent to it.
More interestingly, perhaps, I can reject such in the following way. I treat 'truth' as a linguistic variable and assign membership functions to quantifiers of 'truth' like 'absolutely no', 'little bit', 'little', 'medium', 'high', 'very high', and 'all true'. Adjacent categories overlap at some points, while non-adjacent categories overlap at no points. Consequently, 'very high truth' works out as neither 'little bit truth', nor 'absolutely no truth.'
Oh wait... you said 'at least little bit' true. Perhaps if you modified this to say that truth values come either having 0 degree of truth or a truth value equal or greater than that of a positive infinitesimal, then it might work. I guess you can call that 'two-valued' in a sense, but we often don't call statements with truth value of 10^-200 true, we call them false. So, there may exist something techincally to such as 'two-valued', but practially speaking I don't see it.
[It's a plenty fuzzy predicate, but certainly some of us are not at all bald.]
Sure. Then again, everyone one of his has space in between hairs, since atoms come out discrete.
[Maybe I shouldn't have used the term "quantifier concept". However, I wasn't suggesting anything like the view that you criticized.]
Good... that's actually a relief.
Coin,
[There is a critical-- but common-- misunderstanding here.]
Yeah... I forgot about that condition there. Still, it remains that Goedel doesn't say anything about truth and provability, so far as I can see from the text. He talks about provability, and basically shows provability can't work out as bivalent for all formal systems (that there exist some propositions for some formal systems where you can't prove the proposition, nor prove the negation).
[The problem you identify comes not in "accepting such a system as PM or ZFC or a similar formal system", but in attempting to accept a meaningful formal system at all.]
So there exists a mismatch between form and meaning. One intepretation of that comes as that one can't use maths to analyze language, since math comes as formal and language comes as informal. But, applications of fuzzy set theory make *some* progress towards analyzing language through math. Of course, it works out as an approximation at best, but still it happens to some degree, and the problem becomes more tractable when you use higher types of fuzzy sets.
[But of course it is only in a formal system that we can make demands like "statements which are true should be provable" in the first place]
If allow degrees of provability and degrees of truth, I don't see that.
Posted by: Doug | November 9, 2007 12:28 AM
Grrr... I started thinking too numerically. In a three-valued logic with truth values of {T, U, F}, there exists the ordering of F
So, in response to your query... no. In fact, one can even construct a three-valued logic in a quasi/psuedo logical positivist way with truth values of 'true', 'false', and 'meaningless'. A strict positivist might even claim that ordering to truth values would give them too much meaning for the 'meaningless' predicate to apply, as I understand positivism. Looking back, I wrote something admittedly sketchy on how one might get a positivist to accept such a logic, not for propositions, but declarative statements (which hopefully I indicated how such a hairline distinction might work and why you *need* it for such a three-valued positivistic logic... although I don't know, I've just looked back). You can find it here:
http://www.xanga.com/Spoonwood/583936702
/a-possible-positivist-three-valued-logic.html
Posted by: Doug | November 9, 2007 12:59 AM
Sorry, the link doesn't work.
It's the Saturday, April 14, 2007 entry at
www.xanga.com/spoonwood
Posted by: Doug | November 9, 2007 1:00 AM
However, I am unaware of the implications of allowing truth to be 'shared' across formal systems. This may end up being an incoherent statement.
Posted by: Xanthir, FCD | November 9, 2007 10:15 AM
Doug I really have no desire to try and teach you meta-logic within the confines of a blog comment column. If you really want to know why Gödel's theory is about the fundamental difference between truth and provability in formal systems then read Raymond M. Smullyan, Gödel's incompleteness theorems, New York, 1992. If you still think we are wrong after that then nobody can help you.
I will get back to the subject of classical science and two valued logic at the weekend when I have more time and less work.
Posted by: Thony C. | November 9, 2007 11:54 AM
I have conversed at length, face to face as well as in blogosphere, with well intentioned crackpots who simply cannot stand, for emtional reasons, Gödel's theory.
It arouses visceral hatred in perhaps the same way that Einstein does to anti-Relativists (especialy Aetherists) and Darwin (especially Intelligent Design-kooks).
And they are even less likely to chip away at it, let alone demolish it, as it does not depend on the Physical universe (Special or General Relativity) or Life as we Know It (neodarwinian synthesis).
Worse to me are smart but aggressively self-promoting and well-funded cultists such as the uncredentialed Bostrom sidekick Eliezer currently having an ignorantly phrased DNA information theory question well-answered on Scott Aaronson's blog by people who found a good question buried in the falsifed ignorance, and gave the cultist a series of interesting and mathematically valid answers. The loon has won over Scott Aaronson, and other bloggers who should know better, in part because of an alleged nonprofit foundation with Big Names in the board, which has had to move from state to state 3 times due to malignant financial irregularities, making one of my favorite blogs someplace that I won't post to for quite a while.
Sorry. I think we'd all rather discuss Gödel, and why people rcoil in horror from its conclusions. I'm tempted to start a diwscussion about Gregory Chaitin, who was so generous to me with his time at the ICCS-2007 conference last week. But not now.
Posted by: Jonathan Vos Post