Logic - 2017-07-01

user21820

05:36

@user170039 If you read what I wrote earlier, you can see that what you have quoted from Rota ("Whereas the facts of mathematics, once discovered, will never change") is simply false.

There is no way one can specify what are "facts of mathematics" without using some syntactic system to capture some semantic concept. To give a concrete example, the system PA captures the semantic notion of natural numbers, and we usually have a collection in MS that satisfies PA. But that means you accept an axiom in MS that asserts the existence of such a collection N. Only after that can you talk about arithmetic truths/facts, by defining them to be sentences that N satisfies.

Without such an approach, there is simply no meaning to the phrase "facts of mathematics".

You cannot say that natural numbers exist in the real world and go from there, because scientifically the current consensus is in fact that the observable universe is finite, and so there cannot be a real-world interpretation of PA.

This I've already explained in my linked post. If you have not read it yet, here it is again:

8

A: What are the arguments for and against "one true arithmetic"?

In short: The so-called definition of natural numbers as those that can be obtained from 0 by adding 1 repeatedly is circular, but there is no viable alternative, which already makes it impossible to uniquely pin down natural numbers mathematically. Worse still, there does not seem to be ontologi...

user21820

06:02

@user170039: In case it isn't clear, I'm saying two things: (1) Rota can't be right on that quote because "facts of mathematics" cannot be made meaningful and precise without some formal system; (2) Current scientific knowledge tells us that there is no real-world interpretation of PA, so even the notion of arithmetical 'facts' (not to say non-arithmetical 'facts' of mathematics) that all mathematicians (except finitists) accept do not have basis in the real world! Its only basis is PA itself.

By the way I never said that we have to use an axiomatic method, whatever you may mean by that. I instead said that we have to use some syntactic system, which is equivalent to a proof verifier program; it is irrelevant whether the system can be interpreted to have deductive rules and axioms or not. Feel free to clarify any point. =)

