Uma pseudovariedade de mon´oides ´e uma classe de mon´oides finitos fechada para produtos directos finitos, submon´oides e imagens homomorfas. Dada uma classe C de mon´oides finitos, a menor pseudovariedade de mon´oides que cont´em C ´e a classe de todas as imagens homo- morfas de submon´oides de um produto directo de um n´umero finito de elementos de C. Esta pseudovariedade de mon´oides diz-se a pseudovariedade de mon´oides gerada por C. O produto semidirecto V⋊W das pseudovariedades de mon´oides V e W ´e a pseudovariedade de mon´oides gerada por todos os produtos semidirectos monoidais M⋊N, com M ∈ V e N ∈ W. Analoga- mente definimos o produto semidirecto reverso V⋉W e o produto semidirecto bilateral V ⋊⋉ W das pseudovariedades de mon´oides V e W. Claramente temos V⋊W ⊆ V ⋊⋉ W e V⋉W ⊆ V ⋊⋉ W.
Nesta disserta¸c˜ao fazemos referˆencia `as seguintes pseudovariedades de mon´oides: 1. Ecom, a pseudovariedade de todos os mon´oides finitos cujos idempotentes comutam; 2. J, a pseudovariedade de todos os mon´oides J-triviais;
1.7. Pseudovariedades
3. L, a pseudovariedades de todos os mon´oides L-triviais; 4. R, a pseudovariedades de todos os mon´oides R-triviais; 5. A, a pseudovariedade de todos os mon´oides aperi´odicos;
6. Ab, a pseudovariedade de mon´oides de todos os grupos abelianos; 7. Ab2, a pseudovariedade de mon´oides gerada por C2;
8. O, a pseudovariedade de mon´oides gerada por {On| n ∈N}; 9. OD, a pseudovariedade de mon´oides gerada por {ODn| n ∈N}; 10. OP, a pseudovariedade de mon´oides gerada por {OPn| n ∈N}; 11. OR, a pseudovariedade de mon´oides gerada por {ORn| n ∈ N}; 12. Dih, a pseudovariedade de mon´oides gerada por {D2n | n ∈N}; 13. POI, a pseudovariedade de mon´oides gerada por {POIn| n ∈N}; 14. PODI, a pseudovariedade de mon´oides gerada por {PODIn | n ∈N}.
Para justificar a pertinˆencia dos resultados obtidos no Cap´ıtulo 4 que envolvem estas pseu- dovariedades, seleccion´amos certos factos acerca de algumas das pseudovariedades descritas em cima que mencionamos aqui. ´E bem conhecido que a pseudovariedade R ´e gerada por {T+
n | n ∈ N} e que a pseudovariedade J ´e gerada pelos mon´oides sint´acticos das linguagens test´aveis por peda¸cos e ´e tamb´em gerada por {O+n | n ∈ N} [60]. Temos ainda que as pseu- dovariedades R e J, assim como a pseudovariedade O, est˜ao contidas na pseudovariedade A. Por outro lado, a pseudovariedade O ´e auto-dual e n˜ao cont´em todos os semigrupos R-triviais embora toda a banda finita perten¸ca a O [39]. Na realidade, todo o semigrupo finito cujos idempotentes formam um ideal est´a contido na pseudovariedade O [70]. Temos ainda que a pseudovariedade POI est´a propriamente contida na pseudovariedade O [16, 40] e todo o produto semidirecto de uma cadeia (i.e. um semireticulado que forma uma cadeia para a ordem usual) por um semigrupo de O tamb´em pertence a O [32]. Finalmente, a pseudovariedade O n˜ao ´e finitamente baseada [62].
Em rela¸c˜ao `a pseudovariedade OP, sabemos que esta pseudovariedade ´e auto-dual e que cont´em todos os semigrupos comutativos [9].
Terminamos estas considera¸c˜oes referindo que a pseudovariedade J ∩ Ecom ´e gerada pelos mon´oides {POI+n | n ∈ N}, como foi provado em [40].
Cap´ıtulo 2
Mon´oides de transforma¸c˜oes totais
mon´otonas que preservam uma
parti¸c˜ao uniforme numa cadeia finita
Neste cap´ıtulo determinamos os cardinais e as caracter´ısticas dos mon´oides Om×n, O+m×n, Om×n− e ODm×n. Come¸camos por observar que, para m = 1 ou n = 1, os mon´oides Om×n, O+m×n, Om×n− e ODm×ncoincidem, respectivamente, com os mon´oides Omn, O+
mn, O−mne ODmn. Relembramos que o cardinal de On´e 2n−1n−1 e foi determinado por Howie em [41], que, juntamente com Gomes em [36], obteve a caracter´ıstica de On, que ´e n. Por sua vez, o cardinal de O+
n (que ´e igual ao de O−
n) ´e o n-´esimo n´umero de Catalan, i.e. n+11 2nn, e pode ser encontrado em [53], e as caracter´ısticas de O+
n e de On− s˜ao n − 1 (cf. Subsec¸c˜ao 1.4.1). Por fim, o cardinal de ODn ´e 2 2n−1n−1 − n e a sua caracter´ıstica ´e ⌈n
2⌉ + 1. Estas express˜oes foram obtidas por Fernandes, Gomes e Jesus em [23]. Assim, neste cap´ıtulo, consideramos m, n ≥ 2.
Na primeira sec¸c˜ao usamos o produto em coroa para caracterizar alguns destes mon´oides. Seguidamente, na segunda sec¸c˜ao, fornecemos express˜oes para os cardinais dos mon´oides men- cionados e terminamos, com a terceira sec¸c˜ao, onde estabelecemos as caracter´ısticas de Om×n, O+
m×n, O−m×n e ODm×n. Estes resultados encontram-se em [28], [29] e [30].
2.1
O produto em coroa
Tendo por objectivo neste cap´ıtulo encontrar os cardinais e as caracter´ısticas dos mon´oides Om×n, O+
m×n, Om×n− e ODm×n, dedicamos esta sec¸c˜ao ao produto em coroa. Come¸camos por recordar o isomorfismo entre Tm×ne Tn≀Tm estabelecido por Ara´ujo e Schneider em [5] e referido na Sec¸c˜ao 1.5. Depois, usamos este isomorfismo para caracterizar o mon´oides Om×n, O+m×n e O−
m×n.
Sejam α ∈ Tm×n e β ∈ Tm a aplica¸c˜ao definida por: para cada j ∈ {1, . . . , m}, jβ ´e o elemento de {1, . . . , m} tal que Ajα ⊆ Ajβ. Para cada j ∈ {1, . . . , m}, seja αj ∈ Tn definida
2. Os mon´oidesOm×n,O + m×n, O − m×n e ODm×n por kαj = ((j − 1)n + k)α − (jβ − 1)n, com k ∈ {1, . . . , n}. Sendo α = (α1, α2, . . . , αm; β) ∈ Tm n × Tm, a fun¸c˜ao ψ : Tm×n −→ Tn≀ Tm α 7−→ α ´e um isomorfismo.
Observamos que a restri¸c˜ao de ψ a Om×n n˜ao ´e, em geral, um isomorfismo de Om×n no produto semidirecto On ≀ Om. Por exemplo, para m = n = 2, tomemos α = (α1, α2; β), com α1 = 1 2 2 2 ! , α2 = 1 2 1 1 ! e β = 1 2 1 1 ! . Ent˜ao α ∈ O2 ≀ O2 e αψ−1 = 1 2 3 4 2 2 1 1 ! / ∈ O2×2.
De facto, o mon´oide Om×n n˜ao ´e, em geral, isomorfo a Om ≀ On. Por exemplo, podemos mostrar que |O2×2| = 19 enquanto |O2≀ O2| = 27.
Consideremos
Om×n= {(α1, . . . , αm; β) ∈ Om
n × Om | jβ = (j + 1)β implica nαj ≤ 1αj+1, para todo o j ∈ {1, . . . , m − 1}}.
Notemos que, se (α1, . . . , αm; β) ∈ Om×n e 1 ≤ i < j ≤ m s˜ao tais que iβ = jβ, ent˜ao nαi ≤ 1αj.
Proposi¸c˜ao 2.1.1 Om×n ´e um submon´oide de Tn≀ Tm (e de On≀ Om) isomorfo a Om×n. Demonstra¸c˜ao. O que faremos ´e demonstrar que Om×n = Om×nψ. Em particular obte- mos que Om×n ´e um submon´oide de On ≀ Om. Seja (α1, . . . , αm; β) ∈ Om×n e tomemos α = (α1, . . . , αm; β)ψ−1 ∈ Tm×n. Sejam x, y ∈ {1, . . . , mn} tais que x ≤ y. Ent˜ao x ∈ Ai e y ∈ Aj, para alguns 1 ≤ i ≤ j ≤ m. Assim, xα = (x − (i − 1)n)αi + (iβ − 1)n e yα = (y − (j − 1)n)αj+ (jβ − 1)n. Se i = j ent˜ao
x ≤ y ⇒ x − (j − 1)n ≤ y − (j − 1)n
⇒ (x − (j − 1)n)αj ≤ (y − (j − 1)n)αj
⇒ xα = (x − (j − 1)n)αj+ (jβ − 1)n ≤ (y − (j − 1)n)αj + (jβ − 1)n = yα . Se i < j e iβ < jβ ent˜ao xα ≤ (iβ)n ≤ (jβ − 1)n < (jβ − 1)n + 1 ≤ yα.
Finalmente, se i < j e iβ = jβ, ent˜ao (x − (i − 1)n)αi ≤ nαi ≤ 1αj ≤ (y − (j − 1)n)αj, donde xα = (x−(i−1)n)αi+(iβ −1)n ≤ (y−(j −1)n)αj+(iβ −1)n = (y−(j −1)n)αj+(jβ −1)n = yα. Consequentemente, α ´e uma transforma¸c˜ao crescente e portanto Om×n⊆ Om×nψ.
2.1. O produto em coroa
Reciprocamente, sejam α ∈ Om×n e (α1, . . . , αm; β) = αψ.
Come¸camos por mostrar que β ∈ Om. Sejam i, j ∈ {1, . . . , m} tais que i ≤ j. Como in ∈ Ai e Aiα ⊆ Aiβ, temos (in)α ∈ Aiβ. Analogamente, (jn)α ∈ Ajβ. Por outro lado, i ≤ j implica in ≤ jn e assim (in)α ≤ (jn)α. Conclu´ımos que iβ ≤ jβ.
A seguir, provamos que αj ∈ On, para qualquer 1 ≤ j ≤ m. Sejam j ∈ {1, . . . , m} e x, y ∈ {1, . . . , n} tais que x ≤ y. Ent˜ao (j − 1)n + x ≤ (j − 1)n + y, donde ((j − 1)n + x)α ≤ ((j − 1)n + y)α e assim xαj = ((j − 1)n + x)α − (jβ − 1)n ≤ ((j − 1)n + y)α − (jβ − 1)n = yαj.
Finalmente, seja j ∈ {1, . . . , m − 1} tal que jβ = (j + 1)β. Ent˜ao, como α ∈ Omn, temos nαj = ((j − 1)n + n)α − (jβ − 1)n = (jn)α − (jβ − 1)n
≤ (jn + 1)α − (jβ − 1)n = (jn + 1)α − ((j + 1)β − 1)n = 1αj+1. Portanto, Om×nψ ⊆ Om×n e assim Om×n = Om×nψ, como pretend´ıamos demonstrar. Consideremos
T+m×n= {(α1, . . . , αm; β) ∈ Tnm× Tm+ | jβ = j implica αj ∈ Tn+, para todo o j ∈ {1, . . . , m}}. Observemos que, como β ∈ T+
m implica mβ = m, ent˜ao T +
m×n⊆ Tnm−1× Tn+× Tm+. Proposi¸c˜ao 2.1.2 T+m×n ´e um submon´oide de Tn≀ Tm isomorfo a Tm×n+ .
Demonstra¸c˜ao. Com a finalidade de mostrar que T+m×n ⊆ Tm×n+ ψ, seja (α1, . . . , αm; β) um elemento de T+m×n e tomemos α = (α1, . . . , αm; β)ψ−1. Pretendemos provar que α ∈ Tmn+. Seja x ∈ {1, . . . , mn} e tomemos j ∈ {1, . . . , m} tal que x ∈ Aj. Ent˜ao xα ∈ Ajβ e, como β ∈ T+
m, temos j ≤ jβ. Se j < jβ ent˜ao j ≤ jβ − 1 e assim x ≤ jn ≤ (jβ − 1)n < (jβ − 1)n + 1 ≤ xα. Se jβ = j ent˜ao αj ∈ T+
m e assim x = x − (j − 1)n + (j − 1)n ≤ (x − (j − 1)n)αj+ (j − 1)n = xα. Donde, conclu´ımos que α ∈ T+
mn.
Reciprocamente, sejam α ∈ Tm×n+ e αψ = (α1, . . . , αm; β).
Primeiro, observemos que, para todo o j ∈ {1, . . . , m}, como Ajα ⊆ Ajβ e α ∈ Tm×n+ , temos jn ≤ (jn)α ≤ (jβ)n e assim j ≤ jβ. Donde β ∈ T+
m.
Seja j ∈ {1, . . . , m} tal que jβ = j e tomemos k ∈ {1, . . . , n}. Ent˜ao
kαj = ((j − 1)n + k)α − (jβ − 1)n ≥ (j − 1)n + k − (jβ − 1)n = (j − 1)n + k − (j − 1)n = k. Logo, αj ∈ T+
n e assim Tm×n+ ψ ⊆ T +
m×n, como quer´ıamos demonstrar e temos imediatamente provada a afirma¸c˜ao da proposi¸c˜ao.
Seja O+m×n = Om×n∩ T+m×n = {(α1, . . . , αm; β) ∈ Om−1 n × O+n × O+m | jβ = (j + 1)β implica nαj ≤ 1αj+1 e jβ = j implica αj∈ O+ n, para todo o j ∈ {1, . . . , m − 1}}.
2. Os mon´oidesOm×n,O +
m×n, O
−
m×n e ODm×n
Como ψ ´e injectiva, pelas Proposi¸c˜oes 2.1.1 e 2.1.2, temos
O+m×n= Om×nψ ∩ Tm×n+ ψ = (Om×n∩ Tm×n+ )ψ = O+m×nψ, pelo que:
Corol´ario 2.1.3 O+m×n ´e um submon´oide de Tn≀ Tm (e de On≀ Om) isomorfo a O+m×n. Analogamente, sendo O−m×n = {(α1, . . . , αm; β) ∈ O− n × Om−1n × O−m | (j − 1)β = jβ implica nαj−1 ≤ 1αj e jβ = j implica αj∈ O− n, para todo o j ∈ {2, . . . , m}}, temos:
Proposi¸c˜ao 2.1.4 O−m×n ´e um submon´oide de Tn≀ Tm (e de On≀ Om) isomorfo a O−m×n.