Quantum logic

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Quantum_logic 

 

In quantum mechanics, quantum logic is a set of rules for reasoning about propositions that takes the principles of quantum theory into account. This research area and its name originated in a 1936 paper by Garrett Birkhoff and John von Neumann, who were attempting to reconcile the apparent inconsistency of classical logic with the facts concerning the measurement of complementary variables in quantum mechanics, such as position and momentum.

Quantum logic can be formulated either as a modified version of propositional logic or as a noncommutative and non-associative many-valued (MV) logic.

Quantum logic has been proposed as the correct logic for propositional inference generally, most notably by the philosopher Hilary Putnam, at least at one point in his career. This thesis was an important ingredient in Putnam's 1968 paper "Is Logic Empirical?" in which he analysed the epistemological status of the rules of propositional logic. Putnam attributes the idea that anomalies associated to quantum measurements originate with anomalies in the logic of physics itself to the physicist David Finkelstein. However, this idea had been around for some time and had been revived several years earlier by George Mackey's work on group representations and symmetry.

The more common view regarding quantum logic, however, is that it provides a formalism for relating observables, system preparation filters and states. In this view, the quantum logic approach resembles more closely the C*-algebraic approach to quantum mechanics. The similarities of the quantum logic formalism to a system of deductive logic may then be regarded more as a curiosity than as a fact of fundamental philosophical importance. A more modern approach to the structure of quantum logic is to assume that it is a diagram—in the sense of category theory—of classical logics (see David Edwards).

Differences with classical logic

Quantum logic has some properties that clearly distinguish it from classical logic, most notably, the failure of the distributive law of propositional logic:

p and (q or r) = (p and q) or (p and r),

where the symbols p, q and r are propositional variables. To illustrate why the distributive law fails, consider a particle moving on a line and (using some system of units where the reduced Planck's constant is 1) let

p = "the particle has momentum in the interval [0, +1/6]"

q = "the particle is in the interval [−1, 1]"

r = "the particle is in the interval [1, 3]"

Note: The choice of p, q, and r in this example is intuitive but not formally valid (that is, p and (q or r) is also false here); see section "Quantum logic as the logic of observables" below for details and a valid example. 

We might observe that:

p and (q or r) = true

in other words, that the particle's momentum is between 0 and +1/6, and its position is between −1 and +3. On the other hand, the propositions "p and q" and "p and r" are both false, since they assert tighter restrictions on simultaneous values of position and momentum than is allowed by the uncertainty principle (they each have uncertainty 1/3, which is less than the allowed minimum of 1/2). So,

(p and q) or (p and r) = false

Thus the distributive law fails.

Introduction

In his classic 1932 treatise Mathematical Foundations of Quantum Mechanics, John von Neumann noted that projections on a Hilbert space can be viewed as propositions about physical observables. The set of principles for manipulating these quantum propositions was called quantum logic by von Neumann and Birkhoff in their 1936 paper. George Mackey, in his 1963 book (also called Mathematical Foundations of Quantum Mechanics), attempted to provide a set of axioms for this propositional system as an orthocomplemented lattice. Mackey viewed elements of this set as potential yes or no questions an observer might ask about the state of a physical system, questions that would be settled by some measurement. Moreover, Mackey defined a physical observable in terms of these basic questions. Mackey's axiom system is somewhat unsatisfactory though, since it assumes that the partially ordered set is actually given as the orthocomplemented closed subspace lattice of a separable Hilbert space. Constantin Piron, Günther Ludwig and others have attempted to give axiomatizations that do not require such explicit relations to the lattice of subspaces. 

The axioms of an orthocomplemented lattice are most commonly stated as algebraic equations concerning the poset and its operations. A set of axioms using instead disjunction (denoted as ${\displaystyle \cup }$) and negation (denoted as ${\displaystyle ^{\perp }}$) is as follows:

• ${\displaystyle a=a^{\perp \perp }}$
• ${\displaystyle \cup }$ is commutative and associative.
• There is a maximal element ${\displaystyle 1}$, and ${\displaystyle 1=b\cup b^{\perp }}$ for any ${\displaystyle b}$.
• ${\displaystyle a\cup (a^{\perp }\cup b)^{\perp }=a}$.

An orthomodular lattice satisfies the above axioms, and additionally the following one:

• The orthomodular law: If ${\displaystyle 1=(a^{\perp }\cup b^{\perp })^{\perp }\cup (a\cup b)^{\perp }}$ then ${\displaystyle a=b}$.

Alternative formulations include sequent calculi, and tableaux systems.

The remainder of this article assumes the reader is familiar with the spectral theory of self-adjoint operators on a Hilbert space. However, the main ideas can be understood using the finite-dimensional spectral theorem.

Quantum logic as the logic of observables

One semantics of quantum logic is that quantum logic is the logic of boolean observables in quantum mechanics, where an observable p is associated with the set of quantum states for which p (when measured) is true with probability 1 (this completely characterizes the observable). From there,

• ¬p is the orthogonal complement of p (since for those states, the probability of observing p, P(p) = 0),
• p∧q is the intersection of p and q, and
• p∨q = ¬(¬p∧¬q) refers to states that are a superposition of p and q.

Thus, expressions in quantum logic describe observables using a syntax that resembles classical logic. However, unlike classical logic, the distributive law a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) fails when dealing with noncommuting observables, such as position and momentum. This occurs because measurement affects the system, and measurement of whether a disjunction holds does not measure which of the disjuncts is true.

