High School Is everything in math either an axiom or a theorem?

[PeroK]

I've been meaning to ask about that. It seems to me that what Gödel actually discovered is that self-reference is different kind of thing that isn't compatible with normal everyday logic i.e. the pattern of true/false doesn't necessarily apply to self-referential statements. I have yet to see an example of it in a non-self-referential context i.e. a statement that isn't self-referential and not true/false. It seems that as long as you stay away from self-reference, you should be fine.

The so-called axiom of choice cannot be proved to be true or false, but is generally adopted as an additional axiom.

 

[Feynstein100]

The so-called axiom of choice cannot be proved to be true or false, but is generally adopted as an additional axiom.

I don't get it. Would you mind elaborating?

 

[PeroK]

The other very important aspect of mathematics is the objects we choose to study. From the natural numbers to groups to differential equations to topology etc.

There's also the way we think about mathematics. Which is outside the formal system of axioms and theorems. Question's like how do I go about proving this? Is it true? Can I find a counterexample? Etc.

 

[PeroK]

I don't get it. Would you mind elaborating?

Try an Internet search.

The premise of your posts seems to be that we should forget Goedel and pretend Incompleteness isn't a thing.

 

[TeethWhitener]

I've been meaning to ask about that. It seems to me that what Gödel actually discovered is that self-reference is different kind of thing that isn't compatible with normal everyday logic i.e. the pattern of true/false doesn't necessarily apply to self-referential statements. I have yet to see an example of it in a non-self-referential context i.e. a statement that isn't self-referential and not true/false. It seems that as long as you stay away from self-reference, you should be fine.

There are a few different things going on here. First is that Gödel doesn’t specifically say that the Gödel sentence (the technical version of “this is not provable”) is unconditionally true. He proved that if it is false, then the logical system is inconsistent (NB—I’m skipping over a lot of model theory technicalities here). Or, from the contrapositive, if the system is consistent, then the Gödel sentence is true.

Second is the necessity of self-reference for unprovability. Note that Gödel uses self-reference to prove his incompleteness theorems, but unprovable statements don’t require self-reference. Here’s a list of unprovable statements (called “independent”) on Wikipedia:
https://en.m.wikipedia.org/wiki/List_of_statements_independent_of_ZFC
There are subtleties here that I’m eliding because they go well beyond a B level thread.

Third is the relationship between self-reference and the bivalence (two-valuedness) of standard logic. This is actually pretty well-trodden: it can be shown, for instance, that for certain semantic instantiations of the liar paradox (i.e., “this sentence is false”), if you model the sentence with a logic that has more truth values than just “true” and “false,” the liar sentence will take one of those non-Boolean values.

But these are three separate ideas that are all kind of scrambled together in your post, when really they should be treated separately.

 

[Stephen Tashi]

Numbers are a kind of mathematical object that have certain properties. Why do they have these properties? There's no answer to that.

I disagree. The reasons that numbers have certain properties is that people invented the numbers and gave them certain properties. They gave them properties that made them useful in modeling many physical situations, There may be no answers to why physical situations have certain properties, but the reasons numbers have their properties is a topic for studies in sociology, culture, history.

 

[pinball1970]

I disagree. The reasons that numbers have certain properties is that people invented the numbers and gave them certain properties.

Did we invent the numbers? Give them properties? The nomenclature is ours (Arabic, Roman, Babylonian etc) but did we invent the actual numbers?
Give them properties? Even numbers, primes?
EDIT: I know this is straying away from the OP a little.

 

[SSequence]

There are a few different things going on here. First is that Gödel doesn’t specifically say that the Gödel sentence (the technical version of “this is not provable”) is unconditionally true. He proved that if it is false, then the logical system is inconsistent (NB—I’m skipping over a lot of model theory technicalities here). Or, from the contrapositive, if the system is consistent, then the Gödel sentence is true.

Second is the necessity of self-reference for unprovability. Note that Gödel uses self-reference to prove his incompleteness theorems, but unprovable statements don’t require self-reference.

There are few points that I feel are worth adding:
(1) I think that one thing here is that the way the godel sentence is formulated, the reference to provable isn't in some difficult meta-mathematical sense [but relative to the theory under consideration itself].

