Symbolic Logic

This chapter provides notes on first-order logic.

First-order logic (FOL) is the field of logic most people are familiar with. It's the kind of logic we'd encounter in a "Logic 101" course, and it's the logic most heavily used in mathematics. We begin first with propositional logic.

Primitives

Before we study logic formally, let's set some ground rules. Because of how low-level logic is, there's a tendency to plunge down an all too familiar sequence:

What is ${x}$ ? ${x}$ is ${y.}$

What is ${y?}$ ${y}$ is ${z.}$

What is ${z?}$ ${z}$ is ${z'.}$

${\vdots}$

While such questions are important and interesting, we need this sequence to converge as a sanity check. In logic and mathematics, we avoid infinite regression by using primitive notions — a concept that is not defined in terms of previously-defined concepts. We have to start somewhere, and if we aren't starting at the same place, well, we'll just have to go our separate ways.

Our first primitive notion is a symbol:

symbol. A symbol is a drawing or mark perceptible by sight.

For example, all of the following are symbols:

\iff~~9~~\land~~~\lor~~\in \\ P~~~Q~~~\nc~~~\infty~~\Sigma~~ \\ \neg~~\{~~+~~-~~!~~?~~0~~ \\ x~~~(~~<~~\pi~~\sqrt{}~~\uint\\ {\bf A}~~f~~\lxor~~\div~y~~~] \\

From the primitive notion of a symbol, we can construct our first definition.

alphabet. A finite set of symbols is called an alphabet, which we may arbitrarily denote as ${\Sigma}$ .

For example, the set:

\set{0,1}

is an alphabet of two symbols, ${0}$ and ${1.}$ The alphabet:

\set{0,1,2,3,4,5,6,7,8,9}

is an alphabet of 10 symbols. This particular alphabet is called the Hindu-Arabic numerals, and each element of the set is called a digit. Having defined what an alphabet is, here is our next definition:

string. A string ${\sigma}$ of length ${n}$ is an ${n}$ -tuple:

(a_i : {(i \neq n \nc i + 1) \land (1)})

where each ${a_i}$ is a member of some alphabet ${\Sigma.}$ That is, ${a_i \in \Sigma.}$ There exists a unique string where ${n=0,}$ which we call the empty string, denoted ${\lambda.}$ We say that the first symbol ${a_0}$ in ${\sigma}$ is the first letter and the last symbol ${a_n}$ is the last letter. The set of all strings on the alphabet ${\Sigma}$ is the disjoint union:

\Sigma^* = \bigsqcup\limits_{n} A^n.

When we want to explicitly refer to a string divorced of all connotations, we will use question marks. For example, to denote the string "cookie", we write:

\string{\text{cookie}}

to denote the string 2518 we write:

\string{2518}

Next, we define a method for combining strings.

concatenation. Given the strings ${a = (a_1,\ldots,a_n)}$ and ${b=(b_1,\ldots,b_m)}$ on an alphabet ${\Sigma,}$ the concatenation ${ab \in \Sigma^*}$ is defined as:

ab = a_1, \ldots, a_mb_1, \ldots, b_n

Thus, we say that ${ab}$ is a string on ${\Sigma}$ of length ${m + n.}$ We define concatenation to be associative: ${(ab)c = a(bc)}$ for all ${a,b,c \in \Sigma^*.}$ We define the empty string ${\lambda}$ to be the identity element: ${\lambda a = a = a \lambda.}$ And we define concatenation to have two-sided cancellation: If ${ab=ac,}$ then ${b=c,}$ and if ${ac = bc,}$ then ${a=b.}$

Propositional Alphabet

We begin by stating the first few symbols of our alphabet:

\set{\top~~~\bot~~~\neg~~~\lor~~~\land~~~0~~~1}

These symbols are given the following meanings.

Symbol	Meaning
${\top}$	constant 1
${\bot}$	constant 0
${\neg}$	not
${\lor}$	or
${\land}$	and

These first few symbols are called propositional connectives. Next, we have a set, denoted ${ּ\tav,}$ where each member of ${\tav}$ is a symbol for a propositional atom. For now, ${\tav}$ comprises the Hindu-Arabic numerals, and the Latin and Greek letters, lower and uppercase. For example, two common symbols we'll use from ${\tav}$ are ${p}$ and ${q.}$ Informally, we can think of these as just symbols where we'd "plug in" statements: ${1+1=2,}$ ${2 \dv 5,}$ ${3!=6,}$ etc. The symbol ${\tav}$ is the Hebrew letter tav.

Definition of a Proposition

With the basic constructions, we define a proposition as follows.

proposition. Let ${\Sigma}$ be the alphabet ${\tav \sqcup \set{\top,~\bot,~\neg,~\lor,~\land}.}$ A proposition is a string ${w}$ on ${\Sigma,}$ for which there exists a sequence ${\ix{s_1,\ldots,s_n},}$ where ${n \geq 1,}$ such that ${w = s_n.}$ For each ${k \in \set{1,\ldots,n},}$ either ${w_k \in \Sigma}$ or there are ${i,j \in \set{i,\ldots,k-1}}$ such that ${w_k}$ is a member of the set of concatenations ${\set{\neg w_i, \lor w_i w_j, \land w_i, w_j}.}$ We denote the set of propositions on ${\Sigma}$ as ${\text{Prop}(\Sigma).}$

This definition seems awfully rigid, but it can't be helped (we're defining something that underlies all of mathematics). Fortunately, outside of the definition box, we can take a breather and look at things informally. In short, the definition says, a proposition is a string consisting only of symbols from our alphabet ${\Sigma,}$ which we defined as:

\tav \sqcup \set{\top,~\bot,~\neg,~\lor,~\land}.

That is, the disjoint union of the set of propositional atoms and the set of propositional connectives. That string, however, isn't just any string. It's a string ${\rho}$ with at least one of the following properties:

${\rho}$ is an atom.
${\rho}$ is ${\top.}$
${\rho}$ is ${\bot.}$
Where ${p,q \in \text{Prop}(\Sigma),}$ ${\rho}$ is one of the propositions ${\neg p,}$ ${\lor pq,}$ or ${\land pq.}$

Note that we've defined our propositions in prefix notation — ${\land pq}$ and ${\lor pq.}$ The benefit to prefix notation is that it follows naturally from our definitions. The cost, however, is readability. As such, we adopt the following convention without apology or compromise: Given a string ${\land ab,}$ we may also write ${a \land b,}$ and given a string ${\lor ab,}$ we may also write ${a \lor b.}$