A calculus of the absurd

Chapter 21 Lower-level logic

One of the wonderful things about logic is that one can study it at many different levels. In the previous section, a “working subset” of logic which is kind of necessary (and remarkably, also sufficient) for all other mathematics was described. In this section, I write down many amazing things I have discovered on the internet, which allow us to develop logics (yes, logics in the plural) for various purposes.

At this point we are no longer entirely in the realm of mathematics proper - it really sits on the boundary between philosophy and mathematics. There are a few fundamental questions we are interested in the answer to,

  • • what does it mean for something to be true?

  • • when is something true?

  • • how can we prove that something is true?

  • • can we mechanise our intuitions about whether or not something is true (this is essentially equivalent to the question “can we codify mathematics on a computer”, but not completely)

21.1 Proof systems

In Chapter 6 a lot of methods for proving things were given, but it was kind of given that these work, and are valid methods of proof. This begs the question (well if it doesn’t, them I’m begging it now) - “can we prove our proof techniques”?

First we can try to develop a system for telling us if something is true. There are multiple ways in which we can try to do this, but one specific idea is that we can define a “proof system”, which is a mathematical construct that allows us to reason about proofs.

  • Definition 21.1.1 A proof system \(\Pi \) is a four-tuple

    \begin{equation} \Pi = (\tau , \phi , \mathcal {P}, S). \end{equation}

    Here \(\tau \), \(\phi \), \(\mathcal {P}\) and \(S\) have specific meanings

    • • The set \(S\) of all possible statements in our proof system.

    • • The set \(\mathcal {P}\) is the set of all possible proofs in our proof system.

    • • The function \(\tau : S \to \{0, 1\}\) defines whether a given statement is true or not (as eone might guess, if \(\tau (x) = 1\), then the statement \(x\) is true, and otherwise it is false.

    • • The function \(\phi : S \times \mathcal {P} \to \{0, 1\}\) is called a verification function and takes a proof \(\mathcal {P}\) for a statement \(S\) and returns \(1\) if this is a valid proof of \(S\), and false if it is not.

There are two key attributes of proof systems that we are primarily interested in; these are soundness and completeness.

  • Definition 21.1.2 A proof system \(\Pi \) is sound if and only if for every \(s \in S, p \in \mathcal {P}\) such that

    \begin{equation} \phi (s, p) = 1, \end{equation}

    the statement \(s\) is true, i.e.

    \begin{equation} \tau (s) = 1. \end{equation}

In natural language, I would read this as “a proof system is sound if and only if every statement for which there is a valid proof is true”. This is the property that we most interested in; as the name suggests unsound proof systems are not particularly useful!

  • Definition 21.1.3 A proof system is complete if there is a proof for every true statement; that is for every \(s \in S\) such that

    \begin{equation} \tau (s) = 1, \end{equation}

    there exists some \(p \in \mathcal {P}\) which is a proof of \(s\) - that is, for this \(p\)

    \begin{equation} \phi (s, p) = 1. \end{equation}

This is less useful than soundness, but it is still an interesting property to think about.