# Progressing in Propositional Logic

I am self-studying precalculus-level mathematics in perhaps a more formal way than usual, which means that I am reading about logic, sets, proofs, etc.

The text I am looking at contains as an example of a statement that is not a proposition the following:

"This sentence is false."

The text provides the following reasoning:

$\quad$The statement “This sentence is false” is not a proposition because it is neither true nor false. It is an example of a paradox—a situation in which, from premises that look reasonable, one uses apparently acceptable reasoning to derive a conclusion that seems to be contradictory. If the statement “This sentence is false” is true, then by its meaning it must be false. On the other hand, if the given statement is false, then what it claims is false, so it must be true.

I need someone to please elaborate a little more on this explanation. Specifically, I am not quite sure about what it means to "assume" or "suppose" that something is the case. How is this different from asserting the truth of the statement? Second, why is it that if a statement leads to a contradiction, then the statement must not be true? Lastly, this example sometimes doesn't even appear in other texts and it doesn't seem helpful, since it has only confused me. What am I supposed to take from this example and why do some texts omit it?

For Mauro ALLEGRANZA:

Let $p$ be the statement that $p$ is false. As you said, from a "reasonable" conception of truth, we know that (0) $p\rightarrow\lnot p$ and (0') $\lnot p\rightarrow p$. We reason as follows:

(1) $p$ (assumption)
(2) $p\rightarrow\lnot p$ from (0)
(3) $\lnot p$ from (1) and (2) by modus ponens
(4) $p\land\lnot p$ from (1) and (3) by $\land$-introduction

From the assumption that $p$ is true, we derive the contradiction (4) that $p$ is both true and false. Thus, $p$ cannot be true, so it must be false.

But if $p$ is false, we have the following:

(5) $\lnot p$ (assumption)
(6) $\lnot p\rightarrow p$ from (0')
(7) $p$ from (5) and (6) by modus ponens
(8) $p\land\lnot p$ from (5) and (7) by $\land$-introduction

From the assumption $\lnot p$, we are able to derive the contradiction (8) that $p$ is both true and false. Thus, $\lnot p$ cannot be true.

Since assuming $p$ to be true leads to a contradiction and assuming $p$ to be false leads to a contradiction, $p$ cannot have a truth value, and so it is not a proposition.

However, I became confused when using the following argument.

(1') $p\rightarrow\lnot p$ from (0)
(2') $\lnot p\rightarrow p$ from (0')
(3') $p\leftrightarrow\lnot p$ from (1') and (2') by $\leftrightarrow$-introduction.

Now, since for any statement $p$, $p\leftrightarrow\lnot p$ is a contradiction, i.e, always false, (1') or (2') must be false, as [(1')$\land$(2')]$\rightarrow$(3') is a tautology, with $(3')\equiv F$. However, from our conception of truth, we know that (1') and (2') are both true for this particular statement. Yet, for any actual proposition $p$, $(p\rightarrow\lnot p)\land (\lnot p\rightarrow p)$ is a contradiction. What does this mean?

• It is an old "philosophical riddle"; see Liar Paradox. – Mauro ALLEGRANZA Apr 16 '16 at 8:28
• The Liar Paradox is linked to self reference and this phenomenon is the source of many troubles, but also of some interseting mathematical discoveries: see Paradoxes and Contemporary Logic. – Mauro ALLEGRANZA Apr 16 '16 at 8:35
• @MauroALLEGRANZA Your answer below is exactly what I needed. However, it raised a few more questions. Please see the response above. – user185744 Apr 19 '16 at 17:40
• I do not understand why this question has not been more significantly upvoted given that it has been viewed over a hundred times. To me this kind of earnest truthseeking is what the site is supposed to be for. – Ben Blum-Smith Mar 16 '17 at 14:43

Consider the sentence Liar, which says of itself (i.e., says of Liar) that it is false.

(Liar) Liar is false.

This seems to lead to contradiction as follows. If the sentence ‘Liar is false’ is true, then Liar is false [because, according to a "reasonable" conception of truth, a sentence S is true iff S corresponds to some fact; S is false iff S does not correspond to any fact]. But if Liar is false, then the sentence ‘Liar is false’ is true [for the same reason].

Since Liar just is the sentence ‘Liar is false’, we have it that Liar is false if and only if Liar is true. But, now, if every sentence is true or false, Liar itself is either true or false, in which case — given our reasoning above — it is both true and false. This is a contradiction.

Contradictions, according to many logical theories (e.g., classical logic, intuitionistic logic, and much more) imply absurdity, that is, that every sentence is true.

Formally, if we assume (i.e. if we consider as the starting point of our argument) that:

1) $p \leftrightarrow \lnot p$

and we consider the law of Excluded middle:

2) $p \lor \lnot p$

we can formalize the following proof (using Natural Deduction):

3) $p$ --- assumed [a]

4) $p \to \lnot p$ --- from 1) by $\leftrightarrow$-elim