Let's take the example of first order PA as a (standard) example. The theorems of PA will be recursively enumerable (or, in alternative terminology, computably enumerable). Now the word "proveable" in the godel sentence for PA can be thought of as saying "proveable in PA" [that is, it is just talking about the theory under consideration].

(2) Secondly, when we say that godel sentence is true (assuming consistency of theory under consideration), then we are usually implicitly assuming the "standard" natural numbers. But it seems that you didn't want to get into this point in some more detail to avoid confusion.

(3) Also, it is worth mentioning that there are few versions of the incompleteness theorem. This was explained in an older post much better than I can:
https://www.physicsforums.com/threa...t-incompleteness-theorem.941469/#post-5954255

Here it is perhaps worth mentioning that, in the first version, the godel sentence gives a specific example of statement is independent.

(4)

Second is the necessity of self-reference for unprovability. Note that Gödel uses self-reference to prove his incompleteness theorems, but unprovable statements don’t require self-reference. Here’s a list of unprovable statements (called “independent”) on Wikipedia:

Now I know I am definitely nitpicking here, but I think it wouldn't be unsuitable to point out this briefly. A statement being "unproveable" in a given system is not equivalent to being "independent". To elaborate a bit, a statement being "unproveable" means that it can't be shown true in the given theory [in other words, the statement is not theorem of the given theory]. However, this is not equivalent to independence because we haven't eliminated the possibility of statement being shown false in the our theory [in other words, the negation of the given statement might still be a theorem of our theory].

Independence means that a statement is neither proveable nor disprovable in our given theory. Now I am sure you were aware of this. But I was nitpicking here so that someone who hasn't encountered these notions before doesn't get too confused.

Also, I think goodstein sequences are another good example of independence for first order PA (some others can be found mentioned on a source like wikipedia).

(5) Finally one point with respect to independence of CH. The truth and falsity of CH has no number-theoretic consquences [this particular statement can be made precise]. It is an interesting point. However, quite honestly I have no idea whatsoever why its actually true though. This definitely goes beyond the scope of this thread anyway [and my knowledge on this topic too].

 

[pinball1970]

It would be good to have @fresh_42 to comment here.

Yes some fresh input would be good!

 

[jim mcnamara]

A really good read meant for people with a secondary school background- "Godel Escher Bach, an Eternal Golden Braid" by Douglas Hofstadter This book does a great job of exploring the topics in this thread, IMO. And a lot more....

 

[SSequence]

I disagree. The reasons that numbers have certain properties is that people invented the numbers and gave them certain properties. They gave them properties that made them useful in modeling many physical situations, There may be no answers to why physical situations have certain properties, but the reasons numbers have their properties is a topic for studies in sociology, culture, history.

I certainly don't take this view [just talking about very last line].

This kind of view (particularly when talking about natural numbers), is very close to formalist way of thinking in my opinion. Certainly some mathematicians and logicians (including professional ones in both categories) do take this view at least to the extent I know. As far as I understand, there are variety of reasons that this view is taken. My guess is that some of the reasons [why mathematicians or even logicians might take this view] might be technical while other reasons might be of more practical nature.

Are there mathematicians or logicians who don't take this view? My guess would be that at least there would be some who don't take the quoted view.

I think I could briefly point out a highly simplified version of both views above and various reasons why they might be held [of course only based upon my own observation of these things]. But it seems to me that a discussion on this will steer off course very fast, so I think I will avoid it here (since the discussion in the thread seems to be about a different topic). However, it should perhaps be said that some of technical points raised by those do take a more formalist view are definitely nuanced.

Edit:
I noticed that you didn't specifically mention natural numbers, so perhaps you had something else in mind. In that case, I suppose this reply might not be directly relevant.

 

[Feynstein100]

I disagree. The reasons that numbers have certain properties is that people invented the numbers and gave them certain properties. They gave them properties that made them useful in modeling many physical situations, There may be no answers to why physical situations have certain properties, but the reasons numbers have their properties is a topic for studies in sociology, culture, history.

You basically ignored everything I said in my previous post. We can't have a meaningful discussion if you don't address my arguments

 

[PeroK]

Did we invent the numbers? Give them properties? The nomenclature is ours (Arabic, Roman, Babylonian etc) but did we invent the actual numbers?
Give them properties? Even numbers, primes?
EDIT: I know this is straying away from the OP a little.