For an example, consider a simple one-dimensional particle with position denoted by x and momentum by p, and define observables:

• a — |p| ≤ 1 (in some units)
• b — x < 0
• c — x ≥ 0

Now, position and momentum are Fourier transforms of each other, and the Fourier transform of a square-integrable nonzero function with a compact support is entire and hence does not have non-isolated zeroes. Therefore, there is no wave function that vanishes at x ≥ 0 with P(|p|≤1) = 1. Thus, a ∧ b and similarly a ∧ c are false, so (a ∧ b) ∨ (a ∧ c) is false. However, a ∧ (b ∨ c) equals a and might be true. 

To understand more, let p₁ and p₂ be the momenta for the restriction of the particle wave function to x < 0 and x ≥ 0 respectively (with the wave function zero outside of the restriction). Let ${\displaystyle |p|\!\upharpoonright _{>1}}$ be the restriction of |p| to momenta that are (in absolute value) >1.

(a ∧ b) ∨ (a ∧ c) corresponds to states with ${\displaystyle |p_{1}|\!\upharpoonright _{>1}=0}$ and ${\displaystyle |p_{2}|\!\upharpoonright _{>1}=0}$ (this holds even if we defined p differently so as to make such states possible; also, a ∧ b corresponds to ${\displaystyle |p_{1}|\!\upharpoonright _{>1}=0}$ and ${\displaystyle p_{2}=0}$). As an operator, ${\displaystyle p=p_{1}+p_{2}}$, and nonzero ${\displaystyle |p_{1}|\!\upharpoonright _{>1}}$ and ${\displaystyle |p_{2}|\!\upharpoonright _{>1}}$ might interfere to produce zero ${\displaystyle |p|\!\upharpoonright _{>1}}$. Such interference is key to the richness of quantum logic and quantum mechanics.

The propositional lattice of a classical system

The so-called Hamiltonian formulations of classical mechanics have three ingredients: states, observables and dynamics. In the simplest case of a single particle moving in R³, the state space is the position-momentum space R⁶. We will merely note here that an observable is some real-valued function f on the state space. Examples of observables are position, momentum or energy of a particle. For classical systems, the value f(x), that is the value of f for some particular system state x, is obtained by a process of measurement of f. The propositions concerning a classical system are generated from basic statements of the form

"Measurement of f yields a value in the interval [a, b] for some real numbers a, b."

It follows easily from this characterization of propositions in classical systems that the corresponding logic is identical to that of some Boolean algebra of subsets of the state space. By logic in this context we mean the rules that relate set operations and ordering relations, such as de Morgan's laws. These are analogous to the rules relating boolean conjunctives and material implication in classical propositional logic. For technical reasons, we will also assume that the algebra of subsets of the state space is that of all Borel sets. The set of propositions is ordered by the natural ordering of sets and has a complementation operation. In terms of observables, the complement of the proposition {f ≥ a} is {f < a}. 

We summarize these remarks as follows: The proposition system of a classical system is a lattice with a distinguished orthocomplementation operation: The lattice operations of meet and join are respectively set intersection and set union. The orthocomplementation operation is set complement. Moreover, this lattice is sequentially complete, in the sense that any sequence {E_i}_i of elements of the lattice has a least upper bound, specifically the set-theoretic union:

${\displaystyle \operatorname {LUB} (\{E_{i}\})=\bigcup _{i=1}^{\infty }E_{i}.}$

The propositional lattice of a quantum mechanical system

In the Hilbert space formulation of quantum mechanics as presented by von Neumann, a physical observable is represented by some (possibly unbounded) densely defined self-adjoint operator A on a Hilbert space H. A has a spectral decomposition, which is a projection-valued measure E defined on the Borel subsets of R. In particular, for any bounded Borel function f on R, the following extension of f to operators can be made:

${\displaystyle f(A)=\int _{\mathbb {R} }f(\lambda )\,d\operatorname {E} (\lambda ).}$

In case f is the indicator function of an interval [a, b], the operator f(A) is a self-adjoint projection, and can be interpreted as the quantum analogue of the classical proposition

