Logic - 2017-09-05

Wildcard

08:10

@user21820 I like that, and I think I agree. :) I hadn't considered "real numbers" as a type as it relates to programs.

user21820

@Wildcard: Hello!

Wildcard

@user21820 I don't think I said that...I definitely wouldn't say that.

@user21820 Hello!

user21820

Aug 30 at 7:44, by Wildcard

In my own philosophy of mathematics (and again, I'm not trying to "convert" anyone), (a) there is no such thing as a non-computable number.

Aug 30 at 7:45, by Wildcard

Therefore, all numbers are computable (or else they're not numbers), and thus the inclusion or omission of the word "computable" from the word "number" can't change the meaning of a statement, only make it more or less clearly communicative. :)

Wildcard

Right. For numbers that's true. :)

user21820

Ah.

I see.

Wildcard

08:12

I believe in the existence of an awful lot of things that aren't computable. I just don't believe it makes the slightest bit of sense to refer to any of those things as "numbers." :D

@user21820 This is an interesting question, though. I'm not sure I can answer it fully....

My first impulse, though, is to say "no," I don't believe that.

user21820

Okay so suppose you temporarily accept the definedness of the halting problem, then you're objecting to calling the halting oracle a number?

If not, I don't quite know what you may be thinking of that you believe is not computable.

In my mind the general answer to the halting problem is uncomputable, but it relies on first accepting that there is always a yes/no answer.

I don't mind the viewpoint that we shouldn't be referring to these things as numbers, too.

I'd call them concepts instead.

Wildcard

@user21820 Agreed.

I want to answer at greater length...wasn't planning to do it in real time. :D I'll pop in tomorrow and answer your many comments more fully.

user21820

Sure sure.

I also think that there are basically only two defendable philosophilal positions on the halting problem. Either one accepts that natural numbers are a fixed absolute notion, and satisfy PA, in which case the halting problem is more or less decided for every given program and input. Or one rejects PA, in which case we can't even do mathematics.

Wildcard

@user21820 The quick answer to this, though, is that there are many things outside of mathematics. :D And lots of things in mathematics that may be represented by numbers, but have existence without reference to numbers (such as geometry and graph theory).

user21820

@Wildcard Ok this at least answers my query about some things you believe are uncomputable. Sure. Life is not computable, I think.

Wildcard

08:19

@user21820 Hmmm. That's interesting. I believe there are meaningful questions about numbers that can't be decided or proven at all—or disproven. (Or at least, that this is a very distinct possibility.)

@user21820 Right. I get annoyed whenever I see someone implicitly assume (in philosophical discussion) that the human mind is some sort of Turing Machine.

It's begging the question.

user21820

@Wildcard This is a separate issue from truth value. The incompleteness theorems already show what you're stating here.

What I was asking was whether you believe the halting problem has an answer, even if it cannot be obtained by us.

Wildcard

@user21820 Right. I also will say I think conditionally defined numbers are silly, and aren't really numbers. E.g. "define a to equal 1 if the collatz conjecture is true, and 0 otherwise." A is not a number.

@user21820 Yes. But it's not always meaningful to assume so. As in the "definition" of $a$ in the above comment. :)

A lot of modern math, in my opinion, is (bad) philosophy hiding under symbology.

user21820

@Wildcard This follows trivially from your non-acceptance of oracles as denoting numbers. But I don't get your last comment; either the oracle is a meaningful concept, or it is not.

This is separate from the question of whether we can obtain/use the oracle.

Wildcard

@user21820 Define "meaningful."

:D

user21820

Meaning...

Wildcard

08:23

@user21820 Ah, but is it, though?

user21820

Jokes aside, that's why I phrased my original question as simply whether you believe the answer always exists for any program and input that I give to you explicitly.

Wildcard

If you go back to my original commentary (I believe in this chat room) about the purpose of mathematics, you will find a somewhat harshly utilitarian view.

@user21820 I think that is a deeply philosophical question, and not at all something that should be taken for granted.

@user21820 I shall instead say, it always makes the most sense to proceed as if the answer DOES exist for any program or input.

But that may or may not be actually true.

user21820

Namely, before I give the program and input to you, do you already believe that the answer is either "halts" or "doesn't halt". If you don't completely believe it, I would like to know why.

(I'd emphasize that here we're already assuming the concept of ideal programs makes sense, which wouldn't in a finite world but let's not talk about that...)

Wildcard

@user21820 Right, but see, I think those two questions are inextricably linked.

Or rather—

user21820

Then I guess your answer is that we can't assume the world is not finite.

Wildcard

08:27

@user21820 Not quite.

user21820

Why not? I said "can't assume the world is not finite" not "assume the world is finite".

Wildcard

It's just that I don't think the choice of "halts" or "doesn't halt" must be an absolute excluded middle to do mathematics.

You can assume absolutely anything. :D

user21820

By "assume" I mean "assume as true based on your beliefs".

Either you do assume that the world is finite, in which case you could say that halting oracles are nonsense.

Or you don't assume so.

Wildcard

Is there another way for something to be true? (See, this is where most mathematicians dive off from philosophy.)

:)

