3

I have some questions about under what conditions a set of truth assignments is the model of some set of sentences.

To be more precise, suppose I'm dealing with only propositional logic. Let $K$ be a set of truth assignments, i.e. those maps assigning truth values to propositional variables.

For any set $\Sigma$ of sentences, let $Mod(\Sigma):=\{v:v\ \mbox{is a truth assignment and v satisfies $\Sigma$}\}$.

Definition. Let $K$ be a set of truth assignments. Call $K$ definable if $K=Mod(\Sigma)$ for some set $\Sigma$ of sentences; if such $\Sigma$ can be chosen finite (or equivalently, containing a single sentence), then $K$ is finitely definable.

I can prove that, in a language with only finitely many propositional variables, any set of truth assignments is definable. Since in such language there are only finitely many truth assignments, what I proved can be rephrased as: any finite set of truth assignments is definable. Now my questions are:

  1. In a language with denumerably many propositional variables, there are continuum many truth assignments. Does what I proved still hold in this case? Is any set of truth assignments, or any finite set of truth assignments, definable? Or finitely definable?
  2. Is there a criterion for a set of truth assignments to be definable or finitely definable in a general setting? What would happen if we work in a language with uncountably many propositional variables?

Thank you in advance for anyone who might help me about this.

Pachara
  • 63

1 Answers1

1

A few observations:

  • Being finitely definable implies there are only finitely many variables used in $S$. Thus, any valid truth assignment for $S$ will remain one if we flip the truth value of any of the remaining variables from true to false or vice versa. If this is not the case with a set of truth assignments (i.e. no finite subset of the variables has this property), it is not finitely definable.
  • Any finite set of truth assignments is definable (regardless of the cardinality of the set of variables; the set of sentences will actually have the same cardinality).
    • This is easy to achieve for each truth assignment separately (just add one sentence for each variable, forcing it to be true or false, depending on what the assignment says).
    • In order to do it for more than one assignment simultaneously, it's sufficient to note that one can find a finite subset of variables which distinguishes them (i.e. every pair of truth assignments will differ in at least one variable from this subset). This set can then be used to build one distinguishing sentence for each truth assignment which says "We're dealing with this truth assignment." (being just a conjunction of the variables and their negations, depending on what the assignment says about them).
    • Then, for each variable in the assignment, we'll add an implication of the form "distinguishing sentence $\Rightarrow$ variable" (or $\neg$ variable, depending on what the assignment tells us). Thus, we've essentially added (infinite) implication saying that the distinguishing sentence determines the rest of the truth assignment completely.
    • Finally, a sentence one formed as a disjunction of all distinguishing sentences guarantees the only satisfying assignments will be the ones we are interested in.
  • Note that the above construction does not work for infinitely many statements since the "big disjunction" would yield an infinite sentence. I actually suspect that a set of all truth assignments which assign value of "true" to exactly one variable might not be definable -- although that's just a gut feeling for now.
Peter Košinár
  • 10,810