• Measurement of A yields a value in the interval [a, b].

This suggests the following quantum mechanical replacement for the orthocomplemented lattice of propositions in classical mechanics. This is essentially Mackey's Axiom VII:

• The orthocomplemented lattice Q of propositions of a quantum mechanical system is the lattice of closed subspaces of a complex Hilbert space H where orthocomplementation of V is the orthogonal complement V^⊥.

Q is also sequentially complete: any pairwise disjoint sequence{V_i}_i of elements of Q has a least upper bound. Here disjointness of W₁ and W₂ means W₂ is a subspace of W₁^⊥. The least upper bound of {V_i}_i is the closed internal direct sum. 

Henceforth we identify elements of Q with self-adjoint projections on the Hilbert space H. 

The structure of Q immediately points to a difference with the partial order structure of a classical proposition system. In the classical case, given a proposition p, the equations

${\displaystyle I=p\vee q}$

${\displaystyle 0=p\wedge q}$

have exactly one solution, namely the set-theoretic complement of p. In these equations I refers to the atomic proposition that is identically true and 0 the atomic proposition that is identically false. In the case of the lattice of projections there are infinitely many solutions to the above equations (any closed, algebraic complement of p solves it; it need not be the orthocomplement).

Having made these preliminary remarks, we turn everything around and attempt to define observables within the projection lattice framework and using this definition establish the correspondence between self-adjoint operators and observables: A Mackey observable is a countably additive homomorphism from the orthocomplemented lattice of the Borel subsets of R to Q. To say the mapping φ is a countably additive homomorphism means that for any sequence {S_i}_i of pairwise disjoint Borel subsets of R, {φ(S_i)}_i are pairwise orthogonal projections and

${\displaystyle \varphi \left(\bigcup _{i=1}^{\infty }S_{i}\right)=\sum _{i=1}^{\infty }\varphi (S_{i}).}$

Effectively, then, a Mackey observable is a projection-valued measure on R. 

Theorem. There is a bijective correspondence between Mackey observables and densely defined self-adjoint operators on H. 

This is the content of the spectral theorem as stated in terms of spectral measures.

Statistical structure

Imagine a forensics lab that has some apparatus to measure the speed of a bullet fired from a gun. Under carefully controlled conditions of temperature, humidity, pressure and so on the same gun is fired repeatedly and speed measurements taken. This produces some distribution of speeds. Though we will not get exactly the same value for each individual measurement, for each cluster of measurements, we would expect the experiment to lead to the same distribution of speeds. In particular, we can expect to assign probability distributions to propositions such as {a ≤ speed ≤ b}. This leads naturally to propose that under controlled conditions of preparation, the measurement of a classical system can be described by a probability measure on the state space. This same statistical structure is also present in quantum mechanics. 

A quantum probability measure is a function P defined on Q with values in [0,1] such that P(0)=0, P(I)=1 and if {E_i}_i is a sequence of pairwise orthogonal elements of Q then

${\displaystyle \operatorname {P} \!\left(\sum _{i=1}^{\infty }E_{i}\right)=\sum _{i=1}^{\infty }\operatorname {P} (E_{i}).}$

The following highly non-trivial theorem is due to Andrew Gleason: 

Theorem. Suppose Q is a separable Hilbert space of complex dimension at least 3. Then for any quantum probability measure P on Q there exists a unique trace class operator S such that

${\displaystyle \operatorname {P} (E)=\operatorname {Tr} (SE)}$

for any self-adjoint projection E in Q.

The operator S is necessarily non-negative (that is all eigenvalues are non-negative) and of trace 1. Such an operator is often called a density operator. 

Physicists commonly regard a density operator as being represented by a (possibly infinite) density matrix relative to some orthonormal basis. 

For more information on statistics of quantum systems, see quantum statistical mechanics.

Automorphisms

An automorphism of Q is a bijective mapping α:Q → Q that preserves the orthocomplemented structure of Q, that is

${\displaystyle \alpha \!\left(\sum _{i=1}^{\infty }E_{i}\right)=\sum _{i=1}^{\infty }\alpha (E_{i})}$

for any sequence {E_i}_i of pairwise orthogonal self-adjoint projections. Note that this property implies monotonicity of α. If P is a quantum probability measure on Q, then E → α(E) is also a quantum probability measure on Q. By the Gleason theorem characterizing quantum probability measures quoted above, any automorphism α induces a mapping α* on the density operators by the following formula:

${\displaystyle \operatorname {Tr} (\alpha ^{*}(S)E)=\operatorname {Tr} (S\alpha (E)).}$

The mapping α* is bijective and preserves convex combinations of density operators. This means

