Revista de Matema´tica: Teor´ıa y Aplicaciones 2013 20(1) : 79–94 cimpa – ucr issn: 1409-2433 sobre una construccio´n de un monoide libre con identidad sobre un topos E con el objeto de los nu´meros naturales about the construction of a free monoid with identity on a topos E with the object of natural numbers Osvaldo Acun˜a Ortega∗ Received: 17/May/2012; Revised: 4/Dec/2012; Accepted: 5/Dec/2012 ∗CIMPA & Escuela de Matema´tica, Universidad de Costa Rica, 2060 San Jose´, Costa Rica. 79 80 o. acun˜a Resumen Damos una construccio´n del monoide libre con identidad sobre un objeto X,M(X). Donde M(X) = {R ∈ ΩN×N×X/R es funcional y ∃n∈N dom R = [n]} iX−−→ ΩN×N×X . Palabras clave: Teor´ıa de topos, objetos K–finitos, nu´meros naturales. Abstract We proved that the free monoid with identify in X is M(X) = {R ∈ ΩN×N×X/R es funcional y ∃n∈N dom R = [n]} iX−−→ ΩN×N×X . Keywords: Topoi, K–finite objects, natural numbers. Mathematics Subject Classification: 03G30, 18B25. 1 Introduccio´n En [2] probamos que M(X) es un monoide con identidad y que |= R ∈ M(X)⇒ dom R = [L(R)], donde L :M(X) −→ (N,+) es un homomor- fismo de monoides con identidad. 2 Resultados previos Para cada X ∈ |E|, E es un topos con el objeto de los numeros naturales, defina jX : X −→ Ω N×N×X tal que |= jX(a) = {(0, 0, a)}. Lema 1 jX se factoriza a trave´s de M(X). Demostracio´n. |= (n,m, b) ∈ jX(b) ∧ (n,m, b) ∈ jX(b) ⇒ (n,m, b) = (n,m, b)⇒ b = b por lo tanto jX es funcional y |= dom jX(a) = ∃pr12({(0, 0, a)}) = {pr12(0, 0, a)}= {(0, 0)}= [1] entonces |= dom jX(a) = [1] y |= jX(a) ∈M(X). Define ηX : X −→M(X) el u´nico morfismo tal que ηX ◦ iX = jX . Proposicio´n 2 M(−) se puede extender a un functon de manera u´nica tal que M(−) se transforma en un subfuncton de ΩN×N×−; tiene al functor identidad de E como un subfunctor, via η. Ma´s au´n M(−) se factoriza a trave´s de la categor´ıa de los monoides con identidad de E. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 81 Demostracio´n. Debemos probar que para cualquier flecha g : X −→ Y de E, existe una u´nica flecha M(g) : M(X) −→ M(Y ) tal que en el siguiente diagrama ambos cuadrados conmutan: Para probar la existencia de M(g) y la conmutatividad del cuadrado su- perior es suficiente probar internamente que ∃id×g manda elementos de M(X) en elementos de M(Y ). (i) ∃id×g(R) un funcional si R es funcional: |= (n,m, b) ∈ ∃id×g(R) ∨ (n,m, b) ∈ ∃id×g (R) ⇒ ∃k1(n,m, x1) ∈ R ∧ g(x1) = b ∧ ∃x2(n,m, x2) ∈ R ∧ g(x2) = b ⇒ ∃x1∃x2(n,m, x1) ∈ R ∧ (n,m, x2) ∈ R ∧ g(x1) = b ∧ g(x2) = b ⇒ ∃x1∃x2x1 = x2 ∧ g(x1) = b ∧ g(x2) = b ⇒ b = b. (ii) |= dom ∃id×g(R) = dom (R): |= (n,m) ∈ dom ∃id×g(R) ⇔ ∃b∈Y (n,m, b) ∈ ∃id×g (R) ⇔ ∃b∃xg(x) = b ∧ (n,m, x) ∈ R ⇔ ∃x∃bg(x) = b ∧ (n,m, x) ∈ R ⇔ ∃x(n,m, x) ∈ R ⇔ (n,m) ∈ dom R. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 82 o. acun˜a Por lo tanto |= dom ∃id×g (R) = dom R y luego |= `(∃id×g(R)) = `(R). (i) y (ii) dicen que ∃id×g ◦ iX se factoriza a travez de M(X), por lo tanto existe una flecha u´nica M(g) tal que ∃id×g ◦ iX = iY ◦M(g). Probaremos ahora que el siguiente diagrama conmuta: |= ∃id×g (jX(a)) = ∃id×g{(0, 0, a)}= {id×g(0, 0, a)}= {(0, 0, g(a))} entonces como |= jY (g(a)) = {(0, 0, g(a))} se tiene que |= ∃id×g(jX(a)) = jY (g(a)) y entonces |= ∃id×g ◦ jX = jY ◦ g. Por definicio´n de ηX tenemos que ∃id×g ◦ iX ◦ ηX = iY ◦ ηY ◦ g, pero ∃id×g ◦ iX = iY ◦M(g) Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 83 y entonces iY ◦M(g) ◦ ηX = iY ◦ ηY ◦ g lo que implica que M(g) ◦ ηX = ηY ◦ g dado que iY es mo´nica y as´ı se tiene que conmuta: La unicidad de M(g) es consecuencia de su definicio´n y del hecho de que iY es mo´nico, esto prueba que M(idX) = idM (X) y M(f ◦ g) = M(f) ◦M(g). Hemos visto que para todo X ∈ |E|, M(X) es un monoide con identidad. La u´nica cosa que falta por probar es la conmutatividad de los siguientes diagramas: (i) Es suficiente probar que ∃idXg(R1 ∗R2) = ∃idXg(R1) ∗ ∃idXg(R2) Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 84 o. acun˜a donde R1 y R2 son variables de tipo M(X): |= (n,m, b) ∈ ∃id×g(R1 ∗R2) ⇔ ∃xg(x) = b ∧ (n,m, x) ∈ R1 ∗R2 ⇔ ∃xg(x) = b ∧ ∃k1((n, k1, x) ∈ R1 ∨ (k1, m, x) ∈ R2) ∧n +m+ 1 = `(R1) + `(R2) ⇔ ∃k1(∃xg(x) = b ∧ (n, k1, x) ∈ R1 ∨ ∃xg(x) = b ∧ (k1, m, x) ∈ R2) ∧n +m+ 1 = `(R1 + `(R2)) ⇔ ∃k1((n, k1, b) ∈ R1 ∨ (k1, m, x) ∈ R2) ∧ n+m+ 1 = `(R1) + `(R2) ⇔ (n,m, b) ∈ ∃id×g (R1) ∗ ∃id×g (R2). Por lo tanto |= ∃id×g(R1 ∗R2) = ∃idXg(R1) ∗ ∃idXg(R2). (ii) Es suficiente probar que |= ∃idXg(φX) = φY ; esto es claro ya que ∃idXg tiene un adjunto derecho Ω idXg entonces preserva coproductos. Recuerde que φX : 1 −→ Ω X es el objeto inicial de la categor´ıa interna ΩX . Denotemos la categor´ıa de monoides con identidad de E por monoide (E). Hemos visto que M(−) es un functor de E a monoide (E). Debemos probar que el diagrama es tal que M(−) es un adjunto izquierdo del functor i (inclusio´n). Sea r˜ : M(X) −→ ΩN×N×X definido por |= r˜(R) = {(n,m, x)/(n, s(m), x) ∈ R} donde s : N −→ N es el morfismo sucesor. Lema 3 r˜ se factoriza por M(X) y |= `(r˜(R)) = p(`(R)), donde p : N −→ N es la funcio´n predecesor. Demostracio´n. (i) r˜(R) es funcional: |= (n,m, x) ∈ r˜(R) ∧ (n,m, x) ∈ r˜(R) ⇒ (n, s(m), x) ∈ R ∧ (n, s(m), x) ∈ R⇒ x = x. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 85 (ii) |= dom (r˜(R)) = [p ◦ `(R)]: |= (n,m) ∈ dom (r˜(R)) ⇔ n+ s(m) + 1 = `(R) ⇔ p(n+ s(m) + 1) = p(`(R)) ⇔ n+ p(s(m)) + 1 = p(`(R)) ⇔ n+m+ 1 = p(`(R)) ⇔ (n,m) ∈ [p(`(R))]. Defina r : M(X) −→ M(X) la u´nica flecha tal que iX ◦ r = r˜. Sea ϑ el subobjeto de M(X)×X dado por {(R, x)/(p(`(R)), 0, x) ∈ R} −−→ inc` M(X)×X donde inc` es la inclusio´n. Lema 4 (i) ϑ es funcional. (ii) dom ϑ = {R ∈M(X)/`(R)> 0}. (iii) ( inc` φX ) : dom ϑ+ 1 −→M(X) es un isomorfismo. Demostracio´n. (i) Evidente, en particular existe un morfismo u´nico θ : dom ϑ −→ X tal que |= (p(`(R)), 0, θ(R)) ∈ R. (ii) |= R ∈ dom ϑ ⇔ ∃x(R, x) ∈ ϑ ⇔ ∃x(p(`(R)), 0, x) ∈ R ⇔ (p(`(R)), 0) ∈ dom R ⇔ p(`(R)) + 0 + 1 = `(R) ⇒ p(`(R)) + 1 = `(R) ⇒ `(R) > 0. ∴ dom ϑ ⊆ {R/`(R) > 0} Por otro lado |= `(R) > 0 ⇒ s(p(`(R))) = `(R) ⇔ p(`(R)) + 1 = `(R) ⇔ R ∈ dom ϑ. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 86 o. acun˜a Por lo tanto dom θ ⊇ {R/`(R) > 0} y entonces dom ϑ = {R/`(R) > 0}. (iii) Los cuadrados de los siguientes diagramas son productos fibrados: El diagrama de la derecha es un producto fibrado por (ii). El dia- grama de la izquierda claramente conmuta, queremos demostrar que es un produto fibrado: |= R ∈ `−1(0) ⇒ `(R) = 0 (ya que `(R) = dom R) ⇒ dom R = φ ⇒ Ωpr12( dom R) = Ωpr12(φ) = φ (∃pr12 ` Ω pr12) ⇒ R ≤ Ωpr12( dom R) = φ ⇒ R = φ (donde pr12 es la proyeccio´n N × N×X −→ N × N). Esto prueba que el cuadrado izquierdo es un producto fibrado. Por universalidad del producto fibrado a lo largo de ` y como N = 1+ s(N), se tiene que ( inc` φX ) es un isomorfismo. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 87 Lema 5 |= r(R) ∗ iX(θ(R)) = R. Demostracio´n. |= (n,m, x) ∈ r(R) ∗ iX(θ(R)) ⇔ ∃k1((n, k1, x) ∈ r(R) ∨ (k1, m, x) ∈ iX(θ(R))) ∧ n+m+ 1 = `(R) ⇔ ∃k1((n, s(k1), x) ∈ R ∧ s(k1) = m) ∨∃k1(k1 = 0 ∧m = 0 ∧ x = θ(R)) ∧ n+m+ 1 = `(R) ⇒ (n,m, x) ∈ R ∨ (m = 0 ∧ (p(`(R)), 0, x) ∈ R) ∧ n +m+ 1 = `(R) ⇒ (n,m, x) ∈ R ∨ (m = 0 ∧ n+ 1 = `(R) ∧ (p(`(R)), 0, x) ∈ R) (como |= n+ 1 = `(R)⇔ n = p(`(R))) ⇒ (n,m, x) ∈ R ∨ (n,m, x) ∈ R ⇒ (n,m, x) ∈ R. Por lo tanto r(R) ∗ iX(θ(R)) ⊆ R. Por otro lado tenemos que: |= (n,m, x) ∈ R ⇒ ((n,m, x) ∈ R ∧m > 0) ∨ ((n, 0, x) ∈ R ∧m = 0) ⇒ ∃k1((n,m, x) ∈ R ∧m = s(k1)) ∨ ((n, 0, x) ∈ R ∧m = 0) ⇒ ∃k1((n, s(k1), x) ∈ R ∧ s(k1) = m) ∨((p(`(R)), 0, x) ∈ R ∧m = 0 ∧ n = p(`(R))) ⇒ ∃k1((n, s(k1), x) ∈ R ∧ s(k1) = m) ∨∃k1 (k1 = 0 ∧m = 0 ∧ x = θ(R) ∧ n +m+ 1 = `(R)) ⇔ (n,m, x) ∈ r(R) ∗ iX(θ(R)). Luego |= R ⊆ r(R) ∗ iX(θ(R)) y as´ı |= R = r(R) ∗ iX(θ(R)). Proposicio´n 6 Si (B, ·, e) es un objeto monoide con identidad en un topos E y f : X −→ B cualquier flecha en E, entonces existe a lo sumo una flecha h que preserva productos e identidad tal que el siguiente dia- grama conmuta: Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 88 o. acun˜a Demostracio´n. Suponga que existen flechas h1, h2 : M(X) → B que preservan la estructura de monoide con identidad de M(X) y h1 ◦ ηX = h2 ◦ ηX . Considere {n/∀R∈M (X)(`(R) = n⇒ h1(R) = h2(R))} −→ N. Denote este subobjeto de N por S. Queremos probar que S = N. Sabemos que |= `(R) = 0⇒ R = φ; por lo tanto tenemos que: |= `(R) = 0 ⇒ R = φ ⇒ h1(R) = h2(R) = e y as´ı |= `(R) = 0 ⇒ h1(R) = h2(R) y as´ı |= 0 ∈ S. Por otro lado tenemos (por lemas 3 y 5) |= n ∈ S ∧ `(R) = s(n) ⇒ R = r(R) ∗ iX(θ(R)) ∧ `(r(R)) = n ∧ n ∈ S ⇒ h1(iX(θ(R))) = h2(iX(θ(R))) ∧R = r(R) ∗ iX(θ(R)) ∧ h1(r(R)) = h2(r(R)) ⇒ h1(R) = h2(R). Entonces |= n ∈ S ∧ `(R) = s(n) ⇒ h1(R) = h2(R) si y solo si |= n ∈ S ⇒ (`(R) = s(n)⇒ h1(R) = h2(R)), y entonces |= n ∈ S ⇒ s(n) ∈ S. Por el principio de induccio´n S = N y h1 = h2. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 89 Lema 7 Si B ∈ |E|, tiene una seccio´n global ν : 1 −→ B, entonces existe un morfismo natural Jν : M(B) −→ B N×N con respecto B. Demostracio´n. Si R es una variable del tipo M(B), Jν esta´ definida internamente por: |= Jν(R) = {(n,m, b)/(n,m, b) ∈ R∨q(n+m+ 1 = `(R)) ∧ b = ν)}. (i) jν(R) es funcional: (como [|q(n+m + 1 = `(R)) ∧ (n+m+ 1 = `(R))|] = φ) |= (n,m, b) ∈ Jν ∧ (m, n, b ′) ∈ Jν(R)⇒ ((n,m, b) ∈ R ∧ (n,m, b ′) ∈ R)∨ (b = ν ∧ b′ = ν∧q((n+m+1) = `(R))∨ (b′ = ν∧q(n+m+1 = `(R))∧ (n,m, b) ∈ R)∨ (b = ν∧q(n+m+1 = `(R))∧ (n,m, b′) ∈ R) ⇒ b = b′ ∨ b = b′ ⇒ b = b′. (ii) dom Jν(R) = p N×Nq: es claro que |= n+m+ 1 = `(R)⇔ (n,m) ∈ dom R⇔ ∃b∈B(n,m, b) ∈ R, por lo tanto |= n+m+ 1 = `(R)∨q(n+m+ 1 = `(R)) ⇒ ∃b∈B(n,m, b) ∈ R∨q(n+m+ 1 = `(R)) (como |= ∃b∈Bb = ν) ⇒ ∃b∈B(n,m, b) ∈ R∨q(n+m+ 1 = `(R)) ∧ ∃b(b = ν) ⇒ ∃b∈B((n,m, b) ∈ R∨q(n+m+ 1 = `(R) ∧ b = ν)) ⇔ ∃b∈B(n,m, b) ∈ Jν(R). Luego |= n+m+ 1 = `(R)∨q(n+m+ 1 = `(R))⇒ ∃b∈B(n,m, b) ∈ Jν(R), lo que es equivalente a [|n+m+ 1 = `(R)∨q(n+m+ 1 = `(R))|] ⊆ [|∃b∈B(n,m, b) ∈ Jν(R)|]; pero [|n+m+ 1 = `(R)∨q(n+m+ 1 = `(R))|] = verdad, Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 90 o. acun˜a y entonces [|∃b∈B(n,m, b) ∈ Jν(R)|] = verdad. As´ı debemos tener que |= ∃b∈B(n,m, b) ∈ Jν(R), por lo tanto |= ∀(n,m)∃b∈B(n,m, b) ∈ Jν(R), es decir |= dom Jν(R) = pN× Nq y (i), (ii) nos dicen que Jν se factoriza por BN×N. Probemos que Jν es natural, esto es si f : B −→ B ′ es cualquier flecha entonces el siguiente diagrama conmuta: |= fN×N(Jν(R)) = fN×N({(n,m, b)/(n,m, b) ∈ R∨q(n+m+ 1 = `(R))∧ b = ν}) = ({(n,m, f(b))/(n,m, b) ∈ R∨q(n+m+ 1 = `(R)) ∧ b = ν}) = {(n,m, b′)/∃b((b ′ = f(b) ∧ (n,m, b) ∈ R) ∨q(n+m+ 1 = `(R)) ∧ b = ν ∧ b′ = f(b))} = {(n,m, b′)/(n,m, b′) ∈M(f)(R)∨q(n+m+ 1 = `(R)) ∧ b′ = f(ν)} = Jf◦ν(M(f)(R)), pero esto es |= fN×N(Jν(R)) = Jf◦ν(M(f)(R)), lo que prueba la naturalidad de Jν . Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 91 3 Construccio´n del monoide Sea (B, ·, e) un monoide con identidad. Nosotros aplicaremos el u´ltimo lema a la identidad e : 1 −→ B y entonces podemos definir la siguiente flecha: donde k : N → N×N es el isomorfismo de Cantor y es la flecha iteracio´n- finita definida en (1). Proposicio´n 8 Sea (B, ·, e) un monoide con identidad e : 1 → B, en- tonces: (i) El siguiente diagrama conmuta (ii) µB :M(B) −→ B preserva productos. Demostracio´n. Claramente tenemos que (i) |= Je({(0, 0, b)}) = {(n,m, x)/(0, 0, b) = (n,m, x) ∨ x = e ∧ (n ∈ s(N) ∨m ∈ s(N))} entonces |= BK(Je(iB(b))) = {(n, k)/(n, k) = (0, b)∨ x = e ∧ n ∈ s(N)}, Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 92 o. acun˜a por lo tanto |= (BK(Je(iB(b))), `(iB(b))) = ({(n, x)/(n, x) = (0, b)∨ x = e ∧ n ∈ s(N)}, 1). Como |= ∑ 1 = 1 y |= `(iB(b)) = 1, tenemos que |= (BK(Je(iB(b))), 1) = e ◦ b = b por propiedades de y entonces |= µB(iB(b)) = b. (ii) Por induccio´n tenemos: sea S = {n/∀R1, ∀R2(`(R1) = n⇒ µB(R1 ∗R2) = µB(R1) · µR(R2))}. (α) Hemos visto que |= `(R2) = 0⇒ R2 = φ, entonces |= µB(φ) = (B K× ∑ ((Je, `)(φ))) = (({(n, x)/x= e}, 0)) = e, por lo tanto |= `(R2) = 0⇒ µB(R1 ∗ φ) = µB(R1) · µB(φ) = µB(R1) y as´ı |= `(R2) = 0⇒ µB(R1 ∗R2) = µB(R1) · µB(R2), entonces |= 0 ∈ S. (β) Para cualquier variable R de tipoM(B) como `(R) > 0 tenemos por las propiedades ba´sicas de que: |= (BK(Je(R ∗ iB(b))), `(R)∑ 0 i+ `(R) + 1) = (BK ◦ Je(R ∗ iB(b)), `(R)∑ 0 i+ `(R)) · b de la construccio´n de Je tenemos: |= BK(Je(R ∗ iB(b)))i = B K ◦ Je(R)(i− `(R)). Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 sobre la construccio´n de un monoide libre... 93 Tenemos que (BK(Je(R ∗ iB(b)))j, `(R)∑ 0 i+ `(R) + 1) = (BK(Je(R)(j − `(R))), `(R)∑ 0 i+ `(R)) · b = (BK(Je(R))j, `(R)∑ 0 i) · b, por lo tanto |= (BK ◦ Je(R ∗ iB(b)), `(R)+1∑ 0 i) = (BK ◦ Je(R), `(R)∑ 0 i) · b y entonces |= µB(R ∗ iB(b)) = µB(R) · b. Por otro lado |= n ∈ S ∧ `(R2) = s(n)⇒ µB(R1 ∗R2) = µB(R1 ∗ (r(R2) ∗ iB(θ(R2)))) = µB((R1 ∗ r(R2)) ∗ iB(θ(R2))) = µB(R1 ∗ r(R2)) · θ(R2) = (µB(R1) · µB(r(R2))) · θ(R2) = µB(R1) · µB(r(R2) ∗ iB(θ(R2))) = µB(R1) · µB(R2), entonces |= n ∈ S ∧ `(R2) = s(n)⇒ µB(R1 ∗R2) = µB(R1) · µB(R2), o equivalentemente |= n ∈ S ⇒ (`(R2) = sn ⇒ µB(R1 ∗R2) = µB(R1) · µB(R2)); y entonces |= n ∈ S ⇒ s(n) ∈ S. Por inducio´n tenemos que N = S y la prueba queda lista. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013 94 o. acun˜a Teorema 9 (M(X), ηX) es el monoide libre generado por X . Demostracio´n. Sea g : X −→ B cualquier flecha y (B, ·, e) es un monoide con identidad e : 1 −→ B. La proposicio´n 8 nos dice que existe µB : M(B) −→ B tal que preserva productos y µB ◦ φ B = e, por lo tanto tenemos que el siguiente diagrama conmuta: M(g) preserva productos e identidades y entonces µB◦M(g) hace lo mismo por la proposicio´n 6, µB ◦M(g) es u´nico tal que conmuta: por lo tanto ηX es una flecha universal y la prueba queda completa. Referencias [1] Acun˜a–Ortega, O. (1977) Finiteness in Topoi, Ph. D. Dissertation, Wesleyan University, Middletown, CT. [2] Acun˜a–Ortega, O. (2011) “Una nota sobre objetos k − finitos en un topos Booleano con el objeto de los nu´meros naturales”, Revista de Matema´tica: Teor´ıa y Aplicaciones 19(2): 239–245. [3] Acun˜a–Ortega, O.; Linton, F.E.J. (1979) “Finiteness and decidability I”, in: Applications of Sheaves, Lecture Notes in Mathematics 753, Springer–Verlag, New York: 80–100. Rev.Mate.Teor.Aplic. (ISSN 1409-2433) Vol. 20(1): 79–94, January 2013