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?
 A: 
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. 
A: 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.
