Hierarchy of logical systems

This post is a generalization to one of my previous posts, Abstractions with Set Theory.

At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems.

These systems, though they differ in many details, share the common property of considering only expressions in a fixed formal language.

Here’s the hierarchy of these logical systems:

  1. Propositional logic
    This branch of logic is concerned with the study of propositions (whether they are True or False) that are formed by other propositions with the use of logical connectives.

    The most basic logical connectives are AND \land, OR \lor, and NOT \lnot.

    The connectives are commutative. Here are their values (T stands for True, F for false):
    T \land T = T, everything else is F.
    F \lor F = F, everything else is T.
    \lnot F = T, \lnot T = F.

    We can also use variables to represent statements.

    For example, we can say “a = Salad is organic”, and thus a is a True statement.
    Another example is “a = Rock is organic”, and thus a is a False statement.
    “a = Hi there!” is neither a True nor a False statement.

    Propositional logic defines an argument to be a list of propositions. For example, given the two propositions A \lor B, \lnot B we can conclude A.

    An argument is valid iff for every row where the propositions are True, the conclusion is also True.

    An easy way to check the validity of this argument is to use the definitions above and draw a table with all possible values of A and B.

    A	B	A OR B	NOT B
    F	F	F		T
    F	T	T		F
    T	F	T		T
    T	T	T		F
    

    In this case, the row where all of the propositions are true is 3. We see that the conclusion A is also True, so the argument is valid and will hold for any value we put in place of A or B.

    Besides using tables to check for values, we can also construct proofs given a natural deduction system.

    We can use the system’s rules to either prove or disprove a statement.

  2. First-order logic
    This logical system extends propositional logic by additionally covering predicates and quantifiers.

    A predicate P(x) takes as an input x, and produces either True or False. For example, having “P(x) = x is a organic”, then P(Salad) is True, but P(Rock) is False.

    Note that in set theory, P would be a subset of a relation, i.e. P \subseteq A \times \{ True, False \}. When working with other systems we need to be careful, as this is not the case with FOL. In the case of FOL, we have P(Salad) = True, P(Rock) = False, etc as atomic statements (i.e. they cannot be broken down into smaller statements).

    There are two quantifiers introduced: forall (universal quantifier) \forall and exists (existential quantifier) \exists.

    In the following example the universal quantifier says that the predicate will hold for all possible choices of x: \forall x P(x)
    In the following example the existential quantifier says that the predicate will hold for at least one choice of x: \exists x P(x)

  3. Second-order logic, …, Higher-order (nth-order) logic
    First-order logic quantifies only variables that range over individuals; second-order logic, in addition, also quantifies over sets; third-order logic also quantifies over sets of sets, and so on.

For example, Peano’s axioms (the system that defines natural numbers) are a mathematical concept expressed using a combination of first-order and second-order logic.

This concept consists of a set of axioms for the natural numbers, and all of them (except the ninth, induction axiom) are statements in first-order logic.

The base axioms can be augmented with arithmetical operations of addition, multiplication and the order relation, which can also be defined using first-order axioms.

The axiom of induction is in second-order, since it quantifies over predicates.

In my next post we’ll have a look at intuitionistic logic, a special logical system based on type theory.

Advertisements

3 thoughts on “Hierarchy of logical systems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s