self study IEA: Introdução a Estruturas Algébricas

Sessões

IEA (0) & CFR1 (0): Pré e Introdução [video]

• Introdução meta
• Revisão: type errors, linguagem de demonstrações matemáticas
• Exemplos: teoremas sobre a transitividade da (|)

hw

1. Trabalhe nos pré-requisitos.
2. Dê uma lida nos Capítulos 1 e 2.
3. A gente viu no #intro-lang-proofs › aplicando a mesma função nos dois lados como justificar (demonstrar) isso, descubrindo que é uma propriedade fundamental das funções. Desafio: usando uma linguagem de programação que já usou no IMD, mostre que ela não merece usar o termo «função» mostrando como quebrar essa regra. Proibido usar qualquer coisa de random. Postem tentativas/brigas/dúvidas no #programming.
4. Uma tentativa para resolver o hw anterior foi a seguinte: considerar, em JavaScript, que temos 1 == '1' mas f(1) != f('1') onde f é “a função” x => x + 1. O desafio deste hw é achar um motivo bom para desconsiderar essa como resposta válida para o hw anterior.

IEA (1): Introdução [video]

• Os inteiros e sua estrutura
• Propriedades de operações
• Aridades, nulária, unária, e constantes
• Os strings com concatenação
• Associatividade e como a definir
• Parseamento e árvore sintáctica
• A idéia da abstração algébrica
• Trade-off entre axiomas e modelos
• O papel dum exemplo-guia para uma estrutura algébrica
• Comutatividade
• Permutações, sua notação, e o S₃
• Enter Álgebra: a operação (∘)
• Do exemplo-guia S₃ para a definição de grupo
• inversos e um problema de escopo
• «Existe único …» e como expressá-lo
• Θ. (id-uniq)

hw.1

1. Cap. 10: §«Permutações»
2. Escreva sozinho uma demonstração completa da unicidade de identidade numa estrutura de grupo. Quais leis tu precisou mesmo?
3. Demonstre a unicidade dos inversos.
4. Infira teoremas que envolvem mais que um dos três protagonistas da alma de grupo: a operação (binária), a identidade, e os inversos. Por exemplo: o inverso do inverso deve ser o quê? O inverso da identidade? Etc. (O Etc é importantíssimo!)
5. (Para quem não trabalhou ainda no IDMa:) Cap. 3: §«Primeiros passos»

IEA (2): Grupos [video]

• Definição de grupo
• grupos aditivos vs multiplicativos
• teoria dos grupos e as primeiras conseqüências
• (canL) cancelamento pela esquerda
• detalhamento das justificativas
• aplicando a mesma função nos dois lados
• como demonstrar com apenas um cálculo
• (id-!) unicidade da identidade
• (resR) resoluções únicas
• (inv-id), (inv-inv), (inv-op)
• igualdade não é exatamente simétrica
• uns exemplos e nãoexemplos
• como definir operações
• tabelas Cayley e Grupoku™

hw.2

1. Capítulo «Teoria dos grupos»: até §«Tabelas de Cayley»

IEA (3) [video]

• Mais sobre Grupoku
• umas primeiras potências em grupo
• associatividade sintáctica e precedência sintáctica
• duas definições de potências para n ≥ 0 e sua equivalência
• potências negativas
• diagramas comutativos
• ordem de grupo e de membro de grupo
• o ℘A munido com qual das (∪),(∩),(),(∆), vira um grupo?

hw.3

1. Capítulo «Teoria dos grupos»: até p.447.
2. Demonstre a equivalência entre as duas definições alternativas de potência (x10.40)
3. Ache as ordens de todos os membros do grupo S₃
4. Sejam $G$ grupo e $a \in G$. Se $a^m = e$ para algum $m\in\mathbb{Z}_{\neq0}$, então $o(a)<\infty$.
5. Demonstre ou refute: G abeliano ⇔ (∀a,b:G)[ (ab)⁻¹ = a⁻¹b⁻¹ ]
6. Demonstre ou refute: G abeliano ⇔ (∀a,b:G)[ (ab)² = a²b² ]
7. Demonstre: Se para 3 consecutivos inteiros i, temos (∀a,b:G)[ (ab)ⁱ = aⁱbⁱ ], então G é abeliano.
8. Demonstre que trocando o 3 por 2 no hw anterior, vira-se indemonstrável.
9. Problemas: Π10.1, Π10.2, Π10.4, Π10.5, Π10.6, Π10.7

