Wikipedia:Reference desk/Archives/Mathematics/2019 January 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 29

Truth vs provability

I am not a professional mathematician, but a former physicist with a certain curiosity and a very dim understanding of some concepts of formality.

I am aware of statements being neither provable nor disprovable within certain axiomatic systems, and that whilst it is possible to introduce new axioms these necessarily either create an inconsistent system, or an incomplete one in which statements that can be made within the new system are neither provable nor disprovable. This much, to me, makes "sense".

What seems less clear is that I have heard that provability and truth are not the same. If a statement is neither provable nor disprovable, how is its truth value even defined? Are there mathematical statements that have been shown to be neither provable nor disprovable; however, their truth value is well-defined. If so, where is this "truth" contained?--Leon (talk) 20:51, 29 January 2019 (UTC)

Let's have a look at the most useful axiom system of arithmetic, being Peano system. So, it turns out that there are some arithmetical statements, e.g. Goodstein theorem, known to be true for the standard natural numbers, i.e. the "finite" natural numbers, even though those statements are neither provable nor disprovable in Peano system, because it fails to exclude non-standard models of natural numbers (i.e. including "infinite" natural numbers), for which those true arithmetical statements are false (that's why they are not provable in that axiom system), just as it fails to exclude the standard model of natural numbers (i.e. of the "finite" natural numbers only), for which those true arithmetical statements are true (that's why they are not disprovable in that axiom system). The same is true for any other (effective consistent) axiom system of arithmetic, because one can still find out other statements undecidable in that axiom system, because it will fail to exclude other models of natural numbers, for which those statements are false, just as it will fail to exclude other models of natural numbers, for which those arithmetical statements are true. Hope this helps. HOTmag (talk) 22:17, 29 January 2019 (UTC)

Star trooper man The thing to keep in mind is there's no such thing as "provable" or "disprovable" full stop. There is only provability or disprovability from specific axioms. So a particular set of axioms may not prove or disprove the proposition P you're interested in, but if you add some stronger axiom, then it may. The question is whether the stronger axiom is a good one to add, because if you take the (wrong) view that all axioms are equal, then you could always just add P (or ¬P) and have a trivial proof (or refutation).

So what does it mean for an axiom to be a good one to add? There is a variety of views on this. The "realist" or "Platonist" view is that, at least in many cases, our axioms are not uninterpreted strings, but are rather assertions about some well-specified objects (natural numbers in the case HOTmag talks about, but could be real numbers, or sets, or other things). In that case a "good" axiom is simply one that's actually true of the objects being discussed. How you might find that out, other than by proof, is a complicated topic, and again there are many diverse views. --Trovatore (talk) 22:27, 29 January 2019 (UTC)

Trovatore, are you suggesting that a particular mathematical object can, at least sometimes, be said to be only incompletely defined by any system of axioms? Regarding HOTmag's point, it seems to be the case that beyond a certain level of complexity (enough to specify the natural numbers) undecidable statements will always exist (I apologise if I misunderstood); in which case, where is this definition of e.g. the natural numbers? What constitutes this specification? Or, is it a mistake to presume that it exists, but rather our choice of axioms to augment the system is informed by our requirements--Leon (talk) 22:40, 29 January 2019 (UTC)

Well, there are several subtleties here. First of all, when I speak of axioms, I usually mean axioms in first-order logic. The discussion changes completely if we consider second-order logic with full semantics, but let's leave that aside for the moment.

Given that understanding, axioms don't define objects. Axioms talk about objects. The objects are supposed to be understood separately from the axioms.

There is another digression here; there are certain mathematical concepts that can be said to be defined by their axioms (say, the notion of group or vector space). But that's different. A group is a model of the group axioms, and the group axioms don't talk about the behavior of groups, but rather about the behavior of elements of a group. --Trovatore (talk) 22:50, 29 January 2019 (UTC)

I'll have to read something about first- and second-order logic to understand much more. However, I'm a little confused: if the axioms do not define the natural numbers, is there a "formal" definition of them? Sure, I know what the natural numbers are, but is there a definition of them in some highly formal language?--Leon (talk) 13:27, 30 January 2019 (UTC)

Unfortunately, there isn't (and can't be) such a formal definition, full stop. It turns out, that even the axiom of infinity, can't be complete, in the sense of having every arithmetical statement decidable by that axiom. If you wish to express the idea of a (finite) "natural number", being sure the non-standard natural numbers are excluded, you must express yourself informally, e.g. by saying "0,1,2, and so on". Every human being is supposed to (intuitively) understand what you mean by that implicit description of the (finite) natural numbers. HOTmag (talk) 16:17, 30 January 2019 (UTC)

