Wednesday, September 28, 2011

Signatures and predicate logic

1Terms and signatures¶

If $S_1, ... S_k$ are symbols such that $S_1 ... S_k$ is a term, then for any $j < k$, $S_1 ... S_j$ is not a term (so cutting it off before the end kills it?).

A term that is not a constant symbol or a variable starts with some kind of function. If it starts with a variable, it is that variable. What?

For example: $Z^7 = \{ +, \cdot, 0, S, <\}$ where $Z$ is a signature composed of the terms in the set¹, which could theoretically be anything. You can draw an operator tree for each term, breaking it down into its components. The operators could be prefix, or postfix, or infix, but in this case they're prefix I think, by convention^?. Each term is uniquely readable.

In this language, terms are polynomials, possibly with multiple variables, with the natural numbers as coefficients.

1.1Predicate logic and atomic formulas¶

1. If $t_1, t_2$ are terms, $t_1 = t_2$ is an atomic formula.
2. If $p$ is an $n$-ary predicate symbol and $t_1, ... t_n$ are terms, then $P t_1 ... t_n$ is an atomic formula.

For example: $<SS0 \cdot x+yz$ (written in prefix form; would look like $SS0 < x\cdot(y+z)$ in infix form) is an atomic formula.

Any given formula might not be atomic.

Finally, if $\alpha$ is a variable and $\Phi$ is a formula, then $\exists \alpha (\Phi)$ and $\forall \alpha (\Phi)$ are formulas. For example: $\exists x ((< S0 + xy) \lor (\cdot x z = SSx)) \iff (x = \cdot Syz$. Or, in infix form: $\exists x ((S0 < x+y) \lor (x \cdot z = SSx)) \iff (x = (Sy \cdot z))$².

2Free and bound variable occurrences¶

Any occurrence of a variable in an atomic formula (so something without a $\exists$ or $\forall$) is free. An occurrence of a variable in $\neg \Phi$ or $\Phi \land \Psi$ etc is free or bound depending on the corresponding occurrences in $\Phi$ and $\Psi$, if used. So the boolean connectives don't alter free/bound status.

Basically a variable $\forall$ is bound if you, well, bind it with a $\forall \alpha$ or $\exists \alpha$. Other variables that have not been bound are free.

An example with integration:

$$\int_0^t (x^2 + t) \,dx$$

$t$ is free, $x$ is bound.

A formula with no free occurrences of variables is called a sentence, like a death sentence or prison sentence perhaps.

2.1The role of the equality symbol¶

The term $x=x$ is not a tautology. It is a logical axiom, though. Also, $x+y = y+x$ is not universally true (although it is true for the natural numbers). What this really means is $\forall x \forall y(x + y = y + x)$.

This is a sentence for the natural nmbers. If we have a signature in which $+$ is a valid operator and $=$ is a relation symbol, then we can interpret the sentence as either true or false^?. More generally, given any signature $\Sigma$, the $\Sigma$-language $L_{\Sigma}$ is the a countably ininite set of all the possible $\Sigma$ formulas.