Двач.hk не отвечает.
Вы видите копию треда, сохраненную 12 сентября в 14:12.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Математической индукции и её приложениям тред 75512 В конец треда | Веб
Пора положить раз и навсегда конец этой теме. Закрыть этот вопрос. Поставить так сказать жирную точку и никогда более не возвращаться.
2 75571
Следующий будет "коммутативности сложения тред"?
3 75572
>>5571
мейби
4 75577
>>5571
если бы умножения, было бы интересней

можно было бы обсудить разные доказательства теоремы о классификации алгебр с делением
5 75920
>>5512 (OP)
А вопрос то какой? Чему жирную точку ставить?
6 75921
>>5920
Что такое база и что такое шаг, и как они связаны и побольше примеров хотелось бы
7 75929
>>5921
Представь, что у тебя задана некоторая формальная система с правилом (правилами) вывода. Построим ориентированный граф, вершинами которого является некоторое множество А синтаксически корректных высказываний твоей системы, а ориентированными ребрами - импликации между ними.

Такой граф будет задавать некоторое отношение на некотором множестве высказываний. Как и в любом орграфе, в нем существует ядро - то есть подмножество вершин, из которых потенциально достижимы все остальные вершины. Это ядро будет являться базисом индукции. Шагом индукции будет применение этого отношения к множеству вершин (то есть однократный переход из вершины в вершину по стрелочкам). Если ты сумеешь доказать, что все выражения в ядре орграфа истинны и он при этом связен, то из этого немедленно следует, что, двигаясь из ядра по стрелочкам, мы можем в итоге посетить все вершины графа - и, следовательно, ВСЕ выражения, принадлежащие множеству А, истинны.

То есть, индукция - это просто частный случай волнового алгоритма. Математики пользуются его элементарной версией и не прямо, а косвенно, через параметризацию некоторого математического объекта и использованием особенностей структуры множества значений параметра. Например, доказывая по индукции выражение для суммы арифметической прогрессии, мы параметризуем это выражение (выделяя переменную n, значения которой принадлежат множеству натуральных чисел) и используем тот факт, что на множестве N существует линейный порядок - то есть бесконечную ориентированную цепь с ядром в вершине 1. Сначала мы доказываем истинность выражения в ядре этого орграфа (он же базис, он же истинность выражения при значении параметра n = 1), а потом доказываем его связность (т. н. шаг индукции, или наличие импликации между вершинами k и k + 1 для любого k > 1).

Аналогичный фокус мы можем выполнить для любого количества параметров и для любых множеств, на которых задано какое-то отношение. Наш орграф может быть не только цепью, как в классическом случае, а иметь самую причудливую форму.
7 75929
>>5921
Представь, что у тебя задана некоторая формальная система с правилом (правилами) вывода. Построим ориентированный граф, вершинами которого является некоторое множество А синтаксически корректных высказываний твоей системы, а ориентированными ребрами - импликации между ними.

Такой граф будет задавать некоторое отношение на некотором множестве высказываний. Как и в любом орграфе, в нем существует ядро - то есть подмножество вершин, из которых потенциально достижимы все остальные вершины. Это ядро будет являться базисом индукции. Шагом индукции будет применение этого отношения к множеству вершин (то есть однократный переход из вершины в вершину по стрелочкам). Если ты сумеешь доказать, что все выражения в ядре орграфа истинны и он при этом связен, то из этого немедленно следует, что, двигаясь из ядра по стрелочкам, мы можем в итоге посетить все вершины графа - и, следовательно, ВСЕ выражения, принадлежащие множеству А, истинны.

То есть, индукция - это просто частный случай волнового алгоритма. Математики пользуются его элементарной версией и не прямо, а косвенно, через параметризацию некоторого математического объекта и использованием особенностей структуры множества значений параметра. Например, доказывая по индукции выражение для суммы арифметической прогрессии, мы параметризуем это выражение (выделяя переменную n, значения которой принадлежат множеству натуральных чисел) и используем тот факт, что на множестве N существует линейный порядок - то есть бесконечную ориентированную цепь с ядром в вершине 1. Сначала мы доказываем истинность выражения в ядре этого орграфа (он же базис, он же истинность выражения при значении параметра n = 1), а потом доказываем его связность (т. н. шаг индукции, или наличие импликации между вершинами k и k + 1 для любого k > 1).

Аналогичный фокус мы можем выполнить для любого количества параметров и для любых множеств, на которых задано какое-то отношение. Наш орграф может быть не только цепью, как в классическом случае, а иметь самую причудливую форму.
8 75930
>>5929
Слишком сложно для меня, понял немного только про n. Она при любых раскладах должна принадлежать натуральным числам?
9 75960
>>5930
Нет, необязательно. Просто индукция на N это классический случай.
Параметр может принимать значения из любого множества. Но нам выгодны только те множества, на которых задано относительно простое отношение, которое мы можем использовать. На N мы используем линейный порядок, потому что граф этого отношения очень прост и регулярен (достаточно рассмотреть один элемент в базе и индуктивный переход для любой пары вершин, чтобы получить доказательство сразу для всех значений параметра). Но если множество не выстроено в линеечку, решетку или другую регулярную конструкцию, и граф отношений спутан кое-как, то особой выгоды от параметризации не будет - т. к. тогда придется рассматривать множество частных случаев (множество элементов в базе и отдельные цепочки импликаций).

Для понимания просто посмотри какой-нибудь видосик с работой волнового алгоритма, это же классика CS. У тебя есть ориентированный граф. В графе есть истинные (помеченные) вершины. Запускаем алгоритм - и метка распространяется по ребрам на смежные вершины - а потом с них на следующие и так далее. Если истинные вершины принадлежали ядру графа, то все вершины в итоге станут истинными. Если нет - то возможен случай, когда некоторые вершины останутся непомеченными.
10 76544
Я дебил
Сосед за партой спереди дебил
Сосед соседа за партой спереди дебилы.
По закону индукции все вокруг дебилы.
11 76591
>>6544
Я сзади сижу.
12 76604
>>6544

Это было бы верно, если бы после добавления в любую толпу дебилов еще одного человека, оказывалось что это снова толпа дебилов.
13 76605
>>6604
Как-то костыльно.
Допустим, вокруг все дебилы (или на всей планете). И других мы даже помыслить не можем. Тогда метод индукции работает: все всегда дебилы.
14 76612
>>6605

Если мы сразу знаем, что людей конечное число, и все они дебилы, то тогда что же мы доказываем?
15 76618
>>6612
допустим, мы пока не знаем.
и пытаемся доказать.
и у нас получается это сделать.
# OP 16 76665
Короче рекурсия это очень простая хуйня, где следующая операция пользуется результатом предыдущей. Счёт это рекурсия мы к 8 прибавляем 1 потом к 9 прибавляем 1, почему блять так сложно это преподносят, чтобы никто не догадался?
17 76666
>>6665
Не, это не рекурсия, а рекуррентность
18 76667
>>6666
А рекурсия тогда что?
19 76671
>>6618

Допустим, мы не знаем. Дальше как доказывать?
20 76672
>>6665
люди там деньги зарабатывают.
попробуй подойди к таким со своим упрощением.
сразу на необитаемом острове окажешься.
будешь изучать торсионные поля.
Обновить тред
Двач.hk не отвечает.
Вы видите копию треда, сохраненную 12 сентября в 14:12.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
« /math/В начало тредаВеб-версияНастройки
/a//b//mu//s//vg/Все доски