Second order logic theory describable by first order logic

53 Views Asked by At

I have a question to the preconditions to describe a second order theory by first order logic.

Consider the second order logic theory of the Natural Numbers $N_{1}=\left(\mathbb{N},+,\cdot\right)$, which is equivalent to the first order theory $N_{2}=\left(P\left(\mathbb{N}\right),E,\mathbb{N},+,\cdot\right)$, where $P\left(\mathbb{N}\right)$ is the powerset of the Natural Numbers.

We added the powerset to the first order universe, so we can quantify over the elements of the powerset.

My question is about the $E$. $E$ is defined as a subset of the Cartesian product between $\mathbb{N}$ and $P\left(\mathbb{N}\right)$, $E\subseteq\mathbb{N}\times P\left(\mathbb{N}\right)$, with the condition $nEr\Longleftrightarrow n\in r$ with $n\in\mathbb{N}$ and $r\in P\left(\mathbb{N}\right)$.

For what we need $E$?

Thanks for answering.

1

There are 1 best solutions below

5
On

Firstly, note that the powerset of $\mathbb{N}$ is only sufficient to interpret the monadic second-order theory of $\mathbb{N}$, i.e. the second-order theory which only allows for second-order variables of arity one (set variables, if you like). So your question is really about the relationship between the monadic second-order theory of $\mathbb{N}$ and the first-order theory of $\mathcal{P}(\mathbb{N})$.

In this context, you need the relation $E$ to interpret atomic formulas of the form $X(t)$ where $X$ is a second-order variable of arity one (a set variable) and $t$ is a term. Such an atomic formula is true in a given interpretation if and only if the number which interprets $t$ lies in the set which interprets $X$. Translating $X(t)$ into a first-order language thus results in $E(t,X)$ (or if you will, $t\,E\,X$).