It's a good question. We didn't define numbers so that explicitly there are infinitely many primes, for example. That property is a logical consequence of the definition and axioms but not a direct intention.

Likewise some of the references above to consequences of the axioms being counter-intuitive.

 

[SSequence]

It's a good question. We didn't define numbers so that explicitly there are infinitely many primes, for example. That property is a logical consequence of the definition and axioms but not a direct intention.

Yeah, I don't think that infinitely many primes or other simple results would have any issue. Even several complicated results would have no issue either in my opinion. I don't feel that there should be any contention about several of the basic results (and even several not so basic results). The problem of evaluating truth becomes (much) harder as we go on to more difficult statements (about natural numbers) which we might have shown using more "maximalist" principles so to speak. At least that is what I think (some may agree while others may not).

================================

Here is my personal view on this (in just few sentences). A large number of results related to natural numbers could be proved in fairly weak theories (even weaker than PA or HA ---"heyting arithmetic"). Here I mean several results that one would find in actual books. Now it is my personal view that, on the very least, HA only proves "true" statements about natural numbers [unless I am severely mistaken about some important aspects specific to HA itself]. There are certain (philosophical) reasons why I think so, even if I don't know the details of the theory myself. At any rate, this view then automatically includes theories weaker than HA too. It seems to me that perhaps some of these weaker theories (such as PRA) may be even more immediately self-evident (in their truth), but without knowing the details it is still a guess on my part.

Note that previous paragraph doesn't necessarily preclude (before-hand) stronger theories also proving only true statements about natural numbers.

Of course there are several more views to this than just the one I described. I have only described my personal view here (I felt that describing various other views on this would make the post just way too long .... almost five or six times in length at least).

 

[TeethWhitener]

To elaborate a bit, a statement being "unproveable" means that it can't be shown true in the given theory [in other words, the statement is not theorem of the given theory]

I’m not sure this is helpful. It lumps nontrivial unprovable statements in with simple falsehoods (assuming soundness and consistency).

Secondly, when we say that godel sentence is true (assuming consistency of theory under consideration), then we are usually implicitly assuming the "standard" natural numbers. But it seems that you didn't want to get into this point in some more detail to avoid confusion.

Yes, the thread was marked B level (high school level). I don’t know if there’s a high school in the world that dives into non-standard models of the Peano axioms. And it quickly gets extremely confusing discussing Godel’s incompleteness theorems in the context of his completeness theorem.

 

[SSequence]

I’m not sure this is helpful. It lumps nontrivial unprovable statements in with simple falsehoods (assuming soundness and consistency).

I will try to quote from two different sources:
https://en.wikipedia.org/wiki/Independence_(mathematical_logic)
Quote:
"A sentence $\sigma$ is independent of a given first-order-theory $T$ if $T$ neither proves nor refutes $\sigma$; that is, it is impossible to prove $\sigma$ from $T$, and it is also impossible to prove from $T$ that $\sigma$ is false."https://www.quora.com/What-is-the-d...lity-undecidability-and-independence-from-ZFC
The first sentence of the second paragraph of the answer seems to agree with what I wrote. Also the comment about $1 \neq 1$ may be relevant.

=============================

I think I understand what you are saying. However, it seems to me that discerning between a simple (or not so simple) falsehood is not obvious.The point I think is that generally speaking, with assumption of consistency of our given theory, any statement can be put into exactly one of the following three categories:
(1) The statement can shown to be true in the given theory.
(2) The statement can shown to be false in the given theory.
(3) The statement can neither shown to be true nor false in the given theory.

When we show that the given statement is unprovable in our given theory, then we have eliminated possibility-(1). When we show that the negation of the given statement is unprovable in our given theory, then we have eliminated possibility-(2). To show independence we have to eliminate both possibility-(1) and (2).

=============================

As an example, let's look at CH [given all the usual assumptions about consistency etc.]. What godel showed was negation of CH wasn't provable in ZFC [basically by exhibiting a (class) model in which CH was true]. Cohen showed that CH wasn't provable in ZFC. Together these results showed independence of CH from ZFC.

Here is a quote from wikipedia for the sake of completeness:
https://en.wikipedia.org/wiki/Continuum_hypothesis
"Gödel showed that CH cannot be disproved from ZF, even if the axiom of choice (AC) is adopted (making ZFC)."
....
"Cohen showed that CH cannot be proven from the ZFC axioms, completing the overall independence proof."

 

