Confused about definability of a function in logic

53 Views Asked by At

Consider language $L = \{ +\}$ and consider the $L$-structure $M =(\mathbb{N},+)$. I define $\{ 0 \}$ (i.e., $0$ is the only number that satisfies the formula) in two ways. One is, $\phi[x]= x+x \simeq x$, and the other one is $\phi = \exists x(x+x \simeq x)$. In the first one, $x$ is a free variable, while in the second one, $x$ is a bound variable. Is there a difference between these two formulas? What's the point for free variables? Please help me answer these two questions as I am very confused about writing formulas in first-order languages.

1

There are 1 best solutions below

5
On

Your second sentence is just a sentence which happens to be true - it doesn't define $0$. $0$ is the unique witness to that sentence being true, but that's a different thing. In particular, note that "$0$ is the unique witness to the sentence "$\exists x(x=x+x)$"" is saying exactly that "the formula $x=x+x$ defines $0$."

A sentence is either true or false. A formula $\psi$ with $n$ free variables carves out a subset of $M^n$ (namely $\{(a_1, . . . , a_n): M\models \psi(a_1, . . . , a_n)\}$) - in particular a formula with one free variable carves out a subset of $M$. An element $a$ of $M$ is definable if there is some formula carving out $\{a\}$ - that is, if there is some $\psi(x)$ such that $M\models\forall x(\psi(x)\iff x=a)$. One of the motivations behind model theory is that if we care about a structure, we care about its definable elements, and its definable subsets, and the definable subsets of its Cartesian powers.