ZT5's Shortform

post by Victor Novikov (ZT5) · 2022-12-09T22:29:02.933Z · LW · GW · 7 comments

Contents

7 comments

7 comments

Comments sorted by top scores.

comment by Victor Novikov (ZT5) · 2022-12-09T22:28:09.497Z · LW(p) · GW(p)

The Parable of Gödel-Löb.

Three people discovered that no formal system can prove its own validity [LW · GW].

The first person decided to trust his own reasoning unconditionally. This allowed him to declare anything he wished as true, as he had already chosen to see all of his conclusions as correct. He declared he could fly, and jumped off a cliff. Reality disagreed.

The second person decided to mistrust his own reasoning unconditionally. He could not formally prove that he needed to eat and drink to survive, so he laid down on the ground and did nothing until he died of starvation.

The third person did something clever, yet obvious, and decided to trust his reasoning in a safe and bounded manner, and also mistrust his reasoning in a safe and bounded manner. He went on to explore reality, and was proven wrong about many of his conclusions (as choosing to trust his reasoning did not automatically make it correct). But ultimately he believed he made the correct choice, as taking the first step to greater understanding required him to have some degree of trust in himself.

comment by Victor Novikov (ZT5) · 2023-03-10T09:54:37.148Z · LW(p) · GW(p)

It's weird how in common language use saying something is provable is a stronger statement than merely saying it is true.
While in mathematical logic it is a weaker statement.
Because truth already implies provability.
But provability doesn't imply truth.

Replies from: Vivek
comment by Vivek Hebbar (Vivek) · 2023-03-10T09:58:45.344Z · LW(p) · GW(p)

??? For math this is exactly backward, there can be true-but-unprovable statements

Replies from: ZT5
comment by Victor Novikov (ZT5) · 2023-03-10T10:01:18.405Z · LW(p) · GW(p)

Then how do you know they are true?

If you do know then they are true, it is because you have proven it, no?

But I think what you are saying is correct, and I'm curious to zoom in on this disagreement.

Replies from: Vivek
comment by Vivek Hebbar (Vivek) · 2023-03-10T10:08:19.026Z · LW(p) · GW(p)

See Godel's incompleteness theorems.  For example, consider the statement "For all A, (ZFC proves A) implies A", encoded into a form judgeable by ZFC itself.  If you believe ZFC to be sound, then you believe that this statement is true, but due to Godel stuff you must also believe that ZFC cannot prove it.  The reasons for believing ZFC to be sound are reasons from "outside the system" like "it looks logically sound based on common sense", "it's never failed in practice", and "no-one's found a valid issue".  Godel's theorems let us convert this unprovable belief in the system's soundness into true-but-unprovable mathematical statements.

More mundanely, there are tons of "there doesn't exist" statements in number theory which are very likely to be true based on unrigorous probabilistic arguments, but are apparently very hard to prove.  So there are plenty of things which are "very likely true" but unproven.  (I get this example from Paul Christiano, who brings it up in relation to ARC's "heuristic arguments" work.  I think Terence Tao also has a post about this?)

Replies from: ZT5
comment by Victor Novikov (ZT5) · 2023-03-10T10:43:24.941Z · LW(p) · GW(p)

I think we understand each other! Thank you for clarifying.

The way I translate this: some logical statements are true (to you) but not provable (to you), because you are not living in a world of mathematical logic, you are living in a messy, probabilistic world.

It is nevertheless true, by the rule of necessitation in provability logic, that if a logical statement is true within the system, then it is also provable within the system. P -> □P. Because the fact that the system is making the statement P is the proof. Within a logical system, there is an underlying assumption that the system only makes true statements. (ok, this is potentially misleading and not strictly correct)

This is fascinating! So my takeaway is something like: our reasoning about logical statements and systems is not necessarily "logical" itself, but is often probabilistic and messy. Which is how it has to be, given... our bounded computational power, perhaps? This very much seems to be a logical uncertainty [? · GW] thing.

comment by Victor Novikov (ZT5) · 2022-12-07T11:03:15.834Z · LW(p) · GW(p)

My intuition felt it was important that I understand Löb's theorem. Because that's how formal logic systems decide to trust themselves, despite not being able to fully prove themselves to be valid (due to Gödel's incompleteness theorem). Which applies to my own mind as well.
This has always been true. But now I know. Updated on this.