В сценарии, который я сейчас читаю по лямбда-исчислению, бета-эквивалентность определяется следующим образом:
-эквивалентность является наименьшей эквивалентности , который содержит .
Я понятия не имею, что это значит. Может кто-нибудь объяснить это более простыми словами? Может быть с примером?
Мне это нужно для леммы, вытекающей из теоремы Черча-Рассера:
Если M N, то есть L с M L и N \ twoheadrightarrow_ \ beta L.
logic
terminology
lambda-calculus
type-theory
magnattic
источник
источник
Ответы:
Более конструктивно: сначала примените правила 1 и 2, затем повторяйте правила3 и 4 снова и снова, пока они не добавят новые элементы в отношение.
источник
Это действительно элементарная теория множеств. Вы знаете, что такое рефлексивное отношение, что такое симметричное отношение и что такое транзитивное отношение, верно? Отношение эквивалентности - это такое, которое удовлетворяет всем трем из этих свойств.
Вы, наверное, слышали о «транзитивном замыкании» отношения ? Ну, это не что иное, как минимум транзитивное отношение , которое включает . Вот что означает термин «закрытие». Точно так же вы можете говорить о «симметричном замыкании» отношения , «рефлексивном замыкании» отношения и «замыкании эквивалентности» отношения точно таким же образом.R R R R R
Подумав немного, вы можете убедить себя, что транзитивное замыкание есть . Симметричное замыкание есть . Рефлексивным замыканием является (где - отношение идентичности).R R∪R2∪R3∪… R∪R−1 R∪I I
Мы используем обозначение для . Это рефлексивное транзитивное замыкание в . Теперь заметим, что если симметричен, то каждое из соотношений , , , , ... симметрично. Следовательно, также будет симметричным.R∗ I∪R∪R2∪… R R I R R2 R3 R∗
Таким образом, замыкание эквивалентности является транзитивным замыканием его симметричного замыкания, т. Е. . Это представляет последовательность шагов, некоторые из которых являются шагами вперед ( ) и шагами назад ( ).R (R∪R−1)∗ R R−1
Говорят, что отношение обладает свойством Черча-Россера, если замыкание эквивалентности совпадает с составным отношением . Это представляет собой последовательность шагов, в которой все шаги вперед идут первыми, а затем все шаги назад. Таким образом, свойство Черча-Россера говорит, что любое чередование шагов вперед и назад можно эквивалентно выполнить, выполнив шаги вперед вперед и шаги назад позже.R R∗(R−1)∗
источник