Математическая индукция штоле?

Ну да, но обычно бывает индуктивный переход без фокусов, всё строго и без предположений. Как в школе прям

Доказательство в студию!

а еще все натуральные числа равны

докажем, что для любого N все любые два натуральных числа a, b <= N будут равны: a=b

база: N=1 => a=b=1 => a=b

переход: пусть верно для N-1, докажем для N

рассмотрим любую пару чисел a, b <= N; и рассмотрим числа a-1, b-1. Очевидно, что a-1,b-1<=N-1, значит (по индукц. предположению) a-1=b-1 => a=b, чтд.

из доказанного автоматически следует, что число внешних узлов в дереве, сколько бы их там ни было, равно N (как и любому другому натуральному числу)

buddhist, как тебе такое доказательство?

Лемма 5.5 Бинарное дерево с N внутренними узлами имеет N + 1 внешних узлов.

Эта лемма доказывается методом индукции: бинарное дерево без внутренних узлов имеет один внешний узел, следовательно, лемма справедлива для N=0. Для N>О любое бинарное дерево с N внутренними узлами имеет к внутренних узлов в левом поддереве и N-1-k внутренних узлов в правом поддереве для некоторого А: в диапазоне между 0 и N-1, поскольку корень является внутренним узлом. В соответствии с индуктивным предположением левое поддерево имеет к+1 внешних узлов, а правое поддерево - N-k внешних узлов, что в сумме составляет N+1.

А ещё можно доказать, что брадобрей - это заговор капиталистических империалистов!

определение бинарного дерева покажи оттуда. походу, в нем не может быть узлов с единственным сыном. тогда все ок.

а если может, то индукционный переход не сработает

а ты докажи! а то пока пустые слова только

Определение 5.1 Бинарное дерево - это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла.

Короче из Седжвика «алгоритмы на c++»

тогда все ок, лемма верна.

нота в том, что дерево, которое не подойдет под лемму, по этому определению не является бинарным. например:

  A
 /
b

не бинарное, так как правое поддерево узла A (пустое поддерево) не является бинарным по определению

Есть еще задача о ранце. Там похожее «индуктивное предположение» в рекурсивном решении. Верю, конечно. Но не очевидно мне.

а ты докажи!

а ты сначала добейся!

Так индукция ведь и есть по сути рекурсия. Доказывая утверждение для N == k, ты, собственно, используешь то, что ты с помощью того же самого доказательства можешь доказать утверждение для N == k - 1. И рекурсия заканчивается при N == 0.

На псевдоагде это как-то так:

induction statement base increment 0 = base statement
induction statement base increment n = increment statement (n - 1)

Отсюда, собственно, и видно, что рекурсия и индукция не сильно отличаются.

Рекурсия — это процесс, а индукция — доказательство. Думаешь, можно считать, что это одно и то же?

доказательство через еще не доказанное

Любое доказательство строиться из недоказанного, из аксиом. Чем больше свистоперделок аксиом, тем легче доказывать.

Рекурсия — это процесс, а индукция — доказательство.

А ты — лох.

«индуктивное предположение»

... в мат. индукции всегда есть «индуктивное предположение», школоло

Собственно, в дедукции тоже есть дедуктивное. Если Все X имеют свойство Y то X1 имеет свойство Y. Ключевое слово — «если»

Рекурсия — это процесс

http://en.wikipedia.org/wiki/Recursion#Recursion_in_mathematics

Индукция - это не доказательство, балбес! Когда ж ты поймешь, что тебе не нужно умничать.

Рекурсия — это процесс, а индукция — доказательство. Думаешь, можно считать, что это одно и то же?

Брауэр, Гейтинг и Колмогоров считали, что можно; Карри и Говард строго это доказали

Если быть точней, принцип (один из) построения доказательств. Просто, когда говоришь что-то, расчет идет на то, что читают не школьники, поэтому не уточняется. Но для тебя я сделал исключение.

На самом деле, почему бы тогда не считать итерацию доказательством? Ведь любая рекурсия выразима через итерацию.

умерь чсв

http://en.wikipedia.org/wiki/Mathematical_induction

The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis).

Вообще, то что у тебя - это, вроде, структурная индукция.

Ага, тоже уже нашёл это

Предположение мат.индукции - не аксиома, и приплёл ты их сюда совершенно не к месту.

Про матиндукцию никто не говорил, это отдельная тема.

Да неужели

Определенно.

man Curry-Howard isomorphism

А итерация — это тоже доказательство по перл-харбарду?

Я смогу тебе ответить на этот вопрос только после того, как ты мне ответишь, что такое, по-твоему, итерация. Потому что иначе всё сведётся к спору об определениях.

Ну давай пока остановимся на википедиевском определении

Итерация в математике — результат повторного применения какой-либо математической операции.

Думается мне, что там должно быть всё-таки не «результат повторного применения», а «повторное применение», ибо процесс и результат процесса — разные вещи. (На самом деле, такое написание тоже можно истолковать, как «повторное применение», но я заранее уточню, чтобы потом не было придирок)

какой-либо математической операции

Ну давай я сделаю допущение, что математической операцией в данном случае является доказательство, потому что мы говорим именно об этом. Тогда волшебным образом получим:

Итерация в математике — повторное применение доказательства

ВНЕЗАПНО, повторное применение доказательства есть доказательство.

Думается мне, что там должно быть всё-таки не «результат повторного применения», а «повторное применение», ибо процесс и результат процесса — разные вещи. (На самом деле, такое написание тоже можно истолковать, как «повторное применение», но я заранее уточню, чтобы потом не было придирок)

Абсолютно сгласен То есть, ответ — да?

Да.

ВНЕЗАПНО, повторное применение доказательства есть доказательство.

Кстати, не кажется ли Вам, что это порочный круг (впрочем, как и с рекурсией)? Это чем то напоминает парадокс Рассела.

Парадокс Рассела тут при чём?

Если у рекурсии или итерации есть условие остановки доказательства (в индукции это называется базой), то никаких проблем. Иначе это не доказательство.

Ящетаю, что тут надо отделить мух. Есть процесс а есть результатат процесса. Так вот, рекурсию, как и итерацию, можно считать процессом док-ва, но не результатом его. И глуповато выглядит утверждение, что процесс доказательства и есть само доказательство. Доказательство — это не есть процесс его. Процесс — есть средство.

есть условие остановки доказательства

Вообще-то не обязано. Определение нат ряда по индукции тому пример, но я не об этом

Противоречие в самом определении Вашем:

повторное применение доказательства есть доказательство.

Доказательства еще нет, а ты УЖЕ, используешь его для его же самого:) Парадокс рассела — просто как аллюзия.

Доказательство есть процесс. Результат — доказанное утверждение. Рекурсия и итерация — методы построения доказательства, грубо говоря.

Я не делаю в речи различия между процессом доказательства и самим доказательством, ибо это слишком громоздко, собеседник обычно умеет сам понимать, где что. Это всё равно что всегда указывать явно, о чём ты говоришь: о функции или о процессе её исполнения.

Ну тогда (со стороны тех умников-математиков) это просто капитанство. Это очевидные вещи, тащемта.

определение нат ряд по индукции

У него есть некоторое начало, которое при наличии фантазии можно назвать условием остановки, вывернутым наизнанку. Ну, рассмотрим любое число n и «спустимся» по нему к нулю, на каждом шаге отнимая по единице, для того, чтобы убедиться, что число n — натуральное. Собственно, на существовании нуля и основывается существование натуральных чисел.

Да, некоторые вместо нуля берут единицу и начинают натуральные числа с неё.

доказательства ещё нет

Неправда. Ты можешь повторно применять только уже доказанное (в общем случае — не доказанное, но считающееся истинным: аксиомы, доказательства, предположения).

есть условие остановки доказательства
Вообще-то не обязано. Определение нат ряда по индукции тому пример

единица, не?

Это всё равно что всегда указывать явно, о чём ты говоришь: о функции или о процессе её исполнения.

Между прочим, я вижу в этом огромную проблему мировосприятия программистов. Большинство, ИМХО, не могут понять разницы между программой и текстом программы. Отсюда и дыра, которое породила быдло-фп парадигму, которая гнилая концептуально, от самых корней.

единица, не?

Нет, это шаг

Ну, рассмотрим любое число n и «спустимся» по нему к нулю, на каждом шаге отнимая по единице, для того, чтобы убедиться, что число n — натуральное

Похоже на вот это http://ru.wikipedia.org/wiki/Метод_бесконечного_спуска

база ведь. (или 0)

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

Панацеи не существует, все парадигмы взаимозаменяемы, вопрос лишь в удобстве. Олсо, некоторое ФП ближе к математике, поэтому про него проще что-нибудь реально доказать, чем про более распространённые парадигмы. И корни у него ровно поэтому почище будут. Я всё сказал.