Transformasi dan Parametrisitas Alami

11

Dalam Teorema Gratis! , Wadler mengatakan bahwa karakterisasi parametrik dapat diekspresikan kembali dalam hal transformasi alami yang lemah dan ini akan menjadi subjek makalah lebih lanjut. Kertas mana yang dia maksud?

Pendekatan kategoris ke paramtericty saya tahu menggunakan transformasi dinatural seperti dalam Functorial Polymorphism oleh Bainbridge, Freyd, Scedrov dan PJ Scott. Apa hubungan antara lemahnya transformasi alami dan formulasi transformasi dinamik dari parametrik?

reference-request ct.category-theory parametricity sonat
sumber
2
Saya hampir takut untuk membuat komentar ini, tetapi saya akan mengaku bahwa saya tidak mengerti kata teknis dalam pertanyaan ini. Mungkinkah menambahkan beberapa tautan ke definisi untuk pakar (mengerikan) ini?
Suresh Venkat
1
Sepertinya pekerjaan untuk @UdayReddy.
Dave Clarke
5
Sejauh yang saya tahu, makalah yang dimaksud dalam Teorema Gratis! (sayangnya) tidak pernah ditulis. Saya cukup yakin pemahaman parametrisitas saat ini dalam hal teori kategori paling baik ditangkap oleh Scones dan kategori koma . Lihat misalnya Mitchell & Scedrov dan ini n-Kategori Café pos.
cody
Suresh, maaf karena tidak memberikan tautan yang relevan. Cody, terima kasih telah mengedit posting dan menyebutkan scone dan kategori koma.
sonat

Jawaban:

8

Sayangnya, pernyataan Wadler terlalu samar bagi saya untuk mengatakan apa yang ingin ia gunakan dari "kelemahan transformasi alami". Ini tebakan. Kotak relasi-pelestarian sering dapat disusun kembali sebagai kotak komutatif longgar. Ini adalah bagaimana mereka dulu ditulis dalam kertas / buku teori automata tua. Lihat paragraf 1.2 dalam Catatan saya tentang Semigroup . Untuk melakukan hal semacam ini, Anda harus mencampuradukkan hubungan dan morfisme dan berpura-pura sama. Saya juga tidak yakin bahwa itu memberi Anda sesuatu yang baru. Ini hanya notasi yang lebih buruk untuk mengatakan hal yang sama dengan pelestarian hubungan.

Silakan menjelajahi koneksi, tetapi saya tidak yakin Anda akan menemukan sesuatu yang baru dengan melakukannya.

Uday Reddy
sumber
Terima kasih banyak untuk tautannya. Formulasi dalam paragraf 1.2 masih menetapkan teori untuk saya. Bagaimana Anda berbicara tentang inklusi? Apakah Anda berasumsi bahwa kategorinya adalah alegori atau memiliki sifat seperti topos? Jika ini adalah reformualtion dari transformasi alami yang lemah, apa yang menjadi 2-kategori yang mendasarinya? Saya juga membaca bagian "Pengkategorian" tetapi tidak dapat menemukan apa pun tentang lemahnya transformasi alami.
sonat
x→yx≤yf→gf≤gR⊆S:Rel(A,B)
Oh, jadi kategorinya sudah diperbaiki! Saya pikir Wadler merujuk pada formulasi yang lebih umum dan abstrak yang masuk akal dalam kelas kategori tertentu yang mengandung Rel sebagai kasus khusus (dan agak sepele). Jika kita hanya bekerja di Rel, tidak ada gunanya memperkenalkan struktur yang lebih tinggi namun berdegenerasi. Sekarang saya mengerti jawaban awal Anda.
sonat
@ SonatSüer: Jika Anda tertarik dengan generalisasi, cara standar untuk menggeneralisasi hubungan ke kategori selain dari Set adalah memperlakukannya sebagai "bentang monic bersama". Anda mungkin mendapatkan kategori yang diperkaya dengan pesanan di muka alih-alih diperkaya dengan poset, tetapi struktur 2-kategori masih sama.
Uday Reddy
@ SonatSüer: Dan, jika Anda benar-benar tertarik pada teori aksiomatik yang tepat yang mencakup semua yang kami ketahui, saya dapat merujuk Anda ke makalah kami yang terbaru Hubungan logis dan Parametrikitas - Program Reynolds .
Uday Reddy