Mathematics and unprovable assumptions

[Canute]

I've tried every combination of those key presses that I can think of and it doesn't work. I'm sure this is my fault but I'm mystified. I must be one of the few people who find philosophy easier than writing umlauts.

 

[Tsunami]

Kant, Gödel, Tarski - help

Hi, (not finished yet, but fear of my computer crashing makes me post this alreadY)

I'm sorry for being lazy again and asking for help here instead of looking stuff for myself, but I'm being lazy merely because I've tons of other stuff to read.

What I want to understand is:

1) Under what conditions does Gödel's incompleteness theorem 1 hold? (That for theories defined in a certain way, statements exists which are true but unprovable)

2a) Why does geometry not obey these conditions?
2b) What properties does geometry for Tarski to be able to prove geometry to be complete?

3a) Kant's point is that the way we experience the world, shapes our theories a priori. His idea was that math (and logic) fundamentally is a priori: there are certain basic assumptions in math and logic which are given before every conscious theory. So, math is not based on analysis of given things and experiences: rather, it starts with synthetic assumptions, something we add to the things that are given, by experiencing them.

3b) Gödel was very much influenced by Kant, and his incompleteness theorem was inspired by or at least backed up by the idea that math is a priori. It is because our theories about logic are incomplete, that it becomes necessary to say we need the way our thinking works to found this logic. This is the line of thought Gödel would use (I think). I'm not stating that he's right, but that this was his goal. So, I'm wondering, what does Gödel's idea and Tarski nuance imply for our possible knowledge? So, please, I encourage to take this to a broader level than certain regions of mathematics, or certain regions of logic, and see for what kind of knowledge in general, Tarski's and Gödel's theories hold.

There's been a lot of discussion on this forum about Gödel, and Tarski - much of these discussions have been totally messed up because people were divided in two sides, the laymen who saw all kinds of strong implications in Gödel etc. , and the mathematicians who became increasingly frustrated by this (and understandably so).

So, I'd like this thread to be about stating what implications are present, and nothing more than this. So as to increase understanding. Thank you.

 

[Hurkyl]

In what follows, for a statement P, the notation ~P denotes "not P".


Suppose we have a language L.


In this language, we have chosen certain predicates N, P, and M. Intuitively, their meaning is:
N(x) := x is a natural number.
P(x, y, z) := x + y = z
M(x, y, z) := x * y = z


Suppose we have a set S of axioms.
Suppose further that S is "Turing-recognizable" a.k.a. "recursively denumerable".
Any finite set is Turing-recognizable... but Gödel's theorem still works for Turing-recognizable infinite sets of axioms. Essentially, we simply require that there exists an algorithm that can write down elements of S one at a time, and every element of S will eventually appear in this list.


There is a set Th(S), the "theory of S". It consists of every statement that can be proven from S.
Suppose that the axioms of natural number arithmetic (written in terms of N, P, and M) are elements of Th(S).
Suppose further that S is consistent, meaning that Th(S) doesn't contain everything. (In particular, if P is in Th(S), then ~P is not in Th(S))


Then Gödel's theorem says that Th(S) is not complete.
In particular, this means that there exists a statement P in the language L with the properties:
P is not in Th(S)
~P is not in Th(S)

In other words, P can be neither proven nor disproven from S.


If we have a model of S, then every statement in our language L is either true or false in this model. In particular, either P or ~P will be a true statement (in this model) that cannot be proven from the axioms.

-------------------------------------------------------------

The reason Gödel's theorem is not applicable to Euclidean geometry is because it is impossible to formulate the predicate "x is a natural number".


I've only seen Tarski's proof of completeness in the algebraic setting.

There's a set of axioms for a kind of thing called a "real closed field" -- these axioms are simply the first-order logic versions of the axioms of the real numbers.