user21820

Um by "true" I mean in reality.

Wildcard

08:29

@user21820 Or you assume so only sometimes.

:)

I swear I'm not trying to bait you. I know it might seem like I am....

user21820

That's why I said "based on your beliefs".

Wildcard

Ah, but how do you define "reality"?

user21820

I don't buy a utilitarian approach that just assumes things when convenient for argument.

That's why I keep wanting to pin your opinion down.

Wildcard

lOL

LOL

user21820

Otherwise I can't figure out what you really believe.

Reality is the world which you perceive.

Wildcard

08:30

See, the funny thing is that none of this impedes my ability to do mathematics.

user21820

I know that.

That's why it's a philosophical question.

So what's your current answer?

> Either you do assume that the world is finite, in which case you could say that halting oracles are nonsense. Or you don't assume so.

Wildcard

One moment, writing a long comment....

user21820

Ok ok. =)

Wildcard

I think you could postulate a universe where there is no successor function. Where there is no such thing as "quantity" and where the "natural" numbers looked far more esoteric and mind-bendingly theoretical than the most advanced gobbledy gook to come out of discussions of "hierarchies of infinite cardinalities."

I think there is absolutely no limit to what can be dreamed up.

I think (and here's a wild one) I think that mathematics does not have to be consistent to be useful and that consistent > correctness is an arbitrary that limits the utility and diversity of mathematical thought.

user21820

Yes but see I'm asking about what you believe about the world you perceive around you. Not about what we can dream up, which of course includes worlds that don't exist.

(I got to go and do something for about 15 min anyway, so I'll reply later.)

Wildcard

08:33

@user21820 Aha.

@user21820 Sounds good. :)

@user21820 I need to sleep in any case. It's been a very interesting Labor Day weekend....

Catch you tomorrow!

user21820

09:08

@faux: Hello and welcome! Feel free to inquire anything about logic here.

user21820

09:44

→ 56 messages moved to trash

@Wildcard Okay good night!

Wildcard

@user21820 Night. :)

user21820

@faux: Did you have a question about (mathematical) logic? =)

Wildcard

@user21820 So maybe I should get this question narrowed down more precisely. I thought we were talking about ideal TMs and halting oracles, which obviously don't have to do with the world we perceive around us.

@user21820 And I'm not really utilitarian, either.

Actually, to discuss mathematical pedagogy for a second, I think that math as taught in high school (and probably the first year of college) is nothing more than doing the basic drills so you can play the game.

It's like learning to dribble a basketball, and shoot free throws, and passes, and running drills, and NOTHING else, and calling it basketball. But never actually playing the game.

user21820

@Wildcard In some sense yes, in some sense no. PA was invented to describe counting numbers, which were physically represented. One could argue that PA does indeed describe some physical representations, such as finite binary strings in electronic storage media. Or one could argue that PA fails to do so at large scales.

If you take the former, then the halting problem always has an answer because the physical representations representing programs executed on inputs will either halt or not halt.

If you take the latter, as I do, then one could refine the conjecture to say that PA merely approximately describes the real world binary strings.

Wildcard

@user21820 Interesting; I think that's the first time in this chat I've gotten a clear insight into your views.

user21820

09:51

And then the halting problem may become meaningless at large space/time scales.

Wildcard

@user21820 I agree with this. Especially the word "may."

And now I really do need to sleep; I just wanted to get our conversation to a good point first. :)

user21820

@Wildcard Well I don't like putting up my views first, to avoid colouring people's views. So that I can see what they think first. =D =D

Wildcard

@user21820 Ditto. But I don't think I quite succeeded. :D

user21820

@Wildcard Sure sure have a good rest!

Wildcard

G'Night!

@user21820 In retrospect I think much of this discussion was "fencing" to avoid giving away too much first. =D

user21820

09:54

@Wildcard I think we are far more similar than we think.

I hope I didn't just make a contradictory statement. =D

user131753

14:22

Did you receive a ping @user21820? If you aren't busy then can we discuss something in Martin Sleziak's Room?

user21820

@user170039: Sure. I did receive it but just now was busy.

user131753

