Too fast. Why? — Banno

Ok. I Googled "natural deduction as basis for math" and the following popped up right at the top:

What can you assume in natural deduction?
In natural deduction, to prove an implication of the form P ⇒ Q, we assume P, then reason under that assumption to try to derive Q. If we are successful, then we can conclude that P ⇒ Q. In a proof, we are always allowed to introduce a new assumption P, then reason under that assumption.

Now this is just what I call perfectly normal mathematical deduction. That's how mathematicians do proofs. To prove P implies Q we assume P and derive Q. If that's natural deduction, I've been using it all my life! Like the literary character who discovered he'd always been speaking prose.

So if that's all ND is, then it appears to be perfectly standard everyday mathematical reasoning.

I still don't understand the technical distinction being made by the Wiki article on ND, but based on this example, ND is just how everyone does math.

But I can see how we might have different pictures of mathematics, which are despite that functionally equivalent: one of maths as a series of axiomatic systems, the other as a language that becomes increasingly complex as new formation rules are added. — Banno

I don't think this is what's being said by ND. As the Google example shows, ND is basically normal everyday mathematical reasoning. To show P implies Q we assume P and derive Q.

Need to take a break so we don't post over each other. Yes, ND is just deduction. But in ND, any theorem can be taken as axiomatic, to be discharged as the deduction proceeds. As I say, they are functionally equivalent. See https://thephilosophyforum.com/discussion/comment/575534

Need to take a break so we don't post over each other. Yes, ND is just deduction. But in ND, any theorem can be taken as axiomatic, to be discharged as the deduction proceeds. As I say, they are functionally equivalent. — Banno

Ok I waited a bit. I did not understand ND from its Wiki page. But I did completely understand it from the Google description: To prove P implies Q, I assume P and derive Q. This is basic, everyday mathematical practice.

I should point something out. Mathematicians don't use formal logic. They use this kind of casual, everyday reasoning. In formal logic, the things people talk about are foreign to working mathematicians. By the standards of formal logic, no working mathematician has ever seen a proof, if you look at it that way.

So whatever ND is, if it's just "To prove P implies Q assume P and derive Q," then that's what I've been doing all my life and that's what everyone else does. Any distinction between that and some other kind of formal logic is "inside baseball" for logicians and apparently of little interest to mathematicians.

Bottom line, I don't see how ND can add anything to mathematical practice, nor relieve us of the need to start somewhere by writing down our axioms. If you add axioms one at a time making sure they are complete and consistent, you will never get to the arithmetic of the natural numbers, which is known to be incomplete.

Don't know if this was helpful to you, but it sure was to me. "Today I learned" that natural deduction is just the normal type of reasoning done by mathematicians. So in the end, thanks for mentioning it!

Mathematicians don't use formal logic. — fishfry

That was the point of the explorations into the foundations of maths that led to incompleteness and so on - to give maths the rigidity of logic, conceived of as axiomatic. But what happened is that in including counting in logic, the axiomatic enterprise fell apart; maths is much larger than any given set of axioms.

SO the lesson might be that when the love of axioms tried to tighten up mathematics, it ended up toppling the axioms.

I don't see how ND can add anything to mathematical practice, nor relieve us of the need to start somewhere by writing down our axioms. — fishfry

I suspect that in mathematics any true formula can serve as an axiom from which to develop more cool mathematics. That's quite a different thing to an axiom in logic.

SO the lesson might be that when the love of axioms tried to tighten up mathematics, it ended up toppling the axioms. — Banno

Indeed. It was Hilbert who said, "Wir müssen wissen – wir werden wissen ("We must know — we will know."). And as I recall. it was either a few days before or after that, that Gödel announced his incompleteness theorems. The search for mathematical certainty ended in the proof of uncertainty. Be careful what you wish for, or something like that.

I suspect that in mathematics any true formula can serve as an axiom form which to develop more cool mathematics. That's quite a different thing to an axiom in logic. — Banno

We don't know what the true formulas are. But it's true that math and logic are very different.

Can you tell me, from your knowledge of ND, is my Google-ish description that "To prove P implies Q we assume P and derive Q," is a fair summary of what it's about? I've seen natural deduction mentioned many times but never knew what it is.

Pretty much. ND consists in formation rules and a couple of rules of derivation - modus ponens in particular.

