Без потери общности
Без потери общности (часто сокращается до 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]
Пример
Рассмотрим следующую теорему (которая является случаем принципа ящика ):
Если три объекта окрашены в красный или синий цвет, то должно быть как минимум два объекта одного цвета.
Доказательство:
Предположим, без потери общности, что первый объект красный. Если любой из двух других объектов красный, то мы закончили; если нет, то оба других объекта должны быть синими, и мы все еще закончили.
Вышеприведенный аргумент работает, потому что точно такое же рассуждение можно было бы применить, если бы было сделано альтернативное предположение, а именно, что первый объект синий, или, аналогично, что слова «красный» и «синий» можно свободно менять местами в формулировке доказательства. В результате использование «без потери общности» в этом случае допустимо.
Смотрите также
Ссылки
- ^ Chartrand, Gary ; Polimeni, Albert D.; Zhang, Ping (2008). Математические доказательства / Переход к высшей математике (2-е изд.). Pearson/Addison Wesley. стр. 80–81 . ISBN 978-0-321-39053-0.
- ^ Дейкстра, Эдсгер В. (1997). «WLOG, или несчастье неупорядоченной пары (EWD1223)». В Брое, Манфред; Шидер, Биргит (ред.). Математические методы в разработке программ (PDF) . НАТО ASI Series F: Компьютерные и системные науки. Том. 158. Спрингер. стр. 33–34 . doi :10.1007/978-3-642-60858-2_9. ISBN 978-3-642-64588-4.
- ^ "Ациклическое неравенство с тремя переменными". www.cut-the-knot.org . Получено 21 октября 2019 г.
Внешние ссылки
- WLOG на PlanetMath .
- «Без потери общности» Джона Харрисона — обсуждение формализации аргументов «WLOG» в автоматизированной программе доказательства теорем.
