24 1. Logic and foundations Here is the non-counterfactual version: Theorem 1.10.11 (Informal statement). Let L be a formal language that contains the concepts of predicates and strings and allows self-reference, and let M be an interpretation of that language. Let T() be a predicate in L that takes sentences as input. Then there exists a sentence G such that the truth value of T(G) (in M) is different from the truth value of G (in M). Proof. We define G to be the self-referential “liar sentence”, G := “T(G) is false”. Then, clearly, G is true if and only if T(G) is false, and the claim follows. Using the Quining trick to achieve indirect self-reference, one can remove the need for direct self-reference in the above argument: Theorem 1.10.12 (Impredicativity of truth. (Informal statement)). Let L be a formal language that contains the concepts of predicates and strings, and let M be an interpretation of that language (i.e. a way of consistently assigning values to every constant, ranges to every variable, and truth values to every sentence in that language) that interprets strings in the standard manner (so, in particular, every sentence or predicate in L can also be viewed as a string constant in M). Then there does not exist a “truth predicate” T(x) in L that takes a string x as input, with the property that for every sentence x in L, that T(x) is true (in M) if and only if x is true (in M). Remark 1.10.13. A more formal version of the above theorem is given by Tarski’s undefinability theorem, which can be found in any graduate text on logic. Here is the non-counterfactual version: Theorem 1.10.14 (Informal statement). Let L be a formal language con- taining the concepts of predicates and strings, and let T(x) be a predicate on strings. Then there exists a sentence G in L with the property that, for any interpretation M of L that interprets strings in the standard manner, that the truth value of T(G) in M is different from the truth value of G in M. Proof (Sketch). We use the “Quining” trick. Let Q(x) be the predicate on strings defined by Q(x) := “x is a predicate on strings, and T(x(x)) is false” and let G be the G¨ odel sentence G := Q(Q). Then, by construction, G is true in M if and only if T(G) is false in M, and the claim follows.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.