[Math] Showing propositional logic is consistent

logicpropositional-calculus

In order to receive an answer that I can understand, I would like to give all the definitions and knowledge I have about logic. I started studying it recently in order to understand physics better.

My knowledge is based on following lecture 1 "Geometric anatomy of theoretical physics", https://youtu.be/V49i_LM8B0E.

I study logic in a way that has the following philosophy: I define what logic is before the set theory and then define set theory in terms of things I learn in logic. I understand that the logic I have learned and I am using is very primitive, but I am satisfied with it and I feel this is rigorous enough because the definitions I use (which are given next) are intuitive and if this is my starting point in the foundations of mathematics, then I can not hope to make it rigorous (whatever this word means) as I have no previous axioms or definitions.

  1. Propositional logic:

    • A proposition $p$ is "something" that is either true or false.
    • Logical operator is "something" that from given propositions creates a new proposition. Examples include "and", "or", "not" and so on, which are defined using truth tables.
    • Tautology is a proposition that is always true (denote it as $\top$).
    • Contradiction is a proposition that is always false (denote it as $\bot$).
    • Two propositions $p$ and $q$ are logically equivalent if $p \iff q$ is a tautology.

  2. Axiomatic systems and theory of proofs:

    • Axiomatic system is finite amount of propositions $a_1, a_2, …, a_N$
      which are called axioms (in this definition I again assume that finite is something intuitive and it is okay if it is not properly defined, and numbers $1,2,3…$ could be replaced with some pre-mathematical numbers like slashes or flowers, or whatever).
    • Proof of proposition $p$ within axiomatic system $a_1, a_2, …, a_N$ is a finite sequence of propositions $q_1, q_2, …, q_M$ such that $q_M$ is $p$ and
      for any $1 \leq j \leq M$ one of these is true: $q_j$ is an axiom from axiomatic system; $q_j$ is a tautology; there are some previous statements with $m < j$ and $n < j$ such that $(q_m \land q_n) \Rightarrow q_j$ is a tautology.
    • If there exists a proof of proposition $p$ within axiomatic system $a_1, a_2, …, a_N$ then we say $p$ is provable within this axiomatic system.
    • Axiomatic system is inconsistent if $\bot$ is provable. Else we call axiomatic system consistent.

All these previous definitions seem okay for me and I am willing to accept them. Now the question goes like this: show that propositional logic is consistent. Then it is given that propositional logic has no axioms in its axiomatic system.

Question 1: Why propositional logic has no axioms?

My thoughts: I guess because intuitively axioms are some propositions that we would like to assume to be always true in the theory, but which should not be just logical tautologies as one could always remove them from the axiomatic system due to the definition of what the proof is. But on the other hand if I want to prove that if $P$ is true and $P \Rightarrow Q$ is true then $Q$ is true, I take my axiomatic system to consist of propositions $P$ and $P \Rightarrow Q$, don't I?

Question 2: Why propositional logic is consistent?

My thoughts: I guess I understand the intuitive proof that if axiomatic system has no axioms then I can prove only tautologies and from the third option in the definition of the proof I can make statements that use two previous statement, which in the case of both being tautologies produce new tautology. But what I would really like for someone to show me or help me to think about is how to write the proof as it is defined previously, where no words are allowed but only sequence of propositions that satisfy one of the three options in the definition.

Also any comments about the definitions (maybe I am misinterpreting some of them) would be very much appreciated.

Best Answer

Question 1: Why propositional logic has no axioms?

There are different proof systems for propositional calculus; some - called Hilbert-style - have axioms and rules; some, like e.g. Natural Deduction rules only.

When we speak of propositional logic, we usually speak of the language and the calculus: thus, we say that propositional logic is consistent because we cannot derive $\bot$ in the calculus.

Question 2: Why propositional logic is consistent?

We associate to the logic a semantics: for classical logic, the usual semantics is defined via the truth tables for the connectives.

We define the concepts of tautology and tautological consequence as well as the related properties of soundness and completeness.

Soundness implies that the calculus derives only tautologies (while completeness means that the calculus derives all the tautologies).

The key points of soundness are:

  • the propositional axioms (if any) are tautologies;

  • the inference rules (like modus ponens) must preserve truth.

Having said that, we immediately have the consistency of the claculus:

$\bot$ is not a tautology.

For an introduction, we can see: S.Simpson, Mathematical Logic (2013).

Related Question