Nevertheless, it is relevant to note that any proof verifier program and hence any syntactic system can be captured by a single 1-parameter arithmetical formula in PA (this is a non-trivial result that can be proven using Godel's beta function), and so PA is strong enough to know whether or not a purported proof in a given system is correct. Since PA is itself a first-order theory, one could argue that the axiomatic method is sufficient, at least on the meta level.

To be precise, take any syntactic system S with proof verifier program V, namely that for every strings p,x we have that V accepts (p,x) if p is a correct proof of x over S and rejects otherwise. Then there is a 1-parameter arithmetical formula φ such that for any strings p,x we have ( PA |− φ(c(p,x)) iff V accepts (p,x) ) and ( PA |− ¬φ(c(p,x)) iff V rejects (p,x) ), where c(p,x) is the Godel code of (p,x). Thus PA can 'implement' any syntactic system even if it is not axiomatic.

The distinction between the system level and meta level is an important one. For a concrete example, while some mathematicians reject the meaningfulness of some set theories like ZFC and hence may reject the meaningfulness of some theorem P over ZFC, none of them (even including most finitists) would reject the fact that ZFC proves P, because it is a syntactical fact rather than a semantic one.

user131753

06:51

First of all let me declare that I haven't gone through the post you linked in your last comment (I will when I have more time). So if the answer to my questions has been already discussed there, just leave a comment below my latest comment along the lines of "See my post again". Now let me mention out some points that I would like to be more clear about.

user131753

1. "There is no way one can specify what are "facts of mathematics" without using some syntactic system to capture some semantic concept." - indeed this seems the most plausible. But one may ask, "How do you know that indeed there is "no way one can specify what are "facts of mathematics" without using some syntactic system to capture some semantic concept?"

user131753

2. In the same vein, one may ask, "How do you know that without such an approach, there is simply no meaning to the phrase "facts of mathematics""?

user131753

You may think that I am simply trolling (as this is the general response I got when I tried to discuss this question with four of my professors, each one of them also said something similar to what you said) and if you do please let me know that, I will explain my reasons. But I am not going to do so now because that is not relevant at this point.

user131753

And also I don't understand what you mean, "By the way I never said that we have to use an axiomatic method, whatever you may mean by that. I instead said that we have to use some syntactic system, which is equivalent to a proof verifier program; it is irrelevant whether the system can be interpreted to have deductive rules and axioms or not." But isn't a syntactic system just an implementation of the axiomatic method @user21820?

user21820

@user170039 It's indeed valid to ask that question. I do claim that it is so, because unless we can perform mind-to-mind transfer of thoughts, ultimately we have to come down to syntactic communication, originally natural language and later more formal languages.

Of course, I would be proven wrong by just one example of precise communication of reasoning without using any syntactic language. But I just don't believe it's possible.

user131753

07:05

Exactly. I also don't believe that it is possible. But I think that this is what Rota was trying to say.

user21820

@user170039 It is easier for me to answer this question. The burden is on the one who claims that there is meaning, to specify what meaning it has.

@user170039 As for what Rota is trying to say, the quote you've cited is simply false and mathematicians didn't know that earlier. It could be believable in the time of Hilbert especially when he still hoped for a self-justifying system. But it's no longer valid now.

user131753

I see. However, I need to go for sometime now. See you soon.

user21820

Anyway I don't know whether Rota (like other mathematicians) changed his mind after Godel's result.

Sure.

See you next time!

By the way I didn't think you were trolling.

@user170039 A syntactic system is precisely as I have defined above: chat.stackexchange.com/transcript/message/38498356#38498356

David Varela

@user21820 nice link you posted

I think questioning the natural numbers is a good way to jump head first into a rabbit hole

user21820

@DavidVarela Hahaha yes. Personally I got down to the natural numbers only after looking closely at the circularity in mathematics and realized that syntax is at the bottom of it all.

@user170039: We can use any arbitrary total program as a proof verifier for a system, such as by interpreting an empty output as rejection and non-empty output as acceptance. Most total programs then correspond to meaningless systems, but some correspond to non-axiomatic methods. For example I can imagine making a Fitch-style system to allow inline reasoning about programs. Arguably it won't be completely axiomatic since it needs to support the desired program semantics including references.

David Varela

07:22

I think syntax serves the same role as axioms, no? (if I understand what you mean by syntax) You have to agree on some sort of baseline and build up from there

user21820

So by using total programs to represent syntactic systems I'm attempting to capture all conceivable systems, axiomatic or not. We can actually reason that these are all there is, because any practical system must allow both parties to verify in finite time the correctness of any claim (assertion) with evidence (proof). That requires a terminating syntactic algorithm (total program), because we are bound by syntactic language. All non-syntactic languages are imprecise.

David Varela

@user21820 Also, I'm curious about your starred comment; can you recommend a good intro logic book?

user21820

@DavidVarela Yes in a way; syntactic systems is the natural generalization of traditional axiomatic systems. The latter came long before algorithms were defined and grasped.

Even Godel essentially built a compiler in arithmetical formulae without realizing the computability aspect at first.

@DavidVarela You may be interested in some links from my profile page, one of which is:

5

A: What are the prerequisites for studying mathematical logic?

I think for starting material you can't beat Introduction to Logic by Patrick Suppes, and old book but one that clearly explains the intuitions behind logic. After that you can read Stephen Simpson's Mathematical Logic lecture notes available here, which uses modern notation and also has some bas...

Those who already have mathematical background should skip Suppes' book and go straight to Simpson's notes.

Not sure which comment you're referring to though; the top one is by shredalert, not me. =)

David Varela

"If people read ... ideas about proper logic ..." <- that comment

user21820

Ah that one was for people who don't even use logical reasoning and hence make all sorts of fallacies, so much so that Wikipedia even has a whole list of them. =)

@DavidVarela @user170039: As for a baseline, indeed you two may be interested in thinking about the philosophical commitments necessary for each step up from the syntactic baseline:

8

A: Are sets and symbols the building blocks of mathematics?

The things you actually write on the paper or some other medium are not definable as any kind of mathematical objects. Mathematical structures can at most be used to model (or approximate) the real world structures. For example we might say that we can have strings of symbols of arbitrary length,...

David Varela

07:29

@user21820 cool, thanks for the link, its very complete. I studied some logic on my own and I took a 'theory of computation' in school, but I have far from complete knowledge of it I think

user131753

You said that "syntactic systems is the natural generalization of traditional axiomatic systems" whereas one of our professor told us that "syntactic systems are examples of precise formulations of traditional axiomatic systems". Aren't they contradictory @user21820?

user21820

@DavidVarela I also have far from complete knowledge of logic; I am only comfortable up to the incompleteness theorems and the computability aspect of it. Beyond that there's a whole lot I don't know, and you'll have to ask people like Noah Schweber and Carl Mummert. =)

user131753

Because as is generally understood in mathematics 'examples' are special cases of more general propositions. Isn't it?

user21820

@user170039 Your professors meant a different thing. Traditional axiomatic systems were done and described in natural language. Today they can be precisely specified via programs (capturing them as syntactic systems). So what they meant was that we can use syntactic systems as examples of precise formulations of traditional axiomatic systems (other formulations usually not so precise).

It wouldn't be correct to claim that all syntactic systems are formulations of traditional axiomatic systems, and I don't think they meant to claim that.

user131753

I see. Thanks for clarifying @user21820.

David Varela

07:39

@user21820 holy crap that second link is a great outline, I'll take a closer look later. What is intimidating to me is that even if you have a firm grasp on the formal aspect of logic, you still have to deal with the cognitive/psychological aspect in order to get the big picture of reasoning

user131753

By the way, have you read the paper The Pernicious Influence of Mathematics upon Philosophy @user21820?

user21820

@user170039 Before programs were known precisely, all logicians described their systems using natural language, which is very ambiguous. It's interesting to see how imprecise their descriptions were in comparison to a concrete proof verifier program today. It's an incredible advancement we have had in precision, thanks to people like Turing and von Neumann.

@user170039 No I haven't. Where can I read a free copy?

user131753

In this book (see Chapter 12), which turns out after searching google by the phrase "THE PERNICIOUS INFLUENCE OF MATHEMATICS UPON PHILOSOPHY pdf" (written exactly as I did).

user21820

@user170039: Interesting I didn't see that when I did the google search.

shredalert

libgen.io and b-ok.org are pretty standard

use a proxy if they're blocked

user131753

07:51

@shredalert: But I am not sure if they are legal.

user21820

On reading the first page, it is clear that Rota was mistaken in the sense I thought, which is that he didn't realize the philosophical problem with basic arithmetic.

At least in that writing.

user21820

08:05

For example he says "It is a fact that the altitudes of a triangle meet at a point." but the only way to define these ideal geometric points and lines, not to say altitudes and triangles, is via a formal system. There is no physical line in the real-world; even the path of a single photon is not straight because of massive bodies. It's only straight in ideal flat space-time, which is a mathematical notion.

One could be careful and claim that for triangles (say made by lasers) up to a certain size on earth, the altitudes (as verified by some optical measurements) can be observed to coincide within some error margin. This is no longer a mathematical fact but an empirical fact that is approximated by the Euclidean geometric fact.

So there still remains the clear distinction between mathematical facts (which only exist with respect to some formal system) and real-world facts (which exist independent of formal systems).

shredalert

@user170039 Of course they're not. lol

user400188

08:26

o/ @shredalert @user21820

shredalert

o/ @user400188

user400188

Reading through the past comment I see the logic room was enjoying some interesting philosophical discussion.

shredalert

Good stuff

user21820

@user400188: Yea. Feel free to join in. Though I may not reply so quickly. =)

