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

Без потери общности (часто сокращается до 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 .
^ Дейкстра, Эдсгер В. (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 г.

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

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

[2] Дейкстра, Эдсгер В. (1997). «WLOG, или несчастье неупорядоченной пары (EWD1223)». В Брое, Манфред; Шидер, Биргит (ред.). Математические методы в разработке программ (PDF) . НАТО ASI Series F: Компьютерные и системные науки. Том. 158. Спрингер. стр. 33–34. дои : 10.1007/978-3-642-60858-2_9 .

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

[1]

[2]

[3]