Liar Paradox Revisited

post by Chris_Leong · 2019-04-17T23:02:45.875Z · score: 11 (3 votes) · LW · GW · 15 comments

Contents

  Patching with INFINITE-LOOP
  Patching with an oracle
  Patching with ORACLE-LOOP
  Final Note
15 comments

A well-known brainteaser asks about the truth of the statement "this statement is false". My previous article [LW · GW] on this topic, outlined common approaches to this problem and then argued that we should conceive of two distinct kinds of truth:

I should add that some statements can only be defined using a combined notion of truth, ie. "The car is red and 1+1=2".

My point was that if we chose to extent logical/mathematical statements outside of their usual bound, we shouldn't be surprised that it breaks down and that if we choose to patch it, there will be multiple possible ways of achieving this.

Patching with INFINITE-LOOP

So let's consider how we might attempt to patch it. Suppose we follow the Formalists (ht CousinIt) and insist that "true" or "false" or only applied to sentences that can be evaluated by running a finite computation process. Let's add a third possible "truth" value: INFINITE-LOOP.

Consider the following sentence:

The truth value of this sentence is not INFINITE-LOOP

This seems to be a contradiction because the sentence is infinitely recursive, but at the same time denies this.

In order to understand what is happening, we need to make our algorithm for assigning truth values more explicit:

if expansion terminates:
Resolve truth value normally
else:
Assign INFINITE-LOOPif expansion terminates:

What we see here is that if the sentence is not able to be expanded without ending up in an infinite loop, it is assigned the truth value INFINITE-LOOP without any regard to what the sentence asserts. So there isn't actually an inconsistency, at most, this system for assigning truth values just isn't behaving how we'd want.

In fact consider the following:

A: This sentence is false
B: Sentence A has a truth value of INFINITE-LOOP

According to the above algorithm, assigning INFINITE-LOOP to B is correct, when it seems like it should be TRUE. Further, this system assigns INFINITE-LOOP to:

1+1=2 or this sentence is false

when perhaps it'd be better to assign it a value of TRUE.

Patching with an oracle

Being able to talk about whether or not sentences end up in an infinite loop seems useful. So we can imagine that we have a proof oracle that can determine whether sentence will end up in a loop or not.

for reference in sentence:
if oracle returns INFINITE-LOOP:
Evaluate the clause given the value INFINITE-LOOP as the truth value of the reference
else:
Expand normally

However, our oracle still doesn't demystify:

The truth value of this sentence is not INFINITE-LOOP

As our algorithm would replace the first clause with INFINITE-LOOP and hence evaluate

INFINITE-LOOP is not INFINITE-LOOP

to FALSE. But then:

FALSE is not INFINITE-LOOP

so we would expect it to also be TRUE.

So perhaps we should define our oracle to only work with sentences that don't contain references to INFINITE-LOOPS. Consider the following situation:

A: This sentence is false
B: Sentence A has a truth-value of INFINITE-LOOP
C: Sentence B is true
D: Sentence C is true

B would be TRUE (even though it refers to INFINITE-LOOP, the oracle only has to work with the reference "Sentence A"). However, C would be undefined.

We could fix this by allowing the oracle to return TERMINATES for sentences that can be evaluated after one level of expansion with our initial definition of an oracle. We can then allow sentence D to be true by allowing the oracle to return TERMINATES for any sentence that can be evaluated after two levels of expansion and we can recursively extend this definition until infinity.

This also resolves cases like:

1+1=2 or this sentence is false

The second clause evaluates to INFINITE-LOOP and since this is a truth value, rather than actually infinitely looping, (TRUE OR INFINITE-LOOP) should give true.

Patching with ORACLE-LOOP

We still haven't figured out how to handle cases like:

The truth value of this sentence is not INFINITE-LOOP

I would suggest that we might want to repeat our first move and say that the truth value is ORACLE-LOOP whenever an oracle fails to resolve it (even if we expand it an infinite number of times, we still end up with a sentence containing INFINITE-LOOP). We can then stack meta-levels and further metalevels on top of this.

Final Note

I'll finish by noting that we could also define another notion of truth whether a statement is true when there is a single fixed point. This would result in statements like:

This sentence is true

Being set to true instead of INFINITE-LOOP.

In any case, the way that we extend the concept of truth to apply to these degenerate cases is purely up to what we find convenient. Obviously

15 comments

Comments sorted by top scores.

comment by Dagon · 2019-04-17T21:35:43.079Z · score: 4 (2 votes) · LW · GW

Consider patching by tabooing "truth". Declarative sentences don't actually have truth value, except in the sense where "truth" is a handwave toward conveying information which allows an update of the receiver's beliefs. The improvement of predictions enabled by this update is sometimes referred to as "truth".

Don't get me wrong - it's a very useful shorthand, and in many many cases you don't need to expand it. But in the adversarial case where statements are picked to break the normal use of "truth", the right response is to abandon the simple concept for those cases.