Following Trovatore, let me elaborate a little bit. So, the problem is that there is no (effective) system of axioms that can define the natural numbers. We can only determine what cannot be a natural number, because all agree that natural numbers must satisfy Peano axiom system. The problem is: any (effective consistent) axiom system of the natural numbers is a necessary condition only - yet not a sufficient one, because it fails to exclude non-standard models of natural numbers (e.g. models containing "infinite" natural numbers), just as it fails to exclude the standard model of natural numbers. Anyways (back to your original first question), when stating that a given arithmetical statement is true, we usually mean that it's true for the standard natural numbers. HOTmag (talk) 23:09, 29 January 2019 (UTC)

Well, it's not just effective sets of axioms that can't define the naturals. No set of first-order axioms can define the naturals; there are nonstandard models of true arithmetic. You can get one, for example, by taking the ultrapower of the naturals by a nonprincipal ultrafilter on the naturals.

But I think the discussion betrays an excessively optimistic idea of what formalization can accomplish. Formalization is not going to tell you what the natural numbers are. You already know what the natural numbers are, as well as you're ever going to. They're 0, 1, 2, and so on. You can elaborate that as much as you want to, but any elaboration is going to involve more complicated mental operations than that. --Trovatore (talk) 04:43, 30 January 2019 (UTC)

Well, we can define S (in a second order language), to be "the class of all first order arithmetical statements true for the finite natural numbers (0,1,2 and so on)".

That axiom system, is really non-effective (since there is no algorithm that can determine for every first order arithmetical statement whether it belongs to that axiom system), yet that (non-effective) system of first order arithmetical axioms is, not only consistent, but also complete, so that every first order arithmetical statement is decidable in that (non-effective) consistent system of first order arithmetical axioms. That's why I wrote "effective" rather than "first order". HOTmag (talk) 07:49, 30 January 2019 (UTC)

Your S is true arithmetic, which I linked. You're right that it's complete. What it doesn't do is define the natural numbers, because it has models that are not isomorphic to the natural numbers. --Trovatore (talk) 16:22, 30 January 2019 (UTC)

Yeah, S allows to have various non-isomorphic models of the natural numbers (e.g. models constructed by the ultrapower of the natural numbers), just as the definition of electron allows to have various electrons - different from each other. However, that definition of electron does define "the" electron, because all electrons under that definition have the same "relevant" features (weight and electric charge and so forth), while other features (e.g. location and velocity and so forth) - that make all electrons different from each other - are "irrelevant". The same is true for S: Really, it allows to have non-isomorphic models - different from each other - of natural numbers, but S does define "the" standard model of natural numbers, because all models under S have the same "relevant" features (i.e. every first order arithmetical statement true in one model of S is true also in any other model of S), while other features of those models (e.g. their form and cardinality and so forth) - that make all those models different from each other - are irrelevant. To sum up (if that was not clear enough up to now), by my saying (in my previous post) "define the natural numbers", I meant "have a definition by which every first order arithmetical statement is decidable the same way". HOTmag (talk) 17:18, 30 January 2019 (UTC)

Ah, but that completely misses the point. There are lots of different structures that have the same first-order theory, and they are very different among themselves. Per structuralism, you "define" the natural numbers by specifying them up to isomorphism, not up to elementary equivalence. --Trovatore (talk) 17:52, 30 January 2019 (UTC)

You claim I miss the point. However, it seems like you've forgotten what the point was. So, I've been trying to explain, why I wrote "effective". I explained all of that, by presenting the class S, being a (non-effective) system of first order arithmetical axioms, that is, not only consistent, but also complete, so that every first order arithmetical statement is decidable in that (non-effective) consistent system of first order arithmetical axioms. That's why I wrote "effective" rather than "first order", because this had been the point, in my view. HOTmag (talk) 18:35, 30 January 2019 (UTC)