No axioms. That's pivotal. Instead there is a rule of assumption: one can introduce any proposition on chooses at any time, and rules for deriving more theorems from those assumptions

The derive bit is perhaps misleading, since if you assume A and also assume, but not derive, B, then it follows that A⊃B.

It was Hilbert who said, "Wir müssen wissen – wir werden wissen ("We must know — we will know."). And as I recall. it was either a few days before or after that, that Gödel announced his incompleteness theorems. — fishfry

'You can't know'.

No axioms. That's pivotal. Instead there is a rule of assumption: one can introduce any proposition on chooses at any time, and rules for deriving more theorems from those assumptions — Banno

Yes but there are no axioms in any deduction system. First you have the rules of deduction, then you add in some rules of set theory, say, and you crank out your theorems. It's like saying gasoline doesn't have a steering wheel. Gasoline is the stuff you put in your car, and the gas makes the car go. In order to apply the deduction system to something you have to write down some axioms. The axioms aren't part of the deduction system. So it's not a pivotal aspect of ND that there are no axioms. To do math, you write down some axioms and then use the rules of deduction to derive theorems. If you have no axioms you have rules of deduction but you can't prove anything.

Unless you mean that we can introduce our axioms in an ad hoc manner, for example, saying "if we assume the axiom of unions and we have sets X and Y then we can conclude that there a set X union Y. Is that what you mean by not having axioms?

Quick question: why can't we throw out self reference with regard to Gödel like they did with Russell's paradox?

Quick question: why can't we throw out self reference with regard to Gödel like they did with Russell's paradox? — Gregory

I found an answer on math.SE which you may or may not find satisfactory. See the checked answer by Asaf Karagila. I'm repeating it verbatim here:

Self-reference has a problem, if you want to think about it in terms of "I am not provable" sort of approach. A well-formed formula cannot refer to itself. Moreover, a formula cannot refer to the meta-theory (which is where proofs exist).

What Gödel did was two things:

1. Internalize the meta-theory into the natural numbers via coding, and show that this internalization is very robust.

2. Showed that there is a sentence with Gödel number n, whose content is exactly "the sentence coded by n is not provable".

The importance is in both points. They allow us both (limited) access to the meta-theory and the proofs; as well circumvent the problem of being a well-formed formula while still referring to itself. And while the importance of the incompleteness theorem is mainly in the fact that it shows there is no reasonable way to have a finitary proof-verification process to mathematics, and also prove or disprove every sentence; the proof itself is also important because it gives us the internalization of the meta-theory into the natural numbers.

https://math.stackexchange.com/questions/1962462/g%C3%B6dels-incompleteness-theorem-question-about-self-reference

FWIW we don't "throw out self reference" to fix Russell's paradox. Rather, we outlaw unrestricted comprehension and require restricted comprehension.

That is, if $P$ is a predicate, we outlaw set specifications of the form $\{x : P(x)\}$, which says we can form a set out of all the things that satisfy the predicate.

Instead we require that the predicate is used to cut down an existing set. So we have some set $X$ that already exists, we say that we can form a new set $\{x \in X: P(x)\}$. That makes all the difference.

For example if we form the set of everything that's not a member of itself, as in $R = \{x : x \notin x\}$, we get Russell's paradox.

But if we start with, say, the natural numbers, we may legally form the set $S = \{x \in \mathbb N: x \notin x\}$, we do NOT get any contradiction.

Let's walk through it Is 0 an element of itself? No, so 0 is in $S$. Is 1 an element of itself? No, so 1 is in $S$. Continuing like this, we see that $S$ is just the set of natural numbers. The paradox goes away.

Unless you mean that we can introduce our axioms in an ad hoc manner, for example, saying "if we assume the axiom of unions and we have sets X and Y then we can conclude that there a set X union Y. Is that what you mean by not having axioms? — fishfry

I so mean.


But we call them assumptions.

It needs to be borne in mind that mathematics is ultimately a system, game-like in nature, where we have complete freedom to choose our starting premises aka axioms.
— TheMadFool

This is exactly the view that Gödel opposed. He believed that mathematics is objective; that mathematical truth is something that we study, not something we make up. If the axioms don't settle a given mathematical question, that's the fault of the axioms. There is truth "out there" waiting to be discovered. — fishfry

The question then is, is math discovered or invented?

One of the reasons why some, like Gödel I suppose, believe math is discovered is how math seems to,

