Prove that a set of first-order formulas contains instances

16 Views Asked by At

A set $\Gamma$ of (first-order) formulas is said to contain instances when, for every existentially quantified formula $\exists x A$ of the language, the following holds:

There is some term $t$ in the language s.t. $\Gamma \models \exists x A \rightarrow [A]\frac{t}{x}$.

Now, let $\frak{I}, \sigma$ be such that for every $d \in D$ there is a $t \in \mathcal{T}_\mathcal{S}$, s.t. $\varphi^\sigma_\frak{I}(t) = d$. Define $$\Gamma := \{A \in \mathcal{F}_\mathcal{S}~|~\frak{I}, \sigma \models A\}$$

My question is: How do you use the information on $\frak{I}, \sigma$ above to prove that $\Gamma$ contains instances?

Note on the notation:

  • $D$ stands for a domain, and $d$ for an object of the domain.

  • $\frak{I}$ stands for an interpretation (structure);

  • $\sigma$ stands for a variable assignment;

  • $\mathcal{F}_\mathcal{S}$ stands for the set of formulas in the language $\mathcal{S}$.