[TeethWhitener]

Consider the statement, "If unicorns exist, they will have horns". In this case, the axiom is unicorns existing and isn't true, however, the statement that follows it is kind of true. Because if unicorns did exist, they would have horns.

This is incorrect. Axioms are true by default. So if your axiom is “unicorns exist,” it’s true. In fact, in this post you seem to be asserting that “if unicorns exist, they will have horns” is the axiom. That’s fine; it simply means that it can’t be true that both “unicorns exist” and “unicorns don’t have horns.” If you take as an axiom “unicorns exist” it says nothing about whether “unicorns have horns” is true or not. If “unicorns have horns” is true, then the conditional “if unicorns exist, they will have horns” is also true. If not, then the conditional is false.

 

[TeethWhitener]

I will try to quote from two different sources:
https://en.wikipedia.org/wiki/Independence_(mathematical_logic)
Quote:
"A sentence $\sigma$ is independent of a given first-order-theory $T$ if $T$ neither proves nor refutes $\sigma$; that is, it is impossible to prove $\sigma$ from $T$, and it is also impossible to prove from $T$ that $\sigma$ is false."https://www.quora.com/What-is-the-d...lity-undecidability-and-independence-from-ZFC
The first sentence of the second paragraph of the answer seems to agree with what I wrote. Also the comment about $1 \neq 1$ may be relevant.

=============================

I think I understand what you are saying. However, it seems to me that discerning between a simple (or not so simple) falsehood is not obvious.The point I think is that generally speaking, with assumption of consistency of our given theory, any statement can be put into exactly one of the following three categories:
(1) The statement can shown to be true in the given theory.
(2) The statement can shown to be false in the given theory.
(3) The statement can neither shown to be true nor false in the given theory.

When we show that the given statement is unprovable in our given theory, then we have eliminated possibility-(1). When we show that the negation of the given statement is unprovable in our given theory, then we have eliminated possibility-(2). To show independence we have to eliminate both possibility-(1) and (2).

=============================

As an example, let's look at CH [given all the usual assumptions about consistency etc.]. What godel showed was negation of CH wasn't provable in ZFC [basically by exhibiting a (class) model in which CH was true]. Cohen showed that CH wasn't provable in ZFC. Together these results showed independence of CH from ZFC.

Here is a quote from wikipedia for the sake of completeness:
https://en.wikipedia.org/wiki/Continuum_hypothesis
"Gödel showed that CH cannot be disproved from ZF, even if the axiom of choice (AC) is adopted (making ZFC)."
....
"Cohen showed that CH cannot be proven from the ZFC axioms, completing the overall independence proof."

I understand your nitpick; I’m not convinced it’s helpful when OP is making basic logic mistakes (e.g., post 47).

 

[Stephen Tashi]

Did we invent the numbers? Give them properties? The nomenclature is ours (Arabic, Roman, Babylonian etc) but did we invent the actual numbers?
Give them properties? Even numbers, primes?

The only way to interpret that question becomes a familiar debate about whether numbers (and other mathematical concepts) were discovered or invented. You are suggesting that human beings developed language to describe something that already existed.

My take on that:

If we interpret "exist" to mean something that exists in a purely physical sense (like my coffee cup) then I can verify the existence of examples where (the current) concept of numbers models many of the physical properties well. Finding such examples requires not only finding examples of the noun number, but it also requires giving a physical interpretation to what we mean by "=", "+" etc.

I don't regard numbers as having an existence that physically causes 3+2 = 5. There are physical situations where this doesn't work (like computing the final volume after two volumes of different chemicals are added to the same flask). One can always object to such examples by saying that they are not what is meant by 3+2 = 5. This is a convenient type of a argument. It merely says that situations where a property of numbers works prove the physical existence of that property and situations where the property doesn't work are automatically disqualified from consideration.

 

[Stephen Tashi]

Are there mathematicians or logicians who don't take this view?

On a practical level, almost everyone (including most mathematicians) think of numbers as having objective elementary properties without worrying about which of these properties are axioms and which are theorems. Mathematics education proceeds this way. The elementary properties of numbers are drilled into children. Textbooks about calculus assume students remember the elementary properties of numbers. Only very specialized and advanced courses deal with systematizing the elementary properties of numbers - stating which are assumptions and which can be proven. Only a small percentage of the human population takes such courses.

 

