Math Problems Vault

Problem II.3.1

Construct derivations of the following sequents in SC:

?

(a)

$\vdash (A \supset A)$ ;

(b)

$(A \supset B), (B \supset C) \vdash (A \supset C)$ ;

(c)

$\vdash (\neg \neg A \equiv A)$ ;

(d)

$(A \supset (B \supset C)), (A \supset B), A \vdash C$ ;

(e)

$(A \supset B), \neg B \vdash \neg A$ ;

(f)

$A, \neg B \vdash \neg (A \supset B)$ .

Problem II.3.2

Prove the substitution rule for SC: if the sequent $A_{1}, \ldots , A_{n} \vdash B$ is derivable, $P$ is a variable and $C$ is any formula, then the sequent $A_{1}(P \backslash C), \ldots , A_{n}(P \backslash C) \vdash B(P \backslash C)$ is derivable.

?

Problem II.3.3

Prove that the following rules are admissible in SC:

?

(a)

$\dfrac {\Gamma_{1} \vdash A; \ \Gamma_{2}, A \vdash B}{\Gamma_{1}, \Gamma_{2} \vdash B}$ (cut);

(b)

$\dfrac {\Gamma , A, B \vdash C}{\Gamma , (A \& B) \vdash C}$ (combining premises);

(c)

$\dfrac {\Gamma , (A \& B) \vdash C}{\Gamma , A, B \vdash C}$ (splitting premises);

(d)

$\dfrac {\Gamma , A \vdash C; \ \Gamma , B \vdash C}{\Gamma , (A \vee B) \vdash C}$ (case analysis);

(e)

$\dfrac {\Gamma , A \vdash B}{\Gamma , \neg B \vdash \neg A}$ (contraposition);

(f)

$\dfrac {\Gamma , \neg B \vdash \neg A}{\Gamma , A \vdash B}$ (proof by contradiction);

(g)

$\dfrac {A_{1}, \ldots , A_{n} \vdash B}{\vdash ((A_{1} \& \ldots \& A_{n}) \supset B)}$ (introduction of and $\supset$ );

(h)

$\dfrac {\vdash ((A_{1} \& \ldots \& A_{n}) \supset B)}{A_{1}, \ldots , A_{n} \vdash B}$ (elimination of and $\neg$ ).

Problem II.3.4

Prove that if the rule $\dfrac {\Gamma_{1} \vdash A}{\Gamma_{2} \vdash A}$ is admissible in SC for every formula $A$ , then the rule $\dfrac {\Gamma_{1} \vdash }{\Gamma_{2} \vdash }$ is admissible in SC.

?

Problem II.3.5

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

Problem II.3.6

(a)(b)(c)

Prove that the following rules are admissible in SC:

?

(a)

$\dfrac {\Gamma , A \vdash B; \ \Gamma , B \vdash A}{\Gamma \vdash (A \equiv B)}$ ;

(b)

$\dfrac {\Gamma \vdash (A \equiv B)}{\Gamma , A \vdash B}$ ;

(c)

$\dfrac {\Gamma \vdash (A \equiv B)}{\Gamma , B \vdash A}$ .

Problem II.3.7

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

Problem II.3.8

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 the derivability in SC of the sequent $(B \equiv B_{1}) \vdash (A \equiv A_{1})$ (the replacement theorem for SC).

?

Problem II.3.9

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

Problem II.3.10

Let $A$ be a formula and $A_{1}$ its CNF (see 1). Prove the derivability in SC of the sequent $\vdash (A \equiv A_{1})$ .

?

Problem II.3.11

Prove that for every identically true CNF $A$ the sequent $\vdash A$ is derivable in SC.

?

Problem II.3.12

(a)(b)(c)

Prove that:

?

(a)

if the sequent $A_{1}, \ldots , A_{n} \vdash B$ is derivable in SC, then the formula $((A_{1} \& \ldots \& A_{n}) \supset B)$ is identically true;

(b)

if the sequent $\vdash B$ is derivable in SC, then the formula $B$ is identically true;

(c)

if the sequent $A_{1}, \ldots , A_{n} \vdash$ is derivable in SC, then the formula $\neg (A_{1} \& \ldots \& A_{n})$ is identically true.

Problem II.3.13

Prove that the sequent $\vdash A$ is derivable in SC if and only if $A$ is identically true (the completeness theorem for SC).

?

Problem II.3.14

Are the following sequents derivable in SC:

?

(a)

$\vdash ((P \vee Q) \supset (P \& R))$ ;

(b)

$\vdash (((P \supset Q) \supset Q) \supset P)$ ;

(c)

$\vdash (((P \supset Q) \supset Q) \supset Q)$ ;

(d)

$\vdash (\neg (P \vee \neg P) \supset (P \vee \neg P))$ ;

(e)

$P \vdash \neg (P \supset \neg P)$ ;

(f)

$(P \supset Q) \vdash (Q \supset P)$ ?

Problem II.3.15

Prove the interpolation theorem for SC: if the sequent $A \vdash B$ is provable and the sequents $A \vdash$ and $\vdash B$ are not provable, then there exists a formula $C$ , all of whose variables occur both in $A$ and in $B$ , such that the sequents $A \vdash C$ and $C \vdash B$ are provable (such a formula $C$ is called an interpolant).

?

Problem II.3.16

(a)(b)

Construct interpolants (see Problem II.3.15) for the following sequents:

?

(a)

$\neg (\neg Q \vee R) \vdash (P \supset Q)$ ;

(b)

$\neg (P \supset \neg (Q \& S)) \vdash ((S \supset (P \supset R)) \supset R)$ .

Problem II.3.17

(a)(b)(c)

Are the following sequences of formulas derivations in PC:

?

(a)

$(P \supset (P \vee Q))$ ;

(b)

$(P \supset (P \vee Q))$ , $((P \supset (P \vee Q)) \supset (P \supset (P \supset (P \vee Q))))$ , $(P \supset (P \supset (P \vee Q)))$ ;

(c)

$(P \supset (Q \supset P))$ , $((P \supset (P \vee Q)) \supset Q)$ , $Q$ ?

Problem II.3.18

(a)(b)(c)

Construct derivations of the following formulas in PC:

?

(a)

$(P \supset P)$ ;

(b)

$((P \vee P) \supset P)$ ;

(c)

$(P \supset \neg \neg P)$ .

Problem II.3.19

Prove that if $A$ is derivable in PC, then $A(P \backslash B)$ is derivable in PC for any variable $P$ and formula $B$ (the substitution rule).

?

Problem II.3.20

(a)(b)

Find the minimal set $\Gamma$ such that the following sequence is a derivation in PC from $\Gamma$ :

?

(a)

$(P \supset (Q \supset R))$ , $P$ , $(Q \supset R)$ , $Q$ , $R$ ;

(b)

$((P \supset \neg \neg Q) \supset (\neg Q \supset \neg P))$ , $(P \supset \neg \neg Q)$ , $(\neg Q \supset \neg P)$ , $\neg Q$ , $\neg P$ .

Problem II.3.21

Prove that $A \vdash A$ in PC.

?

Problem II.3.22

Prove that the following rules are admissible in PC:

?

(a)

$\dfrac {\Gamma \vdash A}{B, \Gamma \vdash A}$ ;

(b)

$\dfrac {B, B, \Gamma \vdash A}{B, \Gamma \vdash A}$ ;

(c)

$\dfrac {\Gamma , A, B, \Gamma_{1} \vdash C}{\Gamma , B, A, \Gamma_{1} \vdash C}$ ;

(d)

$\dfrac {\Gamma \vdash A; \ A, \Gamma_{1} \vdash B}{\Gamma , \Gamma_{1} \vdash B}$ ;

(e)

$\dfrac {A_{1}, \ldots , A_{n} \vdash B}{A_{1}(P \backslash C), \ldots , A_{n}(P \backslash C) \vdash B(P \backslash C)}$ .

Problem II.3.23

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

?

Problem II.3.24

Prove for PC:

?

(a)

$\Gamma , A, B \vdash (A \& B)$ (introduction of );

(b)

$\Gamma , A \vdash (A \vee B)$ (introduction of $\vee$ );

(c)

$\Gamma , B \vdash (A \vee B)$ (introduction of $\vee$ );

(d)

$\dfrac {\Gamma , A \vdash B; \ \Gamma , A \vdash \neg B}{\Gamma \vdash \neg A}$ (introduction of $\neg$ );

(e)

$\Gamma , (A \& B) \vdash A$ (elimination of );

(f)

$\Gamma , (A \& B) \vdash B$ (elimination of );

(g)

$\dfrac {\Gamma , A \vdash C; \ \Gamma , B \vdash C}{\Gamma , (A \vee B) \vdash C}$ (elimination of $\vee$ );

