Satisfiability of Formulas of the Predicate Calculus

Prove that a formula $A$ of signature $\sigma$ is satisfiable in the algebraic system $\mathfrak {M} = \langle M; \sigma \rangle$ if and only if $A$ is satisfiable in every enrichment $\mathfrak {M}' = \langle M; \sigma ' \rangle$.

Prove that for every sentence $A$ of signature $\sigma$ relative to the algebraic system $\mathfrak {M} = \langle M; \sigma \rangle$, we have $\mathfrak {M} \vDash A$ or $\mathfrak {M} \vDash \neg A$.

Prove that:

Prove that a quantifier-free formula is identically true if and only if it can be obtained by substitution from some identically true formula of the propositional calculus.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be a subsystem of the system $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$. Prove that for every sentence $A$ of signature $\sigma$ relative to the algebraic system $\mathfrak {M} = \langle M; \sigma \rangle$, $\mathfrak {M} \vDash A$ if and only if $\mathfrak {M}_{2} \vDash \rho_{P}(A)$, where $\mathfrak {M}_{2} = \langle M_{1}; \sigma , P \rangle$ is an enrichment of $\mathfrak {M}_{1}$ and $\rho_{P}(A)$ is the relativization of the formula $A$, with, for every $a \in M_{1}$,

Are the formulas satisfiable:

Are the formulas identically true:

Let $A(t)$ be obtained from $A(x)$ by replacing all free occurrences of the variable $x$ by the term $t$. Prove the identical truth of the following formulas, if the term $t$ is free for $x$ in $A(x)$:

Give examples of formulas $A(x)$ and terms $t$ such that formulas (a) and (b) of the preceding problem are not identically true.

Prove that the formula

is satisfiable in some infinite model and false in all finite ones.

Prove that the formula

is true in every model containing at most three elements.

Prove that the following formulas are true in every finite model, but not identically true:

Write a formula with 1-ary predicates, satisfiable only in models containing at least five elements.

Prove the identical truth of the following formulas:

Let $A$ be a formula, $B$ a subformula of the formula $A$, and $A_{1}$ the result of replacing some occurrence of $B$ in $A$ by the formula $B_{1}$. Prove that if $B \sim B_{1}$, then $A \sim A_{1}$ (the replacement theorem).

Prove that for every formula there exists an equivalent prenex normal form.

Reduce to prenex normal form, taking $A$ and $B$ to be quantifier-free formulas:

Let $\sigma = \langle \left\{ P_{i}^{n_{i}}\right\}_{i \in I}, \left\{ f_{j}^{n_{j}}\right\}_{j \in J}, \left\{ a_{k}\right\}_{k \in K} \rangle$, and let $T$ be the set of all terms of signature $\sigma$. Define predicates and functions on $T$ so that $T$ becomes an algebraic system of signature $\sigma$.

For the formula $\forall x \exists z \forall y \exists u ((y > z \supset y > x) \& (u < z) \& \neg (u < x))$, construct the $\forall$-formula whose existence is asserted in Problem II.5.21(b). For the system $\mathfrak {M} = \langle \mathbb {N}; {<} \rangle$, find the required enrichment.

For the formula $\forall x \forall y \exists z \exists t (P(x, t) \& \neg P(y, z))$, construct the $\forall$-formula whose existence is asserted in Problem II.5.21(b). For any system $\mathfrak {M} = \langle M; P \rangle$, where $M = \left\{ 0, 1\right\}$, find a suitable enrichment.

For the formula

and the system $\mathfrak {M} = \langle \mathbb {N}; S^{3}, P^{3} \rangle$ from Problem II.4.9, construct the Skolem functions (see Problem II.5.21(b)).

Prove that if a formula of signature $\sigma$ is satisfiable, then it is satisfiable on some algebra of terms of a signature $\sigma ' \supseteq \sigma$.

Let $A^{*}$ be a Skolem normal form of the sentence $A$. Show that $A \sim A^{*}$ does not hold in general. Is it always true that $A \vDash A^{*}$? A similar question for $A^{*} \vDash A$.