comment by shminux · 2019-04-17T15:55:14.861Z · score: 4 (2 votes) · LW · GW

I really like the idea that an evaluation algorithm of a proposition can either terminate or end up in a fixed point, mapping back to the evaluation algorithm itself. It unites mathematical and non-mathematical statements instead of separating them, and it allows for algorithm-dependent outcomes of propositions, which fits well into my anti-realist ontology. In this approach a lack of convergence would be an indication that a new, potentially higher-level evaluation algorithm (I call those "models") is required.

Going by what you have presented, some basic hierarchy could be something like this:

Evaluating algorithm-1: Immediately/obviously/postulated true or false, no extra evaluation needed

Evaluating algorithm-2: Evaluated to true or false with or the evaluating algorithm-2 (your "infinite loop")

Evaluating algorithm-3: Evaluated to one of the 2 above or to itself, if the "evaluation field" is not closed.

Etc.

comment by Chris_Leong · 2019-04-17T10:20:50.526Z · score: 4 (2 votes) · LW · GW

I can't figure out how to indent my code

comment by habryka (habryka4) · 2019-04-17T19:18:19.012Z · score: 2 (1 votes) · LW · GW

Open a code-block by typing ``` (triple tick), then press enter.

comment by Chris_Leong · 2019-04-17T23:03:01.120Z · score: 2 (1 votes) · LW · GW

Didn't work, just showed the triple ticks

comment by habryka (habryka4) · 2019-04-18T03:32:54.601Z · score: 2 (1 votes) · LW · GW

Weird, here is a gif of how it's supposed to work:

http://www.giphy.com/gifs/IgigWli9bG8OmtpFPv

Are you using the markdown or the draft-js editor? If it's the markdown editor, then surrounding things with those ticks should make everything in between them code.

comment by Chris Leong (chris-leong) · 2019-04-18T14:36:00.995Z · score: 1 (1 votes) · LW · GW

Probably wrong editor

comment by habryka (habryka4) · 2019-04-18T23:22:43.616Z · score: 2 (1 votes) · LW · GW

Hmm, it looks like it was written in the draft-js editor. In any case, I fixed it for you.

comment by Said Achmiz (SaidAchmiz) · 2019-04-17T19:06:52.110Z · score: 2 (1 votes) · LW · GW

Try editing the post on GreaterWrong. There’s a “code block” button in the editor—select your code and click it, it’ll generate the right Markdown to make it a code block.

comment by Richard_Kennaway · 2019-04-17T21:18:11.634Z · score: 3 (2 votes) · LW · GW

There are a couple of books I know of that deal with paradoxes of circularity. I've read the first one (a long time ago, so don't ask me about the details) but not the second.

"The Liar: An Essay on Truth and Circularity" by Barwise and Etchemendy, which is all about the liar paradox, its elaborations, and attempts to resolve them.

"Vicious Circles: On the Mathematics of Non-Wellfounded Phenomena" by Barwise and Moss is more wide-ranging.

comment by Pattern · 2019-04-18T22:45:12.077Z · score: 2 (2 votes) · LW · GW
The truth value of this sentence is not INFINITE-LOOP

Can't this sentence be assigned the value of "True"? If you have those 3 possible assignments (and there is no additional "unknown" value that may be assigned) then the sentences may be true or false or "infinite loop". If it were infinite loop then it would be false. If it were false then it would be infinite loop. But if it is true, then (since true isn't infinite loop) it is true.

comment by Chris_Leong · 2019-04-23T09:53:28.103Z · score: 2 (1 votes) · LW · GW

Yep, it can be assigned that if you use the fixed point definition of truth.

comment by avturchin · 2019-04-17T11:31:49.159Z · score: 2 (1 votes) · LW · GW

A similar conjecture is: "Omniscent Omega tells you that you see is an illusion."

It could be interpreted as a) Omega is real, it said truth and thus I see is an illusion. b) Omega is not real and thus Omega is illusion, no matter what it says. In both cases I see an illusion.

This paradox appears in the discussions about the Simulation Argument in the following form: some people object to SA: if I am in simulation, I can't make any conclusion about the outside world and thus I can't use the computer power estimations to prove future AI capabilities, and thus SA does not work.

However, as it is already assumed that you are in simulation, SA is already proved, no matter what you can or can not conclude, and it is similar to (b) branch of Omega paradox from above.

comment by Pattern · 2019-04-18T22:41:19.000Z · score: 1 (1 votes) · LW · GW
In any case, the way that we extend the concept of truth to apply to these degenerate cases is purely up to what we find convenient. Obviously

How does this last sentence end?

comment by Gurkenglas · 2019-04-18T10:23:12.486Z · score: 1 (1 votes) · LW · GW

compare https://en.m.wikipedia.org/wiki/Turing_jump