first order language
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 , \neg$$
• Quantifier: $$\forall$$
• Variables, one for each $$i \in \mathbb{N}_{1}$$: $$v_{i}$$
• Equality symbol: =
• Constant symbols: A set of symbols
• Function symbols, for each $$n \in \mathbb{N}_{1}$$: A set of $$n$$-ary function symbols
• Relation symbols, for each $$n \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 $$\left ( C_{\mathcal{L}} , F_{\mathcal{L}} , R_{\mathcal{L}} \right )$$, we can denote the set of variables by $$V_{\mathcal{L}}$$

term
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 f{t}_{1} t_{2} \ldots 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}$$
formula
If $$\mathcal{L}$$ is a first order language, then a formula of $$\mathcal{L}$$ is a non-empty finite string $$\phi$$ of symbols from $$\mathcal{L}$$ such that:
1. $$\phi : \equiv = t_{1} t_{2}$$ where $$t_{1} , t_{2}$$ are terms of $$\mathcal{L}$$
2. $$\phi : \equiv R t_{1} t_{2} \ldots t_{n}$$ where $$R$$ is an $$n$$-ary relation symbol of $$\mathcal{L}$$ and $$t_{1} , t_{2}$$ are terms of $$\mathcal{L}$$
3. $$\phi : \equiv \left ( \neg \alpha \right )$$ where $$\alpha$$ is a formula of $$\mathcal{L}$$
4. $$\phi : \equiv \left ( \alpha \vee \beta \right )$$ where $$\alpha , \beta$$ are formulas of $$\mathcal{L}$$
5. $$\phi : \equiv \left ( \forall v \right ) \left ( \alpha \right )$$ where $$v$$ is a variable and $$\alpha$$ is a formula of $$\mathcal{L}$$
Atomic Formula
The atomic formulas of $$\mathcal{ L }$$ are formulas that satisfy clause 1 or 2 of their definition
language of number theory
We define the language $$\mathcal{L}_{N T} = \left ( \left \lbrace \mathtt{0} \right \rbrace , \left \lbrace \mathtt{S} , \mathtt{+} , \mathtt{\cdot} , \mathtt{E} \right \rbrace , \left \lbrace \mathtt{\lt} \right \rbrace \right )$$ as the language of number theory.
$$\mathcal{L}$$-Structure
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 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 $$\left ( A , \left \lbrace c^{\mathfrak{A}} : c \in C_{\mathcal{L}} \right \rbrace , \left \lbrace f^{\mathfrak{A}}{:} f{\in} F_{\mathcal{L}} \right \rbrace , \left \lbrace R^{\mathfrak{A}} : R \in R_{\mathcal{L}} \right \rbrace \right )$$
standard number theory structure
Given $$\mathcal{L}_{N T}$$, we define the structure $$\mathfrak{N} := \left ( \mathbb{N}_{0} , \left \lbrace 0 \right \rbrace , \left \lbrace S , + , \cdot , E \right \rbrace , \left \lbrace \lt \right \rbrace \right )$$, 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$$ multiplication $$2 \cdot 4 = 8$$, $$E$$ for exponentiation $$E \left ( 3 , 2 \right ) = 9$$
variable assignment function
If $$\mathfrak{A}$$ is an $$\mathcal{L}$$-structure, a variable assignment function is any function of the form $$s : V_{\mathcal{L}} \to A$$
$$x$$-modification of an assignment function
If $$s$$ is a variable assigment function into $$\mathfrak{A}$$ and $$x \in V_{\mathcal{L}}$$ and $$a \in A$$, then $$s \left [ x \mid a \right ]$$ is the variable assigment function defined as follows
$$s \left [ x \mid a \right ] \left ( v \right ) := \left \lbrace \begin{matrix} s \left ( v \right ) & \text{if } v \text{ is a variable other than } x \\ a & \text{if } v \text{ is the variable } x \end{matrix} \right .$$
and we say that $$s \left [ x \mid a \right ]$$ is an $$x$$-modification of the assigment function $$s$$
An $$x$$-modification of $$s$$ is just like $$s$$, except we bind the variable $$x$$ to the element $$a$$ of $$\mathfrak{A}$$'s universe
term assignment function
Suppose that $$\mathfrak{A}$$ is an $$L$$-structure and $$s$$ is a variable assigment function into $$\mathfrak{A}$$. The function $$\overline{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 $$\overline{s} \left ( t \right ) = s \left ( t \right )$$
• if $$t$$ is the constant $$c$$ then $$\overline{s} \left ( t \right ) = c^{\mathfrak{A}}$$
• if $$t : \equiv f{t}_{1} t_{2} \ldots t_{n}$$ then $$\overline{s} \left ( t \right ) = f^{\mathfrak{A}}{\left ( \overline{s} \left ( t_{1} \right ) , \overline{s} \left ( t_{2} \right ) , \ldots , \overline{s} \left ( t_{n} \right ) \right )}$$
interpretation of a term
Given an $$\mathcal{L}$$-structure $$\mathfrak{A}$$, and a term $$t$$ from $$\mathcal{L}$$, we say that it's interpretation in $$\mathfrak{A}$$ is $$\overline{s} \left ( t \right )$$
numbers in the number theory structure
What is the interpretation in $$\mathfrak{N}$$ of the term $$t$$ defined as $$\mathtt{E S S S 0 S S 0}$$

The interpretation is $$\overline{s} \left ( \mathtt{E S S S 0 S S 0} \right )$$ which is equal to $$\mathtt{E}^{\mathfrak{A}} \left ( \overline{s} \left ( \mathtt{S S S 0} \right ) , \overline{s} \left ( \mathtt{s s 0} \right ) \right )$$, we know that $$\mathtt{E}^{\mathfrak{A}} = E$$ (the exponentiation function).

Now considering $$\overline{s} \left ( \mathtt{S S 0} \right )$$ it becomes $$S \left ( \overline{s} \left ( \mathtt{S 0} \right ) \right )$$ which becomes $$S \left ( S \left ( \overline{s} \left ( \mathtt{0} \right ) \right ) \right )$$ and since $$\overline{s} \left ( \mathtt{0} \right ) = \mathtt{0}^{\mathfrak{A}} = 0$$ (the natural number 0), then $$\overline{s} \left ( \mathtt{S S 0} \right ) = 0 + 1 + 1 = 2$$, similarly we can find that $$\overline{s} \left ( \mathtt{S S S 0} \right ) = 3$$

From the above paragrpah we know that $$E \left ( \overline{s} \left ( \mathtt{S S S 0} \right ) , \overline{s} \left ( \mathtt{s s 0} \right ) \right )$$ becomes $$E \left ( 3 , 2 \right )$$ which equals $$9$$, so therefore the interpretation of $$\mathtt{E S S S 0 S S 0}$$ in $$\mathfrak{N}$$ is $$9$$.

A Free Varaible in a Formula
Suppose that $$v$$ is a varaible and $$\phi$$ is a formula, then $$v$$ is free in $$\phi$$ iff exactly one of the following holds:
1. $$\phi$$ is atomic and $$v$$ occurs in $$\alpha$$
2. $$\phi :\equiv \left( \neg \alpha \right)$$ and $$v$$ is free in $$\alpha$$
3. $$\phi : \equiv \left( \alpha \lor \beta \right)$$ and $$v$$ is free in at least one of $$\alpha$$ or $$\beta$$
4. $$\phi : \equiv \left( \forall u \right) \left( \alpha \right)$$ and $$v$$ is not $$u$$ and $$v$$ is free in $$\alpha$$
For All Makes a Variable not Free
Free Variable For All Easy
Show that $$x$$ is not free in $$\phi :\equiv \left( \forall x \right) \left( x = x \right)$$
Free Variable For All Medium
Show that in the following formula $$\phi$$ defined as $\left( \forall v_2 \right) \left( \neg \left( \left( \forall v_3 \right) \left( \left( v_1 = S \left( v_2 \right) \lor v_3 = v_2 \right) \right) \right) \right)$ $$v_1$$ is free in $$\phi$$, but $$v_2$$ and $$v_3$$ are not

We'll start by showing that $$v_2$$ is free in $$phi$$