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