5) $\lnot p$ --- from 3) and 4) by $\to$-elim (modus ponens)

6) $p \land \lnot p$ --- from 3) and 5) by $\land$-intro

7) $\lnot p$ --- assumed [b]

8) $\lnot p \to p$ --- from 1) by $\leftrightarrow$-elim

9) $p$ --- from 7) and 8) by $\to$-elim (modus ponens)

10) $p \land \lnot p$ --- from 7) and 9) by $\land$-intro

11) $p \land \lnot p$ ---- from 2), 3)-6), 7)-10) by $\lor$-elim, discharging temporary assumptions [a] and [b].

Conclusion, from the assumption: "Liar is false if and only if Liar is true" we have derived the contradiction "Liar is both true and false".

A proposition is a sentence of which we can always determine its truth-value: true or false. Examples: "the book on my desk is red" or "$2<4$".

Propositional logic is base on a ultra-simplified model of language.. In it, the propositional variables: $p,q,\ldots$ must be replaced by propositions and thus propositions must be "linguistic entities" that can be true or false without expections nor ambiguities, because the semantics of (classical) propositional logic is based on the two truth-values: T and F.

There are some possible solutions to the paradox: truth-value gaps.

Natural language is quite complex and thus it cannot be described with a simplified model like that of propositional logic: we have to take into account indicative sentences which lacks truth-value.

• What is [a] and [b] referring to in the argument? Also, if we can derive a contradiction $B$ (which in my mind is roughly another statement that "goes against" an assumption, a previously proved theorem, or an axiom) from some statement $A$, then the statement $A$ must be false. Why? My best answer to this is that we have shown that $A\implies B$. In the case that $B$ "goes against" (contradicts?) a previously proved theorem or an axiom, we know that $B$ is false. Hence, $A$ is also false. In the case that $B$ goes against the assumption $A$, how then do we know that $B$ must be false? – user185744 Apr 17 '16 at 18:10
• @K.Hotz - [a] and [b] are pointers to the formulae in 3) and 7): they are the temporary assumptions used for $\lor$-elimunation (i.e. poof by cases). – Mauro ALLEGRANZA Apr 17 '16 at 18:26
• Yes; $p \leftrightarrow \lnot p$ is a contradiction (not only false, but always false - verify it with a truth-table). The Liar argument is: "if Liar is true, then Liar is false" and "if Liar is false, then Liar is true". Thus: "Liar is true iff Liar is false" - Contradiction ! – Mauro ALLEGRANZA Apr 17 '16 at 18:30
• Allow me to summarize your answer in order to move on. Within propositional logic, statements have exactly one truth value -- true or false. A statement is true iff it corresponds to some fact, and false iff it does not correspond to any fact. From this conception of truth, we see that the statement (Liar) is true iff it is false. Since every statement has a truth value, (Liar) itself must be either true or false, but in both cases we arrive at a contradiction. Hence, (Liar) is neither true nor false, and is not a proposition. Correct? Ok for a beginner to feel comfortable with and proceed? – user185744 Apr 22 '16 at 4:49
• @K.Hotz - the rule: $p∨q , ¬p ∴ q$ is disjunctive syllogism; it can be derived from $\lor$-elim. – Mauro ALLEGRANZA Apr 25 '16 at 10:13