7
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ 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$." $\endgroup$
    – player3236
    Commented Oct 1, 2020 at 1:34
  • $\begingroup$ @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. $\endgroup$
    – S.C.
    Commented Oct 1, 2020 at 1:47
  • $\begingroup$ 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$. $\endgroup$ Commented Oct 1, 2020 at 9:38
  • $\begingroup$ The "rules" for evaluating complex formulas are the usual one (i.e. truth table for connectives; see 4B and 4C above). $\endgroup$ Commented Oct 1, 2020 at 9:39
  • $\begingroup$ 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$ ... $\endgroup$ Commented Oct 1, 2020 at 9:43

1 Answer 1

7
$\begingroup$

I want to note first that this introductory section of Chang and Keisler is about propositional logic (which the authors call sentential logic). When people talk about model theory, they usually mean model theory of first-order logic, and this is what most of the book is devoted to. So the notions of "model", "theory", "valid", etc. will get different definitions in the context of first-order logic in the next chapter.

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).$$

P.S. Yes, "power" is a synonym for "cardinality".

$\endgroup$
2
  • $\begingroup$ Thank you for the response! I wanted to track why your example is a valid sentence when restricting myself to the language of this book (I know from truth tables that this is always true...i.e. the statement that something is simultaneously both false and true is always false...thus negating such a statement is always true). If you could critique my edit I would greatly appreciate it! (...also, after writing that mini proof out, I can certainly see why people prefer using truth tables hah!) $\endgroup$
    – S.C.
    Commented Oct 1, 2020 at 8:26
  • $\begingroup$ 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. $\endgroup$ Commented Oct 1, 2020 at 13:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .