Predicate Calculi

Prove that every sequent derivable in SC is derivable in PrSC.

Let $A_{1}, \ldots , A_{n}, A$ be formulas of SC, $B$ a formula of PrSC, and $A'_{1}, \ldots , A'_{n}, A'$ the formulas obtained from $A_{1}, \ldots , A_{n}, A$ by substituting $B$ for the propositional variable $P$. Prove that if the sequent $A_{1}, \ldots , A_{n} \vdash A$ is derivable in SC, then $A'_{1}, \ldots , A'_{n} \vdash A'$ is derivable in PrSC.

Prove that the rules of Problems II.3.3 and II.3.6 are admissible in PrSC.

Let $y$ not be free in $A(x)$, let $y$ be free for $x$ in $A(x)$, and let $A(y)$ be obtained from $A(x)$ by replacing all free occurrences of $x$ by $y$. Construct derivations in PrSC of the sequents:

Let $y$ be free for $x$ in the formulas $A_{1}(x), \ldots , A_{n}(x), B(x)$. Prove that if $A_{1}(x), \ldots , A_{n}(x) \vdash B(x)$ is derivable in PrSC, then $A_{1}(y), \ldots , A_{n}(y) \vdash B(y)$ is derivable.

Prove that the following sequents are derivable in PrSC:

Let $A$ be a formula, $B$ a subformula of the formula $A$, $A_{1}$ the result of replacing some occurrence of $B$ in $A$ by the formula $B_{1}$, and $x_{1}, \ldots , x_{n}$ all the free variables of the formulas $A$ and $A_{1}$. Prove that the sequent $\forall x_{1}, \ldots , \forall x_{n} (B \equiv B_{1}) \vdash (A \equiv A_{1})$ is derivable in PrSC (the replacement theorem for PrSC).

Prove that for every formula $A$ there exists a prenex normal form $A'$ such that $\vdash (A \equiv A')$ is derivable in PrSC.

Find the prenex normal form for the following formulas:

Let $A$ be a formula built from atomic formulas and their negations by means of , $\vee$, and the quantifiers $\forall$ and $\exists$ over arbitrary variables. Let $A^{+}$ be the result of simultaneously replacing, in $A$, by $\vee$, $\vee$ by , $\forall$ by $\exists$, $\exists$ by $\forall$, and atomic formulas by their negations. Prove that the sequent $\vdash (A^{+} \equiv \neg A)$ is derivable in PrSC.

Let $A$ be a formula built from atomic formulas and their negations by means of , $\vee$, and the quantifiers $\forall$ and $\exists$ over arbitrary variables. Let $A'$ be the result of simultaneously replacing, in $A$, by $\vee$, $\vee$ by , $\forall$ by $\exists$, $\exists$ by $\forall$, and atomic formulas by their negations. Prove that in PrSC:

Show that a quasi-derivation in PrC from the empty set of formulas is a derivation in PrC.

Are the following sequences derivations in PrC:

What requirements must the formula $A(x)$ satisfy for the following sequence to be a derivation in PrC:

Prove that if $A_{1}, \ldots , A_{n}, A$ are formulas of PC, $B$ is a formula of PrC, $P$ is a propositional variable, and $A_{1}, \ldots , A_{n} \vdash A$ in PC, then $A_{1}(P \backslash B), \ldots , A_{n}(P \backslash B) \vdash A(P \backslash B)$ in PrC.

Construct derivations of the formulas in PrC:

Is the sequence of formulas a derivation from $\Gamma = \left\{ (C \supset A(x))\right\}$ in PrC, where $C$ contains no free occurrences of $x$:

Construct derivations from $\Gamma = \left\{ \forall x (A(x) \supset B(x))\right\}$ in PrC of the following formulas:

Prove that the following rules are admissible in PrC:

Prove the deduction theorem for PrC: if $\Gamma , A \vdash B$, then $\Gamma \vdash (A \supset B)$.

Prove that if in PrC $\Gamma \vdash A$ and $\Gamma , A \vdash B$, then $\Gamma \vdash B$.

Prove that the assertion of Problem II.3.24 of 3 holds in PrC.

Prove the following rules:

Prove that the formula $A(x)$ is derivable in PrC if and only if the formula $\forall x \, A(x)$ is derivable.

Let $z_{1}, \ldots , z_{n}$ not occur bound in $A(z_{1}, \ldots , z_{n})$ or in $B(z_{1}, \ldots , z_{n})$, and let $A(z_{1}, \ldots , z_{n}) \vdash B(z_{1}, \ldots , z_{n})$ in PrC. Prove that there exists a derivation of $B(z_{1}, \ldots , z_{n})$ from $A(z_{1}, \ldots , z_{n})$ in PrC in which $z_{1}, \ldots , z_{n}$ never occur bound.