${\displaystyle \alpha ^{*}(r_{1}S_{1}+r_{2}S_{2})=r_{1}\alpha ^{*}(S_{1})+r_{2}\alpha ^{*}(S_{2})\quad }$

whenever 1 = r₁ + r₂ and r₁, r₂ are non-negative real numbers. Now we use a theorem of Richard V. Kadison: 

Theorem. Suppose β is a bijective map from density operators to density operators that is convexity preserving. Then there is an operator U on the Hilbert space that is either linear or conjugate-linear, preserves the inner product and is such that

${\displaystyle \beta (S)=USU^{*}}$

for every density operator S. In the first case we say U is unitary, in the second case U is anti-unitary.

Remark. This note is included for technical accuracy only, and should not concern most readers. The result quoted above is not directly stated in Kadison's paper, but can be reduced to it by noting first that β extends to a positive trace preserving map on the trace class operators, then applying duality and finally applying a result of Kadison's paper.

The operator U is not quite unique; if r is a complex scalar of modulus 1, then r U will be unitary or anti-unitary if U is and will implement the same automorphism. In fact, this is the only ambiguity possible. 

It follows that automorphisms of Q are in bijective correspondence to unitary or anti-unitary operators modulo multiplication by scalars of modulus 1. Moreover, we can regard automorphisms in two equivalent ways: as operating on states (represented as density operators) or as operating on Q.

Non-relativistic dynamics

In non-relativistic physical systems, there is no ambiguity in referring to time evolution since there is a global time parameter. Moreover, an isolated quantum system evolves in a deterministic way: if the system is in a state S at time t then at time s > t, the system is in a state F_s,t(S). Moreover, we assume

• The dependence is reversible: The operators F_s,t are bijective.
• The dependence is homogeneous: F_s,t = F_s − t,0.
• The dependence is convexity preserving: That is, each F_s,t(S) is convexity preserving.
• The dependence is weakly continuous: The mapping R→ R given by t → Tr(F_s,t(S) E) is continuous for every E in Q.

By Kadison's theorem, there is a 1-parameter family of unitary or anti-unitary operators {U_t}_t such that

${\displaystyle \operatorname {F} _{s,t}(S)=U_{s-t}SU_{s-t}^{*}}$

In fact.

Theorem. Under the above assumptions, there is a strongly continuous 1-parameter group of unitary operators {U_t}_t such that the above equation holds. 

Note that it follows easily from uniqueness from Kadison's theorem that

${\displaystyle U_{t+s}=\sigma (t,s)U_{t}U_{s}}$

where σ(t,s) has modulus 1. Now the square of an anti-unitary is a unitary, so that all the U_t are unitary. The remainder of the argument shows that σ(t,s) can be chosen to be 1 (by modifying each U_t by a scalar of modulus 1.)

Pure states

A convex combination of statistical states S₁ and S₂ is a state of the form S = p₁ S₁ +p₂ S₂ where p₁, p₂ are non-negative and p₁ + p₂ =1. Considering the statistical state of system as specified by lab conditions used for its preparation, the convex combination S can be regarded as the state formed in the following way: toss a biased coin with outcome probabilities p₁, p₂ and depending on outcome choose system prepared to S₁ or S₂.

Density operators form a convex set. The convex set of density operators has extreme points; these are the density operators given by a projection onto a one-dimensional space. To see that any extreme point is such a projection, note that by the spectral theorem S can be represented by a diagonal matrix; since S is non-negative all the entries are non-negative and since S has trace 1, the diagonal entries must add up to 1. Now if it happens that the diagonal matrix has more than one non-zero entry it is clear that we can express it as a convex combination of other density operators. 

The extreme points of the set of density operators are called pure states. If S is the projection on the 1-dimensional space generated by a vector ψ of norm 1 then

${\displaystyle \operatorname {Tr} (SE)=\langle E\psi |\psi \rangle }$

for any E in Q. In physics jargon, if

${\displaystyle S=|\psi \rangle \langle \psi |,}$

where ψ has norm 1, then

${\displaystyle \operatorname {Tr} (SE)=\langle \psi |E|\psi \rangle .}$

Thus pure states can be identified with rays in the Hilbert space H.

The measurement process

Consider a quantum mechanical system with lattice Q that is in some statistical state given by a density operator S. This essentially means an ensemble of systems specified by a repeatable lab preparation process. The result of a cluster of measurements intended to determine the truth value of proposition E, is just as in the classical case, a probability distribution of truth values T and F. Say the probabilities are p for T and q = 1 − p for F. By the previous section p = Tr(S E) and q = Tr(S (I − E)).

Perhaps the most fundamental difference between classical and quantum systems is the following: regardless of what process is used to determine E immediately after the measurement the system will be in one of two statistical states:

• If the result of the measurement is T

