Mathematical Physics

Table of Contents

Logic and the Theory of Proof

Logic

Propositional Logic (0th order logic)

Proposition
A proposition \(p\) is a variable that can take the values \(\mathrm{true}\) or \(\mathrm{false}\). No others.

Propositional logic does not concern itself with deciding whether a given proposition is true or false. It deals with propositions as atomic notions and manipulations of them.

We can build new propositions from given ones via logical operators.

Logical Operators

  • Unary Operators

    Each unary operator creates a new proposition from a given one.

    \(p\) \(\neg p\) \(\mathrm{\small ID} \ p\) \(\top p\) \(\bot p\)
    T F T T F
    F T F T F
  • Binary Operators

    Each binary operator creates a new proposition from two given ones.

    \(p\) \(q\) \(p \land q\) \(p \lor q\) \(p \oplus q\) \(p \Rightarrow q\) \(p \Leftrightarrow q\)
    T T T T F T T
    T F F T T F F
    F T F T T T F
    F F F F F T T

    Pay special attention to the behaviour of the proposition \((p \Rightarrow q)\):

    Ex falso quodlibet.

    Binding strength (decreasing):

    \[\neg, \land, \lor, \Rightarrow, \Leftrightarrow \]

    Theorem

    \[ (p \Rightarrow q) \Leftrightarrow \big( (\neg q) \Rightarrow (\neg p) \big) \]

    Proof
    \(p\) \(q\) \(\neg p\) \(\neg q\) \(p \Rightarrow q\) \(\neg q \Rightarrow \neg p\)
    T T F F T T
    T F F T F F
    F T T F T T
    F F T T T T
    Corollary
    We can use proof by contradiction. i.e. we can either prove that p implies q, or that not q implies not p. The two are equivalent.
  • Higher order operators

    Any higher order operation can be constructed from one binary operation \(\uparrow\) (NAND).

    \(p\) \(q\) \(p \uparrow q\)
    T T F
    T F T
    F T T
    F F T

Predicate Logic (1st order logic)

Predicate
A predicate is a proposition-valued function of some variable(s).

e.g. \(p(x)\) is \(\mathrm{true}\) or \(\mathrm{false}\) dependent on the value of x.

Predicate logic is not concerned with building predicates. Just like propositional logic deals with propositions as the given, atomic subject matter, predicate logic deals with predicates atomically.

We can construct new predicates from given ones.

  • Predicates can be composed of other predicates: \[Q(x, y, z) :\Leftrightarrow P(x) \land R(y, z)\]
  • We can also convert a predicate of one variable into a proposition:

\[\forall x: P(x)\]

Which should be read "For all \(x\), \(P(x)\) is true".

For example \[P(x) : \Leftrightarrow \mathrm{``x \ is \ a \ human \ being"} \Rightarrow \mathrm{``x \ exists"}\]

then

\[\forall x: P(x) \Leftrightarrow \mathrm{true}.\]

This is an example of using a quantifier with a predicate, forming a new proposition.

Existence quantification

\[\exists x : P(x) \Leftrightarrow \neg \big( \forall x: \neg P(x) \big)\]

Corollary

\[\forall x: \neg P(x) \Leftrightarrow \neg \big( \exists x: P(x) \big)\]

  • Remark 1

Quantification can be performed for predicates of more than one variable

\[Q(y) \Leftrightarrow \forall x : P(x, y)\]

Here \(y\) is a free variable and \(x\) is a bound variable.

  • Remark 2

The order of quantification matters:

\[\forall x: \exists y : P(x, y) \nLeftrightarrow \forall y \exists x: P(x, y)\]

For example, the definition of the identity element of some group.

Axiomatic Systems and the Theory of Proofs

Axiomatic System
An axiomatic system is a finite sequence of propositions or propositional schemes \(a_1, a_2, ..., a_N\), which are called the axioms
Proof
A proof of a proposition \(p\) within an axiomatic system \(a_1, a_2, ..., a_N\) is a finite sequence of propositions \(q_1, q_2, ..., q_M\) such that \(q_M \Leftrightarrow p\), subject to the following constraints on any \(q\):

For any \(1 \leq j \leq M\) either

(A) \(q_j\) is a proposition from the list of axioms.

