Теорема, протилежна оберненій
Оскільки я вже згадав у попередньому дописові про третє видання книжки Кормена і компанії «Вступ до алгоритмів» (так звану CLRS), то напишу і тут про ненароком помічену помилку в російському перекладі книжки.
Працюючи з текстом задачі 8-7 («Лема сортування 0-1 і сортування стовпцями», сторінка 208 оригіналу) вирішив зазирнути в російський переклад, як там цю лему назвали, і тут же око вихопило дуже некоректний текст.
У перекладі російською (сторінка 238) є такі слова: «докажем 0-1-лемму сортировки путём доказательства обратной к ней». Але так не буває. Ніколи-ніколи-ніколи доведення оберненого твердження не доводить пряме. Якщо істинне як пряме твердження, так і обернене, то частини тверджень еквівалентні, тобто (А⇒Б ∧ Б⇒А) ⇒ (А⇔Б). Але шляхом доведення Б⇒А неможливо довести А⇒Б.
І в оригіналі було: «prove the 0-1 sorting lemma by proving its contrapositive»
Контрапозитивне твердження (протиставлення) це протилежне оберненому (або обернене протилежному, що те ж саме), тобто (А⇒Б) ⇔ (¬Б⇒¬А) і саме ¬Б⇒¬А можна довести для доведення А⇒Б (що і зроблено далі по тексту).
Цікаво, скільки ще таких неточностей у цьому перекладі з англійської на російську? І зрозуміло, чому я проти таких подвійних перекладів навіть у «технічних» текстах.