# Confusion regarding what a valid sentence is in model theory

I just cracked open the book "Model Theory" by C.C. Chang and H. Jerome Keisler. In their introductory chapter, the authors make the following statements...which I must be interpreting incorrectly:

1. $$\mathscr S$$ is a set of simple statements

2. A model $$A$$ is a subset of $$\mathscr S$$

3. The set of all models has the power $$2^ {\vert \mathscr S \vert}$$

4. $$A \models \phi$$ means that $$\phi \in A$$ and we say that $$\phi$$ holds in model $$A$$.

5. A sentence $$\phi$$ is called valid iff $$\phi$$ holds in all models for $$\mathscr S$$

Now, given these 5 statements, it seems to me that no sentence could ever be valid...because no single element is common to all subsets of a given set. Said differently, $$3.$$ appears (to me) to say that there are $$2^ {\vert \mathscr S \vert}$$ different models for a given $$\mathscr S$$...i.e. there are $$2^ {\vert \mathscr S \vert}$$ different subsets of $$\mathscr S$$. From $$4.$$ I would think that if $$\phi \notin A$$, then we say $$\phi$$ does not hold in $$A$$. Combining my observations together, how could $$5.$$ ever occur?

If anyone could find the error in my thinking, I would greatly appreciate it. Cheers~

(Perhaps the confusion stems from the terminology power in the phrase "...has the power $$2^ {\vert \mathscr S \vert}$$"...I interpreted that as cardinality. Perhaps that is the wrong interpretation?)

Edit: I am going to dissect the example provided in Dr. Kruckman's answer in the below space. But first, I will provide the unintentionally omitted definitions of the $$\models$$ symbol that Dr. Kruckman alluded to:

4B. If $$\phi$$ is $$\psi \land \theta$$, then $$A \models \phi$$ if and only if both $$A \models \psi$$ and $$A \models \theta$$

4C. If $$\phi$$ is $$\lnot \psi$$, then $$A \models \phi$$ iff it is not the case that $$A \models \psi$$. As a side note, I will denote the phrase "is not the case that $$A \models \psi$$" as $$A \require{cancel} \cancel{\models} \psi$$ (sorry if this is atypical).

Claim: $$\lnot (S\land \lnot S)$$ is a valid sentence where $$S$$ is a simple statement (i.e. a 'sentence symbol').

Suppose I select an arbitrary model. Call it $$A'$$. If I can show that $$A' \models \lnot (S\land \lnot S)$$, then I have shown that $$\lnot (S\land \lnot S)$$ holds in all models.

Starting at the "lowest" level of the compound statement proposed above, we have two cases:

Case 1: $$A' \models S$$

Case 2: $$A' \require{cancel} \cancel{\models} S$$

Proceeding with Case 1 first, let $$\omega = \lnot S$$. We know (by assumption) that $$A' \models S$$. By application of 4.C, we can thus conclude that $$A' \require{cancel} \cancel{\models} \omega$$.

Let $$\zeta = S\land \omega$$. By application of 4.B, because $$A' \require{cancel} \cancel{\models} \omega$$, we must have $$A' \require{cancel} \cancel{\models} \zeta$$.

Let $$\gamma = \lnot \zeta$$. By application of 4C., because $$A' \require{cancel} \cancel{\models} \zeta$$, we must have $$A' \models \gamma$$.

But $$\gamma = \lnot (S\land \lnot S)$$. Therefore, we equivalently have $$A' \models \lnot (S\land \lnot S)$$, which is what we set out to prove.

Finishing with Case 2, let $$\omega = \lnot S$$. We know (by assumption) that $$A' \require{cancel} \cancel{\models} S$$. By application of 4.C, we can thus conclude that $$A' \models \omega$$.

Let $$\zeta = S\land \omega$$. By application of 4.B, because $$A' \require{cancel} \cancel{\models} S$$, we must have $$A' \require{cancel} \cancel{\models} \zeta$$.

You can see that we arrive at a "common point" from the Case 1 demonstration and conclude, once again, that $$A' \models \lnot (S\land \lnot S) \ \ \ \ \ \ \square$$

• Are you sure you are not mixing up models with theories? A theory is a set of sentences, and it could have infinitely many models or none at all. A model is a structure, and shouldn't be a set of statements. Statement 4 should then be something like "A theory $\Gamma \models \phi$ means that $\phi \in \Gamma^\models$, the closure of the theory $\Gamma$, and we say that $\phi$ holds in all models of $\Gamma$." Commented Oct 1, 2020 at 1:34
• @playwr3236 I don’t think so. I’m just taking bits and pieces from the intro chapter and paraphrasing (in a fashion that I don’t believe is producing any loss of information). In fact, the notion of “theory” has not even been discussed.
– S.C.
Commented Oct 1, 2020 at 1:47
• It is only a different way of "seeing" it... Usually, in prop logic the counterpart of "model" is a valuation $v$, i.e. a function that assigns to all sentence symbols a truth value. What is a model according to C&K ? The set of sentence symbols that are evaluated to $\text T$ by $v$. Commented Oct 1, 2020 at 9:38
• The "rules" for evaluating complex formulas are the usual one (i.e. truth table for connectives; see 4B and 4C above). Commented Oct 1, 2020 at 9:39
• The proof that $\gamma$ is valid is straightforward. Let $A$ a model, i.e. a subset of $\mathscr S$. Either (i) $S \in A$, in which case $A \vDash S$, and thus $A \nvDash \lnot S$ (Lemma 4C) and thus $A \nvDash (S \land \lnot S)$ (Lemma 4B) and thus $A \vDash \lnot (S \land \lnot S)$ (Lemma 4C again). Or (ii) $S \notin A$ and thus $A \nvDash S$ ... Commented Oct 1, 2020 at 9:43

The mistake you've made is that you've only included item 1 of Definition 1.2.3. The definition $$A\models \varphi$$ iff $$\varphi\in A$$ is only for the case when $$\varphi$$ is a sentence symbol (one of the "simple statements" in $$\mathcal{S}$$). The rest of the definition recursively defines $$A\models \varphi$$ when $$\varphi$$ is a compound sentence like $$S\land S'$$ or $$\lnot S$$.
The idea here is that the sentence symbols represent abstract propositions that could be true or false. You should think of a model as a way of picking which sentence symbols are true (the ones which are elements of the model). Your reasoning correctly shows that no sentence symbol $$S$$ can be valid: there will always be some models in which $$S$$ is true and others in which it is false. But other compound sentences can be valid. For example: $$\lnot (S\land \lnot S).$$
• Your proof seems correct to me, but much longer than it needs to be. I would write something like this: Let $A$ be a model. Then $A\models S$ or $A\models \lnot S$, but not both (since otherwise $S\in A$ and $S\notin A$, contradiction). So $A\not\models S\land \lnot S$, and thus $A\models \lnot (S\land \lnot S)$. Since every model satisfies $\lnot (S\land \lnot S)$, this sentence is valid. Commented Oct 1, 2020 at 13:06