(T) \(q_j\) is a plain tautology (a proposition which is always true independent of any propositions it is composed of, such as \(p \lor \neg p\)).

(M) "Modus ponens"

\[ \big( \exists 1 \leq a, b, \leq j : q_a \land q_b \Rightarrow q_j \big) \Leftrightarrow \mathrm{true}. \]

  • If \(p\) can be proven from \(a_1, ..., a_N\) then we often write \(a_1, ..., a_N \vdash p\).
  • This definition allows us to easily recognise some given statements as a proof, however an altogether different matter is finding a proof in the first place. The theory of proofs does not give you hints on how to find a proof.
  • Any tautology in the axioms can be removed without impairing the utility of the axiomatic system (by axiom T)

Taking an extreme example, the axiomatic system for propositional logic is the empty sequence. Therefore, all we can prove are tautologies.

Consistency
An axiomatic system is called consistent if there is a proposition \(q\) which cannot be proved within the axiomatic system:

\[ \neg \big( a_1, a_2, ..., a_N \vdash q \big) \]

To get a feel for this idea, consider an axiomatic system containing contradicting propositions

\[ ..., s, ..., \neg s, ... \]

Then by deduction rule M, clearly

\[s \land \neg s \Rightarrow q\] "Ex falso quodlibet."

So, a sign of consistency is the existence of a statement which cannot be proven within the system.

Theorem
Propositional logic is consistent
Proof
It suffices to show that there is a proposition which cannot be proven within propositional logic. Propositional logic contains the empty sequence as its list of axioms, so we can only use axiom T or M, and therefore can only prove tautologies. Therefore we cannot prove \(p \land \neg p\). Therefore propositional logic is consistent.
Theorem (Gödel)
Any axiomatic system which is powerful enough to encode the elementary arithmetic of natural numbers is either inconsistent or contains a proposition that can neither be proven nor disproven within the system.

Axiomatic Set Theory (Zermelo-Fraenkel Axioms)

The ∈-relation

Set theory is built on the postulate that there is a fundamental relation (shorthand for a predicate of two variables) called ∈.

A definition of ∈ is not given, apart from the fact that it is a predicate. In addition, the definition of a set is not given either.

Instead, we have 9 axioms which describe the interplay of ∈ and sets. This interplay is the description of set theory that will be given, in order for it not to rely on any prior notions.

Using the ∈ relation, we can immediately define

\[\in(x, y) \equiv x \in y\] \[\notin(x, y) \equiv x \notin y \equiv \neg (x \in y)\]

\[x \subseteq y \Leftrightarrow \forall a: \left( a \in x \Rightarrow a \in y \right)\]

Importantly,

\[x = y \Leftrightarrow x \subseteq y \land y \subseteq x\]

Axiom on ∈-relation

\(x \in y\) is a proposition if and only if \(x\) and \(y\) are sets.

\[\forall x: \forall y: \left( (x \in y) \oplus \neg (x \in y) \right)\]

