Liar Paradox Revisited

post by Chris_Leong · 2019-04-17T23:02:45.875Z · LW · GW · 17 comments

Contents

  Patching with INFINITE-LOOP
  Patching with an oracle
  Patching with ORACLE-LOOP
  Fixed points
  Final Note
None
17 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:

• Statements about the world, where as per Tarski there is a natural interpretation: "Snow is white" is true iff and only iff "Snow is white"
• Logical/Mathematical statements, where the notion truth is constructed to give us a convenient way of talking about our rules of inference within a particular system that normally excludes self-referential statements

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 bounds, 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 by expanding expressions with references to other expressions
else:
    Assign INFINITE-LOOP if expansion fails to terminate

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

Fixed points

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.

Final Note

I actually think there's a similarity here to the Least Interesting Number Paradox. This paradox seems paradoxical only when we fail to define interesting precisely. Once we start to do that, we realise that Interesting Meta-Level 0 and Interesting Meta-Level 1 are different. Similarly, there are different levels of truth depending on how far we go in trying to resolve a question.

17 comments

Comments sorted by top scores.