${\displaystyle {\frac {1}{\operatorname {Tr} (ES)}}ESE.}$

• If the result of the measurement is F

${\displaystyle {\frac {1}{\operatorname {Tr} ((I-E)S)}}(I-E)S(I-E).}$

(We leave to the reader the handling of the degenerate cases in which the denominators may be 0.) We now form the convex combination of these two ensembles using the relative frequencies p and q. We thus obtain the result that the measurement process applied to a statistical ensemble in state S yields another ensemble in statistical state:

${\displaystyle \operatorname {M} _{E}(S)=ESE+(I-E)S(I-E).}$

We see that a pure ensemble becomes a mixed ensemble after measurement. Measurement, as described above, is a special case of quantum operations.

Limitations

Quantum logic derived from propositional logic provides a satisfactory foundation for a theory of reversible quantum processes. Examples of such processes are the covariance transformations relating two frames of reference, such as change of time parameter or the transformations of special relativity. Quantum logic also provides a satisfactory understanding of density matrices. Quantum logic can be stretched to account for some kinds of measurement processes corresponding to answering yes–no questions about the state of a quantum system. However, for more general kinds of measurement operations (that is quantum operations), a more complete theory of filtering processes is necessary. Such a theory of quantum filtering was developed in the late 1970s and 1980s by Belavkin  (see also Bouten et al.). A similar approach is provided by the consistent histories formalism. On the other hand, quantum logics derived from many-valued logic extend its range of applicability to irreversible quantum processes or 'open' quantum systems. 

In any case, these quantum logic formalisms must be generalized in order to deal with super-geometry (which is needed to handle Fermi-fields) and non-commutative geometry (which is needed in string theory and quantum gravity theory). Both of these theories use a partial algebra with an "integral" or "trace". The elements of the partial algebra are not observables; instead the "trace" yields "greens functions", which generate scattering amplitudes. One thus obtains a local S-matrix theory (see D. Edwards).

In 2004, Prakash Panangaden described how to capture the kinematics of quantum causal evolution using System BV, a deep inference logic originally developed for use in structural proof theory. Alessio Guglielmi, Lutz Straßburger, and Richard Blute have also done work in this area.

Liar paradox

From Wikipedia, the free encyclopedia

Jump to navigation Jump to search

 

In philosophy and logic, the classical liar paradox or liar's paradox or antinomy of the liar is the statement of a liar that he or she is lying: for instance, declaring that "I am lying". If the liar is indeed lying, then the liar is telling the truth, which means the liar just lied. In "this sentence is a lie" the paradox is strengthened in order to make it amenable to more rigorous logical analysis. It is still generally called the "liar paradox" although abstraction is made precisely from the liar making the statement. Trying to assign to this statement, the strengthened liar, a classical binary truth value leads to a contradiction.

If "this sentence is false" is true, then it is false, but the sentence states that it is false, and if it is false, then it must be true, and so on.

History

The Epimenides paradox (circa 600 BC) has been suggested as an example of the liar paradox, but they are not logically equivalent. The semi-mythical seer Epimenides, a Cretan, reportedly stated that "All Cretans are liars." However, Epimenides' statement that all Cretans are liars can be resolved as false, given that he knows of at least one other Cretan who does not lie. It is precisely in order to avoid uncertainties deriving from the human factor and from fuzzy concepts that modern logicians proposed a "strengthened" liar such as the sentence "this sentence is false".

The paradox's name translates as pseudómenos lógos (ψευδόμενος λόγος) in Ancient Greek. One version of the liar paradox is attributed to the Greek philosopher Eubulides of Miletus who lived in the 4th century BC. Eubulides reportedly asked, "A man says that he is lying. Is what he says true or false?"

The paradox was once discussed by St. Jerome in a sermon:

"I said in my alarm, Every man is a liar!" Is David telling the truth or is he lying? If it is true that every man is a liar, and David's statement, "Every man is a liar" is true, then David also is lying; he, too, is a man. But if he, too, is lying, his statement that "Every man is a liar", consequently is not true. Whatever way you turn the proposition, the conclusion is a contradiction. Since David himself is a man, it follows that he also is lying; but if he is lying because every man is a liar, his lying is of a different sort.

The Indian grammarian-philosopher Bhartrhari (late fifth century AD) was well aware of a liar paradox which he formulated as "everything I am saying is false" (sarvam mithyā bravīmi). He analyzes this statement together with the paradox of "unsignifiability" and explores the boundary between statements that are unproblematic in daily life and paradoxes.

There was discussion of the liar paradox in early Islamic tradition for at least five centuries, starting from late 9th century, and apparently without being influenced by any other tradition. Naṣīr al-Dīn al-Ṭūsī could have been the first logician to identify the liar paradox as self-referential.

