Qual è la beta di equivalenza?

Question

Nello script Attualmente sto leggendo sul lambda calcolo, beta di equivalenza è definito come questo:

Il $ \ beta $ -equivalence $ \ equiv_ \ beta $ è l'equivalenza più piccolo che contiene $ \ rightarrow_ \ beta $.

Non ho idea di che cosa ciò significhi. Qualcuno può spiegare in termini più semplici? Forse con un esempio?

ho bisogno per un lemma segue dal teorema Chiesa-Russer, dicendo

Se M $ \ equiv_ \ beta $ N poi c'è una L con M $ \ twoheadrightarrow_ \ beta $ L e N $ \ twoheadrightarrow_ \ beta $ L.

Answer 1

$ \ to_ \ beta $ è il rapporto one-step tra i termini del $ \ lambda $ -calcolo. Questa relazione non è né riflessiva, simmetrica, o transitiva. La relazione di equivalenza $ \ equiv_ \ beta $ è il riflessiva, simmetrica, chiusura transitiva di $ \ to_ \ beta $. Questo significa

1. Se $ M \ to_ \ beta M '$ allora $ M \ equiv_ \ beta M' $.
2. Per tutti i termini $ M $, $ M \ equiv_ \ beta M $ detiene.
3. Se $ M \ equiv_ \ beta M '$, allora $ M' \ equiv_ \ beta M $.
4. Se $ M \ equiv_ \ beta M '$ e $ M' \ equiv_ \ beta M '' $, allora $ M \ equiv_ \ beta M '' $.
5. $ \ equiv_ \ beta $ è il rapporto più piccolo condizioni 1-4 soddisfacente.

in modo più costruttivo, applicare prima le regole 1 e 2, quindi ripetere governa $ 3 $ e $ 4 $ più e più volte fino a che non aggiungono nuovi elementi al rapporto.

Answer 2

Si tratta di teoria degli insiemi elementari davvero. Sapete che cosa è una relazione riflessiva, che cosa è una relazione simmetrica, e ciò che è una relazione transitiva, giusto? Una relazione di equivalenza è uno che soddisfa tutti e tre tali proprietà.

Probabilmente avete sentito parlare della "chiusura transitiva" di una relazione $ R $? Beh, non è altro che il relazione transitiva almeno , che include $ R $. Questo è ciò che il termine significa "chiusura". Allo stesso modo, si può parlare di "chiusura simmetrica" ??di una relazione $ R $, la "chiusura riflessiva" di una relazione $ R $ e la "chiusura equivalenza" di una relazione $ R $ esattamente nello stesso modo.

Con qualche pensiero, ci si può convincere che la chiusura transitiva di $ R $ è $ R \ tazza R ^ 2 \ tazza R ^ 3 \ tazza \ ldots $. La chiusura simmetrica è di $ R \ tazza R ^ {- 1} $. La chiusura riflessiva è di $ R \ tazza I $ (dove $ I $ è il rapporto di identità).

Usiamo la notazione $ R ^ * $ a $ I \ tazza R \ tazza R ^ 2 \ tazza \ ldots $. Questo è il chiusura transitiva riflessiva di $ R $. Ora notate che se $ R $ è simmetrica, ciascuna delle relazioni $ I $, $ R $, $ R ^ 2 $, $ R ^ 3 $, ... è simmetrica. Quindi $ R ^ * $ sarà anche simmetrica.

Quindi, alla chiusura di equivalenza di $ R $ è la chiusura transitiva della sua chiusura simmetrica, cioè, $ (R \ tazza R ^ {- 1}) ^ * $. Ciò rappresenta una sequenza di passi, alcuni dei quali sono passi in avanti ($ R $) e alcuni passi indietro ($ R ^ {- 1} $).

Il rapporto $ R $ si dice che abbia la proprietà di Church-Rosser se la chiusura di equivalenza è lo stesso che il composito relazione $ R ^ * (R ^ {- 1}) ^ * $. Ciò rappresenta una sequenza di fasi in cui tutti i passi avanti vengono prima, seguita da tutti i passi indietro. Così, la proprietà di Church-Rosser dice che qualsiasi interleaving di passi avanti e indietro può essere equivalentemente effettuata facendo avanti passi prima e passi indietro in seguito.