(h)

$\Gamma , \neg \neg A \vdash A$ (elimination of $\neg$ ).

Problem II.3.25

Prove that a set $\Gamma$ is consistent if and only if there exists a formula that is not derivable in PC from $\Gamma$ .

?

Problem II.3.26

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Problem II.3.27

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 the replacement theorem for PC:

(B \equiv B_{1}) \vdash (A \equiv A_{1}).

?

Problem II.3.28

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

(t)

(u)

(v)

Problem II.3.29

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

?

Problem II.3.30

(a)(b)(c)

Prove that:

?

(a)

if the sequent $A_{1}, \ldots , A_{n} \vdash B$ is derivable in SC, then $A_{1}, \ldots , A_{n} \vdash B$ in PC;

(b)

if the sequent $A_{1}, \ldots , A_{n} \vdash$ is derivable in SC, then $A_{1}, \ldots , A_{n} \vdash (B \& \neg B)$ in PC;

(c)

if the sequent $\vdash B$ is derivable in SC, then the formula $B$ is derivable in PC.

Problem II.3.31

(a)(b)

Prove that:

?

(a)

all axioms of PC are identically true;

(b)

all formulas derivable in PC are identically true.

Problem II.3.32

Prove the completeness theorem for PC: every identically true formula is derivable in PC.

?

Problem II.3.33

Find formulas $A$ and $B$ such that the derivability in PC of $A$ implies the derivability of $B$ , but it is not true that $A \vdash B$ .

?

Problem II.3.34

Let $A$ be a formula and $P_{1}, \ldots , P_{n}$ all of its variables. Prove that if $A$ is not derivable in PC, then there exist formulas $B_{1}, \ldots , B_{n}$ such that the formula $\neg A(P_{1} \backslash B_{1}, \ldots , P_{n} \backslash B_{n})$ is derivable in PC.

?

Problem II.3.35

(a)(b)(c)

Let $A$ and $B$ be formulas. Set

A \approx B \rightleftharpoons \vdash (A \equiv B) \text{ in PC}; \qquad \left\| A\right\| \rightleftharpoons \left\{ B \mid A \approx B\right\} .

Prove that:

?

(a)

$\approx$ is an equivalence relation on the set $F$ of all formulas;

(b)

the quotient set $F / {\approx } \rightleftharpoons \left\{ \left\| A\right\| \mid A \in F\right\}$ is a Boolean algebra, where $\left\| A\right\| \leq \left\| B\right\| \Leftrightarrow \vdash (A \supset B)$ in PC (this algebra is called the Lindenbaum algebra for PC);

(c)

$A$ is derivable in PC if and only if $\left\| A\right\|$ is the greatest element 1 of the algebra $F / {\approx }$ .

Problem II.3.36

Let $\mathfrak {B}$ be a Boolean algebra. Assign to it the logical matrix $\langle \mathfrak {B}; \left\{ 1\right\} , \& , \vee , \supset , \neg \rangle$ , where $x \& y = x \cap y$ , $x \vee y = x \cup y$ , $x \supset y = -x \cup y$ , $\neg x = -x$ . Prove that $A$ is derivable in PC if and only if $A$ is generally valid in all logical matrices corresponding to Boolean algebras.

?

Problem II.3.37

(a)(b)

?

(a)

Let $T$ be an ultrafilter on the Lindenbaum algebra $F / {\approx }$ (see Problem II.3.35). For an arbitrary variable $P$ , set the value of $P$ equal to $\text{T}$ if $\left\| P\right\| \in T$ , and $\text{F}$ otherwise. Prove that for every formula $A$

A \in T \Leftrightarrow A \text{ is true at these values of the variables}.

(b)

Deduce from (a) the completeness theorem for the calculus PC (see Problem II.3.32).

Problem II.3.38

Let $A$ be a formula, $\Delta$ a system of formulas, and $M$ a logical matrix. Prove that if all formulas of $\Delta$ are generally valid in $M$ , and a direct consequence of formulas generally valid in $M$ is a formula generally valid in $M$ , while the formula $A$ is not generally valid in $M$ , then $A$ is independent of $\Delta$ .

?

Problem II.3.39

Let $M = \left\{ 0, 1, 2\right\}$ , $D = \left\{ 0\right\}$ , $x \& y = \max \left\{ x, y\right\}$ , $x \vee y = \min \left\{ x, y\right\}$ , $x \supset y = \max \left\{ 0, y - x\right\}$ , $\neg x = 2 - x$ . Prove that the formula