Prova IEA.1

IEA (4) [video]

• proposições disfarçadas como igualdades
• Θ. o(a) = n ⇔ existem exatamente n potências distintas de a
• Θ. aᵐ = e ⇔ o(a) | m
• Subgrupos: duas idéias para chegar na sua definição
• um grupo de ordem infinita, pode ter subgrupos de ordem finita?

hw.4

1. Capítulo «Teoria dos grupos»: até §«Subgrupos»
2. O que foi o ? da aula que apareceu nos tipos ? → G e ? → H?
3. Qual o tipo da (≤) que definimos na aula?
4. A (≤) é uma preordem? Ela é uma ordem parcial?
5. Sejam G grupo e K ⊆ H ⊆ G. Suponha que K,H≤G. Podemos inferir que K≤H?
6. No segundo critério visto na aula consideramos o dado G fin. Podemos substituir por H fin? O teorema/critério fica mais fraco ou mais forte assim?
7. No mesmo critério quais dados exatamente precisamos?

IEA (5) [video]

• subgrupos triviais e não-triviais
• podemos usar o termo subgrupo mesmo?
• é a mesma operação mesmo?
• Q: podemos definir uma nova operação num subgrupo?
• O plano complexo e sua interpretação geométrica
• uns (sub)grupos de complexos
• Q: conclusões sobre (⊆) e (≤)
• Critéria de ser subgrupo e o que significa critério
• primeiro critério
• segundo critério e uma dica sobre como demonstrar
• terceiro critério
• o que acontece se apagar um dado do contexto dum teorema

IEA (6) [video]

• Qual o tipo mesmo da (≤)?
• Interseção de subgrupos é subgrupo
• (Como) podemos estender o teorema sobre interseção de subgrupos?
• Tentativa de estender para união
• O que precisamos demonstrar para estendar sobre interseções arbitrárias?
• Q: podemos só demonstrar o teorema sobre as interseções arbitrárias?
• Duas relações que acabam sendo de equivalência: $\mathrm R_H$ e conjugação
• Subgrupo gerado por membro de grupo: ⟨a⟩
• Subgrupo gerado por subconjunto de grupo: ⟨A⟩ (bottom-up)

hw.6