No problem. I guessed so. (By the way, if you think that the last three comments (including this one) are not relevant for this room, feel free to move them to Trash room)

user21820

14:59

It's not a problem; it's related.

user21820

15:39

@user170039: I've read about 20% of the pdf so far. I wish to start mentioning key points so that I don't forget them later. The first point is that Wittgenstein is being very imprecise in what he is said to have written (page 10). I will fault him for at least that, even if one argues that he actually had complete grasp of the incompleteness theorems. Specifically, he implies that Godel's "true" means "proved in Russell's system".

It is easily understood that Godel was working in a meta-system that already assumes the existence of a model of PA. I always emphasize that the meta-system must have such an entity, otherwise (arithmetically) "true" and "false" have no meaning at all. And that notion of arithmetic truth is definitely not coincident with "proved in Russell's system".

Anyone can, if they wish, question whether there is a model of PA in the first place. If there isn't, then all mathematics is built on uncertain foundations, because of the various reasons I've explained before: Accepting any formal system as meaningful already requires commitment to the closure of finite strings under concatenation, whose lengths are a model of PA.

But once one accepts the existence of a model of PA, then there is nothing wrong with the MS already assuming existence of such an entity, and Godel's proof goes through.

user21820

16:48

The second point is that my above comments also addresses Shankar's claim (page 24). He is correct that to treat meta-mathematical statements as purely absolute is an error; it is merely stated within MS, and it's entirely possible that MS is wrong (if you're platonist) or meaningless.

However, he's wrong to say "Gödel was barred by virtue of the logical grammar of mathematical proposition from claiming that he had constructed identical versions of the same mathematical proposition in two different systems." Godel didn't do such a thing, as would be clear to anyone who has basic grasp of logic and model theory.

user21820

17:01

And Floyd's opinion on page 38 (whether an accurate interpretation of Wittgenstein or not) is invalid. It is true that not every English sentence that looks like a factual statement can be assumed to have a truth value. I explicitly explain that issue in one of my posts:

3

A: Is Godel's modified liar an illogical statement?

Your question has two main facets. The first is that you did not grasp the way logic does not fall to the liar paradoxes. The second is that there are deeper reasons as to why we have such apparently innocuous sentences in natural language that seem to defy assimilation into formal logic systems....

But it is invalid to go from that claim to the general claim that all mathematical statements are of the same nature.

If one denies existence of a model of PA (in a physical form), then fine you can say the incompleteness theorems aren't valid (no platonic meaning), but then you need to give a convincing explanation for why RSA decryption works so well. You can find more detail of such issues in the following:

9

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...

Anyway, as of now my opinion on Wittgenstein hasn't really changed; he (like many others) fail to realize the significance of the incompleteness theorems. I'll grant that it may be difficult to see it through Godel's initial work. To appreciate it, one has to fully grasp the computability aspects and the constructive nature of some of the proofs.

I'll try to state the significance very briefly: Formal systems were invented as a way of precisely delineating rules of reasoning by which we would like to ensure sound reasoning via syntactically verifiable deductive steps. But the very notion behind formal systems, namely string manipulation, requires prior philosophical commitment to meaningfulness of finite strings, and requires commitment to the theory of concatenation TC (see details in the paper linked from my post), more or less.

But no formal system that (computably) interprets TC is complete and consistent, as a result of the generalized incompleteness theorems (Godel merely proved them for a single formal system, so it may not have been obvious to casual readers how to generalize them).

To be able to state and prove this fact of incompleteness, the meta-system MS needs very weak assumptions. Definitely ACA is enough, and ACA is essentially what you get if you assume that there is a classical model of TC, plus induction.

So there are only two main defensible positions:
(1) Accept TC as classically meaningful, and hence accept the incompleteness theorems, which apply to anything that computably interprets TC, which include all humanly conceivable formal systems.
(2) Reject TC as classically meaningful, and hence reject the very assumptions underlying all humanly conceivable formal systems themselves! Unless of course you believe that all 'correct' formal systems have some cutoff string length.

Incidentally, as mentioned in my post there are self-verifying theories, which give an intriguing possibility lending support to the last part of (2). Strange, but possible.

By the way, I dislike popular accounts of the incompleteness theorems that do not make clear the dependence on the model of PA in the meta-system. Every explanation in my opinion must define clearly what is meant by (arithmetic) truth. Otherwise it's indeed misleading, and many philosophers have (again in my opinion) done injustice to logic by misusing the incompleteness theorems.

@user170039 Feel free to respond to any point. Though I'd encourage you to first understand the proof of the incompleteness theorems (at least syntactically) before attempting to judge its semantic content or possible lack of it. =)

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic