Mathematical Logic

Definition. A '''first-order language''' $\backslash mathfrak\{L\}\backslash ,$ is a collection of distinct typographical symbols classified as follows:

# The equality symbol $=\backslash ,$; the '''connectives''' $\backslash lor\backslash ,$, $\backslash lnot\backslash ,$; the '''universal quantifier''' and the '''parentheses''' $(\backslash ,$, $)\backslash ,$.
# A countable set of variable symbols $\backslash \{v\_i\backslash \}\_\{i\; =\; 0\}^\backslash infty\backslash ,$.
# A set of constant symbols $\backslash \{c\_\backslash alpha\backslash \}\_\{\backslash alpha\; \backslash in\; \backslash Alpha\}\backslash ,$.
# A set of function symbols $\backslash \{f\_\backslash beta\backslash \}\_\{\backslash beta\; \backslash in\; \backslash Beta\}\backslash ,$.
# A set of relation symbols $\backslash \{R\_\backslash gamma\backslash \}\_\{\backslash gamma\; \backslash in\; \backslash Gamma\}\backslash ,$.

Definition. An $\backslash mathfrak\{L\}\backslash ,$-'''structure''' over the language $\backslash mathfrak\{L\}\backslash ,$, is a bundle consisting of a nonempty set $A\backslash ,$, the universe of the structure, together with:

# For each constant symbol $c\backslash ,$ from $\backslash mathfrak\{L\}\backslash ,$, an element $c^\{\backslash mathfrak\{A\}\}\; \backslash in\; A\backslash ,$.
# For each $n\backslash ,$-ary function symbol $f\backslash ,$ from $\backslash mathfrak\{L\}\backslash ,$, an $n\backslash ,$-ary function $f^\{\backslash mathfrak\{A\}\}\; :\; A^n\; \backslash longrightarrow\; A\backslash ,$.
# For each $n\backslash ,$-ary relation symbol $R\backslash ,$ from $\backslash mathfrak\{L\}\backslash ,$, an $n\backslash ,$-ary relation on $A\backslash ,$, that is, a subset $R^\{\backslash mathfrak\{A\}\}\; \backslash subseteq\; A^n\backslash ,$.

Definition. An $\backslash mathfrak\{L\}\backslash ,$-'''term''' is a nonempty finite string $t\backslash ,$ of symbols from $\backslash mathfrak\{L\}\backslash ,$ such that either

• $t\backslash ,$ is a variable symbol.


• $t\backslash ,$ is a constant symbol.


• $t\backslash ,$ is a string of the form $f\; t\_1\; ...\; t\_n\backslash ,$ where $f\backslash ,$ is an $n\backslash ,$-ary function symbol and $t\_1\backslash ,$, ..., $t\_n\backslash ,$ are terms of $\backslash mathfrak\{L\}\backslash ,$.

Definition. An $\backslash mathfrak\{L\}\backslash ,$-'''formula''' is a nonempty finite string $\backslash phi\backslash ,$ of symbols from $\backslash mathfrak\{L\}\backslash ,$ such that either

• $\backslash phi\backslash ,$ is a string of the form $t\_1\; =\; t\_2\backslash ,$ where $t\_1\backslash ,$ and $t\_2\backslash ,$ are terms of $\backslash mathfrak\{L\}\backslash ,$.


• $\backslash phi\backslash ,$ is a string of the form $R\; t\_1\; ...\; t\_n\backslash ,$ where $R\backslash ,$ is an $n\backslash ,$-ary relation symbol and $t\_1\backslash ,$, ..., $t\_n\backslash ,$ are terms of $\backslash mathfrak\{L\}\backslash ,$.


• $\backslash phi\backslash ,$ is of the form $\backslash lnot(\backslash alpha)\backslash ,$ where $\backslash alpha\backslash ,$ is an $\backslash mathfrak\{L\}\backslash ,$-formula.


• $\backslash phi\backslash ,$ is of the form $(\backslash alpha\; \backslash lor\; \backslash beta)\backslash ,$ where both $\backslash alpha\backslash ,$ and $\backslash beta\backslash ,$ are $\backslash mathfrak\{L\}\backslash ,$-formulas.


• $\backslash phi\backslash ,$ is of the form where $y\backslash ,$ is a variable symbol from $\backslash mathfrak\{L\}\backslash ,$ and $\backslash alpha\backslash ,$ is an $\backslash mathfrak\{L\}\backslash ,$-formula.

Definition. An $\backslash mathfrak\{L\}\backslash ,$-formula that is characterized by either the first or the second clause is called an '''atomic'''.

Definition. Let $\backslash phi\backslash ,$ be an $\backslash mathfrak\{L\}\backslash ,$-formula. A variable symbol $x\backslash ,$ from $\backslash mathfrak\{L\}\backslash ,$ is said to be '''free''' in $\backslash phi\backslash ,$ if either

• $\backslash phi\backslash ,$ is atomic and $x\backslash ,$ occurs in $\backslash phi\backslash ,$.


• $\backslash phi\backslash ,$ is of the form $\backslash lnot(\backslash alpha)\backslash ,$ and $x\backslash ,$ is free in $\backslash alpha\backslash ,$.


• $\backslash phi\backslash ,$ is of the form $(\backslash alpha\; \backslash lor\; \backslash beta)\backslash ,$ and $x\backslash ,$ is free in $\backslash alpha\backslash ,$ or $\backslash beta\backslash ,$.


• $\backslash phi\backslash ,$ is of the form where $x\backslash ,$ and $y\backslash ,$ are not the same variable symbols and $x\backslash ,$ is free in $\backslash alpha\backslash ,$.

Definition. A '''sentence''' is a formula with no free variables.

Definition. A '''variable assignment function''' (v.a.f.) into $\backslash mathfrak\{A\}\backslash ,$ is a function from the set of variables of $\backslash mathfrak\{L\}\backslash ,$ into $A\backslash ,$.

Definition. Let $s\backslash ,$ be a v.a.f. into $\backslash mathfrak\{A\}\backslash ,$. We define the '''term assignment function''' (t.a.f.) $\backslash overline\{s\}\backslash ,$, from the set of $\backslash mathfrak\{L\}\backslash ,$-terms into $A\backslash ,$, as follows:

• If $t\backslash ,$ is the variable symbol $x\backslash ,$, then $\backslash overline\{s\}(t)\; =\; s(x)\backslash ,$.


• If $t\backslash ,$ is the constant symbol $c\backslash ,$, then $\backslash overline\{s\}(t)\; =\; c^\{\backslash mathfrak\{A\}\}\backslash ,$.


• If $t\backslash ,$ is of the form $f\; t\_1\; ...\; t\_n\backslash ,$, then $\backslash overline\{s\}(t)\; =\; f^\{\backslash mathfrak\{A\}\}(\backslash overline\{s\}(t\_1),\; ...,\; \backslash overline\{s\}(t\_n))\backslash ,$.