1. Capítulo «Teoria dos grupos»: até §«Geradores» (cuidado: re-baixe o fmcbook pois o §«Conjugação de grupo», foi locomovido, e faz parte deste hw!
2. Problemas: Π10.1; Π10.2; Π10.7; Π10.8; Π10.11; Π10.12; Π10.13

IEA (7) [video]

• recap: subgrupo gerado por A: bottom-up
• subgrupo gerado por A: top-down
• conjuntos convexos: bottom-up e top-down do convex hull
• mais recap: as relações de equivalência de conjugados e do $\mathrm R_H$
• investigando a $\mathrm R_H$
  • Caso ambos no $H$
  • Caso um dentro um fora do $H$
  • Caso ambos fora do $H$
• A partição induzida pela $\mathrm R_H$

hw.7

1. Desafio: achar conjunto inicial $A$ no plano que demora chegar no $\langle A \rangle$ (conjunto convexo gerado pelo $A$).

IEA (8) [video]

• Coclasses de subgrupo
• Partição do grupo 𝒢 pelas coclasses de H
• Demonstração do teorema de Lagrange
• indice de subgrupo
• Corolário de Lagrange: subgrupos de G com o(G) primo
• a notação Hab²Kb⁻¹KKcaH…etc
• Q: $\mathcal L_H ≟ \mathcal R_H$

hw.8

1. Demonstre que as abordagens top-down e bottom-up concordam para a definição de ⟨A⟩.
2. Demonstre o que faltou para o teorema de Lagrange
   • (i) cada linha tem membros frescos
   • (ii) cada linha tem membros distintos dois-a-dois
3. Demonstre que $\mathcal L_H$ é uma partição de $\mathcal G$, e a $\mathcal R_H$ também.
4. Ache H≤𝒢 tais que $\mathcal L_H \neq \mathcal R_H$.

IEA (9) [video]

• Sobre a top-down e bottom-up abordagem do subgrupo gerado por um subconjunto
• demonstração que as duas abordagens definam o mesmo subgrupo
• improve e seus fixpoints
• Uns grupos de inteiros (aditivos e multiplicativos)
• Mais (corolários de) Lagrange
• partições feitas por coclasses e as relações módulo subgrupo
• o teorema de Euler (FMC1-IDMa) como corolário de Lagrange
• HK ≤ G? KH ≤ G?
• Um exemplo onde $\mathcal L_H \neq \mathcal R_H$
• Uma primeira definição de subgrupo normal e umas equivalentes

hw.9

1. Demonstre que a improve : Set G → Set G é (⊆)-monotônica
2. Θ. Sejam H,K ≤ G. Demonstre: HK = KH ⇔ HK ≤ G
3. Seja N ≤ G. O.s.s.e.:
   • (i) $\mathcal R_H = \mathcal L_H$
   • (ii) $(\mathrm R_H) = (\mathrm L_H)$
   • (iii) $N$ é fechado pelas conjugações
   • (iv) $(\forall g \in G)[ gNg^{-1} \subset N ]$
   • (v) $(\forall g \in G)[ gNg^{-1} = N ]$
   • (vi) $(\forall g \in G)[ gN = Ng ]$
4. Até §«Teoria dos números revisitada»

IEA (10) [video]

• Conjunto quociente
• Congruências
• Grupo quociente
• Entendendo melhor os grupos aditivos ℤ/mℤ
• Definições equivalentes para subgrupo normal
• Significado de igualdade para 3 tipos diferentes
• Relação de equivalência sobre uma partição
• Aviso sobre um erro comum usando gN=Ng ou HK=KH
• {e,ψ,ψ²} ⊴ S₃?

IEA (11) [video]

• Θ. HK = KH ⇔ HK ≤ G
• O grupo das simetrias de um triangulo equilátero
• Quão “novo” é realmente esse grupo?
• “tem a cara” de S₃ e como formalizar isso
• Desenhando os (N)Sub(S₃) e (N)Sub(ℤ/6ℤ)
• Homomorfismo
• Isomorfismo
• Um homomorfismo trivial
• Critério de homomorfismo

hw.10

1. Capítulo «Teoria dos grupos», até §«Morfismos»

IEA (12) [video]

• possíveis conflitos sobre a definição de homomorfismo
• Critérion de homomorfismo de grupos
• kernel (núcleo) e imagem
• Θ. φ injetiva ⇔ kerφ = {⋆}
• Qual a mais forte afirmação sobre kerφ?
• Θ. kerφ ⊴ A
• Θ. G/kerφ ≅ imφ
• kernel ⇒ normal & kernel ⇐ normal ??

hw.11

1. Demonstre sem nenhuma consulta o último palpite da aula: $G/\ker{\varphi} \cong \mathrm{im}\varphi$
2. Capítulo «Teoria dos grupos», §«Kernel, Image»
3. Problemas: Π10.22; Π10.23; Π10.27; Π10.28

Prova IEA.2

IEA (13) [video]

• As idéias principais até agora, vistas no mundo dos grupos
• Teoremas vs Modelos
• As simetrias dum quadrado
• Classes de conjugações
• Hom, End, Aut, Inn, e prefixos de morfismos
• Cuidados sobre teoremas de outras teorias
• Como considerar leis como parte da estrutura
• Teaser FMC3: álgebra universal
• Magma, Semigrupo, Monóide, Grupo, Abel
• Galois e Abel
• potências e generalização para operar em listas
• Tentando aproveitar critéria
• Anéis
• Convenções sintácticas sobre anéis
• Anéis comutativos, Rngs, e Rigs
• Homomorfismo de anéis
• Subanéis

hw 12

1. Resolva finalmente os não resolvidos hw! (Especialmente sobre: Hom(G,G’), Aut(G), Inn(G), etc.)
2. Capítulo «Estruturas Algébricas»: até §«Anéis»
3. Problema: Π11.1

CFR2 (4) & IEA (14): CATS 🐱 (1) [video]

• O que é uma categoria: dados (interface) e leis
• Exemplos de categorias
  • Categoria a partir dum monóide
  • Categoria a partir duma estrutura algébrica (𝐌𝐚𝐠𝐦𝐚, 𝐒𝐞𝐦𝐢𝐠𝐫𝐨𝐮𝐩, 𝐌𝐨𝐧𝐨𝐢𝐝, 𝐆𝐫𝐨𝐮𝐩, 𝐀𝐛𝐞𝐥, 𝐑𝐢𝐧𝐠, …)
  • As categorias 𝟘, 𝟙, 𝟚
  • Categoria a partir duma preordem
• Definições categoriais
  • Objeto terminal
  • Objeto inicial

hw

1. Como definarias a categoria 𝟛?
2. Como definarias a categoria 𝕟?
3. Para cada uma das categorias que encontramos, determina seus objetos iniciais e seus objetos terminais, caso existam. Caso contrário, verifique tal ausência.
   1. As categorias 𝟘, 𝟙, 𝟚, 𝟛, …
   2. A categoria ℂ[ℳ] baseada a um monóide ℳ.
   3. A categoria ℂ[(ℕ;≤)], i.e., a categoria baseada no ℕ com sua (pre)ordem canônica (≤))
   4. A categoria ℂ[(ℤ;≤)]
   5. A categoria ℂ[(ℤ;|)]
   6. A categoria ℂ[(℘S;⊆)]
   7. As categorias de umas estruturas algébricas: $\mathbf{Semigroup}$, $\mathbf{Monoid}$, $\mathbf{Group}$, $\mathbf{Abel}$, $\mathbf{Ring}$

