Question on free variables and definable sets.

27 Views Asked by At

I'm just looking for some clarification about the concept of free variables, and their role in the definition of sets definable in a structure. Sorry if it's a little open-ended, though any help is appreciated.

I've notice that various logic books have different conventions for notation when presenting the free variables that (may) reside in a formula. I'll just quickly establish notation: Let $\sigma$ be a signature for a language of first order logic, and let $V$ be the countable set of all variables. Let $\Phi_\sigma$ denote the set of all formulas over this signature. For $\phi \in \Phi_{\sigma}$, let $F_{\phi}$ denote the set of all variables $x \in V$ that occur freely in $\phi$. Let $\mathbb{A}$ be a $\sigma$-structure, with domain $A$.

Now, some books will differ on what it means when we say $\phi(\vec x)$, where $\vec x = (x_0, \dotsc, x_{n-1})$ is a sequence of variables in $V$ of length $n$, with the intent of determining, given $\vec a \in A ^ n$, whether $\mathbb{A} \models \phi(\vec a)$. For example, some will consider $\vec x$ to consist of exactly the free variables that occur in $\phi$, with each occurring once. In other words, that it's an enumeration of $F_\phi$. Others will relax this and say that when we write $\phi(\vec x)$ out of context, we are implicitly assuming only that $F_{\phi} \subseteq \{x_{0}, \dotsc, x_{n-1}\}$. Others will not require this at all, and allow not only more variables than occur freely in $\phi$, but also not require that the sequence contain all of them. Thus, in this latter convention, the choice of $\vec x$ is somewhat arbitrary. In the first convention above, one can at least require a well ordering on $V$, and say, given $\phi$ above, there is a canonical increasing enumeration $\vec x _{\phi}$ of $F_{\phi}$.

In a given structure $\mathbb{A}$, and given a formula $\phi \in \Phi_\sigma$, one can define the set/relation in $\mathbb{A}$ defined by $\phi$ to be $D(\phi) := \{\vec a \in A ^ n : \mathbb{A} \models \phi(\vec{a})\}$. However, this would depend then on the sequence $\vec x$ chosen for this, right?

Considering for now the lattermost convention above, would it not matter, even for the same formula $\phi$? If we consider distinct $\vec x = (x_0, \dotsc, x_{n-1})$ and $\vec y = (y_0, \dotsc, y_{m-1})$ then we can get different sets, even of different dimensions, so I'm imagining that this chosen sequence should be viewed as a parameter in a definable set (as say we should write $D_{\vec x}(\phi)$ instead). In fact, there is technically no requirement that the sequences $\vec x$ even need be injective, so that there could be repeats. It would at least make sense from a technical standpoint since it would just result in a repeat of coordinates. The same goes for occurrences $x_i$ that don't occur freely in $\phi$, or occurrences of variables that don't appear among the $\{x_i\}_{i \in n}$, since they still make sense from a technical standpoint to ask if $\mathbb{A} \models \phi(\vec x)$, even if silly.

Is it the case that a set definable by a formula $\phi$ with a presentation of variables $\vec x$ with certain silly features (such as with repeated, missing, or extra variables), could also be definable by a modified yet 'similar' formula without them? If so, I guess we could talk about definable sets in a matter that, without loss of generality, avoids that and is more like the former most convention, with the canonical 'sensible' choice of variables.