Every logic book I’ve ever come across, when talking about the semantics of first-order logic, defines concepts like structures and interpretations where the most important element is a set called the “domain of discourse” or the “universe”. Everything is then based on this set. This works very nicely for number theory, but what is the universe of set theory? The set of all sets does not exist. So how do you define all the concepts of semantics?
Semantics for set theory
first-order-logicpredicate-logic
Related Solutions
One approach (though far from the only one), coming mostly from categorical logic (specifically from Pitts's tripos theory), is to change the basic idea of what the underlying universe of a model is. Instead of it being an unstructured set $X$, with true equality as your basic notion of equality, you take sets paired with a Heyting-valued partial equivalence relation $\cdot\approx\cdot:X\times X\to \tau^R$ (using this specific example of topology) requiring
- $x\approx y\subseteq y\approx x$
- $x\approx y\,\cap\,y\approx z\subseteq x\approx z$
Note the absence of reflexivity here, meaning that the kind of equality relations being considered here are more general than the ones I suggested in the comments.
One then requires that all predicates interpreted in this new notion of domain (as functions $X^n\to \tau^R$) respect the equality relation in two ways. I show the unary case, but the adaptation to the $n$-ary case is simple:
- $P(x)\subseteq x\approx x$
- $x\approx y\,\cap\,P(x)\subseteq P(y)$
It's even possible to get more robust interpretations of function symbols by interpreting them as $\tau^R$-valued functional relations, where $\exists x P(x,\vec{y})$ (you need existential quantification to say "is a total function") is interpreted by $\bigcup_{x\in X}P(x,\vec{y})$.
To see that you get non-classical models this way, let $X=\{0,1\}$ with $1\approx 1=\mathbb{R}$, $0\approx 0=1\approx 0=0\approx 1=(0,1)$. You can verify that $\approx$ satisfies the requirements above, and it should also be clear that $0\approx 1\vee 0\not\approx 1$ is not equal to $\mathbb{R}$.
The fun thing about this approach is that the category of objects of the form $(X,\approx)$, with morphisms taken to be (equivalence classes of) functional $\tau^R$-valued relations, not only form a topos, but a topos which is equivalent to the category of sheaves on $\tau^R$. If you want to dig into this construction in a little more detail, I recommend Hyland, Johnstone, & Pitts's "Tripos Theory", which is still a pretty good introduction to the full construction (though requiring a bit of familiarity with category theory).
Best Answer
To be rigorous about this you need to understand the distinction between the metalanguage in which we are reasoning about the semantics and the object languages whose semantics we are reasoning about. The statement that the set of all sets does not exist is relative to the closure properties that we require of the set of all sets: we may assume stronger closure properties in our metalanguage (e.g., the existence of Grothendieck universes containing any set) than we do in our object language (e.g., closure under the axioms of ZF (Zermelo-Fraenkel set theory)). Note that the metalanguage and the object language may have exactly the same syntax: it is the way we are using them and the axioms that we assume in them that matters.
For many purposes in set theory, particularly independence results, it is enough to formulate results predicated on the existence of a model of set theory. E.g., to prove that the axiom of choice $AC$ is independent of the other axioms of $ZF$, we have to show that if $ZF$ has a model, then so does $ZFC = ZF+AC$. This statement does not assume the existence of a model of either $ZF$ or $ZFC$.
Likewise, the completeness theorem states that for any theory $T$ and any sentence $\phi$, if $T \models \phi$ (i.e., if $\phi$ holds in every model of $T$) then $T \vdash \phi$ (i.e., $\phi$ can be derived from $T$ using first-order logic). ZFC can prove this for all $T$, including $T = ZFC$, but that doesn't imply that a model for $ZFC$ can be constructed in $ZFC$.
Note also the assertion $T \models \phi$ in the statement of the completeness theorem is about all models of $T$, not just some chosen standard model with a given universe of discourse. Taking $T$ to be $PA$ (Peano arithmetic), we know from the incompleteness theorem that there are sentences $\phi$ (such as a sentence asserting that $PA$ is consistent) such that $PA \not\vdash \phi$, even though $\phi$ is true if we restrict our universe of discourse to the natural numbers. The completeness theorem then tells us that $PA$ has a model in which $\lnot\phi$ holds.