[pinball1970]

The only way to interpret that question becomes a familiar debate about whether numbers (and other mathematical concepts) were discovered or invented. You are suggesting that human beings developed language to describe something that already existed.

My take on that:

If we interpret "exist" to mean something that exists in a purely physical sense (like my coffee cup) then I can verify the existence of examples where (the current) concept of numbers models many of the physical properties well. Finding such examples requires not only finding examples of the noun number, but it also requires giving a physical interpretation to what we mean by "=", "+" etc.

I don't regard numbers as having an existence that physically causes 3+2 = 5. There are physical situations where this doesn't work (like computing the final volume after two volumes of different chemicals are added to the same flask). One can always object to such examples by saying that they are not what is meant by 3+2 = 5. This is a convenient type of a argument. It merely says that situations where a property of numbers works prove the physical existence of that property and situations where the property doesn't work are automatically disqualified from consideration.

No I don't mean in the physical sense. I have to use a situation to explain it however. (This is an outsider/lay view so it will sound simplistic but I would like to ask this)
An alien species sends a probe to our solar system and finds planets orbiting a star.
There is a quantity of planets and properties of that quantity that exist.
You can add other quantities to reach the total, you can times a quantity by another quantity to reach the total. (They like pluto)

Take away the planets and those relationships still exist, no matter what you call them.
The chemical reaction I would object that you are changing the quantities as you are adding them, losing some volume as gas or precipitate.
It works if you just consider two generic volumes x/2 and add them you end up with volume x.
It works if you completely remove all physical reality and consider two abstract objects x/2 and add them you ALWAYS end up with x.
Does that relationship just exist?

 

[Stephen Tashi]

It works if you just consider two generic volumes x/2 and add them you end up with volume x.

That doesn't necessarily work if you "add" two subcritical volumes of U-235 in a particular way. It may not work if you add two volumes of water that are at different temperatures.

It works if you completely remove all physical reality and consider two abstract objects x/2 and add them you ALWAYS end up with x.

I don't know what it means to add abstract objects. Perhaps you are thinking about computing the cardinality of the union of two sets. Depending on how we interpret "add", it may or may not work with physical objects. It seems to me that you are defining abstract objects to be things x that have the property that x/2 + x/2 = x. So the relationship exists just by your definition

I agree that many physical situations exist where the abstract concept of addition can be interpreted and applied to make a sucessfull prediction. So the abstract concept of numbers and addition exists in sense that there exist physical examples where it can be applied.

It is human beings who recognized the similarities in these situations and created the abstract concept of numbers and addition. This improves the efficiency of thought - employ one abstract pattern that can be applied in many situations instead of treating each situation separately.

 

[nuuskur]

There are statements. Classically, every statement is either true or false (but not both). The end.
You can call them statements, propositions, theorems, doesn't matter.

Other than that - either axiom or theorem is sufficiently accurate. Theorem meaning that it requires proof. An axiom is just regarded as a true statement.

 

[pinball1970]

That doesn't necessarily work if you "add" two subcritical volumes of U-235 in a particular way. It may not work if you add two volumes of water that are at different temperatures.I don't know what it means to add abstract objects. Perhaps you are thinking about computing the cardinality of the union of two sets. Depending on how we interpret "add", it may or may not work with physical objects. It seems to me that you are defining abstract objects to be things x that have the property that x/2 + x/2 = x. So the relationship exists just by your definition

I agree that many physical situations exist where the abstract concept of addition can be interpreted and applied to make a sucessfull prediction. So the abstract concept of numbers and addition exists in sense that there exist physical examples where it can be applied.

It is human beings who recognized the similarities in these situations and created the abstract concept of numbers and addition. This improves the efficiency of thought - employ one abstract pattern that can be applied in many situations instead of treating each situation separately.

I had a look around and from what I have read, numbers are a human construct. Mathematics too.
I do not understand that.
This is straying from the OP so I may risk a thread instead.
Frustrating because I do not know enough about the structure and theory to get to the crux of what I mean.
I may have to mail a mentor first to make sure my post makes sense and does not break the rules!

 

