assignment of variables…only if we deal with a non-empty set

If $L$ is a signature, $\mathbb{V}$ a countable set of variables, $\Phi$ a $L$-sentence, $S$ a structure with domain of discourse $\underline{S}$ and $\mu:\mathbb{V}\rightarrow \underline{S}$ a variable assignment, then:

$\Phi$ evaluates to "true" for the assignment $\mu$ iff it evaluates to "true" for every assignment of the variable (this is easy to prove, since the sentence $\Phi$ does not contain any free variables). My question is, why is the above true, only if $\underline{S}$ is non-empty ?

(My knowledge of set theory is almost non-existent, so please use an easy to follow explanation, if it involves anything slightly non-obvious from set-theory)

-
As @Yuval Filmus pointed out, your statement is true without requiring “$\underline{S}$ is non-empty”. Maybe you copied the statement incorrectly. –  beroal Jun 12 '11 at 7:06

When $\underline{S}$ is empty then there is no assignment possible. There is no function from $\mathbb{V}$ to the empty set. Recall that a function maps each element in the range to an element in the domain. So as long as $\mathbb{V}$ is non-empty, there are no functions from it to $\varnothing$.

So the proposition you mention is vacuously true from $\underline{S} = \varnothing$. At the same time, it's not an interesting statement.

-

Yes, no variable assignment is possible for an empty structure. Nevertheless it is perfectly possible to work with them. The branch of logic that does so is often called "free logic". Here "free" means "free of existential suppositions". The Stanford Encyclopedia article [1] makes a further distinction between "free" logic, in which terms may be undefined, and "inclusive" or "universally free" logic, in which an empty domain is permitted. I recommend that article as a good place to read about these logics.

As hardmath points out, the validities in free logic are not the same as usual first order logic, because e.g. $(\exists x)(x = x)$ is classically valid but not valid in free logic. There are more complicated examples; for example, $(\forall y)(\exists x)(x = x)$ is true in an empty domain, but its substitution instances are all false.

Here is the method for assigning truth values without going through variable assignments. Given a structure $M$, first extend the language by adding a new constant symbol $c_x$ for each element $x$ of the domain of $M$. Then an existential sentence is true in $M$ if and only if some substitution instance of it is true (where the quantified variable is replaced by a constant symbol). Similarly a universal statement is true if and only if every substitution instance is true. Even in classical logic I find this approach more elegant than the definition via variable assignments, but the two approaches are equivalent in that context.

-
Note that adding constants from the domain is (1) restrictive to a certain structure and the notion of substructure becomes much more complicated and problematic; (2) Makes an even stronger requirement for the domain of $M$ to be non-empty, as the constants must be interpreted somehow. –  Asaf Karagila Jun 9 '11 at 22:19
I don't follow the criticism. We add constant symbols for the elements of the domain of $M$... in the case the domain in empty nothing gets added, so there's no requirement that the domain has to be nonempty. The reason I find this definition of satisfaction more elegant is that it more directly matches the T-schema. But the general idea is already present in the definition of the elementary diagram of the structure (and $M$ is a substructure of $N$ if and only if the atomic part of the elementary diagram of $M$ is a subset of the elementary diagram of $N$). –  Carl Mummert Jun 9 '11 at 22:56

If we we are dealing with an interpretation of a first-order theory in a model, we want the domain of discourse to be non-empty. While a universal statement can be interpreted as true in an empty domain, it is not possible to interpret statements like $\exists x (x = x)$ as true there, despite the provability of such statements in the predicate calculus with equality.

Using "nonempty" models Gödel proved his completeness theorem, that the statements provable in the predicate calculus are just those that are true in every interpretation. If one allows an empty model, the completeness theorem would fail since the denial of $\exists x (x = x)$ is $\forall x (x \ne x)$ and that (as a universal statement) would be "true" if interpreted in an empty model.

-
For more on empty carriers, many-sorted algebras, etc. see here. –  Bill Dubuque Jun 9 '11 at 15:57

Despite having little grasp in set theory, let me introduce some notation:

• $\langle a,b\rangle$ is an ordered pair whose elements are $a$ and $b$. The ordered pair is such set that the order and recurrence matter (where as $\{a,a,b,a\}$ and $\{a,b\}$ are the same set). That means $\langle a,b\rangle\neq\langle b,a\rangle$ if $a\neq b$.
• A set $R$ such that every element of $R$ is an ordered pair is called a relation. (Note that by this definition the empty set is a relation vacuously).
• A relation $R$ such that for every $a$, if $\langle a,b\rangle$ is a member of $R$, and $\langle a,c\rangle$ is a member of $R$ then $b=c$ (i.e. if $a$ appears in the left coordinate, then it appears exactly once) is called a function. (Note, again, that the empty set satisfies this condition as well).
• If $R$ is a relation then its domain is the collection of all "left coordinates", i.e. the set of all $a$ such that there exists some $b$ and $\langle a,b\rangle$ is a member of $R$.
• If $R$ is a relation the range of $R$ is the collection of all "right coordinates", that is all $b$ such that for some $a$ the ordered pair $\langle a,b\rangle$ is a member of $R$.

Some examples:

1. $\langle 1,3\rangle$ is the ordered pair whose left coordinate is $1$ and right coordinate is $3$.
2. $R=\{\langle 1,2\rangle,\langle 1,4\rangle\}$ is a relation. In this case we usually say that $1R2$ or $R(1,2)$ (as well $R(1,4)$ in this case). Note that $R$ is not a function as $1$ appears in more than one ordered pair in the left coordinate.
3. $F=\{\langle 1,0\rangle, \langle 2,1\rangle, \langle 3,2\rangle\}$ is a relation, and it is in fact a function. In this case we say that $F(1)=0, F(2)=1$ and $F(3)=2$.

A variable assignment $\mu\colon\mathbb V\to\underline S$ is a function whose domain is $\mathbb V$ and its range is a subset of $S$.

That means that $\mu$ is a collection of ordered pairs of the form $\langle x,s\rangle$ whereas $x\in\mathbb V$; $s\in\underline S$; and every $x\in\mathbb V$ appears in exactly one ordered pair of $\mu$.

In particular, there cannot be an ordered pair of the form $\langle x,s\rangle$ where $s\in\emptyset$, since the empty set is... well, empty.

This means that for a variable assignment to be relevant at all we have to have the universe of discourse non-empty.

-