A first order language $$ \mathcal{L}$$ is an infinite collection of distinct symbols, no one of which is contained in another, separated into the following categories

• Parenthesis: $$ (,)$$
• Connectives: $$ \vee <!--\; \vee \; -->,\mathrm{\neg <!--\; \neg \; -->}$$
• Quantifier: $$ \mathrm{\forall <!--\; \forall \; -->}$$
• Variables, one for each $$ i\in <!--\; \in \; -->{\mathbb{N}}_1$$: $$ v_i$$
• Equality symbol: =
• Constant symbols: A set of symbols
• Function symbols, for each $$ n\in <!--\; \in \; -->{\mathbb{N}}_1$$: A set of $$ n$$-ary function symbols
• Relation symbols, for each $$ n\in <!--\; \in \; -->{\mathbb{N}}_1$$: A set of $$ n$$-ary relation symbols

Since the only thing differing from language to language are its constants, variables, functions and relations then we can denote the language $$ \mathcal{L}$$ by $$ (C_{\mathcal{L}},F_{\mathcal{L}},R_{\mathcal{L}})$$, we can denote the set of variables by $$ V_{\mathcal{L}}$$

If $$ \mathcal{L}$$ is a language, a term of $$ \mathcal{L}$$ is a nonempty finite string $$ t$$ of symbols from $$ \mathcal{L}$$ such that

• $$ t$$ is a variable
• $$ t$$ is a constant
• $$ t\equiv <!--\; \equiv \; -->f{t}_1{t}_2\dots <!--\; \dots \; -->t_n$$ is a constant where $$ f$$ is an $$ n$$-ary function symbol if $$ \mathcal{L}$$ and each $$ t_i$$ is a term of $$ \mathcal{L}$$

If $$ \mathcal{L}$$ is a first order language, then a formula of $$ \mathcal{L}$$ is a non-empty finite string $$ \mathrm{\varphi <!--\; \varphi \; -->}$$ of symbols from $$ \mathcal{L}$$ such that:

1. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->=t_1{t}_2$$ where $$ t_1,t_2$$ are terms of $$ \mathcal{L}$$
2. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->R{t}_1{t}_2\dots <!--\; \dots \; -->t_n$$ where $$ R$$ is an $$ n$$-ary relation symbol of $$ \mathcal{L}$$ and $$ t_1,t_2$$ are terms of $$ \mathcal{L}$$
3. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->\left(\mathrm{\neg <!--\; \neg \; -->}\mathrm{\alpha <!--\; \alpha \; -->}\right)$$ where $$ \mathrm{\alpha <!--\; \alpha \; -->}$$ is a formula of $$ \mathcal{L}$$
4. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->(\mathrm{\alpha <!--\; \alpha \; -->}\vee <!--\; \vee \; -->\mathrm{\beta <!--\; \beta \; -->})$$ where $$ \mathrm{\alpha <!--\; \alpha \; -->},\mathrm{\beta <!--\; \beta \; -->}$$ are formulas of $$ \mathcal{L}$$
5. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->\left(\mathrm{\forall <!--\; \forall \; -->}v\right)\left(\mathrm{\alpha <!--\; \alpha \; -->}\right)$$ where $$ v$$ is a variable and $$ \mathrm{\alpha <!--\; \alpha \; -->}$$ is a formula of $$ \mathcal{L}$$

The atomic formulas of $$ \mathcal{L}$$ are formulas that satisfy clause 1 or 2 of their definition

We define the language $$ {\mathcal{L}}_{NT}=(\left\{\mathtt{0}\right\},\{\mathtt{S},\mathtt{+},\cdot <!--\; \cdot \; -->,\mathtt{E}\},\left\{<<!--\; <\; -->\right\})$$ as the language of number theory.

Fix a language $$ \mathcal{L}$$. An $$ \mathcal{L}$$-structure $$ \mathfrak{A}$$ is a non-empty set $$ A$$, called the universe of $$ \mathfrak{A}$$, such that the following holds:

• For each constant symbol $$ c$$ of $$ \mathcal{L}$$, we have an element $$ c^{\mathfrak{A}}$$ of $$ A$$
• For each $$ n$$-ary function symbol $$ f$$ of $$ \mathcal{L}$$, we have a function $$ f^{\mathfrak{A}}:A^n\to <!--\; \to \; -->A$$
• For each $$ n$$-ary relation symbol $$ R$$ of $$ \mathcal{L}$$, we have an $$ n$$-ary relation $$ R^{\mathfrak{A}}$$ on $$ A$$

