Formula Satisfaction Set

logic

Definition

Formula Satisfaction Set

Let $F$ be a formula and let $\mathcal{A}$ be the set of all variable assignments. The formula satisfaction set of $F$ is the set of all assignments under which $F$ is true:

$$\{F\}\stackrel{\mathrm{def}}{=}\{\sigma \in \mathcal{A}\mid [F]\sigma =\text{true}\}$$

In other words, $\{F\}$ contains exactly the assignments that satisfy $F$.

Model vs Assignment

A model is a full semantic object, usually an interpretation together with a variable assignment. A satisfaction set, by contrast, collects only the assignments that make a formula true.

So:

• $\mathcal{M}(F)$ is the set of models of $F$;
• $\{F\}$ is the set of assignments satisfying $F$.

In first-order logic, these are related, but they are not the same object.

Expressiveness

A natural question is whether every set of assignments can be represented as the satisfaction set of some formula.

This depends on the expressive power of the underlying logic. For example, in first-order logic, many sets of assignments are definable, but not every arbitrary subset of the assignment space must be definable.

Example

Even number

Let

$$F:=\exists i(x=2i)$$

Then $\{F\}$ is the set of all assignments $\sigma$ such that $\sigma (x)$ is even.