Satisfaction (First-Order Logic)

first-order-logic

Definition

Satisfaction (First-Order Logic)

Let be an interpretation and a formula. The satisfaction relation

holds when is true under with assignment . The definition is inductive.

Notation

The same symbol appears in two roles, distinguished by what sits on the left:

Left side	Meaning
	Satisfaction — this particular structure and assignment
	Entailment — all structures and assignments

Examples

Consider a structure with:

and , so

and , so

Pick with . Then

so

Since we found satisfying the body:

Pick with . Then

so

Hence

Let be arbitrary. We check each :

	?	?	?
	yes	yes	yes — consequent holds
	no	yes	yes — antecedent false
	no	no	yes — antecedent false

All three satisfy the implication, so

Since was arbitrary, the sentence is true in .

Satisfaction vs. Entailment

The examples above check satisfaction in one structure. Entailment is much stronger: it claims something about all possible structures. To show you must argue that no structure can make true without also making true — no matter what the domain is or who Socrates names. That is why we need proof systems: you cannot enumerate all structures.