CFR2 (5) & IEA (15): CATS 🐱 (2) [video]

• Definição de categoria (recap)
• Exemplos (antigos e novos)
• categorias magras (thin)
• categorias discretas
• categorias a partir de linguagens de programação
• categorias a partir de sistemas de lógica
• objetos: terminal; inicial; zero
• setas: (split) mono; (split) epi; iso
• objetos isômorfos
• Θ. os terminais são isômorfos
• categoria oposta e o princípio da dualidade
• conceitos «self-dual»
• presente da dualidade: Θ (gratuito). os iniciais são isômorfos
• produto e coproduto de dois objetos
• traduzindo e procurando produtos e coprodutos em umas categorias
• abuso do artigo definido
• diagram chasing
• Plicker: tem produtos e coprodutos na categoria 𝐆𝐫𝐨𝐮𝐩?

hw

1. Para cada uma das categorias que encontramos até agora traduza os conceitos de «produto» e «coproduto» e verifique se elas possuem ou não
2. A mesma coisa sobre os conceitos de «terminal», «inicial», «zero», já que conhecemos mais categorias desde a aula anterior
3. Verifique que a (≅) de «é isômorfo a» é uma relação de equivalências nos objetos de qualquer categoria
4. Demonstre que todos os produtos de dois objetos A,B são isômorfos («unicidade» de produtos)
5. Demonstre que todos os coprodutos de dois objetos A,B são isômorfos («unicidade» de coprodutos)
6. Tente definir categorias onde os objetos são:
   1. as categorias(!)
   2. as setas de uma data categoria ℂ

CFR2 (6) & IEA (16): CATS 🐱 (3) [video]

• Propriedades universais
• (≅) é uma relação de equivalência
• Uma categoria com setas matrizes
• (Re)definindo monóides, grupos, grupóides
• A categoria das setas de ℂ
• As categorias “comma”: slice ou over (ℂ/C); coslice ou under (C/ℂ)
• Functors e a categoria 𝐂𝐚𝐭
• Functors em programação funcional
• O que seriam setas entre functors?
• Plicker: A × 1 ≅ A? A × 0 ≅ 0?

hw

