20 6 18 1 2 2.1 A B α A B α: A B A B Rel(A, B) A B (A B) A B 0 AB A B AB α, β : A B α β α β def (a, b) A B.((a, b) α (a, b) β) 0 AB AB Rel(A, B) 1
2 A id A : A A A A id A def = {(a, a) A A a A} 1 { } 1 1 id 1 = 11 2.2 α: A B β : B C α β αβ : A C αβ def = {(a, c) A C b B.((a, b) α (b, c) β)} 2.3 α, α : A B β, β : B C γ : C D 1. (αβ)γ = α(βγ) 2. id A α = α = αid B 3. 0 XA α = 0 XB α0 BY = 0 AY 4. α α β β αβ α β 5. B AB BC = AC 2.4 A B {α λ : A B λ Λ} λ Λ α λ λ Λ α λ λ Λ α λ λ Λ α λ def = {(a, b) A B λ Λ.((a, b) α λ )} def = {(a, b) A B λ Λ.((a, b) α λ )} 2.5 α, β λ : A B λ Λ 1. α ( λ Λ β λ ) = λ Λ (α β λ ) 2. α ( λ Λ β λ ) = λ Λ (α β λ ) 2.6 α: A B β λ : B C λ Λ γ : C D
3 1. α( λ Λ β λ ) = λ Λ (αβ λ ) ( λ Λ β λ )γ = λ Λ (β λ γ) 2. α( λ Λ β λ ) λ Λ (αβ λ ) ( λ Λ β λ )γ λ Λ (β λ γ) 2.6 2.7 Λ = {1, 2} A = {a, b} α, β 1, β 2 : A A α = {(a, a), (a, b)}, β 1 = {(a, a)}, β 2 = {(b, a)} β 1 β 2 = 0 AA αβ 1 = {(a, a)} = αβ 2 α( λ Λ β λ ) = α(β 1 β 2 ) = α0 AA = 0 AA = {(a, a)} = αβ 1 αβ 2 = λ Λ (αβ λ ). 2.8 α: A B α : B A α def = {(b, a) B A (a, b) α} 2.9 α, α, α λ : A B λ Λ β : B C 1. α = α 2. (αβ) = β α 3. α α α α 4. ( λ Λ α λ ) = λ Λ α λ 5. ( λ Λ α λ ) = λ Λ α λ 6. 0 AB = 0 BA AB = BA id A = id A 2.10 α: A B β : B C γ : A C 1. αβ γ α(β α γ) 2. αβ γ (α γβ )β
4 3 3.1 α: A B A B α: A B A a {b B (a, b) α} B A B Map(A, B) A1 Map(A, 1) = { A1 } (a, b) α (a, b ) α b = b a A. b B.(a, b) α α α id B id A αα 3.2 f, h: A B g : B C 1. f g fg 2. f h f h fg (fg) (fg) = g f fg g id B g = g g id C. id A ff = fid B f fgg f = (fg)(fg). f h f h h = id A h ff h fh h fid B = f. f h f = h 3.2 f h
5 3.3 α: A B β : A B α β α β α = β 3.4 α: A B f : R A g : R B α = f g ff gg = id R R = α ((a, b), a ) f a = a ((a, b), b ) g b = b f g (a, b) f g (a, b ) α.(a, (a, b )) f ((a, b ), b) g (a, b ) α.(a = a b = b) (a, b) α α = f g f, g ((a, b), (a, b )) ff gg ((a, b), (a, b )) ff ((a, b), (a, b )) gg a = a b = b (a, b) = (a, b ) ((a, b), (a, b )) id R ff gg = id R f : A B id B f f ff id A id B f f ff id A 3.5 f : A B f f f f f f (f ) f = ff id A
6 f f id B f f = f (f ) f f ff = (f ) f id A f f id B f (f ) = f f. f f f f : A B f A f(a) = {b B f(a) = b} A f(a) f ˆf def ˆf(a) = f(a) ˆf f(a) B i f = ˆfi 3.6 f : A B m m = f f m: X B 3.4 f A1 m: X B g : X 1 f A1 = m g mm gg = id X X 1 X1 g = X1 mm = mm XX = mm X1 X1 = mm gg = id X m f A1 = m X1 f A1 1A = m X1 1A f A1 1X = m X1 1X, f AA = m XA f AX = m XX f AA f = m XA f = m XA f = m (f AX ) = m (m XX ) = m XX m
7 2.10 f f = f f f AA f = f f m XX m id B m XX m m (m XX m) = m m m m f f 3.6 m: X B i X f(a) ˆf 3.7 f : A B m: X B m m = f f f = gm g : A X fm : A X id A = id A id A ff ff = fm mf = (fm )(fm ) (fm ) (fm ) = mf fm = mm mm = id X id X = id X (fm )m = ff f f f = id A f ff f ff f fid A = f ff f = f f = (fm )m g = fm g f = gm g h: A X f = hm m h = hid X = hmm = fm = g 3.7 ˆf fm 3.8 f : A B f = gm g : A X m: X B 4 A B A (B) 4.1 A A : (A) A A def = {(S, a) (A) A a S}
8 4.2 f, g : A (B) f B = g B f = g a A f(a) = g(a) b f(a) S B.((a, S) f b S) S B.((a, S) f (S, b) B ) (a, b) f B (a, b) g B S B.((a, S) g (S, b) B ) S B.((a, S) g b S) b g(a). 4.3 α: A B f : A (B) α = f B f : A (B) (a, S) f S = {b B (a, b) α} a A S B α = f B (a, b) f B S (B).((a, S) f (S, b) B ) S (B).((a, S) f b S) S = {b B (a, b ) α} b S (a, b) α. f 4.2 f : A (B) f B A B 4.4 Rel(A, B) = Map(A, (B)) 5 5.1 ρ: A A 3 A a A.((a, a) ρ)
9 (a, b) ρ (b, c) ρ (a, c) ρ (a, b) ρ (b, a) ρ a = b A ρ a, b A.((a, b) ρ (b, a) ρ) 5.2 ρ: A A (a, b) ρ (b, a) ρ A ρ: A A id A ρ ρρ ρ ρ ρ id A ρ ρ = AA ρ ρ A A ρ A id A ρ ρρ ρ ρ ρ id A ρ A id A ρ ρρ ρ ρ ρ id A ρ ρ = AA ρ A id A ρ ρρ ρ ρ ρ 6 f : A B {(x, y) A A f(x) = f(y)} f(x) = f(y) z B.((x, z) f (y, z) f) z B.((x, z) f (z, y) f ) (x, y) ff ff f
10 f id A ff f (ff )(ff ) = f(f f)f fid B f = ff (ff ) = f f = ff 6.1 A ρ: A A ff = ρ f : A Y 4.3 ρ ρ = f A f : A (A) ρ f ff ff ρ = ff f A f A = ρ 3.4 ρ = u v u v uf A = uρ (f A = ρ ) vv uρ (v ) = vρ ρ (u v = ρ ) vρρ (ρ ) vρ (ρ ) = vf A (f A = ρ ) vf A = vρ (f A = ρ ) uu vρ (u ) = vρρ (u v = ρ ) vρ (ρ ) = vf A (f A = ρ ) uf A = vf A 4.2 uf = vf ρ = u v ff u vff (f ) = ff u uff (vf = uf ) ff ff (u ) ff (f ) ρ = ff 6.1 f : A (A) a A a
11 6.2 ρ: A A ρ = ff f : A (A) 1. a f(a) 2. (a, b) ρ f(a) = f(b) 3. f(a) f(b) f(a) f(b) = ρ (a, a) ρ (a, a) f A S A.((a, S) f (S, a) A ) S A.((a, S) f a S) a f(a) f(a) f(b) (a, b) ρ f(a) f(b) c A.((a, c) f A (b, c) f A ) (a, b) (f A )(f A ) (f A )(f A ) = ρρ ρρ ρ (a, b) ρ f(a) f(b) ρ: A A A A ρ 6.3 A ρ: A A pp = ρ p: A Q 6.1 ff = ρ f : A (A) 3.8 f : A (A) f = pm p: A Q m: Q B m ff = (pm)(pm) = pmm p = pp 6.3 Q A ρ p: A Q
12 7 [3] [1] [2] Allegory 1 [1] P.J. Freyd and A. Scedrov, Categories, Allegories (North-Holland, 1990). [2] P.T. Johnstone, Sketches of an Elephant: A Topos Theory Compendium, Vol.1 (Oxford University Press, 2002). [3] G. Schmidt and T. Ströhlein, Relations and Graphs (Springer-Verlag, 1993).