Explanation and variants

The problem of the liar paradox is that it seems to show that common beliefs about truth and falsity actually lead to a contradiction. Sentences can be constructed that cannot consistently be assigned a truth value even though they are completely in accord with grammar and semantic rules.

The simplest version of the paradox is the sentence:

A: This statement (A) is false.

 

If (A) is true, then "This statement is false" is true. Therefore, (A) must be false. The hypothesis that (A) is true leads to the conclusion that (A) is false, a contradiction.

If (A) is false, then "This statement is false" is false. Therefore, (A) must be true. The hypothesis that (A) is false leads to the conclusion that (A) is true, another contradiction. Either way, (A) is both true and false, which is a paradox.

However, that the liar sentence can be shown to be true if it is false and false if it is true has led some to conclude that it is "neither true nor false". This response to the paradox is, in effect, the rejection of the claim that every statement has to be either true or false, also known as the principle of bivalence, a concept related to the law of the excluded middle.

The proposal that the statement is neither true nor false has given rise to the following, strengthened version of the paradox:

This statement is not true. (B)

If (B) is neither true nor false, then it must be not true. Since this is what (B) itself states, it means that (B) must be true. Since initially (B) was not true and is now true, another paradox arises. 

Another reaction to the paradox of (A) is to posit, as Graham Priest has, that the statement is both true and false. Nevertheless, even Priest's analysis is susceptible to the following version of the liar:

This statement is only false. (C)

If (C) is both true and false, then (C) is only false. But then, it is not true. Since initially (C) was true and is now not true, it is a paradox. However, it has been argued that by adopting a two-valued relational semantics (as opposed to functional semantics), the dialetheic approach can overcome this version of the Liar.

There are also multi-sentence versions of the liar paradox. The following is the two-sentence version:

The following statement is true. (D1)

The preceding statement is false. (D2)

Assume (D1) is true. Then (D2) is true. This would mean that (D1) is false. Therefore, (D1) is both true and false.

Assume (D1) is false. Then (D2) is false. This would mean that (D1) is true. Thus (D1) is both true and false. Either way, (D1) is both true and false – the same paradox as (A) above.

The multi-sentence version of the liar paradox generalizes to any circular sequence of such statements (wherein the last statement asserts the truth/falsity of the first statement), provided there are an odd number of statements asserting the falsity of their successor; the following is a three-sentence version, with each statement asserting the falsity of its successor:

E2 is false. (E1)

E3 is false. (E2)

E1 is false. (E3)

Assume (E1) is true. Then (E2) is false, which means (E3) is true, and hence (E1) is false, leading to a contradiction. 

Assume (E1) is false. Then (E2) is true, which means (E3) is false, and hence (E1) is true. Either way, (E1) is both true and false – the same paradox as with (A) and (D1). 

There are many other variants, and many complements, possible. In normal sentence construction, the simplest version of the complement is the sentence:

This statement is true. (F)

If F is assumed to bear a truth value, then it presents the problem of determining the object of that value. But, a simpler version is possible, by assuming that the single word 'true' bears a truth value. The analogue to the paradox is to assume that the single word 'false' likewise bears a truth value, namely that it is false. This reveals that the paradox can be reduced to the mental act of assuming that the very idea of fallacy bears a truth value, namely that the very idea of fallacy is false: an act of misrepresentation. So, the symmetrical version of the paradox would be:

The following statement is false. (G1)

The preceding statement is false. (G2)

Possible resolutions

Alfred Tarski

Alfred Tarski diagnosed the paradox as arising only in languages that are "semantically closed", by which he meant a language in which it is possible for one sentence to predicate truth (or falsehood) of another sentence in the same language (or even of itself). To avoid self-contradiction, it is necessary when discussing truth values to envision levels of languages, each of which can predicate truth (or falsehood) only of languages at a lower level. So, when one sentence refers to the truth-value of another, it is semantically higher. The sentence referred to is part of the "object language", while the referring sentence is considered to be a part of a "meta-language" with respect to the object language. It is legitimate for sentences in "languages" higher on the semantic hierarchy to refer to sentences lower in the "language" hierarchy, but not the other way around. This prevents a system from becoming self-referential.

However, this system is incomplete. One would like to be able to make statements such as "For every statement in level α of the hierarchy, there is a statement at level α+1 which asserts that the first statement is false." This is a true, meaningful statement about the hierarchy that Tarski defines, but it refers to statements at every level of the hierarchy, so it must be above every level of the hierarchy, and is therefore not possible within the hierarchy (although bounded versions of the sentence are possible).

Arthur Prior

