фундированное множество и индукция

[GlobalMiwka]

Помогите разобраться с определением фундированного множества.

для множества $M$ выполнено условие минимальности. Надо доказать, что прицип индукции выполнен также. Пусть для свойства $B(x)$ выполняется условие индукции $\forall a((\forall a'<a B(a')) \rightarrow B(a))$. Мы хотим показать, что в таком случае свойство $B(a)$ верно для всех элементов $a \in M$. Предположим противное – пусть для некоторых $a$ свойство $B(a)$ ложно. Выберем среди всех таких $a$ минимальный. Тогда для данного $a$ свойство $B(a)$ ложно, а для всех элементов $a'$ меньших $a$ свойство $B(a')$ истинно. Получаем противоречие.

Как ведется рассуждение, если у $a$ нет элементов $a'$ строго меньших $a$ ?

[mihaild]

GlobalMiwka в сообщении #1514608 писал(а):

Как ведется рассуждение, если у $a$ нет элементов $a'$ строго меньших $a$ ?

Ровно так же. Раз строго меньших нет, то для всех строго меньших свойство $B$ выполнено.

[GlobalMiwka]

я что-то не совсем понимаю как читать эту запись. Вот условие импликации $\forall a'<a B(a')$ можно записать так $a'\in \{a':a'<a\} \rightarrow B(a')$ ? тогда $((a'\in \{a':a'<a\}\rightarrow B(a'))\rightarrow B(a))$. Если множество $\{a':a'<a\} = \varnothing$, то $(a'\in \varnothing\rightarrow B(a'))\rightarrow B(a)\Leftrightarrow (\bot\rightarrow B(a'))\rightarrow B(a) \Leftrightarrow (\top\rightarrow B(a))\Leftrightarrow B(a) = \top$

[mihaild]

GlobalMiwka в сообщении #1514613 писал(а):

Вот условие импликации $\forall a'<a B(a')$ можно записать так $a'\in \{a':a'<a\} \rightarrow B(a')$ ?

Лучше не дублировать символы. $c \in \{b : b < a} \rightarrow B(c)$ - так точно можно. Но запись $x \in \{y : P(y)\}$ не очень понятно зачем нужна, вместо неё можно сразу написать $P(x)$.
Если с кванторами, но без ограниченных кванторов - то так: $\forall a' (a' < a) \rightarrow B(a')$.

[GlobalMiwka]

я там правку сделал. Ясно тогда любой элемент, который не имеет предшественника обладает свойством $B$ ?

-- 16.04.2021, 21:58 --

Правда для меня странно немного выгляит выражение $a'\in\varnothing\rightarrow B(a')$. Получается мы рассматриваем элемент $a'$ пустого множества полученного предикатом $P(a) = \{a':a'<a\}$, хотя его, т.е. элемента, не существует, тогда что означает $B(a')$ для несуществующего элемента $a'\in\varnothing$, или так принято ? Правда мне сама запись вроде верна.

[iifat]

GlobalMiwka в сообщении #1514608 писал(а):

Как ведется рассуждение, если у $a$ нет элементов $a'$ строго меньших $a$ ?

Для этого, как понимаю, и вводится в определение индукции на натуральных $B(1)$ (ну, или 0, в зависимости от). Неужто в определение индукции произвольных множеств с минимальностью аналог отсутствует?

[Someone]

GlobalMiwka в сообщении #1514615 писал(а):

для меня странно немного выгляит выражение $a'\in\varnothing\rightarrow B(a')$.

Давайте на это взглянем с формальной стороны. Чтобы опровергнуть данное высказывание, нужно предъявить такой элемент $a'\in\varnothing$, что $B(a')$ ложно. Сможете?

[GlobalMiwka]

Someone в сообщении #1514653 писал(а):

GlobalMiwka в сообщении #1514615 писал(а):

для меня странно немного выгляит выражение $a'\in\varnothing\rightarrow B(a')$.

Давайте на это взглянем с формальной стороны. Чтобы опровергнуть данное высказывание, нужно предъявить такой элемент $a'\in\varnothing$, что $B(a')$ ложно. Сможете?