1. Describe nature (math models e.g. Minkowski spacetime)

2. Describe nature accurately (we can make very precise predictions to, say, the 15th decimal place)

There's a book titled "The Unreasonable Effectiveness of Mathematics in the Natural Sciences." authored by Eugene Wigner. It's a book that captures this sentiment.

However, we can't/don't know beforehand which mathematical object will prove itself useful in the description of nature. Given this, we need to experiment with math which basically involves tinkering around with the axioms as arbitrarily or as whimsically as possible. The objective? Generate as many mathematical objects as possible so that we can find the one that's the best fit in re nature.

In summary, possibly true that math is a discovery (it's fundamental to nature, the universe) but to find the best possible mathematical object to capture nature's essence as it were, we need to treat math as an invention and play with the axioms. :chin:

I so mean.


But we call them assumptions. — Banno

Ok, I think we're all clear and in agreement then.

We can start with the inference rules of ND, and, one-by-one, introduce as assumptions the standard axioms of ZF set theory. Of course there are infinitely many axioms because Specification and Replacement are actually axiom schemas, meaning that they each represent one axiom for each of infinitely many predicates. But presumably we can do that. [Specification can be derived from Replacement so technically we only need Replacement].

So far so good. Now as soon as you add the axiom of Infinity, you will have a model of the Peano axioms, and you'll introduce incompleteness. So in the end this is all exactly the same as standard set theory.

I did look this up in the Wiki article on first-order logic, which is the logic used for set theory. It says, in the section, "Hilbert-style systems and natural deduction,"

A deduction in a Hilbert-style deductive system is a list of formulas, each of which is a logical axiom, a hypothesis that has been assumed for the derivation at hand, or follows from previous formulas via a rule of inference. The logical axioms consist of several axiom schemas of logically valid formulas; these encompass a significant amount of propositional logic. The rules of inference enable the manipulation of quantifiers. Typical Hilbert-style systems have a small number of rules of inference, along with several infinite schemas of logical axioms. It is common to have only modus ponens and universal generalization as rules of inference.

Natural deduction systems resemble Hilbert-style systems in that a deduction is a finite list of formulas. However, natural deduction systems have no logical axioms; they compensate by adding additional rules of inference that can be used to manipulate the logical connectives in formulas in the proof.

So as far as I can understand, you get the same set theory either way.

One of the reasons why some, like Gödel I suppose, believe math is discovered is how math seems to,

1. Describe nature (math models e.g. Minkowski spacetime)

2. Describe nature accurately (we can make very precise predictions to, say, the 15th decimal place) — TheMadFool

My sense is that these mundane physical considerations were not on Gödel's mind. He believed in the Platonic existence of abstract sets including large cardinals, sets far too large to be of any conceivable interest to the real world. See
2.4.4 Gödel’s view of the Axiom of Constructibility
.

I really can't say what Gödel thought about or believed, since apparently he initially thought the axiom of constructability (the claim that the constructible universe includes all sets) was true, then came to doubt it. But my sense is that he was thinking of the Platonic reality of a very large universe of sets, and was not thinking about the utility of set theory in physics. On the other hand he did do some work in relativity, so who knows.

was thinking of the Platonic reality of a very large universe of sets, and was not thinking about the utility of set theory in physics. On the other hand he did do some work in relativity, so who knows — fishfry

Harold Ravitch, in his own opinion about Gödel, after finishing the dissertation, wrote this:

The literature, in making Gödel a Platonist, a Kantian, a Cantorian, and so forth, seems to have overlooked this possibility. We choose to view Gödel as a unique philosopher and not try to classify him. — Harold Ravitch

I guess (just my simple opinion) that Gödel was transforming through the years as metamorphosis. I am agree with you that so clearly he was a platonist but it is true that he reflects other points of view in his writings. To be honest I don’t defend we should exclude Gödel from these areas and see him as and “unique”philosopher as Ravitch wrote. Probably there are different versions of him to be consider of: Platonism, realism, relativism, etc...

My sense is that these mundane physical considerations were not on Gödel's mind. He believed in the Platonic existence of abstract sets including large cardinals, sets far too large to be of any conceivable interest to the real world. See
2.4.4 Gödel’s view of the Axiom of Constructibility
.

I really can't say what Gödel thought about or believed, since apparently he initially thought the axiom of constructability (the claim that the constructible universe includes all sets) was true, then came to doubt it. But my sense is that he was thinking of the Platonic reality of a very large universe of sets, and was not thinking about the utility of set theory in physics. On the other hand he did do some work in relativity, so who knows. — fishfry

Way above my paygrade! Thanks though. I hope to advance my knowledge in math ASAP.

Update: he retired from teaching in 2019. Look: https://www.coursicle.com/lavc/professors/Harold+Ravitch/
So, for more than 50 years he was a teacher. Probably he has a lot of papers related to this — javi2541997

I can find only two papers, neither related to this topic. If he taught at a community college it might have been difficult to do research and publish.

The question then is, is math discovered or invented? — TheMadFool

Most math people are not concerned with this question. I believe as new math appears on the scene it may have elements of both.

I'll come out straight up and say that my own prejudice is that maths is made up as we go along, but I will admit that I do not have sufficient background to argue saliently for this position. I doubt anyone in this forum does — Banno

Some of it is. For example I recently defined an "attractor form" for a certain class of functions. It's trivial stuff, but may not have been around before. Once defined, then its characteristics are explored. It's hard to tell. My advisor fifty years ago went so far as to state, "There is nothing new in mathematics." Who knows?

I can find only two papers, neither related to this topic. If he taught at a community college it might have been difficult to do research and publish. — jgill

Yes you are right. There are not articles from Ravitch connected to this thread. There is only one article published here: Springer link.

I found related to this topic the following paper or "scheme":

Principles of Predicate Calculus

Way above my paygrade! Thanks though. I hope to advance my knowledge in math ASAP. — TheMadFool

Above mine too actually. My point was that Gödel apparently believed in an expansive view of the set-theoretic universe, and that his Platonism was probably motived by that and not by practical considerations such as its use in physics.

FWIW Gödel cooked up a model of set theory called the constructible universe, in which the axiom of choice and the continuum hypothesis are true. That shows that they're consistent with ZF.

So why not just adopt the axiom that the constructible universe is the true universe of sets? If you did that, AC and CH would be theorems and we'd be done. The reason this assumption is not made is that most set theorists believe that the true universe of sets (if there even is such a thing) has way more sets in it than just the constructible ones. Gödel apparently first believed that the constructible universe was the true universe, and later came to not believe that.

It's trivial stuff, but may not have been around before — jgill

Or it has been waiting around since the big bang for you to come along and discover it.

Probably there are different versions of him to be consider of: Platonism, realism, relativism, etc... — javi2541997

Agreed, his thoughts were probably a lot more complex than the articles about him can capture.

Above mine too actually. My point was that Gödel apparently believed in an expansive view of the set-theoretic universe, and that his Platonism was probably motived by that and not by practical considerations such as its use in physics.

FWIW Gödel cooked up a model of set theory called the constructible universe, in which the axiom of choice and the continuum hypothesis are true. That shows that they're consistent with ZF.

So why not just adopt the axiom that the constructible universe is the true universe of sets? If you did that, AC and CH would be theorems and we'd be done. The reason this assumption is not made is that most set theorists believe that the true universe of sets (if there even is such a thing) has way more sets in it than just the constructible ones. Gödel apparently first believed that the constructible universe was the true universe, and later came to not believe that. — fishfry

From what I could glean from Wikipedia, a constructible set is one which can be, well, constructed via set theoretic operations (intersection, complement, mainly union I suppose). What would it mean to say some sets aren't constructible? Every set can be disassembled/broken down into its subsets and like a chemical compound, reconstituted back to give the original set.

The empty set? Is it constructible? { } U { } = { } but then that's circular. Aah. {1, 4, a} intersection {p, w} = { } but then how is { } made up of {1, 4, a} and {p, w}?

It's too complicated for me. I give up!

L is defined by transfinite recursion. L_0 = 0. That is, the empty set is constructible by definition at the base clause.

Why the zero appears in your formula? Is it related to “transfinite” concept ∞?

I think I didn’t get your argument because I am guessing that transfinite recursion is an infinite constructible loop at the base clause. (?)

I am confused but this enigma is making me think a lot.

https://plato.stanford.edu/entries/set-theory/#GdeConUni

From what I could glean from Wikipedia, a constructible set is one which can be, well, constructed via set theoretic operations — TheMadFool

Wrong article. The Wiki page on "constructible sets" has something to do with topology. Different usage.

This is the relevant page.

https://en.wikipedia.org/wiki/Constructible_universe

The constructible sets are built out of first-order formulas in stages. I don't know enough about this to give a simplified explanation. Basically each stage is built from first-order statements with parameters and quantifiers that range only over the previous stage. It's very logic-y. Wish I could say more but I don't know too much about it. Only that Gödel cooked it up to prove the consistency of AC and CH.

https://plato.stanford.edu/entries/set-theory/#GdeConUni — TonesInDeepFreeze

Already read it. Thanks for the link, I understand it better now :up:

https://plato.stanford.edu/entries/set-theory/#GdeConUni — TonesInDeepFreeze

@TheMadFool This is also a good link if you're interested.

My sense is that these mundane physical considerations were not on Gödel's mind — fishfry

Contra that, in the item I cited, there are mentions of empiricism and the example of the applicability of the mathematics of elasticity to engineering a bridge; see (3) here.

so again:

It seems that for Gödel, being consistent and being true are inseparable; that mathematical truth is displayed in mathematic's empirical applicability; and that hence the consistency of mathematics shows that it is empirically applicable and hence incompatible with the syntactic view. — Banno

So if we trust this secondary source - I have no reason not to - Gödel held something like that we can speak of mathematical propositions being true because they are empirically applicable; that truth is at a meta-level to the mathematics itself; and that together these show that maths is not just stuff we make up.

The exact argument remains opaque, but that is the implication.

Some of it is. — jgill

Yep. Some folk feel a sort of existential angst - why should the mathematics of limits have a use in describing the movement of a cannon ball? Why should the stresses and strains on a bridge be amenable to calculation?

But if it wasn't Young's modulus, wouldn't we just use some other calculation? Don't we choose the mathematics to fit the situation? So why should we be surprised that the mats fits? As if one were surprised to find the end of a screwdriver is just the right shape to drive a screw.

Contra that, in the item I cited, there are mentions of empiricism and the example of the applicability of the mathematics of elasticity to engineering a bridge; see (3) here. — Banno

Yes but your (3) is under the heading that says: "Gödel apparently characterises the syntactic view as consisting of three requirements:"

So he is characterizing the syntactic view. But we've already agreed that he's describing the syntactic view in order to disagree with it.

I would be extremely surprised to find that Gödel advocated Platonism because of the use of math in building bridges or whatever. On the contrary, Gödel's Platonism argued for the existence of large cardinals and other highly abstract and decidedly un-physical entities of set theory.

Again, your (3) is under the heading of the view that Gödel is trying to refute, not advocate for. Am I missing something?

so again:
It seems that for — Banno

, being consistent and being true are inseparable; that mathematical truth is displayed in mathematic's empirical applicability; and that hence the consistency of mathematics shows that it is empirically applicable and hence incompatible with the syntactic view.
— Banno

So if we trust this secondary source - I have no reason not to - Gödel held something like that we can speak of mathematical propositions being true because they are empirically applicable; — Banno

Two things may be true here:

1) It's perfectly possible that Gödel said that, or believed that; or at the very least, that some third-party interpreted his beliefs that way; and

2) I totally do not believe Gödel himself justified his Platonism on day-to-day physical grounds. Gödel believed in large cardinals, and that's one reason he did not believe we should adopt the axiom of constructability.

In other words: You may be right but I still don't believe it. Both those can be true. I believe many false things.

that truth is at a meta-level to the mathematics itself; and that together these show that maths is not just stuff we make up. — Banno

I just can not believe that Gödel paid much attention to the construction of bridges as a justification of large cardinal axioms. Like I say: even if I'm wrong, I'm sticking to my sense of the matter.

The exact argument remains opaque, but that is the implication. — Banno

But wasn't the use of the word empiricism listed under Gödel's description of the syntactic view? The very view that he's describing in order to refute?

I am feeling uneasy expressing strong opinions on things I know nothing about. I don't know what Gödel thought. I do know that he (later in life, at least) came to reject V = L (the axiom that says that the constructible universe is the true universe of sets) because L doesn't have enough sets. And the sets that it's missing are large cardinals, transfinite quantities so large they can't be proven to exist in ZFC and that are as far from empirical concerns as can possibly be.

That's really all I know about it; and I sincerely agree that I could well be completely wrong.

That's a fair point. Ok, he might not have so thought.