Arthur Prior asserts that there is nothing paradoxical about the liar paradox. His claim (which he attributes to Charles Sanders Peirce and John Buridan) is that every statement includes an implicit assertion of its own truth. Thus, for example, the statement "It is true that two plus two equals four" contains no more information than the statement "two plus two equals four", because the phrase "it is true that..." is always implicitly there. And in the self-referential spirit of the Liar Paradox, the phrase "it is true that..." is equivalent to "this whole statement is true and ...". 

Thus the following two statements are equivalent:

This statement is false.

This statement is true and this statement is false.

The latter is a simple contradiction of the form "A and not A", and hence is false. There is therefore no paradox because the claim that this two-conjunct Liar is false does not lead to a contradiction. Eugene Mills presents a similar answer.

Saul Kripke

Saul Kripke argued that whether a sentence is paradoxical or not can depend upon contingent facts. If the only thing Smith says about Jones is:

A majority of what Jones says about me is false.

and Jones says only these three things about Smith:

Smith is a big spender.

Smith is soft on crime.

Everything Smith says about me is true.

If Smith really is a big spender but is not soft on crime, then both Smith's remark about Jones and Jones's last remark about Smith are paradoxical.

Kripke proposes a solution in the following manner. If a statement's truth value is ultimately tied up in some evaluable fact about the world, that statement is "grounded". If not, that statement is "ungrounded". Ungrounded statements do not have a truth value. Liar statements and liar-like statements are ungrounded, and therefore have no truth value.

Jon Barwise and John Etchemendy

Jon Barwise and John Etchemendy propose that the liar sentence (which they interpret as synonymous with the Strengthened Liar) is ambiguous. They base this conclusion on a distinction they make between a "denial" and a "negation". If the liar means, "It is not the case that this statement is true", then it is denying itself. If it means, "This statement is not true", then it is negating itself. They go on to argue, based on situation semantics, that the "denial liar" can be true without contradiction while the "negation liar" can be false without contradiction. Their 1987 book makes heavy use of non-well-founded set theory.

Dialetheism

Graham Priest and other logicians, including J. C. Beall and Bradley Armour-Garb, have proposed that the liar sentence should be considered to be both true and false, a point of view known as dialetheism. Dialetheism is the view that there are true contradictions. Dialetheism raises its own problems. Chief among these is that since dialetheism recognizes the liar paradox, an intrinsic contradiction, as being true, it must discard the long-recognized principle of explosion, which asserts that any proposition can be deduced from a contradiction, unless the dialetheist is willing to accept trivialism – the view that all propositions are true. Since trivialism is an intuitively false view, dialetheists nearly always reject the explosion principle. Logics that reject it are called paraconsistent.

Non-cognitivism

Andrew Irvine has argued in favour of a non-cognitivist solution to the paradox, suggesting that some apparently well-formed sentences will turn out to be neither true nor false and that "formal criteria alone will inevitably prove insufficient" for resolving the paradox.

Bhartrhari's perspectivism