Вы хотите, чтобы я переписал выражение $a'\in\varnothing\rightarrow B(a')$ в виде его отрицания и проверил есть ли элемент, при котором это отрицание истинно ? В виде импликации как это выглядит не совсем ясно. Поробую бездумно по формулам: $(\exists a')\neg (a'\in\varnothing\rightarrow B(a'))\Leftrightarrow (\exists a')\neg(\neg (a'\in\varnothing) \vee B(a'))\Leftrightarrow (\exists a') (a'\in\varnothing \wedge \neg B(a')) \Leftrightarrow \bot$, потому что $a'\in\varnothing$ всегда ложно. Стало быть не существует элемента такого. Все равно не пойму, что вы хотите сказать.

[kotenok gav]

GlobalMiwka, по-моему, ваше непонимание происходит оттого, что вы считаете утверждение $(\forall a\in X\,\operatorname P(a))\rightarrow(\exists a\in X\,\operatorname P(a))$ верным. Это не так, это верно только если множество $X$ непусто. Зато верно утверждение $\neg(\exists a\in X\,\neg\operatorname P(a))\rightarrow(\forall a\in X\,\operatorname P(a))$, и поэтому $\forall a\in \varnothing\,\operatorname P(a)$.

[mihaild]

iifat в сообщении #1514624 писал(а):

Неужто в определение индукции произвольных множеств с минимальностью аналог отсутствует?

Нет, он там не нужен.
Индукция на натуральных числах бывает в двух видах: стандартная с условием $B(0) \wedge \forall n(B(n) \rightarow B(n+1))$ и "полная" $\forall n ((\forall n' <n: B(n')) \rightarrow B(n))$. Для натуральных чисел они эквивалентны, потому что прибавляя по единице мы дойдем до любого натурального числа, но для обобщения подходит вторая формулировка.

GlobalMiwka в сообщении #1514615 писал(а):

тогда что означает $B(a')$ для несуществующего элемента $a'\in\varnothing$, или так принято ?

Ничего не означает. Мы не подставляем никакой "несуществующий" элемент. Мы пишем, что если нам внезапно удастся найти элемент в $\varnothing$, то для него будет выполнено $B$.

[arseniiv]

Вообще $\forall x. P(x)$ выполняется ровно тогда, когда $P$ верно на каждом множестве, так что $\forall x. F(x) \to P(x)$, где $F$ всегда ложно, автоматически верно (так как импликация верна во всех случаях), ну и $F(x) := x \in \varnothing$ будет такой ситуацией.

Если понимать $\forall x \in X. P(x)$ как некоторую возможно бесконечную «конъюнкцию» $P(x_1) \wedge P(x_2) \wedge \ldots$ по всем элементам $x_1, x_2, \ldots \in X$, то для $X = \varnothing$ мы снова получаем интуитивно истину независимо от $P$, ведь пустая конъюнкция должна быть истинной (если её определять, а бывает полезно), так как $\top$ — нейтральный элемент $\wedge$, ровно аналогично нулевой пустой сумме, единичному пустому произведению, пустому пустому объединению и, если мы позволяем себе говорить о классах, классу всех множеств как пустому пересечению (классов). (Или универсальному множеству, если мы его имеем для своей задачи.)

[GlobalMiwka]

Кажется я немного начал понимать.

1. Как я понимал, хотя не изложу как я точно понимал, потому что с новыми знаниями ход мыслей меняется, а старые забываюся. Итак, проверить, что выражение $(\forall a'<a B(a')) \rightarrow B(a)$ исинно при $\forall a$. Оно истинно, когда: 1) $B(a)$ истинно всякий раз, как $\forall a'<a B(a')$ истинно (для данного $a$),когда $\{a'<a\}\neq\varnothing$; 2) $\forall a'<a B(a')$ тоже истинна (для данного $a$), когда $\{a'<a\} = \varnothing$ (то, что надо проверить и я указал как я понимал выражение $\forall a'<a B(a')$).

kotenok gav в сообщении #1514805 писал(а):

GlobalMiwka, по-моему, ваше непонимание происходит оттого, что вы считаете утверждение $(\forall a\in X\,\operatorname P(a))\rightarrow(\exists a\in X\,\operatorname P(a))$ верным. Это не так, это верно только если множество $X$ непусто.

После ваших пояснений и этом пояснении :

arseniiv в сообщении #1514819 писал(а):

Вообще $\forall x. P(x)$ выполняется ровно тогда, когда $P$ верно на каждом множестве, так что $\forall x. F(x) \to P(x)$, где $F$ всегда ложно, автоматически верно (так как импликация верна во всех случаях), ну и $F(x) := x \in \varnothing$ будет такой ситуацией.

Если понимать $\forall x \in X. P(x)$ как некоторую возможно бесконечную «конъюнкцию» $P(x_1) \wedge P(x_2) \wedge \ldots$ по всем элементам $x_1, x_2, \ldots \in X$, то для $X = \varnothing$ мы снова получаем интуитивно истину независимо от $P$, ведь пустая конъюнкция должна быть истинной (если её определять, а бывает полезно), так как $\top$ — нейтральный элемент $\wedge$, ровно аналогично нулевой пустой сумме, единичному пустому произведению, пустому пустому объединению и, если мы позволяем себе говорить о классах, классу всех множеств как пустому пересечению (классов). (Или универсальному множеству, если мы его имеем для своей задачи.)

И того, что в учебниках пишут, что при пустом домене $\forall x. P(x)$ всегда истина, без обяснений.

