Эпсилон-индукция

редактировать

В математике, $∈ {\ displaystyle \ in}$ $\ in$ -индукция (эпсилон-индукция или индукция множеств ) является вариантом трансфинитной индукции.

Рассматриваемая как альтернативная схема аксиомы теории множеств, она называется аксиомой (схемой) (множества) индукция .

Ее можно использовать в теории множеств, чтобы доказать, что все множества удовлетворяют заданному свойству P (x). Это частный случай обоснованной индукции.

Содержание

1 Утверждение
- 1.1 Сравнение с индукцией натурального числа
2 Независимость
3 См. Также

Утверждение

Он утверждает для любого свойства P, что если для каждого набора x истинность P (x) следует из истинности P для всех элементов x, то это свойство P выполняется для всех множеств. В условных обозначениях:

∀ x. ((∀ Y ∈ Икс. П (Y)) → п (х)) → ∀ Z P (z) {\ Displaystyle \ forall x. {\ Big (} \ left (\ forall y \ in x. \, P (y) \ right) \ rightarrow P (x) {\ Big)} \ \ rightarrow \ \ forall z \, P (z)}

{\ Displaystyle \ forall x. {\ Big (} \ left (\ forall y \ in x. \, P (y) \ right) \ rightarrow P (x) {\ Big)} \ \ rightarrow \ \ forall z \, P (z)}

Обратите внимание, что для «нижнего случая», где x обозначает пустой положим, $∀ y ∈ x. P (y) {\ displaystyle \ forall y \ in x. \, P (y)}$ ${\ displaystyle \ forall y \ in x. \, P (y)}$ равно истинно пусто.

Сравнение с индукцией натурального числа

Приведенное выше может сравнивать с $ω {\ displaystyle \ omega}$ $\ omega$ -индукцией по натуральным числам $n ∈ {0, 1, 2,…} {\ displaystyle n \ в \ {0,1,2, \ dots \}}$ ${\ displaystyle n \ in \ {0,1,2, \ dots \}}$ для числовых свойств Q. Это может быть выражено как

(Q (0) ∧ ∀ n. (Q (n - 1) → Q (n))) → ∀ m. Q (m) {\ displaystyle {\ Big (} Q (0) \ land \ forall n. (Q (n-1) \ to Q (n)) {\ Big)} \ \ to \ \ forall m. \, Q (m)}

{\ displaystyle {\ Big (} Q (0) \ land \ forall n. (Q (n-1) \ to Q (n)) {\ Big) } \ \ к \ \ forall m. \, Q (m)}

или, как вариант,

∀ n. (Q (n - 1) → Q (n)) → ∀ m. Q (m) {\ displaystyle \ forall n. {\ Big (} Q (n-1) \ to Q (n) {\ Big)} \ \ to \ \ forall m. \, Q (m)}

{\ displaystyle \ forall n. {\ Big (} Q (n-1) \ to Q (n) {\ Big) } \ \ to \ \ forall m. \, Q (m)}

где для "нижнего регистра" n = 0 мы берем " $Q (- 1) {\ displaystyle Q (-1)}$ ${\ displaystyle Q (-1)}$ " как истинное по определению. Обратите внимание, что индукция множеств также может рассматриваться таким образом, чтобы явно рассматривать нижний случай.

С классическими тавтологиями, такими как $(A → B) ⟺ (¬ A ∨ B) {\ displaystyle (A \ to B) \ iff (\ neg A \ lor B)}$ ${\ displaystyle (A \ to B) \ iff (\ neg A \ lor B)}$ , приведенный выше принцип $ω {\ displaystyle \ omega}$ $\ omega$ -индукции можно перевести в следующее утверждение:

∃ n. (Q (n - 1) ∧ ¬ Q (n)) ∨ ∀ м. Q (м) {\ Displaystyle \ существует п. {\ Big (} Q (n-1) \ land \ neg Q (n) {\ Big)} \ \ lor \ \ forall m. \, Q (m)}

{\ displaystyle \ exists n. {\ Big (} Q (n-1) \ land \ neg Q (N) {\ Big)} \ \ lor \ \ forall m. \, Q (m)}

Это означает, что для любого свойства Q либо существует любое (первое) число $n {\ displaystyle n}$ $n$ , для которого Q не выполняется, несмотря на то, что Q удерживается для предыдущего случая, или - если такого случая отказа нет - Q верно для всех чисел.

Соответственно, в классическом ZF индукция по множеству может быть преобразована в следующее утверждение, поясняющее, какая форма контрпримера препятствует соблюдению свойства множества P для всех множеств:

∃ х. ((∀ Y ∈ Икс. П (Y)) ∧ ¬ P (x)) ∨ ∀ Z P (z) {\ Displaystyle \ существует х. {\ Big (} \ left (\ forall y \ in x. \, P (y) \ right) \, \ land \, \ neg P (x) {\ Big)} \ \ lor \ \ forall z \, P (z)}

{\ Displaystyle \ существует x. {\ Big (} \ left (\ forall y \ in x. \, P (y) \ right) \, \ land \, \ neg P (x) {\ Big)} \ \ lor \ \ forall z \, P (z)}

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

Для любого свойства, если можно доказать, что $∀ y ∈ x. P (y) {\ displaystyle \ forall y \ in x. \, P (y)}$ ${\ displaystyle \ forall y \ in x. \, P (y)}$ подразумевает $P (x) {\ displaystyle P (x)}$ $P ( x)$ , тогда случай отказа исключается, и формула утверждает, что дизъюнкция $∀ z P (z) {\ displaystyle \ forall z \, P (z)}$ ${\ displaystyle \ forall z \, P (z)}$ должна выполняться.

Независимость

В контексте теории конструктивных множеств CZF принятие Аксиомы регулярности будет означать закон исключенного среднего, а также набор-индукция. Но тогда полученная теория будет стандартной ZF. Однако, наоборот, индукция по множеству не влечет ни того, ни другого. Другими словами, с конструктивным логическим каркасом индукция по множеству, как указано выше, строго слабее регулярности.

См. Также