5 ms·

Self-reference and Logic (2005) [pdf]

60 points by idiliv 8y ago

hs86 8y ago
This is great for understanding why simpler logics (Boolean) are computable but too expressive ones (FO) are not. As soon as the logic is able to make statements about itself, things get 'weird'. A not formal(!) but imho still intuitive example: "This sentence has five words." This is a true statement. And we know that the conjunction of two true statements should also be true. "This sentence has five words and this sentence has five words." With eleven words each part of this statement is obviously false and here we can't rely on the "and", which we are used to from the simpler logics, anymore.
- code_duck 8y ago
  This is also the primary topic explored in the well known book Godel, Escher, Bach.
- gerdesj 8y ago
  "This sentence has five words and this sentence has five words." In English "this" need not always be self referential, so I'll retort with "This sentence is imprecise". The two "this"s could refer to two different things. However, the second this would normally become that to indicate comparison but grammatically the original is still sound [with notes]: This sentence [indicates a sentence with five words in it] has five words and this sentence [indicates another sentence, also with five words in it] has five words.
  - jjnoakes 8y ago
    Even if you try to separate what each 'this' refers to, there is still only one sentence, so the sentence becomes meaningless if you do that.
    - white-flame 8y ago
      No, there are 3 sentences implied in the context, but only 1 sentence is visible in this specific example. Natural language normally isn't a fully self-contained representation.
- pretendscholar 8y ago
  Simple, add a period after each statement: This sentence has five words. and. This sentence has five words. Fields medal please.
  - krackers 8y ago
    Why isn't this a valid solution? "This sentence has five words" AND "this sentence has five words" seems to be logically consistent. Doesn't trying to construct the logical proposition in natural english violate some sort of rule?
    - cannabis_sam 8y ago
      What type of logic uses period and quote operators? What are their semantics?
- schoen 8y ago
  I think this is more a problem of deixis or indexicality than of self-reference particularly. https://en.wikipedia.org/wiki/Indexicality#In_linguistic_pragmatics https://en.wikipedia.org/wiki/Indexicality#In_linguistic_pra... https://en.wikipedia.org/wiki/Deixis https://en.wikipedia.org/wiki/Deixis For example, if I say "it's sunny out now" or "today is a warm day" or "Berkeley is east of here" I also run into problems related to the prospect that references may not have the same referent in different contexts. (For example, two speakers can respectively affirm and deny each of these propositions even though they may both agree in all of their beliefs!) The example that you give can also be interpreted as a deictic problem because the referent of "this sentence" can change from sentence to sentence, even though we normally don't expect the referents of noun phrases to change this way.
CliffStoll 8y ago
An excellent paper, especially reviewing the connections of Peano, Tarski, and Godel. I'm surprised that he did not mention Jim Propp's self=referential aptitude test. It starts with: > 1. The first question whose answer is B is question > (A) 1 > (B) 2 > (C) 3 > (D) 4 > (E) 5 And, of course, Bolander's paper ends with an utterly delightful final sentence!
keithnz 8y ago
Runtime Error: Stack Overflow in recursive function.
yters 8y ago
If this sentence is true, then Santa Claus exists. Therefore, Santa Claus exists.
- skh 8y ago
  If P then Q is a true statement when P is false. (Assuming standard two valued logic.). The statement If P then Q being true does not mean Q has to be true. I don’t think you can conclude Santa Claus exists based on your argument.
  - yters 8y ago
    P = P -> Q P = !P v Q Q |= _|_ P = !P v _|_ P = !P
    - skh 8y ago
      Your reasoning only works for valid statements. That is, statements that have a truth value. As you’ve demonstrated P does not have one. For no admissible statement is P equal to not P.
      - yters 8y ago
        1. Premise: P -> Q 2. Premise: ((P -> Q) -> P) -> P 3. (P -> Q) -> P, from 1 4. P, from 2 and 3 5. Q, from 1 and 4
        skh 8y ago
        The P, in your original post, is not a valid formula since it does not have a truth value. You can construct all the proofs and whatnot you want but if P is not a logical statement (one that is either true or false but not both) then the arguments are not valid. Your Q was generic and could have been any statement. In particular one that has been provably shown to be false. If your arguments are correct then you have the ability to prove any false statement is true. Do you really think you have found a way to demonstrate that the standard two-valued logic used in mathematics leads to a contradiction?
firethief 8y ago
Footnote 17 mentions a proposed approach of "extending logic to include contexts", but doesn't name any names. Anyone have a reference I can follow?