Понимаю так $\forall x \in X. P(x) \Leftrightarrow 1 \wedge P(x_1) \wedge P(x_2) \wedge \ldots$, если у нас домен пустой $\bigwedge \limits_{x\in\varnothing}\operatorname P(x) \Leftrightarrow 1 \wedge P(x) P(x_1) \wedge P(x_2) \wedge \ldots \Leftrightarrow 1$ просто остается одна истина из выражения.
$\exists x \in X \operatorname P(x) = \bigvee\limits_{x\in\varnothing} \Leftrightarrow 0 \vee P(x_1) \vee P(x_2) \vee \ldots \Leftrightarrow 0$, т.е. остается только ложь.

Получается $(\forall a\in X\,\operatorname P(a))\rightarrow(\exists a\in X\,\operatorname P(a)) \Leftrightarrow 1 \rightarrow 0$, т.е. импликация ложнa, у меня же получалось $\exists a\in X\,\operatorname P(a) \Leftrightarrow (\exists a')(a'\in\varnothing\rightarrow B(a'))\Leftrightarrow (\exists a')(0 \rightarrow B(a'))\Leftrightarrow 1$, т.е. импликация верна $1 \rightarrow 1$, что не является верным.

-- 18.04.2021, 08:10 --

kotenok gav в сообщении #1514805 писал(а):

Зато верно утверждение $\neg(\exists a\in X\,\neg\operatorname P(a))\rightarrow(\forall a\in X\,\operatorname P(a))$, и поэтому $\forall a\in \varnothing\,\operatorname P(a)$.

а что поэтому в:

kotenok gav в сообщении #1514805 писал(а):

поэтому $\forall a\in \varnothing\,\operatorname P(a)$.

Оно же выражение $\forall a\in \varnothing\,\operatorname P(a)$ не следует из импликации, варажение это же надо проверять.

[kotenok gav]

GlobalMiwka в сообщении #1514870 писал(а):

Оно же выражение $\forall a\in \varnothing\,\operatorname P(a)$ не следует из импликации, варажение это же надо проверять.

Следует, т.к. $\exists a\in\varnothing\,\neg\operatorname P(a)$ ложно по определению пустого множества.

[GlobalMiwka]

kotenok gav в сообщении #1514881 писал(а):

GlobalMiwka в сообщении #1514870 писал(а):

Оно же выражение $\forall a\in \varnothing\,\operatorname P(a)$ не следует из импликации, варажение это же надо проверять.

Следует, т.к. $\exists a\in\varnothing\,\neg\operatorname P(a)$ ложно по определению пустого множества.

У вас что ж получается по Modus Ponens ? А как вы узнали, что импликация $\neg(\exists a\in X\,\neg\operatorname P(a))\rightarrow(\forall a\in X\,\operatorname P(a))$ верна ? Для меня это просто импликация у которой надо установить истинность или ложность посылки и следствия и после этого определить является ли импликация верной. Ваше утверждение, как я полагаю, может быть верным, если посылка и следствие связаны законом исключенного третьего.

Переведу в удобную мне запись, :

$\exists a\in\varnothing\,\neg\operatorname P(a)\Leftrightarrow \bigvee\limits_{a\in\varnothing}\neg P(a)=0$;
$\forall a\in \varnothing\,\operatorname P(a)\Leftrightarrow \bigwedge\limits_{a\in\varnothing}P(a)=1$.

И как здесь для выражения $\bigvee\limits_{a\in\varnothing}\neg P(a) \wedge \bigwedge\limits_{a\in\varnothing}P(a)$ установить выполнение закон исключенного третьего без независимого вычисления знaчений для $\bigvee\limits_{a\in\varnothing}\neg P(a)$ и $\bigwedge\limits_{a\in\varnothing}P(a)$ ? Я не знаю как манипулировать этими символами в $\bigvee\limits_{a\in\varnothing}\neg P(a)$ и $\bigwedge\limits_{a\in\varnothing}P(a)$ , не вдаваясь в смысл, что же такое $P(a)$.

[arseniiv]

То, что $\exists \neg \equiv \neg \forall$ и $\forall \neg \equiv \neg \exists$, можно в принципе считать просто данностью классической логики. И так же оно в некоторой степени аналогично законам де Моргана.


(Классическая логика проста как табурет, и я наверно, честно говоря, к этому времени перестал понимать, почему у людей с ней бывают сложности. В некоторых деталях она менее интуитивна чем интуиционистская логика (закон Пирса!), но например обычных проблем с импликацией это совсем не касается, и проблем с ограниченной квантификацией по пустому множеству тоже, это одинаково в обеих системах. Классическая логика — это в каком-то смысле самая простая нетривиальная логика, для её интерпретации достаточно очень хороших структур — булевых алгебр — и притом конкретно одной булевой алгебры $\mathbb B$, двухэлементной, самой простой за исключением одноэлементной.)