Банк задач по математике

Задача II.7.1

(а)(б)

Доказать, что в ИПР сигнатуры $\sigma$ выводимы:

?

(а)

$((x_{1} = y_{1} \& \ldots \& x_{n} = y_{n}) \supset t(x_{1}, \ldots , x_{n}) = t(y_{1}, \ldots , y_{n}))$ для любого терма $t$ сигнатуры $\sigma$ ;

(б)

$((x_{1} = y_{1} \& \ldots \& x_{n} = y_{n}) \supset (A(x_{1}, \ldots , x_{n}) \equiv A(y_{1}, \ldots , y_{n})))$ для любой формулы $A$ сигнатуры $\sigma$ .

Задача II.7.2

Доказать, что если $\Gamma$ --- множество аксиом теории $T$ сигнатуры $\sigma$ , $\mathfrak {M}$ --- алгебраическая система сигнатуры $\sigma$ , в которой истинны все формулы из $\Gamma$ , то в $\mathfrak {M}$ истинны все теоремы теории $T$ .

?

Задача II.7.3

Пусть предложение $A$ истинно в любой системе, в которой истинны все аксиомы теории $T$ . Доказать, что $A$ принадлежит $T$ .

?

Задача II.7.4

Доказать, что если все аксиомы теории $T$ истинны в некоторой алгебраической системе, то существует модель теории $T$ .

?

Задача II.7.5

Доказать, что всякая непротиворечивая теория имеет модель.

?

Задача II.7.6

Доказать, что если предложение $A$ истинно во всех моделях теории $T$ , то $A$ есть теорема теории $T$ (теорема о полноте ИПР).

?

Задача II.7.7

(а)(б)

Пусть предложение $\forall x_{1} \ldots \forall x_{n} \exists ! y \, A(x_{1}, \ldots , x_{n}, y)$ есть теорема теории $T$ сигнатуры $\sigma$ . Пусть теория $T_{1}$ сигнатуры $\sigma ' = \sigma \cup \left\{ f^{n}\right\}$ , где $f^{n} \notin \sigma$ , имеет в качестве аксиом все аксиомы теории $T$ и

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

?

(а)

Доказать, что для любой формулы $B$ сигнатуры $\sigma '$ существует формула $B^{*}$ сигнатуры $\sigma$ , удовлетворяющая условиям:

если $f^{n}$ не входит в $B$ , то $B^{*} = B$ ;
$(B^{*} \equiv B)$ есть теорема теории $T_{1}$ .

(б)

Доказать, что если $B$ не содержит $f^{n}$ и является теоремой теории $T_{1}$ , то $B$ является теоремой $T$ .

Задача II.7.8

Доказать, что если элементарная теория $T$ имеет бесконечную модель, то $T$ имеет и счетную модель.

?

Задача II.7.9

Доказать, что теория $T$ имеет модель тогда и только тогда, когда каждое конечное подмножество $T_{1} \subseteq T$ выполнимо.

?

Задача II.7.10

Доказать, что если теория $T$ для любого натурального числа $n$ имеет модель мощности, большей $n$ , то эта теория имеет бесконечную модель.

?

Задача II.7.11

Доказать, что не существует предложения, истинного во всех конечных моделях и ложного в любой бесконечной модели.

?

Задача II.7.12

Доказать, что если предложение $A$ истинно во всех бесконечных группах, то $A$ истинно во всех конечных группах достаточно большого порядка.

?

Задача II.7.13

Доказать, что теория равенства $E$ неполна.

?

Задача II.7.14

Доказать, что предложение $A$ сигнатуры $\langle {=} \rangle$ истинно во всех нормальных системах тогда и только тогда, когда $A$ есть теорема теории $E$ .

?

Задача II.7.15

Построить алгоритм, позволяющий по любому предложению сигнатуры $\langle {=} \rangle$ узнавать, является ли это предложение теоремой теории $E$ .

?

Задача II.7.16

(а)(б)

Являются ли следующие предложения теоремами теории $E$ :

?

(а)

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

(б)

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

Задача II.7.17

Пусть сигнатура $\sigma$ содержит один двуместный предикат $P$ , $T$ есть множество предложений, выводимых из $\Gamma = \left\{ A_{1}, A_{2}\right\}$ , где

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))).

Является ли $T$ полной теорией?

?

Задача II.7.18

Доказать, что $Q$ --- непротиворечивая теория.

?

Задача II.7.19

Является ли система предложений $\left\{ Q_{1}, \ldots , Q_{7}\right\}$ независимой?

?

Задача II.7.20

Доказать, что в теории $Q$ невыводимы формулы:

?

(а)

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

(б)

$0 + x = x$ ;

(в)

$\mathbf{s}(x + y) = \mathbf{s}(x) \cdot y$ ;

(г)

$x + y = y + x$ ;

(д)

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

(е)

$x \leq x$ ;

(ж)

$0 \cdot x = 0$ ;

(з)

$\mathbf{s}(x) \cdot y = x \cdot y + y$ ;

(и)

$x \cdot y = y \cdot x$ ;

(к)

$(x \cdot y) \cdot z = x \cdot (y \cdot z)$ ;

(л)

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

(м)

$(x + y) \cdot z = x \cdot z + y \cdot z$ .

Задача II.7.21

(а)(б)

Доказать выводимость в $Q$ формул:

?

(а)

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

(б)

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

Задача II.7.22

Доказать, что всякая модель теории $Q$ бесконечна.

?

Задача II.7.23

(а)(б)(в)(г)

Определить константу 0 и функции $\mathbf{s}, +$ и $\cdot$ так, чтобы моделью теории $Q$ стало множество:

?

(а)

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

(б)

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

(в)

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

(г)

$\mathbb {N} \cup \mathbb {N}' = \left\{ 0, 1, 2, \ldots ; a_{0}, a_{1}, a_{2}, \ldots \right\}$ ( $a_{i} \notin \mathbb {N}$ для всех $i$ и $a_{i} \neq a_{j}$ при $i \neq j$ ).

Задача II.7.24

(а)(б)(в)

Можно ли определить константу 0 и функции $\mathbf{s}, +$ и $\cdot$ так, чтобы моделью теории $Q$ стало:

?

(а)

множество всех целых чисел;

(б)

множество всех неотрицательных рациональных чисел;

(в)

множество всех рациональных чисел?

Задача II.7.25

Доказать, что теория $P$ непротиворечива.

?

Задача II.7.26

Доказать зависимость аксиом теории $P$ .

?

Задача II.7.27

Доказать, что все формулы из задачи II.7.20 являются теоремами теории $P$ .

?

Задача II.7.28

Доказать, что существует нестандартная (т.е. неизоморфная системе $\mathfrak {N}$ ) модель теории $P$ .

?

Задача II.7.29

(а)(б)

Доказать, что следующие формулы являются теоремами $P$ :

?

(а)

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

(б)

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

Задача II.7.30

Доказать, что следующие формулы являются теоремами $P$ :

?

(а)

$0 \leq x$ ;

(б)

$((x \leq y \& y \leq z) \supset x \leq z)$ ;

(в)

$((x \leq y \& y \leq x) \supset x = y)$ ;

(г)

$(x \leq y \vee y \leq x)$ ;

(д)

$\neg x < x$ ;

(е)

$x < \mathbf{s}(x)$ ;

(ж)

$0 < \mathbf{s}(x)$ ;

(з)

$(x < y \vee \neg y < x)$ ;

(и)

$(x < y \vee y < x \vee x = y)$ ;

(к)

$(x < y \equiv \mathbf{s}(x) \leq y)$ ;

(л)

$x \leq x + y$ ;

(м)

$(x < y \equiv x + z < y + z)$ ;

(н)

$(\neg y = 0 \supset x \leq x \cdot y)$ ;

(о)

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

Задача II.7.31

(а)(б)(в)

Доказать, что для любой формулы $A(x)$ с одной свободной переменной $x$ следующие формулы являются теоремами $P$ :

?

(а)

$(\forall x (\forall z (z < x \supset A(z)) \supset A(x)) \supset \forall x \, A(x))$ (возвратная индукция);

(б)

$(\exists x \, A(x) \supset \exists y (A(y) \& \forall z (z < y \supset \neg A(z))))$ (принцип наименьшего числа);

(в)

$(\forall x (A(x) \supset \exists y (y < x \& A(y))) \supset \forall x \, \neg A(x))$ (метод бесконечного спуска).

Задача II.7.32

(а)(б)

Введем следующие сокращения:

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)).

Доказать, что следующие формулы являются теоремами $P$ :

?

(а)

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

(б)

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

Задача II.7.33

Записать формулу $\text{Пр}(x)$ такую, что $\text{Пр}(\Delta_{n})$ является теоремой теории $P$ тогда и только тогда, когда $n$ --- простое число.

?

Задача II.7.34

Введем следующие сокращения:

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)).

Доказать, что следующие формулы являются теоремами $P$ :

?

(а)

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

(б)

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

(в)

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

(г)

$\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)))$ ;

(д)

$\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}))$ ;

(е)

$\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)$ .

Задача II.7.35

Доказать, что любая теорема теории $R$ является теоремой теории $Q$ .

?

Задача II.7.36

Будет ли независимой система формул

\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\} ?

?

Задача II.7.37

Доказать, что стандартная модель арифметики изоморфно вложима в любую модель теории $Q$ .

?

Задача II.7.38

Доказать в ZF:

?

(а)

существование и единственность пустого множества 0:

\exists ! x (x = 0);

(б)

существование и единственность пары:

\forall x \forall y \exists ! z (z = \left\{ x, y\right\} );

(в)

существование и единственность $\left\{ x\right\}$ :

\forall x \exists ! y (y = \left\{ x\right\} );

(г)

аксиому упорядоченной пары:

(\langle x, y \rangle = \langle z, u \rangle \supset (x = z \& y = u));

(д)

аксиому упорядоченной $n$ -ки:

(\langle x_{1}, \ldots , x_{n} \rangle = \langle y_{1}, \ldots , y_{n} \rangle \supset (x_{1} = y_{1} \& \ldots \& x_{n} = y_{n}));

(е)

существование и единственность множества подмножеств:

\forall x \exists ! y (y = \mathcal{P}(x));

(ж)

существование и единственность прямого произведения:

\forall x \forall y \exists ! z (z = x \times y);

(з)

существование и единственность прямого произведения:

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

(и)

существование и единственность области определения функции:

\forall x (\mathrm{Fn}(x) \supset \exists ! y (y = \delta (x)));

(к)

существование и единственность $\cup x$ :

\forall x \exists ! y (y = \cup x);

(л)

существование и единственность $x \cup y$ :

\forall x \forall y \exists ! z (z = x \cup y);

(м)

существование и единственность $x \cap y$ :

\forall x \forall y \exists ! z (z = x \cap y);

(н)

существование и единственность $\cap x$ для $x \neq 0$ :

\forall x (\neg x = 0 \supset \exists ! y (y = \cap x)).

Задача II.7.39

(а)(б)(в)

Доказать в ZF следующие теоремы:

?

(а)

$\neg x \in x$ ;

(б)

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

(в)

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

Задача II.7.40

Доказать, что следующие утверждения об ординальных числах являются теоремами ZF:

?

(а)

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

(б)

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

(в)

$(\mathrm{Ord}(x) \supset W(x))$ , где $W(x)$ есть формула, означающая, что $\in$ есть полный иррефлексивный порядок на $x$ ;

(г)

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

(д)

$((\mathrm{Ord}(x) \& \forall y (\forall z (z \in y \supset A(z)) \supset A(y))) \supset A(x))$ , где $A(x)$ --- формула с одной свободной переменной $x$ (трансфинитная индукция);

(е)

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

(ж)

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

(з)

$((\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))$ .

Задача II.7.41

Доказать в ZF следующие теоремы:

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

Задача II.7.42

Доказать в ZF следующие теоремы:

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

Задача II.7.43

Доказать в ZF принцип индукции для натуральных чисел: для любой формулы $A(x)$ с одной свободной переменной $x$

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

?

Задача II.7.44

Доказать в ZF следующие теоремы:

?

(а)

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

(б)

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

(в)

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

(г)

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

(д)

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

(е)

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

Задача II.7.45

Доказать, что если $A$ есть теорема теории $P$ , то формула $\rho_{N}(A)$ , полученная из $A$ релятивизацией кванторов относительно $N$ , есть теорема теории ZF.

?

Аксиоматические теории