In the ordinary set-theoretic approach to Euclidean geometry (using Hilbert's axioms), we can construct the real numbers, and do all of the geometry algebraically.

Tarksi gave first-order logic versions of Hilbert's axioms to define a first-order logic version of Euclidean geometry. In this formulation, one can construct a real closed field, and then do all of the geometry algebraically in terms of that.

The key thing you can do in real closed fields is "quantifier elimination". E.G. if you have the statement:

"There exists an x such that f(x, y, z) = 0"

then it is possible to rewrite this statement in terms of y and z alone. For example, the statement

"There exists an x such that x²y + z = 0"

is true if and only if "(y = 0 and z = 0) or (y \neq 0 and zy \leq 0)"

 

[Tsunami]

hold on, my computer crashed twice, and I've the idea that this will work better as a separate thread :).

Would you mind reposting this as soon as I finished my post and put it in a new topic?

 

[kant]

I wasn't quite sure what I should call this, so I hope the tile is OK.

Now over the weekend I've on on a general message board where I saw the ideas of mathematics and religion being discussed. The connection with religion is not what I'm interested here, but rather the following sentence that was said and a couple of it's replies.

First one guy said:


Then there was a reply to this asking for some specific examples of these unprovable asumptions.
This request got the following replyn(from a different person to who made the first comment, but who, nevertheles, had shown similar views throughout the rest of the disscusion):


I was just wondering what you here made of this, as I wasn't too sure what it was all about myself. Some feed back on this would be great.

Math is sort of "like" religion. You can t say it is exactly like religion. In religion, the notion of a god cannot be challenged, while in math, the notion of axioms cannot be chanllenged and must be accepted on faith.

 

[Hurkyl]

while in math, the notion of axioms cannot be chanllenged and must be accepted on faith.

A common mistake that entirely misses the point of the axiomatic method.

For example, we define Euclidean plane to be a collection of points and lines (and the relations "congruence", "betweenness", and "incident") that satisfy a collection of axioms.

We don't take thexe axioms on faith -- to talk about the Euclidean plane is to talk about something for which those axioms are true. If we are talking about something for which those axioms are false, then we're not talking about the Euclidean plane.

 

[kant]

A common mistake that entirely misses the point of the axiomatic method.

For example, we define Euclidean plane to be a collection of points and lines (and the relations "congruence", "betweenness", and "incident") that satisfy a collection of axioms.

We don't take thexe axioms on faith -- to talk about the Euclidean plane is to talk about something for which those axioms are true. If we are talking about something for which those axioms are false, then we're not talking about the Euclidean plane.

Sure...sure sure..Those axioms are only true where the space is flat. What is "true" in one set of circumstance, might not be in another set of circumstance( not flat). So what is your point?


when we talk about the axioms; there are assumptions we must accept as self-evident. A point, or a line has not mean what so ever by "themselve". It is not just math. It is language itself. words in a dictionary has a way of defining themselves. A child must begin with self-evident truths about the meaning of certain words by assocation with a particular emotions, and accumulate to build upon those self-evident words to more complex words and expressions...

 

[matt grime]

Sure...sure sure..Those axioms are only true where the space is flat. What is "true" in one set of circumstance, might not be in another set of circumstance( not flat). So what is your point?

the point is to illustrate a common mistake people make

when we talk about the axioms; there are assumptions we must accept as self-evident. A point, or a line has not mean what so ever by "themselve". It is not just math. It is language itself. words in a dictionary has a way of defining themselves. A child must begin with self-evident truths about the meaning of certain words by assocation with a particular emotions, and accumulate to build upon those self-evident words to more complex words and expressions...

Yep, that mistake.

The statements that there are points, lines, and they satisfy the axioms of Euclidean geomoetry can be proven in euclidean space, they are not assumed to be self evidently accepted as true in euclidean space: for example, the parallel postulate.

Let L be a line (let's do it in 2-d) y=mx+c, and let p be a point, suppose L' is some line through p, say y=nx+d, then it is easy to see that there is exactly one parallel choice (n=m, this fixes d) and that any other choice leads to two simultaneous equations in two unknowns that can be solved (i.e. they intersect).

 

[kant]

the point is to illustrate a common mistake people make





Yep, that mistake.

The statements that there are points, lines, and they satisfy the axioms of Euclidean geomoetry can be proven in euclidean space, they are not assumed to be self evidently accepted as true in euclidean space: for example, the parallel postulate.

Let L be a line (let's do it in 2-d) y=mx+c, and let p be a point, suppose L' is some line through p, say y=nx+d, then it is easy to see that there is exactly one parallel choice (n=m, this fixes d) and that any other choice leads to two simultaneous equations in two unknowns that can be solved (i.e. they intersect).

How do you define a point or a line? You are telling me you can prove these stuff by something more fundamental? You are talking about step by step deduction, yes?



There is this very funny joke. In this really old dictionary. If you look up definition of a woman. The definition states: A woman is a partner of man.

 

[matt grime]

All I need to do is declare L, the obvious things, to be the set of lines in R^n, and P to be the set of points, again the obvious things, in R^n and they satisfy the axioms of Euclidean geometry. I am assuming none of the axioms of Euclidean geometry are true, or false, for that matter. I am completely free to attempt to declare any thing to be 'points' and 'lines' but they won't then satisfy the axioms of euclidean geometry.

You are confusing an axiomatic scheme with a model of the axioms. Axioms are not true or false in some sense, they just are. They are only true or false when applied to some model. In the model these things are not assumed true.

I can take any collection of things, and declare something to be a set of lines and something a set of points. I then need to verify that they satisfy the axioms. I can even take the dual space and swap the roles of lines and points. (Think linear spaces, as well.) I can take the disc with points the obvious things, and lines the set of arcs that intersect the boundary at right angles. In this model the axioms of euclidean geometry are demonstrably false: I am not assuming that the parallel postulate is false; it is false by construction."How do you define a point or a line?"
I'll define a point in R^2 to be an element of R^2, and I'll define a line to be a locus of points satisfying a linear relation. Why? Because I can prove this makes it a model of Euclidean geometry and I am assuming none of the axioms are true. I could do it differently. It's easier to think of hyperbolic geometry as it happens because I can think of 3 models of that: the upper half plane, the disc, and the one you get from projecting curves in 3-d to (part of) the plane (which was the original one).

There are certainly philosophical issues to be pondered with axiomatic set theory, but we really ought not to describe axioms as things that are held to be self evidently true. They are just 'things'.Let's take s silly example.

Let's start with axiom 1 'I like brussel sprouts' and axiom 2 'anyone who likes brussel sprouts likes parsnips', then in this system, it is provable that I like parsnips. However I hate brussel sprouts (and I hate parsnips) so the truth or otherwise of the first axiom is irrelevant from drawing conclusions about statements in the axioms.

The same is true in mathematics. If axioms are self-evidently true how can there be more than one geometry?

 

[HallsofIvy]

The whole point of mathematics is that it is applicable to a variety of fields. Newton created calculus in order to solve problems in physics (specifically, the motion of planets). Yet people who are planning to use mathematics to solve problems in biology, psychology, or economics learn the same calculus.

That works precisely because axiomatic systems have "undefined words". In order to apply theorems from calculus (or linear algebra, or differential equations, or tensor theory) I have only to decide what meanings I will give to those undefined terms and then show that the axioms apply (at least approximately- in any real application, we have measurements that are only approximate) and then know that the theorems will be true for this application (again, at least approximately).

That's why mathematics is not "like religion". The one thing that all "Christian Religions" have in common (Jeff Lawson's referentce to "The Christian church" is naive at best- there are may different "Christian churchs" with widely varying beliefs) is that "Jesus Christ was an aspect of God that became human". Certainly no good Christian that I know would take the point of view that that is "true in some systems but not in others" which is exactly what mathematicians do.

No mathematician believes, for example, that "through any point not on a given line there exist a line through that point parallel to that given line" (Playfair's axiom). Mathematician accept that as an axiom for a certain axiomatic system (Euclidean geometry) which has proved to be a good model for many applications but not for some others. We can accept it as true (not assert that it is true in any universal sense) for some applications and as not true for others. I don't know of any religion that does that!