о логике и кванторах
Забавная логическая задача от Джоэла Хэмкинса в твиттере напомнила мне, почему формальная логика - сложное дело. Хэмкинс предложил пересказать словами как можно более ясно смысл следующего утверждения:
∃y (x≠y and y≠z) → ∀x∃y (x≠y and y≠z)
Тут, напомню, ∃ это "существует", а ∀ "для любого" - кванторы существование и всеобщности соответственно.
Всего несколько символов, но из-за чередования кванторов, даже не очень глубокого здесь, немножко заходит ум за разум. Я опишу дальше, как сам разбираю это утверждение, не читайте, если хотите сами подумать и разобраться.
Во-первых, это утверждение о каких-то конкретных x и z. При этом во второй половине, после стрелки импликации, вводится новая переменная x квантором ∀x, которая не имеет отношения к x в x≠y первой части. Если это запутывает, можно переименовать переменную под квантором, скажем, в t, и это ничего не изменит:
∃y (x≠y and y≠z) → ∀t∃y (t≠y and y≠z)
Итак, у нас есть выражение вида "если, то". Часть "если" ∃y (x≠y and y≠z) гласит попросту "кроме x и z, существует еще что-то". При этом есть небольшой подвох: нигде не говорится, что x отличается от z. Если x=z, то это условие говорит "есть минимум два элемента", а если x≠z, то "есть минимум три элемента".
С частью "то" интереснее. "Для любого t существует y, отличающееся от t и z". Если существуют хотя бы три разных элемента, это будет верным, можно в качестве y взять тот из них, кто не t и не z. Но и обратное верно: если ∀t∃y (t≠y and y≠z), то в качестве t мы можем вначале взять z, и отсюда заключить, что есть элемент, не равный z, а потом в качестве t взять этот элемент, и заключить, что есть третий, не равный этим двум. Поэтому вся часть после стрелки реально означает "существуют минимум три элемента".
Смысл первой части зависит от того, равны ли x и z. Если они неравны, тогда первая часть утверждает, что есть минимум три элемента, и вторая часть утверждает то же самое - все утверждение истинно тривиальным образом. Если же x=z, то дела обстоят сложнее: чтобы условие было верным, нужно минимум два элемента, а чтобы заключение - минимум три. Поэтому, "x=z и всего есть два элемента" - единственный вариант, при котором все утверждение не верно.
Мой перевод на человеческий язык: исходное утверждение эквивалентно
"если x равно z, то либо вообще любой элемент равен z, либо есть минимум два таких, что не равны z".
∃y (x≠y and y≠z) → ∀x∃y (x≠y and y≠z)
Тут, напомню, ∃ это "существует", а ∀ "для любого" - кванторы существование и всеобщности соответственно.
Всего несколько символов, но из-за чередования кванторов, даже не очень глубокого здесь, немножко заходит ум за разум. Я опишу дальше, как сам разбираю это утверждение, не читайте, если хотите сами подумать и разобраться.
Во-первых, это утверждение о каких-то конкретных x и z. При этом во второй половине, после стрелки импликации, вводится новая переменная x квантором ∀x, которая не имеет отношения к x в x≠y первой части. Если это запутывает, можно переименовать переменную под квантором, скажем, в t, и это ничего не изменит:
∃y (x≠y and y≠z) → ∀t∃y (t≠y and y≠z)
Итак, у нас есть выражение вида "если, то". Часть "если" ∃y (x≠y and y≠z) гласит попросту "кроме x и z, существует еще что-то". При этом есть небольшой подвох: нигде не говорится, что x отличается от z. Если x=z, то это условие говорит "есть минимум два элемента", а если x≠z, то "есть минимум три элемента".
С частью "то" интереснее. "Для любого t существует y, отличающееся от t и z". Если существуют хотя бы три разных элемента, это будет верным, можно в качестве y взять тот из них, кто не t и не z. Но и обратное верно: если ∀t∃y (t≠y and y≠z), то в качестве t мы можем вначале взять z, и отсюда заключить, что есть элемент, не равный z, а потом в качестве t взять этот элемент, и заключить, что есть третий, не равный этим двум. Поэтому вся часть после стрелки реально означает "существуют минимум три элемента".
Смысл первой части зависит от того, равны ли x и z. Если они неравны, тогда первая часть утверждает, что есть минимум три элемента, и вторая часть утверждает то же самое - все утверждение истинно тривиальным образом. Если же x=z, то дела обстоят сложнее: чтобы условие было верным, нужно минимум два элемента, а чтобы заключение - минимум три. Поэтому, "x=z и всего есть два элемента" - единственный вариант, при котором все утверждение не верно.
Мой перевод на человеческий язык: исходное утверждение эквивалентно
"если x равно z, то либо вообще любой элемент равен z, либо есть минимум два таких, что не равны z".