shredalert

I'm heading out camping in a few hours. Will be back tomorrow.

user400188

08:35

Where are you camping @shredalert ?

user21820

@shredalert: Take care on your camping trip! See you next time! =)

shredalert

@user21820 thanks :)

@user400188 A forest not too far from my city.

shredalert

09:04

Heading off now

Take care all. Will be back tomorrow

user400188

Bye @shredalert . Enjoy your camping :)

user400188

09:20

I am wondering how good my definition of logically follows is at the moment. I have been reading from Suppes (I started it thinking I would need the introduction and am now so far in I feel as though I may as well finish it) and the definition given to me is as follows:

Criterion 1: Given a set of premises, we should infer only those that logically follow
Criterion 2: We must permit all conclusions that logically follow

Next we define a thing called sentential interpretation:
$B$ is a sentential interpretation (SI) of $A$, *if and only if* $B$ may be obtained from $A$ by replacing component atoms of $A$ by other (not necessarily distinct) sentences.

We then develop a way of inferring logical consequences as:
(1) $B$ logically follows from $A$ if all sentential interpretations (SI) of $A\rightarrow B$ are true.
(2) Tautologies are sentences whose atomic SI are all true.
(3) If every atomic SI of a sentence is true, then every SI of a sentence is true.
From (1)-(3) we arrive at (4)
(4) B logically follows from A if B is tautologically implied by A.

That's the definition, however I wonder how useful it really is, when statements like $(A ∧ B) ⇒ C ∴ (A ⇒ C) ∨ (B ⇒ C)$ are so easily proven using it, while Fitch style proofs take extensive time to do the same thing.

user21820

11:20

@user400188: I'm not sure what you mean by "atomic SI" and "true". Truth cannot be defined apart from a model. Your (1) works for propositional logic but not other logics, not even first-order logic unless I'm reading you wrong. The general definition is that A |= B (A logically implies B) iff every model of A satisfies B. The definition of a model depends on the logic, but would in general be an interpretation of all valid strings in the language for which the deduction rules are sound.

@user400188 As for this propositional tautology, you'd have to show me what you consider a proof of it before I can evaluate it. Note that proofs that pass through the meta-system (MS) are not proofs in the system itself. It is possible that you can prove some fact in MS but not in the system S. Often MS can also prove the existence of a proof in S of some theorem P, and this existential proof can be drastically shorter than the shortest proof of P in S.

Furthermore, I believe that a properly designed Fitch-style system won't be much more inefficient than MS (except for specially contrived theorems). Here is a proof of your example:

If A and B implies C:
	A or not A.
	If A:
		If B:
			A and B.
			C.
		B implies C.
		( A implies C ) or ( B implies C ).
	If not A:
		If A:
			Contradiction.
			C.
		A implies C.
		( A implies C ) or ( B implies C ).
	( A implies C ) or ( B implies C ).

As you can see, all you need to shorten the Fitch-style proofs is to include enough useful rules, such as LEM.

user131753

14:50

Maybe Rota was taking a Platonic point of view when he was talking about "mathematical facts" @user21820.

user21820

15:25

@user170039: Exactly. The problem is that platonism is untenable ever since the incompleteness theorems and our current scientific knowledge of special relativity.

In the past, it could be easily imagined that natural numbers have some concrete interpretations in the real world, and hence arithmetic truths are all there to be discovered, not invented. But special relativity took that concreteness away, and Godel took the possibility of self-justification (which would have been a reasonable way of selecting one platonic view over another) away.

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic