Обитаемый набор

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

В конструктивной математике множество A является обитаемым, если существует элемент $a ∈ A {\ displaystyle a \ in A}$ $a \ in A$ . В классической математике это то же самое, что и непустое множество; однако эта эквивалентность недействительна в интуиционистской логике (или конструктивной логике).

Сравнение с непустыми наборами

В классической математике набор является обитаемым тогда и только тогда, когда он не является пустым набором. Однако в конструктивной математике эти определения расходятся. Множество A непусто, если оно не пусто, то есть если

¬ [∀ z (z ∉ A)]. {\ displaystyle \ lnot [\ forall z (z \ not \ in A)].}

\ lnot [\ forall z (z \ not \ in A)].

Он заселен, если

∃ z (z ∈ A). {\ displaystyle \ exists z (z \ in A).}

\ существует z (z \ in A).

В интуиционистской логике отрицание универсального квантора слабее, чем квантор существования, а не эквивалентно ему, как в классическом логика.

Пример

Поскольку обитаемые множества идентичны непустым множествам в классической логике, невозможно создать модель в классическом смысле, которая содержит непустое множество X, но не удовлетворять "X обитаем". Но можно построить модель Крипке M, которая удовлетворяет «X непусто», не удовлетворяя «X обитаем». Поскольку импликация доказуема в интуиционистской логике тогда и только тогда, когда она верна в каждой модели Крипке, это означает, что в этой логике нельзя доказать, что «X непусто» подразумевает «X обитаем».

Возможность этой конструкции опирается на интуиционистскую интерпретацию экзистенциального квантора. В интуиционистской обстановке, чтобы иметь место $∃ z ϕ (z) {\ displaystyle \ exists z \ phi (z)}$ $\ exists z \ phi (z)$ , для некоторой формулы $ϕ {\ displaystyle \ phi}$ $\ phi$ , необходимо, чтобы было известно конкретное значение z, удовлетворяющее $ϕ {\ displaystyle \ phi}$ $\ phi$ .

Например, рассмотрим подмножество X из {0,1} , заданное следующим правилом: 0 принадлежит X тогда и только тогда, когда Riemann гипотеза верна, а 1 принадлежит X тогда и только тогда, когда гипотеза Римана неверна. Если мы предположим, что гипотеза Римана верна или ложна, то X не пусто, но любое конструктивное доказательство того, что X обитаемо, докажет либо, что 0 находится в X, либо что 1 находится в X. Таким образом, конструктивное доказательство того, что X обитаемо, будет определить значение истинности гипотезы Римана, которое неизвестно. Заменив гипотезу Римана в этом примере общим утверждением, можно построить модель Крипке с множеством, которое не является ни пустым, ни обитаемым (даже если сама гипотеза Римана не является когда-либо доказано или опровергнуто).

Ссылки

D. Бриджес и Ф. Ричман. 1987. Разновидности конструктивной математики. Издательство Оксфордского университета. ISBN 978-0-521-31802-0

Эта статья включает материал из набора Inhabited на PlanetMath, который находится под лицензией Creative Commons Attribution / Совместная лицензия.