Apa itu kesetaraan beta?

21

Dalam skrip yang saat ini saya baca pada kalkulus lambda, kesetaraan beta didefinisikan sebagai ini:

The β -equivalence adalah kesetaraan terkecil yang berisi .βββ

Saya tidak tahu apa artinya itu. Adakah yang bisa menjelaskannya dengan istilah yang lebih sederhana? Mungkin dengan contoh?

Saya membutuhkannya untuk seorang lemma yang mengikuti teorema Gereja-Russer, mengatakan

Jika M N maka ada L dengan M L dan N L.β ββββ

agung
sumber
Maaf jika bahasanya tidak sempurna, saya menerjemahkan kutipan dari jerman.
magnattic

Jawaban:

20

β adalah hubungan satu langkah antara istilah-istilah dalamλ -kalkus. Hubungan ini tidak refleksif, simetris, atau transitif. Relasi ekivalensiβ adalah penutupan reflektif, simetris, transitifβ . Ini berarti

  1. Jika maka M β M .MβMMβM
  2. Untuk semua istilah , M β M berlaku.MMβM
  3. Jika , maka M ' ß M .MβMMβM
  4. MβM M β M MβMMβM
  5. β adalah hubungan terkecil yang memenuhi syarat 1-4.

Lebih konstruktif, pertama terapkan aturan 1 dan 2, lalu ulangi aturan dan berulang sampai mereka tidak menambahkan elemen baru ke relasi.434

Dave Clarke
sumber
1
Ok terima kasih, saya pikir saya mengerti. Asumsi pertama saya adalah bahwa berarti bahwa M entah bagaimana dapat direduksi menjadi N, tetapi itu tidak harus berlaku karena mereka jelas juga setara jika mereka dapat direduksi menjadi istilah yang sama. Karena poin Anda 3 ini dapat dibangun, kurasa. Terima kasih, itu banyak membantu. MβN
magnattic
Bukankah hubungannya sangat besar? Apakah saya tidak selalu dapat menemukan Term L untuk Term M sehingga ? LβM
Magnattic
Memang, tapi itu seharusnya tidak bermasalah. Mengapa Anda mencari huruf ? L.
Dave Clarke
Saya tidak tahu Saya hanya berdebat dengan pasangan saya jika selalu akan sangat besar. Terima kasih telah menjelaskan. :)
magnattic
11

Benar-benar teori himpunan elementer. Anda tahu apa itu hubungan refleksif, apa itu hubungan simetris, dan apa itu hubungan transitif, kan? Relasi ekivalensi adalah relasi yang memenuhi ketiga properti tersebut.

Anda mungkin pernah mendengar tentang "penutupan transitif" dari suatu hubungan ? Yah, itu tidak lain adalah hubungan transitif setidaknya yang mencakup . Itulah arti istilah "penutupan". Demikian pula, Anda dapat berbicara tentang "penutupan simetris" dari suatu hubungan , "penutupan refleksif" dari suatu hubungan dan "penutupan ekivalensi" dari suatu hubungan dengan cara yang persis sama.R R R RRRRRR

Dengan beberapa pemikiran, Anda dapat meyakinkan diri sendiri bahwa penutupan transitif adalah R R 2R 3 . Penutupan simetris adalah R R - 1 . Penutupan refleksif adalah R I (di mana saya adalah hubungan identitas). RRR2R3RR1RII

Kami menggunakan notasi untuk I R R 2 . Ini adalah penutupan transitif refleksif dari R . Sekarang perhatikan bahwa jika R simetris, masing-masing hubungan I , R , R 2 , R 3 , ... adalah simetris. Karenanya R juga akan simetris.RIRR2RRIRR2R3R

Jadi penutupan ekivalen dari adalah penutupan transitif dari penutupan simetrisnya, yaitu, ( R R - 1 ) . Ini mewakili urutan langkah, beberapa di antaranya adalah langkah maju ( R ) dan beberapa langkah mundur ( R - 1 ).R(RR1)RR-1

Relasi dikatakan memiliki properti Church-Rosser jika penutupan ekivalensi sama dengan relasi komposit R ( R - 1 ) . Ini mewakili urutan langkah-langkah di mana semua langkah maju datang pertama, diikuti oleh semua langkah mundur. Jadi, properti Church-Rosser mengatakan bahwa setiap interleaving langkah maju dan mundur dapat dilakukan secara setara dengan melakukan langkah maju pertama dan langkah mundur nanti.RR(R1)

Uday Reddy
sumber
2
Jika Anda menambahkan satu kalimat terakhir untuk dikaitkan dengan pertanyaan, ini akan menjadi jawaban yang baik.
Raphael
Semuanya sangat mendasar sehingga orang sampai pada akhirnya dan bertanya-tanya "di mana jawabannya, sebenarnya?"
Marco Faustinelli