Kapan ruang koherensi memiliki pullback dan pushout?

$\newcommand{\symp}{\Bumpeq}$

Relasi koherensi pada set adalah relasi refleksif dan simetris. Ruang koherensi adalah pasangan , dan morfisme antara ruang koherensi adalah hubungan sedemikian sehingga untuk semua dan , $\symp_X$ $X$ $(X, \symp_X)$ $f : X \to Y$ $f \subseteq X \times Y$ $(x,y) \in f$ $(x',y') \in f$

jika $x \symp_X x'$ maka $y \symp_Y y'$ , dan
jika $x \symp_X x'$ dan $y = y'$ maka $x = x'$ .

Kategori ruang koherensi tertutup Cartesian dan monoid. Saya ingin tahu kapan pullback atau pushout ada untuk kategori ini, dan ketika ada beberapa analog pullback atau pushout monoid (dan bagaimana mendefinisikannya, kalau-kalau gagasan ini masuk akal).

pl.programming-languages ct.category-theory domain-theory linear-logic Neel Krishnaswami
sumber

Dari mana definisi ini? Yang ada di Girard, Lafont & Taylor terlihat sangat berbeda.

Charles Stewart

Kedua definisi itu setara. Saya hanya menganggap web sebagai primitif, dari mana kumpulan klik dapat diturunkan.

Neel Krishnaswami

Saya menemukan pilihan definisi Neel jauh lebih dapat dipahami daripada yang asli.

Dave Clarke

Saya akan menyatakan pertanyaan yang jelas: apakah Anda tahu bahwa mereka tidak selalu ada? Dengan kata lain, apakah Anda terbiasa dengan contoh-contoh dari functor ke dalam hubungan koherensi yang tidak memiliki batas / colimit?

Ohad Kammar

Kedua definisi itu setara - Benar, tetapi apakah Anda membuat definisi ini, atau apakah Anda mendapatkannya dari orang lain? Pertanyaan bagus, btw, saya terkejut bahwa tidak ada yang tahu apakah equalizer selalu ada.

Charles Stewart

~~Saya sekarang melihat bagaimana mendefinisikan equaliser untuk ruang koherensi, yang berarti kemunduran selalu ada (karena produk melakukannya).~~ Saya tidak tahu bagaimana melakukan ini, sebenarnya ....

Ingat komposisi itu adalah komposisi relasional yang biasa, jadi jika dan , maka: $f : A \to B$ $g : B \to C$

$f ; g = \{(a,c) \in A \times C \;|\; \exists b \in B.\; (a,b) \in f \land (b,c) \in g\}$

(Dalam definisi ini, eksistensial sebenarnya menyiratkan keberadaan unik . Misalkan kita memiliki sedemikian sehingga dan . Karena kita tahu bahwa , ini berarti . Maka ini berarti kita memiliki dan dan , jadi akibatnya .) $b' \in B$ $(a,b') \in f$ $(b', c) \in g$ $a \Bumpeq_A a$ $b \Bumpeq_B b'$ $b \Bumpeq_B b'$ $(b,c) \in g$ $(b',c) \in g$ $b = b'$

Kami sekarang membuat equaliser. Misalkan kita memiliki ruang koherensi dan , dan morphisms . Sekarang tentukan equalizer sebagai berikut. $A$ $B$ $f, g : A \to B$ $(E, e : E \to A)$

Untuk web, ambil Ini memilih subset token dari di mana baik dan setuju (hingga koherensi - saya memiliki kesalahan ini dalam versi pertama saya ), atau keduanya tidak ditentukan.
$E = {\begin{array}{lc} \forall b . (a, b) \in f ⟹ \exists a^{'} ≎_{A} a . (a^{'}, b) \in g \\ a \in A & \land \\ \forall b . (a, b) \in g ⟹ \exists a^{'} ≎_{A} a . (a^{'}, b) \in f \end{array}}$ $E = \left\{ \begin{array}{l|c} & \forall b.\; (a,b) \in f \implies \exists a' \Bumpeq_A a.\; (a',b) \in g \\ a \in A & \land \\ & \forall b.\; (a,b) \in g \implies \exists a' \Bumpeq_A a.\; (a',b) \in f \\ \end{array} \right\}$ $A$ $f$ $g$
Tentukan hubungan koherensi pada . Ini hanya pembatasan hubungan koherensi pada ke subset . Ini akan menjadi refleksif dan simetris karena adalah. $\Bumpeq_E = \{ (a,a') \in \Bumpeq_A \;|\; a \in E \land a' \in E\}$ $A$ $E$ $\Bumpeq_A$
Peta equalizer hanyalah diagonal . $e$ $e : E \to A = \{(a, a)\;|\;a \in E\}$

Karena saya mengacaukan versi bukti saya yang pertama, saya akan memberikan properti universalitas secara eksplisit. Misalkan kita memiliki objek lain dan morfisme sedemikian rupa sehingga . $X$ $m : X \to A$ $m;f = m;g$

Sekarang definisikan sebagai . Jelas , tetapi untuk menunjukkan kesetaraan kita perlu menunjukkan yang sebaliknya . $h : X \to E$ $\{(x,a) \;|\; a \in E\}$ $h;i \subseteq m$ $m \subseteq h;i$

Jadi asumsikan . Kita sekarang perlu menunjukkan bahwa dan . $(x,a) \in m$ $\forall b.\; (a,b) \in f \implies \exists a' \Bumpeq_A a.\; (a',b) \in g$ $\forall b.\; (a,b) \in g \implies \exists a' \Bumpeq_A a.\; (a',b) \in f$

