Apakah ada jenis non-sepele yang sama dengan turunannya sendiri?

Sebuah artikel yang disebut Derivatif Tipe Reguler adalah Tipe Konteks Satu Lubangnya menunjukkan bahwa "ritsleting" suatu tipe — konteks satu lubangnya — mengikuti aturan diferensiasi dalam aljabar jenis.

Kita punya:

\begin{aligned} \partial_{x} x & \mapsto 1 \\ \partial_{x} 0 & \mapsto 0 \\ \partial_{x} 1 & \mapsto 0 \\ \partial_{x} (S + T) & \mapsto \partial_{x} S + \partial_{x} T \\ \partial_{x} (S \times T) & \mapsto \partial_{x} S \times T + S \times \partial_{x} T \end{aligned}

$\begin{align} \partial_x x &\mapsto 1 \\ \partial_x 0 &\mapsto 0 \\ \partial_x 1 &\mapsto 0 \\ \partial_x (S + T) &\mapsto \partial_x S + \partial_x T \\ \partial_x (S\times T) &\mapsto \partial_xS \times T + S \times \partial_x T \end{align}$

Kita dapat menggunakan model ini untuk memperoleh bahwa turunan dari unit batal, bahwa turunan dari daftar adalah produk dari dua daftar (awalan waktu akhiran), dan seterusnya.

Pertanyaan alami untuk ditanyakan adalah, "apa jenis turunannya sendiri?" Tentu saja kita sudah memiliki , yang memberitahu kita bahwa void (tipe tidak berpenghuni) adalah turunannya sendiri, tetapi itu tidak terlalu menarik. Ini adalah analog dari fakta bahwa turunan nol adalah nol dalam kalkulus infinitesimal biasa. $\partial_x 0 \mapsto 0$

Apakah ada solusi lain untuk persamaan ? Secara khusus, apakah ada analog dari dalam tipe aljabar? Mengapa atau mengapa tidak? $\partial_x T \mapsto T$ $\partial_x e^x = e^x$

type-theory algebra Matthew Piziak
sumber

Ada dalam teori spesies kombinatorial, dan ada itu sesuai dengan spesies set (terbatas), tetapi itu tidak sesuai dengan tipe data aljabar.

Derek Elkins meninggalkan SE

Apa yang Anda maksud dengan "sama"? Di dunia Anda, apakah dan sama? Bagaimana dengan dan ?

(S + T) \to U

$(S + T) \to U$

(S \to U) \times (T \to U)

$(S \to U) \times (T \to U)$

N

$\mathbb{N}$

L i s t (N)

$\mathsf{List}(\mathbb{N})$

Andrej Bauer

@AndrejBauer Yang pertama ya, yang terakhir tidak. sama dengan produk iterasi dalam pikiran saya. Yang mengatakan, saya tidak memiliki model kesetaraan jenis yang ketat dalam pikiran saya, dan jika Anda memiliki model, Anda dapat mengarahkan saya pada saya akan senang membacanya.

L i s t (N)

$\mathsf{List}(\mathbb{N})$

1 + N + N \times N + N \times N \times N + \dots = \sum_{n = 0}^{\infty} N^{n}

$1 + \mathbb{N} + \mathbb{N} \times \mathbb{N} + \mathbb{N} \times \mathbb{N} \times \mathbb{N} + \ldots = \sum_{n=0}^{\infty} \mathbb{N}^{n}$

Matius Piziak

@DerekElkins ketika itu terjadi, artikel lain oleh McBride, yang disebut Clowns to the Left of me, Jokers to the Right menunjukkan bahwa, "Untuk struktur hingga, [iterasi dari operator pada resleting] memunculkan serangkaian seri power dari tipe data langsung, menemukan semua elemen dari kiri ke kanan .... Dengan demikian ada hubungan yang signifikan dengan gagasan spesies kombinatorial ". Jadi saya tidak akan terkejut jika spesies kombinatorial memiliki beberapa peran yang menarik untuk dimainkan dalam konteks pertanyaan ini juga.

Matius Piziak

@ MatthewPiziak Mereka pasti melakukannya. Brent Yorgey sudah membicarakan hal ini sedikit . Lihat juga tesisnya .

Derek Elkins meninggalkan SE

Jawaban:

Pertimbangkan multiset terbatas . Elemen-elemennya diberikan oleh dikutip oleh permutasi, sehingga untuk setiap . Apa konteks satu lubang untuk elemen dalam hal seperti itu? Nah, kita harus memiliki untuk memilih posisi untuk lubang, jadi kita dibiarkan dengan sisa $\mathbf{Bag}\:X$ $\{x_1,\ldots,x_n\}$ $\{x_1,\ldots,x_n\}=\{x_{\pi 1},\ldots,x_{\pi n}\}$ $\pi\in\mathbf{S}_n$ $n>0$ elemen, tetapi kita tidak tahu tentang mana. (Itu tidak seperti daftar, di mana memilih posisi untuk lubang memotong satu daftar menjadi dua bagian, dan potongan turunan kedua memilih salah satu bagian itu dan memotongnya lebih jauh, seperti "titik" dan "tanda" dalam editor, tapi saya ngelantur. ) Konteks satu lubang dalam huruf $n-1$ dengan demikian a $\mathbf{Bag}\:X$ , dan setiap $\mathbf{Bag}\:X$ dapat muncul dengan sendirinya. Berpikir secara spasial, turunan dari $\mathbf{Bag}\:X$ seharusnya menjadi dirinya sendiri. $\mathbf{Bag}\:X$

Sekarang,

B Sebuah g X = \sum_{n \in N} X^{n} / S_{n}

$\mathbf{Bag}\:X = \sum\limits_{n\in\mathbb{N}}X^n/\mathbf{S}_n$

pilihan ukuran tupel , dengan tupel elemen hingga grup permutasi urutan , memberi kita persis perluasan seri daya . $n$ $n$ $n!$ $e^x$

Naif, kita dapat mencirikan jenis kontainer oleh satu set bentuk dan keluarga bentuk tergantung dari posisi : $S$ $P$ sehingga wadah diberikan oleh pilihan bentuk dan peta dari posisi ke elemen. Dengan tas dan sejenisnya, ada sentuhan tambahan.

\sum_{s : S} X^{(P s)}

$\sum\limits_{s:S}X^{(P\,s)}$

"Bentuk" tas adalah beberapa ; "posisi" adalah , himpunan ukuran hingga , tetapi peta dari posisi ke elemen harus invarian dengan permutasi dari . Seharusnya tidak ada cara untuk mengakses tas yang "mendeteksi" pengaturan elemen-elemennya. $n\in\mathbb{N}$ $\{1,\ldots,n\}$ $n$ $\mathbf{S}_n$

Konsorsium Kontainer East Midlands menulis tentang struktur seperti itu dalam Membangun Program Polimorfik dengan Tipe-Tipe Quotient , untuk Matematika Konstruksi Program 2004. Kontainer-kontainer yang berkualitas memperluas analisis struktur yang biasa kita lakukan dengan "bentuk" dan "posisi" dengan membiarkan kelompok automorfisme bertindak pada posisi-posisi tersebut. , memungkinkan kita untuk mempertimbangkan struktur seperti unordered pasang , dengan turunan . Sebuah unordered -tuple diberikan oleh , dan turunannya (ketika adalah tidak berurutan $X^2/2$ $X$ $n$ $X^n/n!$ $n>0$ $n-1$ tuple). Tas mengambil jumlah ini. Kita dapat memainkan game serupa dengan cyclic -tuple, , di mana memilih posisi untuk hole memakukan rotasi ke satu tempat, meninggalkan , tuple yang lebih kecil tanpa permutasi. $n$ $X^n/n$ $X^{n-1}$

"Pembagian tipe" sulit dimengerti secara umum, tetapi pembagian oleh kelompok permutasi (seperti pada spesies kombinatorial) memang masuk akal, dan menyenangkan untuk dimainkan. (Latihan: merumuskan prinsip induksi struktural untuk pasangan unordered angka, , dan menggunakannya untuk melaksanakan penjumlahan dan perkalian sehingga mereka komutatif oleh konstruksi.) $\mathbb{N}^2/2$

Karakterisasi "bentuk-dan-posisi" wadah memaksakan kehalusan pada keduanya. Spesies kombinatorial cenderung terorganisir berdasarkan ukuran , bukan bentuk, yang berarti mengumpulkan istilah dan menghitung koefisien untuk setiap eksponen. Spesies-kontainer-dengan-posisi-set-terbatas dan spesies kombinatorial pada dasarnya berbeda berputar pada zat yang sama.

pekerja pigmen
sumber

Penulis asli muncul! Terima kasih telah datang untuk menunjukkan hasil yang indah ini kepada kami.

Matius Piziak

Bagaimana dengan jumlah tak terbatas Derivatifnya adalah yang sama dengan aslinya dengan asosiatifitas dan komutatifitas jumlah.

\sum_{i, j \in N} X^{i} ?

$\sum_{i, j \in \mathbb{N}} X^i ?$

\sum_{i, j \in N} \underset{i + 1}{\underset{⏟}{X^{i} + \dots + X^{i}}}

$\sum_{i, j \in \mathbb{N}} \underbrace{X^i + \cdots + X^i}_{i+1}$

Juga, jumlah tak terbatas sama dengan ), sehingga kami bisa mencoba untuk menghitung turunan menggunakan daftar. $\sum_{j \in \mathbb{N}} \mathsf{List}(X)$

Andrej Bauer
sumber

Turunan daftar adalah sepasang daftar (akhiran waktu akhiran). Berdasarkan aturan penjumlahan, turunan dari daftar daftar adalah daftar pasangan daftar. Apakah daftar pasangan berpasangan isomorfis dengan daftar daftar?

Matius Piziak

@MatthewPiziak Mungkin lebih mudah untuk memikirkan formulasi pertama sebagai

. Mengambil turunannya, kita mendapatkan

(dengan makna yang jelas untuk

). Sekarang, kita hanya perlu

. Bagi saya, ini terlihat sedikit mirip dengan (sangat informal)

, kecuali koefisien dari seri daya dipilih menjadi

\sum_{i \in N} N \times X^{i}

$\sum_{i\in \mathbb{N}} \mathbb{N}\times X^i$

\sum_{i \in N} i \times N \times X^{i}

$\sum_{i\in \mathbb{N}} i\times \mathbb{N}\times X^i$

i

$i$

N ≃ i \times N

$\mathbb{N}\simeq i\times \mathbb{N}$

e^{x} = \sum_{i} x^{i} / n!

$e^x = \sum_i x^i/n!$

+ \infty

$+\infty$ (yaitu,

), sehingga mereka dapat memenuhi

di dunia tanpa divisi.

N

$\mathbb{N}$

a_{n} = (n + 1) \cdot a_{n + 1}

$a_{n} = (n+1) \cdot a_{n+1}$

chi

@ MatthewPiziak Ups, saya menulis

bukannya

, tapi saya pikir sudah jelas apa yang saya maksud.

n

$n$

i

$i$

chi