Без потери общности

Без потери общности (часто сокращаемой для Wolog , WLOG или WLOG ; реже заявляется, что без какой -либо потери общности или без потери общности ) является часто используемым выражением в математике . Термин используется для указания предположения о том, что следующее выбирается произвольно, сужая предпосылку до конкретного случая, но не влияет на обоснованность доказательства в целом. Другие случаи достаточно похожи на тот, который представлял, что доказывание их следует по существу той же логики. ^{[ 1 ]} В результате, как только доказательство дано для конкретного случая, тривиально адаптировать его, чтобы доказать вывод во всех других случаях.

Во многих сценариях использование «без потери общности» стало возможным благодаря наличию симметрии . ^{[ 2 ]} Например, если некоторые свойства p ( x , y ) реальных чисел, как известно, является симметричным по x и y , а именно то, что p ( x , y ) эквивалентен p ( y , x ), а затем доказывая, что p ( x , y ) удерживается за каждый x и y , можно предположить «без потери общности», что x ≤ y . В этом предположении не существует потери общности, поскольку один раз в случае x ≤ y ⇒ p ( x , y ) было доказано, другой случай следует по взаимозаменяющему x и y : y ≤ x ⇒ p ( y , x ) и и и и Симметрией P , это подразумевает P ( x , y ), тем самым показывая, что P ( x , y ) сохраняется для всех случаев.

С другой стороны, если ни такая симметрия, ни другая форма эквивалентности не могут быть установлены, то использование «без потери общности» не является неверным и может составить экземпляр доказательства - пример - логическая ошибка доказывания претензии доказывая нерепрессущий пример. ^{[ 3 ]}

Пример

Рассмотрим следующую теорему (которая является случаем принципа голубей ):

Если каждый объект окрашены либо красным, либо синим, то должно быть как минимум два объекта одного цвета.

Доказательство:

Предположим, без потери общности, что первый объект является красным. Если какой -либо из двух других объектов красный, то мы закончили; Если нет, то два других объекта должны быть синими, и мы все еще закончены.

Приведенный выше аргумент работает, потому что то же самое рассуждение может быть применено, если альтернативное предположение, а именно, что первый объект был синим, или, аналогично, слова «красный» и «синий» можно свободно обменять в формулировке доказательства. В результате в этом случае использование «без потери общности».

Смотрите также

Ссылки

^ Чартранд, Гэри ; Полимени, Альберт Д.; Чжан, Пинг (2008). Математические доказательства / переход к продвинутой математике (2 -е изд.). Пирсон/Аддисон Уэсли. С. 80–81. ISBN 978-0-321-39053-0 .
^ Dijkstra, Edsger W. (1997). «WLOG, или страдания неупорядоченной пары (EWD1223)». В Брое, Манфред; SCHIEDER, Birgit (Eds.). Математические методы в разработке программы (PDF) . Серия NATO ASI F: Компьютерные и системные науки. Тол. 158. Springer. С. 33–34. doi : 10.1007/978-3-642-60858-2_9 .
^ «Ациклическое неравенство в трех переменных» . www.cut-the-knot.org . Получено 2019-10-21 .

Внешние ссылки

[1] Чартранд, Гэри ; Полимени, Альберт Д.; Чжан, Пинг (2008). Математические доказательства / переход к продвинутой математике (2 -е изд.). Пирсон/Аддисон Уэсли. С. 80–81. ISBN 978-0-321-39053-0 .

[2] Dijkstra, Edsger W. (1997). «WLOG, или страдания неупорядоченной пары (EWD1223)». В Брое, Манфред; SCHIEDER, Birgit (Eds.). Математические методы в разработке программы (PDF) . Серия NATO ASI F: Компьютерные и системные науки. Тол. 158. Springer. С. 33–34. doi : 10.1007/978-3-642-60858-2_9 .

[3] «Ациклическое неравенство в трех переменных» . www.cut-the-knot.org . Получено 2019-10-21 .

[ 1 ]

[ 2 ]

[ 3 ]