Apa operasi logaritma atau root di tipe-ruang?

Baru-baru ini saya membaca The Two Dualities of Computation: Negative and Fractional Types . Makalah ini memperluas jenis-jenis dan jenis-produk, memberikan semantik untuk jenis a - bdan a/b.

Tidak seperti penambahan dan perkalian, tidak ada satu tetapi dua invers dari eksponensial, logaritma, dan rooting. Jika tipe fungsi (a → b) adalah tipe-teoritik eksponensial, diberikan tipe a → b(atau b^a) apa artinya memiliki tipe logb(c)atau tipe a√c?

Apakah masuk akal untuk memperluas logaritma dan root ke tipe sama sekali?

Jika demikian, apakah ada pekerjaan di bidang ini, dan apa saja arahan yang baik tentang bagaimana memahami dampaknya?

Saya mencoba mencari informasi tentang hal ini melalui logika, berharap korespondensi Curry-Howard dapat membantu saya, tetapi tidak berhasil.

lo.logic pl.programming-languages type-theory algebra efrey
sumber

Jawaban:

Jenis memiliki logaritma dengan basis dari kapan tepatnya . Artinya, dapat dilihat sebagai wadah elemen di posisi yang diberikan oleh . Memang, itu soal meminta untuk apa daya harus kita menaikkan untuk mendapatkan . $C$ $X$ $P$ $C \cong P\to X$ $C$ $X$ $P$ $P$ $X$ $C$

Masuk akal untuk bekerja dengan mana adalah functor, setiap kali logaritma ada, artinya . Perhatikan bahwa jika , maka kita pasti memiliki , jadi wadah memberi tahu kita tidak ada yang menarik selain unsur-unsurnya: wadah dengan pilihan bentuk tidak memiliki logaritma. $\mathop{log}F$ $F$ $\mathop{log}\!_X(F\:X)$ $F\:X\cong \mathop{log}F\to X$ $F\:1\cong 1$

Hukum logaritma yang lazim masuk akal ketika Anda berpikir dalam hal set posisi

\begin{array}{rcll} l o g (K 1) & = & 0 & no positions in empty container \\ l o g I & = & 1 & container for one, one position \\ l o g (F \times G) & = & l o g F + l o g G & pair of containers, choice of positions \\ l o g (F \cdot G) & = & l o g F \times l o g G & container of containers, pair of positions \end{array}

$\begin{array}{rcl@{\qquad}l} \mathop{log} (\mathop{K}1) &=& 0 & \mbox{no positions in empty container}\\ \mathop{log} I &=& 1 & \mbox{container for one, one position}\\ \mathop{log} (F\times G) &=& \mathop{log}F+\mathop{log}G & \mbox{pair of containers, choice of positions} \\ \mathop{log} (F\cdot G) &=& \mathop{log}F\times\mathop{log}G & \mbox{container of containers, pair of positions} \end{array}$

Kami juga mendapatkan mana bawah binder. Yaitu, path ke setiap elemen dalam beberapa codata didefinisikan secara induktif dengan iterasi logaritma. Misalnya, $\mathop{log}\!_X(\nu Y. T) = \mu Z. \mathop{log}\!_X T$ $Z=\mathop{log}\!_XY$

l o g S t r e a m = l o g_{X} (ν Y . X \times Y) = μ Z . 1 + Z = N a t

$\mathop{log}\mathop{Stream} = \mathop{log}\!_X(\nu Y. X\times Y) = \mu Z. 1 + Z = \mathop{Nat}$

Mengingat bahwa turunan memberi tahu kita tipe dalam konteks satu lubang dan logaritma memberi tahu kita posisi, kita harus mengharapkan koneksi, dan memang

F 1 ≅ 1 \Rightarrow l o g F ≅ \partial F 1

$F\:1\cong 1 \;\Rightarrow\; \mathop{log}F\cong \partial F\:1$

Di mana tidak ada pilihan bentuk, posisi hanya sama dengan konteks satu lubang dengan elemen-elemen dihilangkan. Secara umum, selalu mewakili pilihan bentuk bersama dengan posisi elemen dalam bentuk itu. $\partial F\:1$ $F$

Saya khawatir saya tidak banyak bicara tentang akar, tetapi orang bisa mulai dari definisi yang sama dan mengikuti hidung seseorang. Untuk lebih banyak menggunakan jenis logaritma, periksa "Fungsi Memo Ralf Hinze, secara politis!". Harus lari ...

pekerja pigmen
sumber

Jawaban dari Da Man sendiri. Selamat datang Conor!

Andrej Bauer

Hmm, saya tertarik untuk melihat jenis akar apa, karena mereka akan membutuhkan jenis yang memiliki jumlah penduduk imajiner. Kecuali saya salah. Saya akan menerima jawaban Anda, tetapi jika Anda punya waktu untuk menguraikan akar-akar yang akan sangat dihargai.

efrey

Bisakah ini terkait dengan seri Taylor ln (1 + x) entah bagaimana?

yatima2975

Dengan logaritma dan eksponensial, saya bertanya-tanya ... apa yang kita butuhkan untuk membangun objek Napier ? (misalnya objek yang seharusnya unik eseperti itu ∂e = e)

Rhymoid

Saya tidak tahu ada pekerjaan yang mengejar baris ini, tetapi beberapa saat memikirkannya membawa saya ke hipotesis ini: bukankah "akar" dari tipe eksponensial hanya menjadi kodomain, dan "logaritma" dari eksponensial hanya domainnya?

Marc Hamann
sumber

Benar, jadi saya pikir intuisi Anda baik tetapi kesimpulan Anda tidak aktif. Operasi root dan operasi logaritma adalah apa yang Anda dapatkan ketika Anda "membalikkan" masing-masing domain atau domain, bukan domain (co) itu sendiri. Pertanyaannya adalah, apa yang kita maksud dengan membalikkan dan apa jenis operasi biner yang dihasilkannya?

efrey

Tidak yakin itu benar. Jika saya memiliki , akar ke- adalah dan basis logaritma adalah . Pembalikan dari operasi, bukan komponen.

x^{y}

$x^y$

y

$y$

x

$x$

x

$x$

y

$y$

Marc Hamann

Maaf, saya belum sepenuhnya jelas dalam terminologi saya. Saya tidak bermaksud bertanya "apa root, apa hasil dari penerapan fungsi logaritma". Saya bertanya-tanya apa operasi rooting. Apa operasi menemukan logaritma itu. Jika →expenentiation, apa dua jenis di bawah operasi root. Apa dua jenis di bawah operasi logaritma. Yang saya maksud dengan "membalikkan argumen" adalah sesuatu yang tidak ada waktu untuk menjelaskannya di sini. Saya akan menjelaskan pertanyaan saya, terima kasih.

efrey

Makalah yang saya tautkan menyediakan semantik untuk jenis a - bdan jenisnya a / b. Saya tidak peduli dengan hasil mengurangi operasi logaritma dan root, tetapi dalam memahami semantik mereka sebagai operator tipe biner.

efrey