I thought we were talking about what it meant to define the natural numbers. The subthread started with your assertion that "that there is no (effective) system of axioms that can define the natural numbers", and my pointing out that the "effective" bit is not really relevant. --Trovatore (talk) 18:39, 30 January 2019 (UTC)

As I have already pointed out: by my saying "define the natural numbers", I meant "have a definition by which every first order arithmetical statement is decidable the same way". That's why the "effective" bit is relevant, because there are [consistent] non-effective systems (e.g. S), that can define the natural numbers, in the sense mentioned - above - as well as in the post wherein I have discussed the definition of electron. HOTmag (talk) 19:18, 30 January 2019 (UTC)

Well, maybe that's what you meant by "define the natural numbers". But it isn't what it means. --Trovatore (talk) 21:55, 30 January 2019 (UTC)

Well, since I don't ascribe much importance to controversies over semantics, I don't think it really matters whether - what I meant by the phrase "define the natural numbers" - was what you thought this phrase should really mean. The main thing is, that both of us agree, that for making sure - that the axiom system the OP is asking about does not exist - it must have all of the following three features: 1. All first order arithmetical statements are decidable in it, hence it has - what I've called - the ability to "define the natural numbers" with respect to first order arithmetical statements. 2. It's consistent. 3. It's effective (as opposed to the class S of axioms as it had been defined by me in a non-effective way). That's why I mentioned the adjective "effective". HOTmag (talk) 23:03, 30 January 2019 (UTC)

We can also stick a bit more to physics and consider whether or not for a file larger than 1 Gb on your hard disk there exists a self-extracting file of size smaller than 1 Mb that will generate it. It's obvious that it's either true or false whether or not such a self-extracting file exists or not. Also, we can be almost sure that it doesn't exist, simply by counting the number of files smaller than 1 Mb and observing that this is much smaller than the number of files within some range of file sizes the large files belongs to. Suppose then that the most likely scenario is true, no such self-extracting file exist for the particular large file. Then we can ask whether a mathematical proof exists for that fact. If such a proof were to exist, then we could in principle find that proof by writing a program that runs through all theorems and uses Hilbert's proof checker's algorithm and will stop at the first instance a theorem is encountered that says that such and such a file larger than 1 Gb cannot be compressed to under 1 Mb. This is then a paradox, because a file that supposedly cannot be compressed is then de-facto generated by this very short program. So, even though almost no files larger than 1 Gb can be compressed to under 1 Mb, in no case can this be proven.

Then since we're talking about real physical devices here (computers that are subject to the laws of physics), this is then a real physical manifestation of incompleteness theorem, it doesn't depend on any choice of axioms other than implied by the relevant laws of physics. Count Iblis (talk) 20:20, 30 January 2019 (UTC)

Doesn't depend on choice of axioms? Then what exactly do you mean by a "mathematical proof" for the fact that no self-extracting file exists for the given file?

Note also that, while (or indeed because) computers are real physical devices, the physical answer to whether a particular large file self-extracts from a smaller file may be non-deterministic and may vary between physical computers meant to be equivalent. That's because computers make "errors", of course. But specifying what you mean by an "error" takes you out of the physical realm again, into the Platonic, or at least if not, you have more explaining to do. --Trovatore (talk) 21:53, 30 January 2019 (UTC)

I think the 'physical' needs to be in quote marks. And we should also have some unbounded amount of disk space and the program might run longer than it takes till the heat death or great rip or whatever ends the universe. With bounded disk space or time the number of possible states is finite (though large!) so we can solve the problem (though not in the lifetime of the universe!). Dmcq (talk) 00:01, 31 January 2019 (UTC)

Leon, If a statement is neither provable nor disprovable, how is its truth value even defined? Let's take a non-mathematical statement as an example: "Abraham Lincoln had pancakes for breakfast on the morning of the battle of Shiloh". Assuming history doesn't record what Lincoln had for breakfast that day, the statement is neither provable nor disprovable. But most of us would say it has a truth value, because either he had pancakes or he didn't. So the concept of being unknowable doesn't seem to be in bad conflict with having a truth value. It has one--we just don't know what it is.

Are there mathematical statements that have been shown to be neither provable nor disprovable; however, their truth value is well-defined. If so, where is this "truth" contained? This is a little trickier but the idea (we will act like it is valid even though it can be disputed philosophically) is there is a definite structure we call "the natural numbers" that goes: 1,2,3... And a statement might be something like "there are infinitely many pairs of twin primes". This has a truth value in the sense that if you had Godlike powers to examine all the prime numbers, you could check whether the statement was true.

Now you can think of a proof as a bunch of symbols and formulas on a page, that follow certain grammatical-like syntactic rules, so you can mechanically check whether the proof is valid. And you can encode the symbols and formulas as a big number N. So "X is provable" means "there exists a number N, with the property that N encodes a proof of X". But if it's not provable, all it means is that there isn't such an N. That's separate from whether X has a truth value. It's like the situation with Lincoln's breakfast.

There's a famous theorem in logic (Gödel's incompleteness theorem) that once a mathematical theory gets powerful enough, it will always have unprovable statements. The proof is technical and I won't go into it but I hope you can see how the concept of an unprovable statement with a truth value at least makes sense. 173.228.123.166 (talk) 08:54, 2 February 2019 (UTC)

Thanks, but I take issue with the Lincoln example as (a) I disagree that the truth value is well-defined, and (b) a mathematical structure is, at the very least, defined rather differently, in that it is constructed, and not contained externally to the mind.--Leon (talk) 19:05, 4 February 2019 (UTC)

Well, you are certainly in good company if you think that mathematical structures don't exist independently of our reasoning about them, but you would also be in good company if you thought the opposite. This is the heart of the controversy between mathematical realism ("Platonism") and formalism.

Possibly more to the point, it is standard in mathematics to talk like a Platonist even if you aren't, especially when talking about things like the incompleteness theorems. It just saves a lot of time. The formalist can maintain mental reservations throughout the discussion and add what she thinks is the real meaning at the end. This way you don't have to keep interrupting yourself to say (for example), when I say I can or can't prove the Goedel sentence, does that mean that a proof exists independent of my reasoning about it? --Trovatore (talk) 19:25, 4 February 2019 (UTC)

Who was the first to discover the well known formula $cis(a+b)=cis(a)cis(b)$ ?

I wonder if this formula, easily provable by means of trigonometry alone, was discovered before Euler discovered the formula $e^{ix}=cis(x),$ which makes the previous formula trivial. HOTmag (talk) 21:43, 29 January 2019 (UTC)

De Moivre's formula was known before Euler's formula, so it is certainly possible that it was known explicitly earlier. (Of course the trigonometric identities that underlie this formula would have been comprehensible to the ancient Greeks.) --JBL (talk) 23:46, 29 January 2019 (UTC)

When I asked about $cis(a+b)=cis(a)cis(b)$, I was quite aware of De Moivre's formula. Unfortunately, it says something about the n-th root of cis, rather than about the n-th power of cis, nor does it say anything about multiplying cis(a) by cis(b). Further, one cannot deduce what cis(a+b) equals, given what cis(na) equals. Anyways, I'm still looking for the first source that explicitely states: $cis(a+b)=cis(a)cis(b).$ HOTmag (talk) 00:04, 30 January 2019 (UTC)

Geez they can't shut this place down soon enough. --JBL (talk) 15:14, 30 January 2019 (UTC)

The encyclopedia credits Hamilton with the cis notation, but I could not find that Euler's formula was known prior to Euler. Good question, though, and I will let you know if I find something new in the library.Tamanoeconomico (talk) 03:05, 30 January 2019 (UTC)

As for the notation cis - I'm not asking about it, and as far as I'm concerned - you are allowed to replace it by cos + isin - if you want to. Anyway, I don't think Euler's formula was known prior to Euler, and that's why I'm not asking about it. I'm asking whether the weaker formula, $cis(a+b)=cis(a)cis(b),$ was known prior to Euler. HOTmag (talk) 07:57, 30 January 2019 (UTC)