Более формальный вывод из доказательства по принципу наименьшего числа?
Когда доказывают какой-то факт, используя принцип наименьшего числа, то заканчивают доказательство, получив противоречие, найдя ещё меньший элемент (чем i-й, когда предположение было, что i-й элемент на самом деле является наименьшим)
Вроде бы звучит естественно и логично сделать вывод, что такого элемента i нет и вроде бы все привыкли к таким рассуждениям
Но, если упарываться формализмом, разве в этом доказательстве нету следующей пропущенной части: если для i-го элемента (который предполагался наименьшим) был найден i-1, являющийся тоже "наименьшим", то (для любого начального j) можно пройтись таким окном, начиная с j и итерируясь по (k, k-1) (уменьшая k), каждый раз находя всё новый и новый "наименьший" элемент, и дойти до базы, которая точно не является наименьшим. ?
Ну и получается то же самое домино, что и в индукции только в другую сторону
Нет, эти рассуждения не нужны, вы перемудрили немного. Вы предположили, что во множестве есть минимальный элемент, но получили, что во множестве есть меньший этого минимума элемент. Противоречие. Ибо все остальные элементы множества больше минимального (по определению минимума). Все. Отсюда следуюет что во множестве нет минимального элемента.
Дальше, да, хорошо бы указать, что любое подмножество положительных целых чисел обязательно имеет минимальный элемент. А раз минимума нет, то подмножества с искомым свойством не существует. Но это очевидный и постоянно повторяемый факт, поэтому его часто пропускают.
Есть еще тонкий момент: рассуждения получающие меньший элемент заданного иногда нельзя применить ко всем числам. Например, если вы работаете с целыми положительными, а предположенный минимальный у вас 1, то из 1 вы меньшее число никак не получите. Поэтому надо сначала проверить, принадлежит ли 1 к множеству и потом предполагать существование минимального элемента > 1.
Просто увидев некоторую симметрию с "домино" индукции, там ведь тоже скипается очевидная часть после базы и шага индукции (что теперь нужно взять базу b0 и подставить в доказынный k-й шаг, применив переход и получив базу b1 и так далее), подумал, что мб здесь так же
Средний