[PeroK]

I had a look around and from what I have read, numbers are a human construct. Mathematics too.
I do not understand that.
This is straying from the OP so I may risk a thread instead.
Frustrating because I do not know enough about the structure and theory to get to the crux of what I mean.
I may have to mail a mentor first to make sure my post makes sense and does not break the rules!

Bring me a number! The whole numbers are an idea. They don't exist independently in nature.

You could use a pile of marked stones to count. That is, in fact, the origin of the term calculus. The leap is to invent an abstract set of things, called numbers, that are free of any single physical representation.

That was a significant breakthrough in the history of mathematics.

 

[pinball1970]

Bring me a number! The whole numbers are an idea. They don't exist independently in nature.

You could use a pile of marked stones to count. That is, in fact, the origin of the term calculus. The leap is to invent an abstract set of things, called numbers, that are free of any single physical representation.

That was a significant breakthrough in the history of mathematics.

I am saying the opposite, the structure exists without us. Regardless of the need for numbers to describe anything, that is just a bonus.
A being in Andromeda will arrive at the same results.

I am happy to be wrong but I think I need more meat to the bones before I take you on.
Let me check out number theory and set theory, possibly the philosophy of maths.
I could be a while...

 

[PeroK]

I am saying the opposite, the structure exists without us.

That probably depends on your definition of "exists". The number five? The set of $n \times n$ invertible matrices? The quaternions? The more advanced the mathematics, the less convinced I am of its independent existence, whatever that means.

 

[pinball1970]

That probably depends on your definition of "exists". The number five? The set of $n \times n$ invertible matrices? The quaternions? The more advanced the mathematics, the less convinced I am of its independent existence, whatever that means.

Fair enough,I know the platform I am claiming from. It is shaky ground.
Let me get back.

 

[pbuk]

I am saying the opposite, the structure exists without us.

That is a matter of philosophy, not maths.

It seems that as long as you stay away from self-reference, you should be fine.

That gets quite tricky: induction is a key principal in mathematics and is a close cousin of self-reference.

I think it would be a good idea to clear up some of the abstract talking in this thread by actually looking at some axioms. Let's look at the Peano Axioms (I'm going to base this on the construction used by MathWorld).

1. Zero is a number.
2. If $a$ is a number, the successor of $a$ is a number.
3. Zero is not the successor of any number.
4. Two numbers of which the successors are equal are themselves equal.
5. If a set $S$ of numbers contains zero and also the successor of every number in $S$, then every number is in $S$.

These axioms construct, completely artifically, the set of natural numbers, and when most mathematicians in the past 100 years talk about natural numbers this (or something similar) is what they are talking about. Using these (and a few more) we can construct propositions such as $2 + 3 = 5$ and $2 + 4 = 5$ and we can attempt to prove them. We find that we can prove that $2 + 3 = 5$ is always true and so we say it is a theorem of Peano Arithmetic, whereas we can prove that $2 + 4 = 5$ is always false and so we say it is not a theorem of Peano Arithmetic.

Now we can start again with a different set of axioms (I dedicate these to @Feynstein100 so let's call them the Pbuk-Dedicated axioms ):

1. Unicorns are animals
2. Unicorns have exactly one horn

... from which we can prove theorems such as "if $u$ is a unicorn then $u$ has exactly one horn".

We can also construct the proposition $P$ "if $a$ is an animal and $a$ has exactly one horn then $a$ is a unicorn" and its negation $P' = \neg P$ "if $a$ is an animal and $a$ has exactly one horn then $a$ is not a unicorn" but we find that we cannot prove either $P$ or $\neg{P}$ using the Pbuk-Dedicated axioms and so we say that $P$ is undecidable in Pbuk-Dedicated arithmetic.

So you see the concepts of axioms, propositions, theorems and decidability exist completely independently of any underlying "truth" behind the axioms.

 

[Feynstein100]

So we got a little distracted. In summary: turns out, yes, everything in math is either an axiom or a theorem. There is a third possibility with undecidable statements but that's too complicated. For most purposes, the duality of axiom/theorem holds. I'm glad we sorted that out.
Correction: Every statement in math is either an axiom or theorem. Math also consists of things that aren't statements, namely mathematical objects. I guess the interaction between these objects could be considered statements but that's not really relevant here.