Propositional Logic

Some Definitions

Propositional logic is a simplified model of what it means to prove things. The statements that propositional logic can work with are called propositions. Propositions consist of the primitives $\perp ,p_1,p_2,p_3,\cdots$ as well as anything of the form $(X⟹Y)$ where $X$ and $Y$ are propositions. Note for pedants, this description allows the existence of propositions that can't be broken down into a finite number of primitives, we don't want such propositions.

Let $A$ be the set of all propositions formed by taking any arbitrary propositions $X$, $Y$ and $Z$, in any of the following three arrangements.

1) $(X⟹(Y⟹X))$

2) $((X⟹(Y⟹Z))⟹((X⟹Y)⟹(X⟹Z)))$

3) $(\left(\right(X⟹\perp )⟹\perp )⟹X)$

The set $A$ is the set of axioms, and the three forms shown above are the infinite axiom schema. For example, taking $X=p_1$ and $Y=(p_2⟹\perp )$ then applying the first schema gets $(p_1⟹((p_2⟹\perp )⟹p_1))\in A$. So this is an axiom.

We say that a set of propositions $S$ implies another proposition $p$, when there exists a proof of $p$ from $S$. Write this as $S⊢p$.

A proof of a proposition $p$ form $S$ is a list $L$ of propositions of length $n\in N$ such that $L_n=p$ and for each $i\le n$, $L_i$ fulfills at least one of the following 3 conditions.

1) $L_i\in S$

2) $L_i\in A$

3) $\exists j,k<i:L_j=(L_k⟹L_i)$ This is called Modus ponens

Example Proof

For example, here is a proof of $(p⟹p)$

Formed using the second axiom schema.

Is then created using the first axiom schema

Can be produced by modus ponens because $L_1=(L_2⟹L_3)$.

Is allowed by using axiom schema 1 again.

Follows by modus ponens again because $L_3=(L_4⟹L_5)$.

Philosophically Important Takeaways

The notion of mathematical proof is fully formalized. There is an entirely mechanical, and fairly fast, method of verifying proofs. Proofs can be generated in a finite amount of time, by brute force search, but this can be much slower.

The proof framework only believes things that you have actually proved in it. From our point of view outside the framework, the proof of $(p⟹p)$ also shows that $(q⟹q)$, but to actually prove that within the framework, you have to go through all the steps again.