Set of formulas in Model Theory

736 Views Asked by At

I'm reading the book Model Theory by Chang and Keisler and there is one thing that always bugs me. Very frequently we have something like $\Sigma(x)$ representing the set of all formulas in a language that have x free, but what does it mean for a set to contain a formula?

The closest I've been able to get to a sensible answer would be to represent each formula by something like $\{x \in A : \psi(x)\}$ (i.e. the set of all elements of the universe of a model that satisfy the formula), but then how would you represent formulas without free variables? That is, suppose I have the sequence of formulas $0 \neq S0$, $0 \neq SS0$, $0 \neq SSS0$ and so on. They are all true of every model of Peano Arithmetic, but how would I build a set that contained these formulas? What does it even mean to have a set contain them?

1

There are 1 best solutions below

7
On BEST ANSWER

Model theory is rarely done in a system which is inadequate for talking about sets to begin with. Often the choice of theory is $\sf ZFC$ or a stronger theory (e.g. $\sf ZFC$ with the addition of large cardinals, or some axiom deciding the continuum function).

In this context, then, a language is a set, and the formulas are finite strings from that alphabet. Note that the fact that we can define when a string is a WFF is exactly the reason why there is a set of all the formulas. Now we can define the predicate which tells us whether or not $x$ is a free variable in a formula.

And that's it, we define the set $\Sigma(x)$ as all those formulas satisfying that predicate.

Alternatively, we can talk about logic and basic model theory in $\sf PA$, or extensions thereof, where we can recursively encode formulas and define the above predicate. Although in that context the set of formulas doesn't exist as above, because it is not an element of the universe (which is a model of $\sf PA$, so the universe contains integers and not sets). But in that case we talk about recursive definitions, and indeed $\Sigma(x)$ is a recursive set.

In either case the meaning of that set is that however we chose to represent the notion of "formula", we could have defined a collection (either a set, or some nicely definable collection of integers) which is interpreted to be exactly those formula in which $x$ is a free variable. This set, or whatever, exists in the meta-theory, and not in the universe of the model.