Similar to a language we may denote it by $$ (A,\{c^{\mathfrak{A}}:c\in <!--\; \in \; -->C_{\mathcal{L}}\},\left\{f^{\mathfrak{A}}:f\in <!--\; \in \; -->F_{\mathcal{L}}\right\},\{R^{\mathfrak{A}}:R\in <!--\; \in \; -->R_{\mathcal{L}}\})$$

Given $$ {\mathcal{L}}_{NT}$$, we define the structure $$ \mathfrak{N}:=({\mathbb{N}}_0,\left\{0\right\},\{S,+,\cdot <!--\; \cdot \; -->,E\},\{<<!--\; <\; -->\})$$, where the constant symbol $$ \mathtt{0}$$ maps to $$ 0$$ (the element of $$ {\mathbb{N}}_0$$), $$ S$$ is the successor function $$ S\left(2\right)=3$$, $$ +$$ is usual addition $$ 3+3=6$$, $$ \cdot <!--\; \cdot \; -->$$ multiplication $$ 2\cdot <!--\; \cdot \; -->4=8$$, $$ E$$ for exponentiation $$ E(3,2)=9$$

If $$ \mathfrak{A}$$ is an $$ \mathcal{L}$$-structure, a variable assignment function is any function of the form $$ s:V_{\mathcal{L}}\to <!--\; \to \; -->A$$

If $$ s$$ is a variable assigment function into $$ \mathfrak{A}$$ and $$ x\in <!--\; \in \; -->V_{\mathcal{L}}$$ and $$ a\in <!--\; \in \; -->A$$, then $$ s[x\mid <!--\; \mid \; -->a]$$ is the variable assigment function defined as follows and we say that $$ s[x\mid <!--\; \mid \; -->a]$$ is an $$ x$$-modification of the assigment function $$ s$$

Suppose that $$ \mathfrak{A}$$ is an $$ L$$-structure and $$ s$$ is a variable assigment function into $$ \mathfrak{A}$$. The function $$ \stackrel{¯<!--\; ¯\; -->}{s}$$, called the term assigment function generated by $$ s$$, is the function with domain consisting of the set of $$ \mathcal{L}$$ terms and codomain $$ A$$ defined as follows

• if $$ t$$ is a variable then $$ \stackrel{¯<!--\; ¯\; -->}{s}\left(t\right)=s\left(t\right)$$
• if $$ t$$ is the constant $$ c$$ then $$ \stackrel{¯<!--\; ¯\; -->}{s}\left(t\right)=c^{\mathfrak{A}}$$
• if $$ t:\equiv <!--\; \equiv \; -->f{t}_1{t}_2\dots <!--\; \dots \; -->t_n$$ then $$ \stackrel{¯<!--\; ¯\; -->}{s}\left(t\right)=f^{\mathfrak{A}}(\stackrel{¯<!--\; ¯\; -->}{s}\left(t_1\right),\stackrel{¯<!--\; ¯\; -->}{s}\left(t_2\right),\dots <!--\; \dots \; -->,\stackrel{¯<!--\; ¯\; -->}{s}\left(t_n\right))$$

Given an $$ \mathcal{L}$$-structure $$ \mathfrak{A}$$, and a term $$ t$$ from $$ \mathcal{L}$$, we say that it's interpretation in $$ \mathfrak{A}$$ is $$ \stackrel{¯<!--\; ¯\; -->}{s}\left(t\right)$$

Suppose that $$ v$$ is a varaible and $$ \mathrm{\varphi <!--\; \varphi \; -->}$$ is a formula, then $$ v$$ is free in $$ \mathrm{\varphi <!--\; \varphi \; -->}$$ iff exactly one of the following holds:

1. $$ \mathrm{\varphi <!--\; \varphi \; -->}$$ is atomic and $$ v$$ occurs in $$ \mathrm{\alpha <!--\; \alpha \; -->}$$
2. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->\left(\mathrm{\neg <!--\; \neg \; -->}\mathrm{\alpha <!--\; \alpha \; -->}\right)$$ and $$ v$$ is free in $$ \mathrm{\alpha <!--\; \alpha \; -->}$$
3. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->(\mathrm{\alpha <!--\; \alpha \; -->}\vee <!--\; \vee \; -->\mathrm{\beta <!--\; \beta \; -->})$$ and $$ v$$ is free in at least one of $$ \mathrm{\alpha <!--\; \alpha \; -->}$$ or $$ \mathrm{\beta <!--\; \beta \; -->}$$
4. $$ \mathrm{\varphi <!--\; \varphi \; -->}:\equiv <!--\; \equiv \; -->\left(\mathrm{\forall <!--\; \forall \; -->}u\right)\left(\mathrm{\alpha <!--\; \alpha \; -->}\right)$$ and $$ v$$ is not $$ u$$ and $$ v$$ is free in $$ \mathrm{\alpha <!--\; \alpha \; -->}$$