The Indian grammarian-philosopher Bhartrhari (late fifth century AD) dealt with paradoxes such as the liar in a section of one of the chapters of his magnum opus the Vākyapadīya. Although chronologically he precedes all modern treatments of the problem of the liar paradox, it has only very recently become possible for those who cannot read the original Sanskrit sources to confront his views and analyses with those of modern logicians and philosophers because sufficiently reliable editions and translations of his work have only started becoming available since the second half of the 20th century. Bhartrhari's solution fits into his general approach to language, thought and reality, which has been characterized by some as "relativistic", "non-committal" or "perspectivistic". With regard to the liar paradox (sarvam mithyā bhavāmi "everything I am saying is false") Bhartrhari identifies a hidden parameter which can change unproblematic situations in daily communication into a stubborn paradox. Bhartrhari's solution can be understood in terms of the solution proposed in 1992 by Julian Roberts: "Paradoxes consume themselves. But we can keep apart the warring sides of the contradiction by the simple expedient of temporal contextualisation: what is 'true' with respect to one point in time need not be so in another ... The overall force of the 'Austinian' argument is not merely that 'things change', but that rationality is essentially temporal in that we need time in order to reconcile and manage what would otherwise be mutually destructive states." According to Robert's suggestion, it is the factor "time" which allows us to reconcile the separated "parts of the world" that play a crucial role in the solution of Barwise and Etchemendy. The capacity of time to prevent a direct confrontation of the two "parts of the world" is here external to the "liar". In the light of Bhartrhari's analysis, however, the extension in time which separates two perspectives on the world or two "parts of the world" – the part before and the part after the function accomplishes its task – is inherent in any "function": also the function to signify which underlies each statement, including the "liar". The unsolvable paradox – a situation in which we have either contradiction (virodha) or infinite regress (anavasthā) – arises, in case of the liar and other paradoxes such as the unsignifiability paradox (Bhartrhari's paradox), when abstraction is made from this function (vyāpāra) and its extension in time, by accepting a simultaneous, opposite function (apara vyāpāra) undoing the previous one.

Logical structure

For a better understanding of the liar paradox, it is useful to write it down in a more formal way. If "this statement is false" is denoted by A and its truth value is being sought, it is necessary to find a condition that restricts the choice of possible truth values of A. Because A is self-referential it is possible to give the condition by an equation.

If some statement, B, is assumed to be false, one writes, "B = false". The statement (C) that the statement B is false would be written as "C = 'B = false'". Now, the liar paradox can be expressed as the statement A, that A is false:

A = "A = false"

This is an equation from which the truth value of A = "this statement is false" could hopefully be obtained. In the boolean domain "A = false" is equivalent to "not A" and therefore the equation is not solvable. This is the motivation for reinterpretation of A. The simplest logical approach to make the equation solvable is the dialetheistic approach, in which case the solution is A being both "true" and "false". Other resolutions mostly include some modifications of the equation; Arthur Prior claims that the equation should be "A = 'A = false and A = true'" and therefore A is false. In computational verb logic, the liar paradox is extended to statements like, "I hear what he says; he says what I don't hear", where verb logic must be used to resolve the paradox.

Applications

Gödel's first incompleteness theorem

Gödel's incompleteness theorems are two fundamental theorems of mathematical logic which state inherent limitations of sufficiently powerful axiomatic systems for mathematics. The theorems were proven by Kurt Gödel in 1931, and are important in the philosophy of mathematics. Roughly speaking, in proving the first incompleteness theorem, Gödel used a modified version of the liar paradox, replacing "this sentence is false" with "this sentence is not provable", called the "Gödel sentence G". His proof showed that for any sufficiently powerful theory T, G is true, but not provable in T. The analysis of the truth and provability of G is a formalized version of the analysis of the truth of the liar sentence.

To prove the first incompleteness theorem, Gödel represented statements by numbers. Then the theory at hand, which is assumed to prove certain facts about numbers, also proves facts about its own statements. Questions about the provability of statements are represented as questions about the properties of numbers, which would be decidable by the theory if it were complete. In these terms, the Gödel sentence states that no natural number exists with a certain, strange property. A number with this property would encode a proof of the inconsistency of the theory. If there were such a number then the theory would be inconsistent, contrary to the consistency hypothesis. So, under the assumption that the theory is consistent, there is no such number.

It is not possible to replace "not provable" with "false" in a Gödel sentence because the predicate "Q is the Gödel number of a false formula" cannot be represented as a formula of arithmetic. This result, known as Tarski's undefinability theorem, was discovered independently by Gödel (when he was working on the proof of the incompleteness theorem) and by Alfred Tarski.

George Boolos has since sketched an alternative proof of the first incompleteness theorem that uses Berry's paradox rather than the liar paradox to construct a true but unprovable formula.

In popular culture

The liar paradox is occasionally used in fiction to shut down artificial intelligences, who are presented as being unable to process the sentence. In Star Trek: The Original Series episode "I, Mudd", the liar paradox is used by Captain Kirk and Harry Mudd to confuse and ultimately disable an android holding them captive. In the 1973 Doctor Who serial The Green Death, the Doctor temporarily stumps the insane computer BOSS by asking it "If I were to tell you that the next thing I say would be true, but the last thing I said was a lie, would you believe me?" However BOSS eventually decides the question is irrelevant and summons security.

In the 2011 videogame Portal 2, GLaDOS attempts to use the "this sentence is false" paradox to defeat the naïve artificial intelligence Wheatley, but, lacking the intelligence to realize the statement a paradox, he simply responds, "Um, true. I'll go with true. There, that was easy." and is unaffected, although the frankencubes around him do spark and go offline.

In the seventh episode of Minecraft: Story Mode titled "Access Denied" the main character Jesse and his friends are captured by a supercomputer named PAMA. After PAMA controls two of Jesse's friends, Jesse learns that PAMA stalls when processing and uses a paradox to confuse him and escape with his last friend. One of the paradoxes the player can make him say is the liar paradox.

In Douglas Adams The Hitchhiker's Guide to the Galaxy, chapter 21 he describes a solitary old man inhabiting a small asteroid in the spatial coordinates where it should have been a whole planet dedicated to Biro (ballpoint pen) life forms. This old man repeatedly claimed that nothing was true, though he was later discovered to be lying.

Rollins Band's 1994 song "Liar" alluded to the paradox when the narrator ends the song by stating "I'll lie again and again and I'll keep lying, I promise".

Robert Earl Keen's song "The Road Goes On and On" alludes to the paradox. The song is widely believed to be written as part of Keen's feud with Toby Keith, who is presumably the "liar" Keen refers to.