Counterexample (Russell's Paradox)

Assume there is some \(s\) that contains all sets that do not contain themselves as an element:

\[\exists s : \forall x : \left( x \in s \Leftrightarrow x \notin x \right)\]

Is this object a set?

If \(s\) is a set, we must be able to decide if \(s \in s\) is true or false (it must be a proposition).

However,

\[s \in s \Rightarrow s \notin s\] \[s \notin s \Rightarrow s \in s\] \[\unicode{x21af}\unicode{x21af}\unicode{x21af}\]

Therefore, \(s\) is not a set.

Axiom on the Existence of an Empty Set

There exists a set which contains no elements.

\[\exists x : \forall y : (y \notin x)\]

Uniqueness

Theorem
there is only one empty set
Proof (textbook style)

Assume \(x\) and \(x'\) are both empty sets. But then

\[\forall y : (y \in x) \Rightarrow (y \in x') \Leftrightarrow x \subseteq x'\]

Similarly,

\[\forall y : (y \in x') \Rightarrow (y \in x) \Leftrightarrow x' \subseteq x\]

Therefore \(x = x' \ \ \blacksquare\)

Proof (formal)
\begin{align} &a_1 \Leftrightarrow \forall y : (y \notin x) \\ &a_2 \Leftrightarrow \forall y : (y \notin x') \\ &q_1 \overset{\small{T}}{\Leftrightarrow} \forall y : (y \notin x) \Rightarrow \forall y : \left( (y \in x) \Rightarrow (y \in x') \right) \\ &q_2 \overset{\small{A}}{\Leftrightarrow} \forall y : (y \notin x) \\ &\big( q_1 \land q_2 \Rightarrow \forall y : \left( (y \in x) \Rightarrow (y \in x') \right) \big) \Leftrightarrow \mathrm{true} \\ &q_3 \overset{\small{M}}{\Leftrightarrow} \forall y : \left( (y \in x) \Rightarrow (y \in x') \right) \Leftrightarrow x \subseteq x' \\ &q_4 \overset{\small{T}}{\Leftrightarrow} \forall y : (y \notin x') \Rightarrow \forall y : \left( (y \in x') \Rightarrow (y \in x) \right) \\ &q_5 \overset{\small{A}}{\Leftrightarrow} \forall y : (y \notin x') \\ &\big( q_4 \land q_5 \Rightarrow \forall y : \left( (y \in x') \Rightarrow (y \in x) \right) \big) \Leftrightarrow \mathrm{true} \\ &q_6 \overset{\small{M}}{\Leftrightarrow} \forall y : \left( (y \in x') \Rightarrow (y \in x) \right) \Leftrightarrow x' \subseteq x \\ &\big( x' \subseteq x \land x \subseteq x' \Rightarrow x' = x \big) \Leftrightarrow \mathrm{true} \\ &q_7 \overset{\small{M}}{\Leftrightarrow} x' = x \ \ \blacksquare\\ \end{align}

Axiom on Pair Sets

Let \(x\) and \(y\) be sets. Then there exists a set which contains as its elements precisely the sets \(x\) and \(y\)

\[\forall x, y \exists m : \forall u \left( u \in m \Leftrightarrow u = y \lor u = x \right) \]

Notation

Denote the set \(m\) by \(\{x, y\}\).

Remember: ordering (as implied by the notation) means nothing. The element relation is just the element relation.

Remark

We create the one element set by pairing the set with itself \(\{x\} := \{x, x\}\).

a symbol such as \(\{x, y, z\}\) is as of yet not defined.

Axiom on Union Sets

Let \(x\) be a set. Then there exists a set whose elements are precisely the elements of the elements of x.

\[\forall x \exists m : \forall u ( u \in m \Leftrightarrow \exists A : u \in A \land A \in x)\]

Notation

\[m = \bigcup x\]

Example 1

Let \(x\) and \(y\) be sets. There exist sets \(\{x\}\) and \(\{y\}\) (by the pair set axiom). Therefore there exists a set \(m = \{\{x\}, \{y\}\}\).

\[\bigcup m = \{x, y\}\]

Example 2

Let \(x = \{\{a\}, \{b, c\}\}\) By the Axiom on Union Sets, there exists a set \(u = \cup x\). We define

\[\{a, b, c\} := \bigcup x\]

From this example, it is easy to see that we can go on to define recursively, for all \(n > 2\)

\[\{a_1, a_2, ..., a_n\} := \bigcup \{\{a_1, a_2, ..., a_{n - 1}\}, \{a_n\}\}.\]

Axiom of Replacement

Let \(R\) be a functional relation, and let \(m\) be a set. Then the image of \(m\) under \(R\) is again a set.

Definition

A relation (think: predicate) \(R\) is called functional if

\[\forall x \exists!y : R(x, y)\]

  • The image of a set \(m\) under a functional relation \(R\) consists of all those \(y\) for which there is an \(x \in m\) such that \(R(x, y)\)
  • The Axiom of Replacement implies, but is not implied by, the principle of restricted comprehension.

Let \(P\) be a predicate of one variable, and let \(m\) be a set. Then those elements \(y \in m\) for which \(P(y)\) holds constitute a set.

Notation
This set is usually denoted

\[\{y \in m | P(y)\}\]

PRC is not to be confused with the INCONSISTENT NOTION of the PUC:

\[\{y | P(Y)\}\]

BAD. Leads to problems such as Russell's paradox.

Author: Laurence Sebastian Bowes

Created: 2018-10-05 Fri 00:19