1. Escreva sozinho as definições categoriais que conhecemos até agora.
2. Fixe duas categorias ℂ,𝔻. Considere cada functor ℂ → 𝔻 como um objeto em uma nova categoria. Como definarias as setas nessa nova categoria?
3. Traduza os conceitos categoriais que temos definido até agora nas novas categorias que conhecemos.
4. Entre na 𝐀𝐛𝐞𝐥. Sejam 𝒜,ℬ objetos desse mundo. Mostre que o grupo abeliano 𝒜×ℬ definido usando as operações component-wise é um produto dos 𝒜,ℬ mesmo (com quais setas?). Mostre que o mesmo grupo abeliano é um coproduto dos 𝒜,ℬ (com quais setas?).
5. O 𝐑𝐢𝐧𝐠 tem inicial? Terminal?
6. Suponha que a $\mathbb C$ tem (co)produtos. A $\mathbb C^{\to}$ tem (co)produtos?
7. Investiga a existência de (co)produtos e (co)terminais nas categorias “comma” ℂ/C e C/ℂ (slice ou over; e coslice ou under).
8. Na aula encontramos maneiras de (re)definir os conceitos de monóide e de grúpo. No mesmo estilo como (re)definarias os conceitos de «homomorfismo entre monóides» e «homomorfismo entre grupos»?
9. Defina functors:
   1. De 𝐆𝐫𝐨𝐮𝐩 para 𝐌𝐨𝐧𝐨𝐢𝐝
   2. De 𝐑𝐢𝐧𝐠 para 𝐀𝐛𝐞𝐥
   3. De 𝐑𝐢𝐧𝐠 para 𝐌𝐨𝐧𝐨𝐢𝐝
   4. De 𝐌𝐨𝐧𝐨𝐢𝐝 para 𝐒𝐞𝐭
   5. De 𝐒𝐞𝐭 para 𝐌𝐨𝐧𝐨𝐢𝐝
   6. De ℂ[ℳ] para 𝐒𝐞𝐭, para uns monóides ℳ que tu gosta
   7. De ℂ[𝒢] para 𝐒𝐞𝐭, para uns grupos 𝒢 que tu gosta

IEA (17): Estruturas Algébricas e mais [video]

• Recap: Noether, kernel, normal
• Recap: estruturas e axiomatizações usando apenas equações
• Ring, Rig, Rng, Distributividade (binária e nulária)
• Domínios de integridade e de cancelamento
• Corpos
• Corpos ordenados
• Corpos ordenados completos
• A unicidade do corpo ordenado completo (esboço)
• Q: outras estruturas? Reticulados, álgebras booleanas, …

hw

1. Um anel é chamado anel booleano sse todos seus membros são idempotentes: (∀x)[x = x²]. Demonstre que em qualquer anel booleano:
   1. (∀x)[x = -x]
   2. (∀x,y)[xy = -yx]
2. Seja R anel comutativo. Demonstre: R é DI ⇔ R é DC.
3. Todo anel booleano é comutativo.
4. Demonstre que todo domínio de integridade finito é um corpo.
5. Seja φ homomorfismo entre corpos. A φ precisa respeitar os (·)-inversos?
6. Capítulo «Estruturas algébricas»: todo.
7. Problemas: Π10.24; Π10.25; Π10.26; Π11.1

IEA (18): Teoremas de Representação; Módulos e espaços vetoriais [video]

• kernel ⇔ normal
• Teoremas de representação
• Um teorema de Cayley e um teorema de Cauchy
• Esboço da demonstração do teorema de Cayley
• Algebras Booleanas e o teorema de representação de Stone
• Aneis e Módulos; Corpos e Espaços Vetoriais
• Plicker: prontos pra provas?

hw

1. Demonstre o teorema de Cayley: todo grupo é isomorfo àlgum subgrupo de algum grupo simétrico.
2. Demonstre o teorema de Cauchy para os grupos abelianos: para todo grupo abeliano 𝒜 de ordem n, e todo primo p que divide o n, existe a∈A com o(a)=p.
3. Verifique: em qualquer espaço vetorial:
   1. $0\mathbf v = \mathbf 0$;
   2. $r\mathbf 0 = \mathbf 0$;
   3. $(-r)\mathbf v = \ominus (r\mathbf v)$;
   4. $r\mathbf v = \mathbf 0 \implies r=0~~\text{ou}~~\mathbf v = \mathbf 0$;
   5. $\ominus \mathbf v = (-1)\mathbf v$;
