Monday, September 26, 2011

Introduction to predicate logic

1Something about boolean algebras¶

If $B$ is a finite boolean algebra and $A = \{a_1, \ldots, a_n\}$ is the set of atoms of $B$, then the map taking $b$ to $\{x \in A, x \subseteq b\}$ is an isomorphism of partial orders.

That is, $f$ is a bijection between $B$ to $\mathcal{P}(A) (f(\bot) = \varnothing)$ and for $b, b' \in B, b \leq b' \iff f(b) \subseteq f(b')$

2Predicate logic¶

2.1Logical symbols¶

• Connectives ($\lnot, \land, \lor, \to, \iff$ as before)
• Variables ($x,y,x', \bar{y}, z, \ldots$)
• Brackets ($(,)$)
• Quantifiers ($\exists, \forall$)
• The equality symbol ($=$)

2.2Signatures¶

A signature is a collection of non-logical symbols, each with an assigned kind and arity¹.

2.2.1Types of symbols¶

• Constant symbols ($c, d', \ldots$)
• For each $n$, an $n$-ary function symbol that stands for a function $\mathcal{M}^n \to \mathcal{M}$ where $\mathcal{M}$ is part of the underlying set. The arity is part of the signature. ^{not really sure what this is saying}
• For each $n$, an $n$-ary predicate symbol $P,Q \ldots$ (stand for subsets of $\mathcal{M}^n$

Note: We treat these non-logical symbols as prefix operators. For instance, we would write $+x3$, not $x+3$.

2.2.2An example¶

Suppose your structure is the Euclidean plane.

"$x$ is between $y$ and $z$

$Bxyz$ for some predicate symbol $B$

Note: the signature may be empty or have just one of the above kinds or two or all three!

2.2.3Terms¶

Given a signature $\Sigma$, a term is one of the following:

1. Any variable or function symbol
2. for any $n$-nary function symbol $f$ and term $t_1, \ldots t_n$ we have a term $ft_1, \ldots, f_n$

The standard signature for studying $\mathbb{N}$ has $\{0, S, +, \cdot, <\}$, where:

• $0$ is a constant
• $S$ is a unary function symbol (the successor function; informally, $Si = (i + 1)$)
• $+, \cdot$ are binary function symbols
• $<$ is a binary predicate symbol