Reduce to Skolem normal form:

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be an arbitrary model and $M \subseteq M_{1}$. Prove that there exists an extension $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$ of the model $\mathfrak {M}$ such that for every formula $A(x_{1}, \ldots , x_{n})$ and any elements $a_{1}, \ldots , a_{n} \in M$,

Let $\mathfrak {M} = \langle M; \sigma \rangle$ and $M = \left\{ m_{1}, \ldots , m_{n}\right\}$. Let $C(x)$ be a formula with free variable $x$ of signature $\sigma_{M} = \sigma \cup M$. Prove that

Prove that if the algebraic system $\mathfrak {M}$ is finite, then for every sentence $A$ one can construct a quantifier-free sentence $A^{*}$ relative to $\mathfrak {M}$ such that $\mathfrak {M} \vDash (A \equiv A^{*})$.

Prove that if an algebraic system is finite, then for every formula one can check in finitely many steps whether it is satisfiable on this system or not.

Prove that a formula of the form $\forall x_{1} \ldots \forall x_{m} \, A(x_{1}, \ldots , x_{m})$, where $A(x_{1}, \ldots , x_{m})$ is a quantifier-free formula without function symbols or constants, is identically true if and only if it is true in every model of $m$ elements.

Prove that a formula of the form $\exists x_{1} \ldots \exists x_{m} \, A(x_{1}, \ldots , x_{m})$, where $A(x_{1}, \ldots , x_{m})$ is a quantifier-free formula without function symbols or constants, is identically true if and only if it is true in every one-element model.

Prove that a formula of the form

where $A(x_{1}, \ldots , x_{m}, y_{1}, \ldots , y_{n})$ is a quantifier-free formula without function symbols or constants, is identically true if and only if it is true in every model of $m$ elements.

Let $A$ be a formula of signature $\sigma = \langle P_{1}, \ldots , P_{n} \rangle$, where $P_{1}, \ldots , P_{n}$ are 1-ary predicate symbols. Prove that $A$ is satisfiable if and only if $A$ is satisfiable in a model containing at most $2^{n}$ elements.

Are the formulas satisfiable:

Let $\sigma = \langle P^{1}, \ldots , P^{n} \rangle$, where $P^{1}, \ldots , P^{n}$ are 1-ary predicate symbols. Prove that for every sentence $A$ of signature $\sigma$ there exists a formula $B$, equivalent to $A$, built by means of , $\vee$ and $\neg$ from $\exists$-constituents, i.e., formulas of the form $\exists x (B_{1} \& \ldots \& B_{s})$, where $s \geq 1$ and $B_{i}$ ($1 \leq i \leq s$) has the form $P(x)$ or $\neg P(x)$ for some $P$ of $\sigma$.

For an $\exists$-constituent $C$ (see Problem II.5.38), denote by $C(B_{1}, \ldots , B_{n})$ the formula obtained from $C$ by erasing the quantifier $\exists x$ and replacing all occurrences of the subformulas $P^{1}(x), \ldots , P^{n}(x)$ in $C$ by $B_{1}, \ldots , B_{n}$ respectively. Prove that the formula

where $C_{1}, \ldots , C_{k + m}$ are $\exists$-constituents, $k \geq 1$, $m \geq 0$, is satisfiable if and only if the formula of the algebra of propositions

is satisfiable.

Indicate a method for constructing, from any sentence $A$ with 1-ary predicates, a formula $B$ of the propositional calculus such that the satisfiability of the formula $A$ is equivalent to the satisfiability of $B$.

Using the method of Problem II.5.40, determine whether the following formulas are satisfiable:

Write a sentence of signature $\langle {=} \rangle$:

Let

Find an infinite system of formulas of signature $\langle {=} \rangle$ satisfiable only in infinite normal models.

Give an example of a formula that is false in every normal model with an odd number of elements, and such that for every even number $n$ there exists a normal model of cardinality $n$ on which this formula is true.