4. Mostre que anel booleano e álgebra booleana são estruturas equivalentes no sentido seguinte:
   • a partir de qualqeur anel booleano R podemos definir uma algrebra booleana BA(R);
   • a partir de qualqeur álgebra booleana A podemos definir um anel booleano BR(A);
   • os BR e BA são inversos entre si;
   • os conceitos de morfismos concordam nas duas interpretações.

Prova IEA.3

hw

1. Mostre como o R/I pode virar um anel, tendo I um ideal do anel R.
2. Um homomorfismo de grupos reflete os subgrupos normais?
3. Verifique que os units dum anel formam um grupo com a multiplicação.

CFR2 (17) & IEA (19): Reticulados [video]

• joins e meets (gerais e binários)
• Reticulados como posets
• Reticulados como algebras
• Misturando algebra e ordem em demonstrações
• Reticulados cotados
• Reticulados booleanos (álgebras booleanas) e aneis booleanos

hw

1. Estabeleça a equivalência entre reticulados como posets e reticulados como álgebras.
2. Demonstre a monotonicidade das (a ∧), (a ∨), (∧ a), e (∨ a)
3. Demonstre a distributividade fraca para qualquer reticulado:
   1. (x ∧ y) ∨ (x ∧ z) ≤ x ∧ (y ∨ z)
   2. …e sua dual?
4. Demonstre a modularidade fraca para qualquer reticulado:
   1. x ≤ z ⇒ x ∨ (y ∧ z) ≤ (x ∨ y) ∧ z
   2. …e sua dual?
5. Sejam L um reticulado, a ∈ L. Chamamos de complemento de a qualquer c ∈ L tal que a ∧ c = ⊥ e a ∨ c = ⊤.
   • Demonstre a unicidade de complementos (mesmo quando não há existência).
6. Def. Seja L reticulado. Chamamos L de reticulado booleano sse: (i) L é distributivo; (ii) L possui ⊥ e ⊤; (iii) Todo membro a de L possui complemento (que necessariamente é único pelo hw anterior). Denotamos o complemento de a por a'. Demonstre que em qualquer reticulado booleano temos:
   1. (a ∨ b)’ = a’ ∧ b’
   2. (a ∧ b)’ = a’ ∨ b’
   3. a ∧ b’ = ⊥ ⇔ a ≤ b
7. Sejam $B, C$ algebras booleanas, e $f : B → C$ homomorfismo de reticulados.
   1. O.s.s.e.:
      • (i) f ⊥ = ⊥ e f ⊤ = ⊤
      • (ii) (∀b∈B)[f(b’) = (f b)’ ]
   2. Suponha que $f$ preserve o complemento '. Logo: $f$ preserve (∨) sse $f$ preserve os (∧).
8. Estabeleça a equivalência entre reticulados booleanos e aneis booleanos.
9. Pensando num reticulado L como algebra, defina o que significa subreticulado e o que subreticulado gerado por A ⊆ L.
10. Pensando num reticulado L como um poset, qualquer A ⊆ L herda uma ordem, assim virando um poset 𝒜 também.
    • Investigue: 𝒜 é um reticulado ⇔ A é um subreticulado de L?
11. Θ. Se um proset possui todos os joins, então ele possui todos os meets (e vice versa).
12. Θ. Sejam L, K reticulados, e f : L → K um mapa. O.s.s.e.:
    • (i) f é monótona (preserva a ordem)
    • (ii) f “adia” joins: f(a∨b) ≥ fa ∨ fb
    • (iii) f “adianta” meets: f(a∧b) ≤ fa ∧ fb
13. Considere a proposição (∗): «se nenhum dos (∨t) e (∧t) distingua entre u e v, então u = v».
    • (i) Entenda o que (∗) significa e o traduza para uma proposição sem gírias;
    • (ii) Demonstre a (∗) para reticulados distributivos.

IEA (20): Livres e livremente gerados; Anel quociente [video]

• lembrete: subgrupo gerado por um subconjunto
• subreticulado gerado por um subconjunto
• reticulado livremente gerado por um conjunto
• monóide livremente gerado por um conjunto
• grupo livremente gerado por um conjunto
• teaser FMC3: álgebra universal
• teaser FMC3: álgebra de termos
• categorias to the rescue! (coiso livremente gerado)
• Aneis, ideais, anel quociente