A = ((P \supset (Q \supset R)) \supset ((P \supset Q) \supset (P \supset R)))

is independent of $\Delta$ , where $\Delta = \left\{ (P \supset (Q \supset P)), ((\neg P \supset \neg Q) \supset (Q \supset P))\right\}$ , using the logical matrix $\langle M; D, \& , \vee , \supset , \neg \rangle$ .

?

Problem II.3.40

Prove the independence of the axiom schemes of the calculus PC.

?

Problem II.3.41

(a)(b)(c)

Let $L$ be the propositional calculus with axiom schemes:

L1. $(A \supset (B \supset A))$ ,

L2. $((A \supset B) \supset ((A \supset (B \supset C)) \supset (A \supset C)))$ ,

L3. $((\neg A \supset \neg B) \supset (B \supset A))$

and rule of inference $\dfrac {A; \ (A \supset B)}{B}$ .

?

(a)

Prove that every formula derivable in $L$ is also derivable in PC.

(b)

Prove the deduction theorem for $L$ .

(c)

Set $(A \& B) = \neg (A \supset \neg B)$ , $(A \vee B) = (\neg A \supset B)$ . Prove that every formula derivable in PC is derivable in $L$ .

Problem II.3.42

(a)(b)

Prove that:

?

(a)

every formula derivable in IPC is derivable in PC;

(b)

$(\neg \neg P \supset P)$ , $(P \vee \neg P)$ are not derivable in IPC.

Problem II.3.43

For the calculus IPC, prove the deduction theorem: if $\Gamma , A \vdash_{\text{I}} B$ , then $\Gamma \vdash_{\text{I}} (A \supset B)$ .

?

Problem II.3.44

(a)(b)(c)(d)

Let ISC be the sequent calculus that differs from SC by the absence of rule 11. Prove that:

?

(a)

if the formula $A$ is derivable in IPC, then the sequent $\vdash A$ is derivable in ISC;

(b)

if the sequent $A_{1}, \ldots , A_{n} \vdash B$ is derivable in ISC, then $A_{1}, \ldots , A_{n} \vdash_{\text{I}} B$ ;

(c)

if the sequent $A_{1}, \ldots , A_{n} \vdash$ is derivable in ISC, then $A_{1}, \ldots , A_{n} \vdash_{\text{I}} (B \& \neg B)$ ;

(d)

if the sequent $\vdash B$ is derivable in ISC, then the formula $B$ is derivable in IPC.

Problem II.3.45

(a)(b)(c)

Prove that:

?

(a)

$\vdash_{\text{I}} (A \supset \neg \neg A)$ ;

(b)

$\vdash_{\text{I}} \neg \neg (\neg \neg A \supset A)$ ;

(c)

$\neg \neg A, \neg \neg (A \supset B) \vdash_{\text{I}} \neg \neg B$ .

Problem II.3.46

Prove that if the formula $A$ is derivable in PC, then the formula $\neg \neg A$ is derivable in IPC.

?

Problem II.3.47

(a)(b)

Let $M_{n} = \left\{ 0, 1, \ldots , n\right\}$ , $D = \left\{ 0\right\}$ , $x \& y = \max (x, y)$ , $x \vee y = \min (x, y)$ ,

x \supset y = \begin{cases} 0, & \text{if } x \geq y, \\ y, & \text{if } x < y, \end{cases} \qquad \neg x = \begin{cases} 0, & \text{if } x = n, \\ n, & \text{if } x < n. \end{cases}

Prove that:

?

(a)

every formula derivable in IPC is generally valid in $M_{n} = \langle M; D, \& , \vee , \supset , \neg \rangle$ ( $n = 1, 2, \ldots$ ).

(b)

the formulas

A_{n} = ((P_{1} \equiv P_{2}) \vee \ldots \vee (P_{1} \equiv P_{n + 1}) \vee \ldots \vee (P_{n} \equiv P_{n + 1}))

are not derivable in IPC ( $n = 1, 2, \ldots$ ).

Problem II.3.48

Let $M = \langle M; D, \& , \vee , \supset , \neg \rangle$ be a logical matrix such that the set of formulas generally valid in $M$ coincides with the set of formulas derivable in IPC. Prove that the set $M$ is infinite.

?