Model Theory Confusion

In an interpretation, are the domain and the subsets slated to go into the predicate letters, supposed to be well-defined sets? If the Axiom of Replacement is used to define a subset of the domain, using a formula, and this formula is undecidable for some $x$ in the domain, then I can't understand how a truth value can be assigned to the sentence "$x$ is in that subset" in the interpretation. I am very confused! Can anyone help?

-
You should view the definition of model, and definition of truth in a model, as being like any other mathematical definition, in, say, group theory. And we can know what it means for a sentence to be true in a structure, even if we don't know whether the sentence is true in that structure. It is best not to drag formal set theory into the game. Model Theory is a field of mathematics like any other. – André Nicolas Aug 3 '11 at 18:28
I would like to record a vote against closing. This, to me, appears to be a question about how model theory should be carried out inside an axiomatic set theory, which is a fair enough question. I'm no expert, but I suspect there may have been some confusion between theory and metatheory. I would certainly like to see a detailed answer from our resident set theorists. – Zhen Lin Aug 4 '11 at 8:55

I can't understand how a truth value can be assigned to the sentence "x is in that subset" in the interpretation.

A model $M$ of set theory will consist of a set $D_M$ (which is the domain of $M$) and a binary relation $E_M$ on $D_M$ (which is the interpretation of the $\in$ symbol) The truth of formulas is defined inductively via the T-schema:

• For $a, b \in D_M$, the formula "$a \in b$" holds in $M$ if and only if $E_M(a,b)$ holds.

• A formula $(\forall x)\phi(x)$ holds in $M$ if and only if for every $a \in D_M$, the formula $\phi(a)$ holds in $M$

• A formula $(\exists x)\phi(x)$ holds in $M$ if and only if there is some $a \in D_M$ such that $\phi(a)$ holds in $M$.

• The truth values of compound formulas $\phi \land \psi$, $\lnot \phi$, $\phi \to \psi$, and $\phi \lor \psi$ are determined from the truth values of $\phi$ and $\psi$ using truth tables.

One aspect of this definition is that, in the clauses for the quantifiers, no provision is made about effectiveness. Even if $D_M$ is countable, we may not have an algorithm that tells us whether $\phi(x)$ holds as a function of $x$ for a fixed $\phi$. But we know that either there is some $a \in D_M$ such that $\phi(a)$ holds, or else for every $a \in D_M$ the negation $\lnot \phi(a)$ holds. In other words the definition about truth values is solely about truth values, not about how we might come to determine truth values effectively.

-

In first order logic, predicate symbols are interpreted by arbitrary sets. For truth values, all we know is that a given formula is either true of false in a given structure. It may depend on set theory axioms, which of the two holds.

I'll give an example. Consider a structure ${\cal A}$ whose domain is ${\cal P}(\mathbb R)$ where a predicate symbol $p$ is interpreted as the set $\{A \subseteq \mathbb R : \aleph_0 < |A| < 2^{\aleph_0}\}$. Now the definition of $\cal A$ is not absolute, meaning that ${\cal A}$ is different in different models of set theory. In each model of set theory ${\cal A} \models \exists x p(x)$ has a definite value. However this values depends on whether CH holds in the given model.

In practice, however, set theoretic questions rarely arise in contemporary model theory. Most properties studied by model theorists do not depend on set theory axioms. It is best to approach model theory as any other branch of mathematics - with naive ideas about sets.

Edit I've changed $\mathbb N$, to $\mathbb R$, which obviously was incorrect.

-
Is it really possible to construct such a predicate $p$? – Zhen Lin Aug 4 '11 at 8:58
I mean, is there a first-order theory $T$, of which $\mathcal{A}$ is a model, such that there is a predicate $p$ which is necessarily interpreted as such a set? – Zhen Lin Aug 4 '11 at 9:22
The answer again depends on CH. If CH holds than $P = \{A \subseteq \mathbb R: \aleph_0 < |A| < 2^{\aleph_0}\} = \emptyset$. So $\lnot \exists x p(x)$ does the job. On the other hand, if CH does not hold, pick an element $A_0 \in P$ and let $P' = P \cup \{\mathbb R\} \setminus \{A_0\}$. Then ${\cal A} = \langle {\cal P}(\mathbb R), P \rangle$ is isomorphic to $\langle {\cal P}(\mathbb R), P' \rangle$. So there is no such theory. – Levon Haykazyan Aug 4 '11 at 11:15
@Zhen Lin: it is not possible to use a theory to ensure that the interpretation consists of particular sets. For example, using Henkin models, it is possible to construct a model of any consistent first-order theory such that domain of them model is any given countable set of objects. – Carl Mummert Aug 4 '11 at 11:34
@Carl: I think that Zhen wants a theory whose only model on $\cal P(\mathbb R)$ interprets $p$ as the set $\{A \subseteq \mathbb R: \aleph_0 < |A| < 2^{\aleph_0}\}$. – Levon Haykazyan Aug 4 '11 at 13:30