Pertama, asumsikan dan . Jadi kita tahu bahwa dan , jadi . Oleh karena itu , dan ada sehingga dan . Karena , kita tahu , dan ada sedemikian rupa sehingga . $b \in B$ $(a,b) \in f$ $(x,a) \in m$ $(a,b) \in f$ $(x,b) \in m;f$ $(x,b) \in m;g$ $a' \in A$ $(x,a') \in m$ $(a',b) \in g$ $x \Bumpeq x$ $a \Bumpeq a'$ $a' \Bumpeq a$ $(a',b) \in g$

Secara simetris, asumsikan dan . Jadi kita tahu bahwa dan , jadi . Oleh karena itu , dan ada sehingga dan . Karena , kita tahu , dan ada sedemikian rupa sehingga . $b \in B$ $(a,b) \in g$ $(x,a) \in m$ $(a,b) \in g$ $(x,b) \in m;g$ $(x,b) \in m;f$ $a' \in A$ $(x,a') \in m$ $(a',b) \in f$ $x \Bumpeq x$ $a \Bumpeq a'$ $a' \Bumpeq a$ $(a',b) \in f$

Neel Krishnaswami
sumber

Saya tidak melihat bagaimana Anda dapat membuktikan universal. Hanya ada satu cara untuk memfaktorkan setiap , dan itu dengan menetapkan sebagai . Jelas , tapi saya tidak mengerti mengapa kebalikannya berlaku: ambil beberapa , dan beberapa , dengan . Maka kita memiliki , maka dari pilihan kita memiliki . Dari definisi komposisi, ada beberapa sedemikian sehingga dan . Kita dapat menyimpulkan bahwa

e

$e$

m : X \to A

$m : X \rightarrow A$

h : X \to E

$h : X \rightarrow E$

h := {(x, a) : (x, a) \in m, a \in E}

$h := \{(x, a) : (x,a) \in m, a \in E\}$

h; e \subset m

$h;e \subset m$

x m a

$xma$

b \in B

$b \in B$

a f b

$afb$

x (m; f) b

$x(m;f)b$

m

$m$

x (m; g) b

$x(m;g)b$

a^{'}

$a'$

x m a^{'}

$xma'$

a^{'} g b

$a'gb$

a \symp a^{'}

$a \symp a'$ , tapi kita hanya tahu dan , jadi kita tidak bisa menyimpulkan bahwa dan selesai.

a f b

$afb$

a^{'} g b

$a'gb$

a = a^{'}

$a=a'$

Ohad Kammar

Ya, Anda benar - subset yang dipilih equalizer harus sesuai dengan koherensi, bukan kesetaraan. Saya telah mengubah definisi untuk mencerminkan hal ini, dan memberikan bukti bahwa diagram tersebut berubah secara eksplisit.

Neel Krishnaswami

Ah ... Tapi sekarang tidak menyamakan diagram. Memang, asumsikan . Kemudian, menurut definisi , kita memiliki , maka ada beberapa sedemikian sehingga . Tapi kita tidak memiliki itu , jadi kami tidak dapat menunjukkan bahwa . Anda tampaknya mengalami masalah yang sama dengan yang saya alami tadi malam, karenanya pertanyaan saya yang jelas di atas. Tapi mungkin Anda akan berhasil di tempat saya gagal! Langkah saya selanjutnya adalah mengambil yang lebih canggih , katakan sesuatu seperti a , tetapi kemudian bukan morfisme yang valid, sehingga diperlukan beberapa pilihan yang lebih cermat.

e

$e$

a (e; f) b

$a(e;f)b$

e

$e$

a f b

$afb$

a^{'} \symp a

$a'\symp a$

a^{'} g b

$a'gb$

a e a^{'}

$aea'$

a (e; g) b

$a(e;g)b$

e

$e$

a e a^{'} ⟺ a \symp a^{'}

$aea' \iff a\symp a'$

e

$e$

Ohad Kammar

Saya sekarang ingat mengapa saya berharap jawabannya ada dalam tesis seseorang. :) Pokoknya, saya akan memikirkannya lebih lanjut - mungkin ada beberapa trik yang mungkin melalui fakta bahwa gambar terbalik berpasangan tidak koheren.

Neel Krishnaswami

Kapan ruang koherensi memiliki pullback dan pushout?

Jawaban: