Math Problems Vault

Problem II.7.1

(a)(b)

Prove that the following are derivable in PrCE of signature $\sigma$ :

?

(a)

$((x_{1} = y_{1} \& \ldots \& x_{n} = y_{n}) \supset t(x_{1}, \ldots , x_{n}) = t(y_{1}, \ldots , y_{n}))$ for every term $t$ of signature $\sigma$ ;

(b)

$((x_{1} = y_{1} \& \ldots \& x_{n} = y_{n}) \supset (A(x_{1}, \ldots , x_{n}) \equiv A(y_{1}, \ldots , y_{n})))$ for every formula $A$ of signature $\sigma$ .

Problem II.7.2

Prove that if $\Gamma$ is a set of axioms of the theory $T$ of signature $\sigma$ , and $\mathfrak {M}$ is an algebraic system of signature $\sigma$ in which all formulas of $\Gamma$ are true, then all theorems of the theory $T$ are true in $\mathfrak {M}$ .

?

Problem II.7.3

Let the sentence $A$ be true in every system in which all axioms of the theory $T$ are true. Prove that $A$ belongs to $T$ .

?

Problem II.7.4

Prove that if all axioms of the theory $T$ are true in some algebraic system, then there exists a model of the theory $T$ .

?

Problem II.7.5

Prove that every consistent theory has a model.

?

Problem II.7.6

Prove that if the sentence $A$ is true in every model of the theory $T$ , then $A$ is a theorem of the theory $T$ (the completeness theorem for PrCE).

?

Problem II.7.7

(a)(b)

Let the sentence $\forall x_{1} \ldots \forall x_{n} \exists ! y \, A(x_{1}, \ldots , x_{n}, y)$ be a theorem of the theory $T$ of signature $\sigma$ . Let the theory $T_{1}$ of signature $\sigma ' = \sigma \cup \left\{ f^{n}\right\}$ , where $f^{n} \notin \sigma$ , have as axioms all axioms of the theory $T$ and

\forall x_{1} \ldots \forall x_{n} \, A(x_{1}, \ldots , x_{n}, f^{n}(x_{1}, \ldots , x_{n})).

?

(a)

Prove that for every formula $B$ of signature $\sigma '$ there exists a formula $B^{*}$ of signature $\sigma$ satisfying the conditions:

if $f^{n}$ does not occur in $B$ , then $B^{*} = B$ ;
$(B^{*} \equiv B)$ is a theorem of the theory $T_{1}$ .

(b)

Prove that if $B$ does not contain $f^{n}$ and is a theorem of the theory $T_{1}$ , then $B$ is a theorem of $T$ .

Problem II.7.8

Prove that if an elementary theory $T$ has an infinite model, then $T$ also has a countable model.

?

Problem II.7.9

Prove that the theory $T$ has a model if and only if every finite subset $T_{1} \subseteq T$ is satisfiable.

?

Problem II.7.10

Prove that if, for every natural number $n$ , the theory $T$ has a model of cardinality greater than $n$ , then this theory has an infinite model.

?

Problem II.7.11

Prove that there is no sentence true in every finite model and false in every infinite model.

?

Problem II.7.12

Prove that if the sentence $A$ is true in every infinite group, then $A$ is true in every finite group of sufficiently large order.

?

Problem II.7.13

Prove that the theory of equality $E$ is incomplete.

?

Problem II.7.14

Prove that a sentence $A$ of signature $\langle {=} \rangle$ is true in every normal system if and only if $A$ is a theorem of the theory $E$ .

?

Problem II.7.15

Construct an algorithm that, for any sentence of signature $\langle {=} \rangle$ , determines whether this sentence is a theorem of the theory $E$ .

?

Problem II.7.16

(a)(b)

Are the following sentences theorems of the theory $E$ :

?

(a)

$\forall x \exists y \forall z (\neg z = x \vee \neg y = z)$ ;

(b)

$\forall x \exists y \forall z \exists v (v = z \& \neg (z = x \& \neg x = y \& v = y))$ ?

Problem II.7.17

Let the signature $\sigma$ contain a single 2-ary predicate $P$ , and let $T$ be the set of sentences derivable from $\Gamma = \left\{ A_{1}, A_{2}\right\}$ , where

A_{1} = \forall x \forall y (P(x, y) \supset \neg P(y, x)),

A_{2} = \forall x \forall y \forall z (P(x, y) \supset (P(y, z) \supset P(x, z))).

Is $T$ a complete theory?

?

Problem II.7.18

Prove that $Q$ is a consistent theory.

?

Problem II.7.19

Is the system of sentences $\left\{ Q_{1}, \ldots , Q_{7}\right\}$ independent?

?

Problem II.7.20

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

Problem II.7.21

(a)(b)

Prove the derivability in $Q$ of the formulas:

?

(a)

$(x + y = 0 \supset (x = 0 \& y = 0))$ ;

(b)

$(x \cdot y = 0 \supset (x = 0 \vee y = 0))$ .

Problem II.7.22

Prove that every model of the theory $Q$ is infinite.

?

Problem II.7.23

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

Define the constant 0 and the functions $\mathbf{s}, +$ and $\cdot$ so that the model of the theory $Q$ becomes the set:

?

(a)

$\mathbb {N} = \left\{ 0, 1, 2, \ldots \right\}$ ;

(b)

$\mathbb {N} \cup \left\{ a\right\} = \left\{ 0, 1, 2, \ldots ; a\right\}$ ( $a \notin \mathbb {N}$ );

(c)

$\mathbb {N} \cup \left\{ a, b\right\} = \left\{ 0, 1, 2, \ldots ; a, b\right\}$ ( $a, b \notin \mathbb {N}$ );

(d)

$\mathbb {N} \cup \mathbb {N}' = \left\{ 0, 1, 2, \ldots ; a_{0}, a_{1}, a_{2}, \ldots \right\}$ ( $a_{i} \notin \mathbb {N}$ for all $i$ and $a_{i} \neq a_{j}$ for $i \neq j$ ).

Problem II.7.24

(a)(b)(c)

Can the constant 0 and the functions $\mathbf{s}, +$ and $\cdot$ be defined so that the model of the theory $Q$ becomes:

?

(a)

the set of all integers;

(b)

the set of all nonnegative rational numbers;

(c)

the set of all rational numbers?

Problem II.7.25

Prove that the theory $P$ is consistent.

?

Problem II.7.26

Prove the dependence of the axioms of the theory $P$ .

?

Problem II.7.27

Prove that all formulas of Problem II.7.20 are theorems of the theory $P$ .

?

Problem II.7.28

Prove that there exists a nonstandard (i.e., not isomorphic to the system $\mathfrak {N}$ ) model of the theory $P$ .

?

Problem II.7.29

(a)(b)

Prove that the following formulas are theorems of $P$ :

?

(a)

$(x + y = y + z \supset x = y)$ ;

(b)

$(\neg z = 0 \supset (x \cdot z = y \cdot z \supset x = y))$ .

Problem II.7.30

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

Problem II.7.31

(a)(b)(c)

Prove that for every formula $A(x)$ with one free variable $x$ , the following formulas are theorems of $P$ :

?

(a)

$(\forall x (\forall z (z < x \supset A(z)) \supset A(x)) \supset \forall x \, A(x))$ (strong induction);

(b)

$(\exists x \, A(x) \supset \exists y (A(y) \& \forall z (z < y \supset \neg A(z))))$ (the least-number principle);

(c)

$(\forall x (A(x) \supset \exists y (y < x \& A(y))) \supset \forall x \, \neg A(x))$ (the method of infinite descent).

Problem II.7.32

(a)(b)

Let us introduce the following abbreviations:

x = \mathrm{rest}(y, z) \rightleftharpoons ((x < z \& \exists u (y = u \cdot z + x)) \vee (z = 0 \& x = y));

z = \left\lfloor \frac{x}{y} \right\rfloor \rightleftharpoons (\exists u (u < y \& x = z \cdot y + u) \vee (y = 0 \& x = z)).

Prove that the following formulas are theorems of $P$ :

?

(a)

$\forall x \forall y \exists ! z (z = \mathrm{rest}(y, x))$ ;

(b)

$\forall x \forall y \exists ! \left( z = \left\lfloor \dfrac {x}{y} \right\rfloor \right)$ .

Problem II.7.33

Write a formula $\mathrm{Pr}(x)$ such that $\mathrm{Pr}(\Delta_{n})$ is a theorem of the theory $P$ if and only if $n$ is a prime number.

?

Problem II.7.34

Let us introduce the following abbreviations:

x / y \rightleftharpoons \exists z (y = x \cdot z);

z = d(x, y) \rightleftharpoons (z / x \& z / y \& \forall u ((u / x \& u / y) \supset u / z));

z = d_{n}(x_{1}, \ldots , x_{n}) \rightleftharpoons \exists u (z = d(x_{1}, u) \& u = d_{n - 1}(x_{2}, \ldots , x_{n})) \quad (n > 2);

u = \beta (x, y, z) \rightleftharpoons u = \mathrm{rest}(x, 1 + y \cdot (z + 1)).

Prove that the following formulas are theorems of $P$ :

?

(a)

$\forall x_{1}, \ldots , \forall x_{n} \exists ! y (y = d_{n}(x_{1}, \ldots , x_{n}))$ ;

(b)

$\forall x \forall y \forall z \exists ! u (u = \beta (x, y, z))$ ;

(c)

$\forall x \forall y \forall z \forall u ((z = d(x, y) \& u = \mathrm{rest}(x, y)) \supset z = d(y, u))$ ;

(d)

$\forall x \forall y ((\neg x = 0 \& \neg y = 0 \& d(x, y) = \mathbf{s}(0)) \supset \exists z \exists u \exists v \exists w (x \cdot z = y \cdot u + \mathbf{s}(0) \& y \cdot v = x \cdot w + \mathbf{s}(0)))$ ;

(e)

$\forall x_{1}, \ldots , \forall x_{n} \forall y_{1}, \ldots , \forall y_{n} ((d_{n}(x_{1}, \ldots , x_{n}) = \Delta_{1} \& y_{1} < x_{1} \& \ldots \& y_{n} < x_{n}) \supset \exists z (\mathrm{rest}(z, x_{1}) = y_{1} \& \ldots \& \mathrm{rest}(z, x_{n}) = y_{n}))$ ;

(f)

$\forall x \forall y \forall z \forall u \exists x_{1} \exists y_{1} (\forall v (v \leq z \supset \beta (x, y, v) = \beta (x_{1}, y_{1}, v)) \& \beta (x_{1}, y_{1}, \mathbf{s}(z)) = u)$ .

Problem II.7.35

Prove that every theorem of the theory $R$ is a theorem of the theory $Q$ .

?

Problem II.7.36

Is the system of formulas

\left\{ R_{1}^{(np)} \mid n, p \in \mathbb {N}\right\} \cup \left\{ R_{2}^{(np)} \mid n, p \in \mathbb {N}\right\} \cup \left\{ R_{3}^{(np)} \mid n, p \in \mathbb {N}, n \neq p\right\} \cup \left\{ R_{4}^{(n)} \mid n \in \mathbb {N}\right\} \cup \left\{ R_{5}^{(n)} \mid n \in \mathbb {N}\right\}

independent?

?

Problem II.7.37

Prove that the standard model of arithmetic is isomorphically embeddable in every model of the theory $Q$ .

?

Problem II.7.38

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

Problem II.7.39

(a)(b)(c)

Prove in ZF the following theorems:

?

(a)

$\neg x \in x$ ;

(b)

$\neg (x \in y \& y \in x)$ ;

(c)

$\neg (x \in y \& y \in z \& z \in x)$ .

Problem II.7.40

Prove that the following statements about ordinal numbers are theorems of ZF:

?

(a)

$(\mathrm{Ord}(z) \supset (y \in z \supset (x \in y \supset x \in z)))$ ;

(b)

$((\mathrm{Ord}(x) \& y \in x) \supset \mathrm{Ord}(y))$ ;

(c)

$(\mathrm{Ord}(x) \supset W(x))$ , where $W(x)$ is a formula meaning that $\in$ is a total irreflexive order on $x$ ;

(d)

$((\mathrm{Ord}(x) \& y = x \cup \left\{ x\right\} ) \supset \mathrm{Ord}(y))$ ;

(e)

$((\mathrm{Ord}(x) \& \forall y (\forall z (z \in y \supset A(z)) \supset A(y))) \supset A(x))$ , where $A(x)$ is a formula with one free variable $x$ (transfinite induction);

(f)

$((\mathrm{Ord}(x) \& \mathrm{Ord}(y)) \supset (x \in y \vee y \in x \vee x = y))$ ;

(g)

$((\mathrm{Ord}(x) \& \neg x = 0) \supset 0 \in x)$ ;

(h)

$((\mathrm{Ord}(x) \& \mathrm{Ord}(y) \& x \in y) \supset \forall u \forall v ((M_{A}(u, x) \& M_{A}(v, y)) \supset u = v))$ .

Problem II.7.41

Prove in ZF the following theorems:

?

(a)

$(\forall y (y \in x \supset \mathrm{Ord}(y)) \supset \mathrm{Ord}(\cup x))$ ;

(b)

$((\neg x = 0 \& \forall y (y \in x \supset \mathrm{Ord}(y))) \supset \mathrm{Ord}(\cap x))$ ;

(c)

$\exists x \, L(x)$ ;

(d)

$\exists ! x (x = \omega )$ ;

(e)

$(\mathrm{Ord}(\omega ) \& 0 \in \omega \& \forall x (x \in \omega \supset x \cup \left\{ x\right\} \in \omega ))$ .

Problem II.7.42

Prove in ZF the following theorems:

?

(a)

$(N(x) \supset \mathrm{Ord}(x))$ ;

(b)

$((N(x) \& y \in x) \supset N(y))$ ;

(c)

$\forall x (N(x) \supset \exists ! y (N(y) \& y = \mathbf{s}(x)))$ ;

(d)

$((N(x) \& N(y) \& \mathbf{s}(x) = \mathbf{s}(y)) \supset x = y)$ ;

(e)

$\neg \mathbf{s}(x) = 0$ ;

(f)

$((N(x) \& \neg x = 0) \supset \exists y (N(y) \& x = \mathbf{s}(y)))$ .

Problem II.7.43

Prove in ZF the induction principle for natural numbers: for every formula $A(x)$ with one free variable $x$ ,

((A(0) \& \forall x ((N(x) \& A(x)) \supset A(\mathbf{s}(x)))) \supset \forall y (N(y) \supset A(y))).

?

Problem II.7.44

Prove in ZF the following theorems:

?

(a)

$\forall x \forall y ((N(x) \& N(y)) \supset \exists ! z (N(z) \& x + y = z))$ ;

(b)

$\forall x (N(x) \supset x + 0 = x)$ ;

(c)

$\forall x \forall y ((N(x) \& N(y)) \supset x + \mathbf{s}(y) = \mathbf{s}(x + y))$ ;

(d)

$\forall x \forall y ((N(x) \& N(y)) \supset \exists ! z (N(z) \& x \cdot y = z))$ ;

(e)

$\forall x (N(x) \supset x \cdot 0 = 0)$ ;

(f)

$\forall x \forall y ((N(x) \& N(y)) \supset x \cdot \mathbf{s}(y) = x \cdot y + x)$ .

Problem II.7.45

Prove that if $A$ is a theorem of the theory $P$ , then the formula $\rho_{N}(A)$ , obtained from $A$ by relativizing the quantifiers with respect to $N$ , is a theorem of the theory ZF.

?