60 points by idiliv 8y ago

hs86 8y ago

This is great for understanding why simpler logics (Boolean) are computable but too expressive ones (FO) are not. As soon as the logic is able to make statements about itself, things get 'weird'. A not formal(!) but imho still intuitive example: "This sentence has five words." This is a true statement. And we know that the conjunction of two true statements should also be true. "This sentence has five words and this sentence has five words." With eleven words each part of this statement is obviously false and here we can't rely on the "and", which we are used to from the simpler logics, anymore.

code_duck 8y ago
This is also the primary topic explored in the well known book Godel, Escher, Bach.
gerdesj 8y ago
"This sentence has five words and this sentence has five words." In English "this" need not always be self referential, so I'll retort with "This sentence is imprecise". The two "this"s could refer to two different things. However, the second this would normally become that to indicate comparison but grammatically the original is still sound [with notes]: This sentence [indicates a sentence with five words in it] has five words and this sentence [indicates another sentence, also with five words in it] has five words.
- jjnoakes 8y ago
  Even if you try to separate what each 'this' refers to, there is still only one sentence, so the sentence becomes meaningless if you do that.
  - white-flame 8y ago
    No, there are 3 sentences implied in the context, but only 1 sentence is visible in this specific example. Natural language normally isn't a fully self-contained representation.
pretendscholar 8y ago
Simple, add a period after each statement: This sentence has five words. and. This sentence has five words. Fields medal please.
- krackers 8y ago
  Why isn't this a valid solution? "This sentence has five words" AND "this sentence has five words" seems to be logically consistent. Doesn't trying to construct the logical proposition in natural english violate some sort of rule?
  - cannabis_sam 8y ago
    What type of logic uses period and quote operators? What are their semantics?
schoen 8y ago
I think this is more a problem of deixis or indexicality than of self-reference particularly. https://en.wikipedia.org/wiki/Indexicality#In_linguistic_pragmatics https://en.wikipedia.org/wiki/Indexicality#In_linguistic_pra... https://en.wikipedia.org/wiki/Deixis https://en.wikipedia.org/wiki/Deixis For example, if I say "it's sunny out now" or "today is a warm day" or "Berkeley is east of here" I also run into problems related to the prospect that references may not have the same referent in different contexts. (For example, two speakers can respectively affirm and deny each of these propositions even though they may both agree in all of their beliefs!) The example that you give can also be interpreted as a deictic problem because the referent of "this sentence" can change from sentence to sentence, even though we normally don't expect the referents of noun phrases to change this way.

CliffStoll 8y ago

An excellent paper, especially reviewing the connections of Peano, Tarski, and Godel. I'm surprised that he did not mention Jim Propp's self=referential aptitude test. It starts with: > 1. The first question whose answer is B is question > (A) 1 > (B) 2 > (C) 3 > (D) 4 > (E) 5 And, of course, Bolander's paper ends with an utterly delightful final sentence!

keithnz 8y ago

Runtime Error: Stack Overflow in recursive function.

yters 8y ago

If this sentence is true, then Santa Claus exists. Therefore, Santa Claus exists.

skh 8y ago
If P then Q is a true statement when P is false. (Assuming standard two valued logic.). The statement If P then Q being true does not mean Q has to be true. I don’t think you can conclude Santa Claus exists based on your argument.
- yters 8y ago
  P = P -> Q P = !P v Q Q |= _|_ P = !P v _|_ P = !P
  - skh 8y ago
    Your reasoning only works for valid statements. That is, statements that have a truth value. As you’ve demonstrated P does not have one. For no admissible statement is P equal to not P.
    - yters 8y ago
      1. Premise: P -> Q 2. Premise: ((P -> Q) -> P) -> P 3. (P -> Q) -> P, from 1 4. P, from 2 and 3 5. Q, from 1 and 4
      - skh 8y ago
        The P, in your original post, is not a valid formula since it does not have a truth value. You can construct all the proofs and whatnot you want but if P is not a logical statement (one that is either true or false but not both) then the arguments are not valid. Your Q was generic and could have been any statement. In particular one that has been provably shown to be false. If your arguments are correct then you have the ability to prove any false statement is true. Do you really think you have found a way to demonstrate that the standard two-valued logic used in mathematics leads to a contradiction?

firethief 8y ago

Footnote 17 mentions a proposed approach of "extending logic to include contexts", but doesn't name any names. Anyone have a reference I can follow?