Let $z_{1}, \ldots , z_{n}$ not occur bound in $A(z_{1}, \ldots , z_{n})$ or in $B(z_{1}, \ldots , z_{n})$; let $x_{1}, \ldots , x_{n}$ be variables not occurring bound in $A(z_{1}, \ldots , z_{n})$ or in $B(z_{1}, \ldots , z_{n})$. Prove that

Let $\Gamma$ be a set of formulas of signature $\sigma$, and $A$ a formula of signature $\sigma$. Prove that if $\Gamma \vdash A$ in PrC, then there exists a derivation of $A$ from $\Gamma$ in PrC consisting only of formulas of signature $\sigma$.

Prove that if the formula $A$ is derivable in PrC, then the sequent $\vdash A$ is derivable in PrSC.

Prove that:

Let $A$ be a formula, $B$ a subformula of the formula $A$, and $A'$ the result of replacing some occurrence of $B$ in $A$ by the formula $B'$. Prove that if $\vdash (B \equiv B')$, then $\vdash (A \equiv A')$ (the replacement theorem for PrC).

Prove that if $\Gamma \vdash A$ in PrC, then $\Gamma \vDash A$.

Prove that all formulas derivable in PrC are identically true.

Prove that if a set of formulas $\Gamma$ is satisfiable, then it is consistent. (A set $\Gamma$ is satisfiable if there exist an algebraic system $\mathfrak {M}$ and values in $\mathfrak {M}$ of the free variables such that all formulas of $\Gamma$ are true for these values of the variables.)

Prove that a set of formulas $\Gamma$ is inconsistent if and only if every formula is derivable in PrC from $\Gamma$.

Prove that if the sets of formulas $T_{0}, T_{1}, T_{2}, \ldots$ are consistent and $T_{i} \subseteq T_{i + 1}$ ($i = 0, 1, 2, \ldots$), then $\bigcup_{i \in \mathbb {N}} T_{i}$ is a consistent set of formulas.

Prove the Lindenbaum theorem: every consistent set of formulas $T$ can be extended to a complete consistent set of the same signature.

Let a set $\Gamma$ of formulas of signature $\sigma$ be complete and satisfy the condition: for every formula of signature $\sigma$ with one free variable $x$, if $\Gamma \vdash \exists x \, A(x)$, then $\Gamma \vdash A(t)$ for some closed term $t$ of signature $\sigma$. Prove that:

Let the set $\Gamma \cup \left\{ \exists x \, A(x)\right\}$ be consistent. Prove that if the variable $y$ does not occur in $\Gamma$ or in $\exists x \, A(x)$, then the set $\Gamma \cup \left\{ \exists x \, A(x), A(y)\right\}$ is consistent.

Prove that every consistent set of sentences is satisfiable (the model existence theorem).

Prove the Lowenheim--Skolem theorem: every satisfiable set of sentences is satisfiable in some countable algebraic system.

Prove that if the sentence $A$ is not derivable in PrC, then $\neg A$ is satisfiable on the natural numbers.

Prove that the formula $A$ is identically true if and only if $A$ is derivable in PrC (Godel's completeness theorem for PrC).

Show that if the sentence $A$ is true in every system on the natural numbers, then $A$ is identically true.

Prove that if the sentence $A$ is satisfiable in some system, then $A$ is satisfiable on the natural numbers.

Prove that if the sentence $A$ is true in every system on which the formulas of a countable set $\Gamma$ are true, then $\Gamma \vdash A$.

Prove that if a set of sentences $\Gamma$ is countable and every finite subset $\Gamma_{1} \subseteq \Gamma$ is satisfiable, then the whole set $\Gamma$ is satisfiable (Mal'tsev's local theorem).

Prove that if the negation of every conjunction of finitely many sentences of a countable set $\Gamma$ is unprovable in PrC, then the set $\Gamma$ is satisfiable.

Prove, for every sentence $A$ and every countable set $\Gamma$,

(the adequacy theorem).

Prove that if $\Gamma$ is a countable set of sentences and $\Gamma \vdash A$, then $\Gamma_{1} \vdash A$ for some finite subset $\Gamma_{1} \subseteq \Gamma$ (Mal'tsev's compactness theorem).

Prove that, for $A$ to be derivable in PrC, it is not sufficient that $A$ be true in every finite system.

Let $A$ be a quantifier-free formula of PrC. Prove that $A$ is derivable in PrC if and only if $A$ is derivable using only axioms 1--10 by rule I.

Are the formulas derivable in PrC: