Circular definition?

270 Views Asked by At

I am new to logic and studying it by Enderton's A Mathematical Introduction to Logic (2nd edition). For question 3.3.1 in the books, which states

Show that in the structure $(\mathbb{N}; \cdot, E)$ we can define the addition relation $\{\langle m, n, m+n\rangle \mid m, n \text{ in }\mathbb{N}\}$. Conclude that in this structure $\{0\}$, the ordering relation $<$, and the successor relation $\{\langle n, S(n)\rangle \mid n \in \mathbb{N}\}$ are definable.

So I think we should first define $0$ since clearly we want to use $x^a \cdot x^b = x^{a+b}$ but $0^0$ causes trouble. With knowing $0$ we can define $+$ by $\forall x(x \neq 0 \land xEv_1 \cdot xEv_2 = xEv_3)$.

However I found someone writing his/her answer on the internet. S/he used $\mathbf{0}$ and $S(n)$ to define $+$! I don't understand. I know boldface $\mathbf{0}$ means constant symbol, but it's not in $(\mathbb{N}; \cdot, E)$. Neither is $S(n)$. Then s/he says we can define $\{0\}$ and $S$ by $(\mathbb{N}; +)$. Is it wrong?

Further question:

If $\mathbf{0}$ is in the structure, can I simply define $\{0\}$ by $v=\mathbf{0}$? I can't see any reason to go back to $(\mathbb{N}; +)$ to define it.

1

There are 1 best solutions below

2
On BEST ANSWER

Comment to :

boldface $\mathbf{0}$ means constant symbol, but it's not in $(\mathbb N;⋅,E)$.

Exactly; in the "outer" world there is the number $0$ but the language has no "name" $\mathbf{0}$ for it.

If $\mathbf{0}$ is in the structure, can I simply define $\{ 0 \}$ by (the formula) $v=\mathbf{0}$ ?

No; $0$ (the number) is in the structure, but the constant $\mathbf{0}$ is not in the langugae. Thus, the formula $v=\mathbf{0}$ is not available.

Thus, the first task is to find a suitable formula defining the number, i.e. identifying univocally it.

Possible solution; having defined $+$, we can say that : $\exists x \forall y \ (y+x=y)$ can be a plausible definition of $0$.

See page 90 : Definability in a Structure, regarding the definability of a subset of the universe or of a relation on the universe. Applied to our example :

$$\{ a \mid \ \vDash_{\mathbb N} \varphi[[a]] \}.$$