self study CFR2 (Conjuntos, Funções, Relações II)

Sessões

CFR2 (1) [video]

• retrações e secções
• funções (L/R)-invertíveis
• funções (L/R)-canceláveis
• como dizer Seja a ∈ A. sem pontos
• confundindo aplicações com composições

hw

1. Verifique cada uma das 8 implicações:
   • f inj ⇔ f L-cancelável ⇔ f L-invertível
   • f sobre ⇔ f R-cancelável ⇔ f R-invertível
2. Capítulo «Funções»: §«Uma viagem épica»; §«Retracções e secções»

CFR2 (2) [video]

• especificações sem pontos
• procurando uma especificação para produto
• ganhando gratuitamente uma especificação para soma (coproduto)
• pairing, copairing, projeções, coprojeções

hw

1. Escreva sozinho as especificações de produto e de coproduto.
2. Verifique que B×A com as toA e toB que definimos, é um produto de A e B
3. o A×B×A com as toA (x,y,z) = x e toB (x,y,z) = y, é um produto de A e B?
4. Mostre que o A∪B não é um coproduto (soma) dos A e B
5. Generalize as especificações de produto e coproduto do caso binário para o caso geral, aplicável em qualquer ℐ-família de conjuntos.
6. Tente formular uma especificação para o que seria a exponenciação Bᴬ de um conjunto B elevado a um conjunto A (dica: lembra da eval?)

CFR2 (3): Enter Cantor [video]

• minisermão
• sobre Cantor
• comparação de cardinalidades
• cardinalidade de conjuntos finitos recursivamente
• definição de equinumerosidade e outras comparações de cardinalidades
• conjuntos contáveis/(d)enumeráveis
• setup do jogo imortal de adivinhar
• uns conjuntos contáveis: ℕ, ℤ, ℕ×ℕ, ℚ, ℘f ℕ, A*, ℕ*, ℘f℘f ℕ
• (=c) é relação de equivalência
• lemma sobre ℘f
• a dupla abstração de Cantor
• primeiro argumento diagonal de Cantor
• cuidado sobre intuições sobre conjuntos finitos
• o conjunto dos algébricos é contável
• o segundo argumento diagonal de Cantor
• um conjunto incontável
• Plicker: para quantas dessas operações a (=c) é uma congruência?: ℘f,⋃,⋂

hw

1. Capítulo «O paraíso de Cantor»; até §«O segundo argumento diagonal de Cantor»
2. Para cada uma das operações seguintes, decida (demonstre/refute) se (=c) é uma congruência: ℘f, ℘, ⋃, ⋂, ∪, ∩, Δ, , (→), (×), (+)
3. Demonstre/refute as (=c) seguintes sobre intervalos de números reais, com $a < b$ e $c < d$:
   1. [0,0] =c [0,0)
   2. (0,1) =c (0,2)
   3. (a,b) =c (c,d)
   4. [a,b] =c [c,d]
   5. (0,1] =c [0,2)
   6. (0,1) =c [0,1]
   7. (0,1) =c [0,1)
   8. [0,1] =c [0,1)
4. Demonstre/refute as =c onde α,β∈ℝ∪{-∞,+∞} com α<β.
   1. (α,β) =c (0,1)
   2. (α,β) =c (0,1)
5. Problemas: Π12.6; Π12.7

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

CFR2 (7): Cantor [video]

• recap sobre o mundo a.C.-vs-d.C.
• duas questões sobre a (≤c):
  • Q. (∀A,B:Set)[ A ≤c B & B ≤ A ⇒ A =c B ]
  • Q. (∀A,B:Set)[ A ≤c B ou B ≤c A ]
• enumeração; ser finito; ser infinito
• mais recap: conjuntos contáveis
• ℘ℕ =c (ℕ→{0,1})
• mais recap: o 2o argumento diagonal de Cantor
• ℝ é incontável
• algébricos vs transcendentais; racionais vs irracionais
• Θ. A ≨c ℘A
• ℝ =c ℝ×ℝ ?
• Plicker: votação sobre as duas questões sobre o (≤c)

hw

1. Demonstre que o quadrado tem o tamanho do seu lado: [0,1]² = [0,1]
2. Será que o cubo tem o tamanho de uma aresta?
3. Investigue as cardinalidades dos:
   1. (ℕ→ℕ)
   2. (ℕ→ℝ)
   3. (ℝ→ℕ)
   4. (ℝ→ℝ)
4. Demonstre a Q-Daví: A ≤c B & B ≤c A ⇒ A =c B
5. Demonstre a Q-Isaac: A ≤c B ou B ≤c A

CFR2 (8): Cantor [video]

• A primeira demonstração de Cantor sobre a incontabilidade do ℝ (1874)
• Θ. (Bernstein, aka CBS) (casamentos)
• Θ. (Bernstein, aka CBS) (sem amor)
• Injeções vistas como codificações
• Θ. (Cantor, aka diagonal) (com depressão)
• Continuum Hypothesis e sua generalização
• Uma carta de Cantor para Dedekind

CFR2 (9): Cantor; Relações [video]

• O conjunto de Cantor
• Comparando intervalos sem e com CBS
• Numeros transfinitos: cardinais e ordinais
• alephs (ℵ) e beths (ℶ)
• Relações
• Composição de relações
• Usando relações para implementar funções
• Adjectivos (propriedades) sobre relações
• Préordens e ordens
• Partições e relações de equivalência
• Mais adjectivos: irreflexividade; assimetria; …
• Diagramas internos de relações binárias
• Teaser sobre fechos de relações a partir de propriedades
• Fechos: a ordem de aplicá-los importa?

hw

1. Capítulo «O paraíso de Cantor»: até §«Os números transfinitos»
2. (A×B)→C =c A → (B→C)
3. Demonstre nossa afirmação que a união dos ℕ, ℘ℕ, ℘℘ℕ, … tem cardinalidade maior que a cardinalidade de cada um desses conjuntos.
4. Compare as cardinalidades dos (A→B) e ℘(A×B)
5. Problemas: Π12.3; Π12.4; Π12.5; Π12.6; Π12.7; Π12.10
6. Para quem estudou reais bem:
   1. Demonstre que o conjunto C[0,1] de todas as funções continuas no ([0,1] → ℝ) é equinúmero com o ℝ
   2. Demonstre que o conjunto de todas as funções monótonas no ([0,1] → ℝ) é equinúmero com o ℝ
7. Chute qual parece ser o peso (length) do conjunto 𝐂 de cantor
8. Capítulo «Relações»: até o primeiro intervalo de problemas
9. Problemas: Π9.1; Π9.2; Π9.3; Π9.4; Π9.5; Π9.6; Π9.7; Π9.8; Π9.9; Π9.10; Π9.11; Π9.12; Π9.13
10. Como definarias a categoria 𝐑𝐞𝐥 de conjuntos e relações entre eles?

CFR2 (10): Relações; Russell; Zermelo [video]

• Relações de equivalência; partições; o conjunto quociente
• o conjunto quociente vs um conjunto quociente
• Fechos: bottom-up e top down
• Sobre a implementação de funções usando relações
• Q: podemos misturar relações de A para A e de A para B?
• Q: o que significa que RelEq’s e Partitions é a mesma coisa?
• O parádoxo de Russell
• Resoluções e Fundamentos de Matemática
• Uns minutos para a palavra de Zermelo
• Uma outra maneira de entender os axiomas duma teoria dos conjuntos
• Q: sobre o princípio da comprehensão geral
• Q: como que surgiu o Ø no ZF3 do nada?
• esquema axiomático vs axioma (Plicker)

hw

1. Capítulo «Relações»: §«Partições» e §«Conjunto quociente»
2. Problemas: Π.15; Π9.16; Π9.17; Π9.18; Π9.19; Π9.20; Π9.22; Π9.23; Π9.24; Π9.25

CFR2 (11): Computabilidade [video]

• Άριστος vs Βλαμμένος

CFR2 (12): Medida e Integração; Cantor [video]

• Uma teaser sobre teoria das medidas
• Integrais: Riemann vs Lebesgue e Borel
• Devil’s staircase (função de Cantor)
• o Hypergame de Zwicker

hw

1. Capítulo «O paraíso de Cantor» (todo).
2. Π12.8; Π12.9; Π12.11

Prova CFR2.1

CFR2 (13): ZF [video]

• Sobre ZF e fundamentos em geral
• Sobre FOL
• ZF2. Emptyset
• Predicados primitivos
• Como assim só tem conjuntos no universo?
• Refletindo sobre o culpado do paradoxo do Russell
• ZF3. Pairset
• Θ. Singleton
• ZF4${}_\varphi$. Separação (esquema)
• Russell: de paradoxo para teorema
• Outras abordagens por outras teorias de conjuntos
• ZFC, polêmicas, hipocrisia
• Conceitos definidos vs primitivos
• ZF5. Powerset
• Nossos conjuntos não são necessariamente coleções de objetos
• ZF6. Unionset
• Θ. bin-union (∪)
• Arvores de construções
• Θ. bin-inter (∩)
• fundamentos: implementações em termos de conjuntos
• tuplas, produto cartesiano, especifiação, o operador de Kuratowski
• Justificando a definição do ⟨,⟩ de Kuratowski
• Teaser: infinidade

hw

1. Mostre que com a implementação de 2-tupla de Kuratowski o produto cartesiano a×b de dois conjuntos a,b, é de fato um conjunto.
2. Capítulo «Teoria axiomática dos conjuntos»: até o primeiro intervalo, sem as partes que falam sobre classes
3. Π15.1; Π15.2; Π15.3; Π15.6; Π15.7

CFR2 (14): ZF; Ordens [video]

• A não-gratuidade do operator Kuratowski
• Relações e funções
• Mais operações binárias
• o desafio do (×)
• Classes (próprias) e operadores function-like (ou class functions)
• Conjuntos estruturados
• P(r)osets: préordens e ordens (parciais)
• preservação de relação e a categoria 𝐏𝐨𝐬𝐞𝐭
• ordem linear, diagramas de Hasse, e «covered-by»
• a categoria dos posets 𝐏𝐨𝐬𝐞𝐭
• um p(r)oset 𝒫 visto como categoria ℂ[𝒫]
• downset, upset
• upper bounds, lower bounds, mínimo, máximo, ⊥, ⊤
• investigando o poset visto como categoria
• iniciais e terminais num poset visto como uma categoria.
• melhor upper bound e melhor lower bound: lub/glb, join/meet, sup/inf, ∨/∧

hw

1. Capítulo «Teoria axiomática dos conjuntos»: até o primeiro intervalo
2. Verifiquem o claim de Matias: um functor de ℂ[𝒫] para ℂ[𝒬] é uma função monótona de 𝒫 para 𝒬
3. Vendo um poset como categoria, traduza a definição categorial de produto e de coproduto.
4. Capítulo «Posets; Reticulados»: §«Conceito, notação, propriedades»

CFR2 (15): ZF [video]

• Tentando vender ZF(C) como fundamentos
• Dedekind-infinito
• Sucessor de conjunto (Zermelo, von Neumann)
• ZF7. Infinidade
• Interseção de famílias vazias
• Possível lixo no I e como jogá-lo fora
• Θ. Existência dos naturais
• Θ. Unicidade dos naturais
• Θ. Teorema da recursão
• funções parciais; aproximações; compatibilidade

hw

1. Capítulo «Teoria axiomática dos conjuntos»: até §«Teoremas de recursão»

CFR2 (16): ZF; Ordens [video]

• Naturais, recursão, indução
• Construindo os inteiros
• Construindo os racionais
• Construindo os reais (à la Cantor)
• Construindo os reais (à la Dedekind)
• ZF8. Replacement (scheme)
• ZF9. Foundation
• Antifoundation axioms
• P(r)osets gratuitos e construções
• poset oposto, discreto, flat
• lift de poset
• desafio: união disjunta, produto, espaço de funções, etc.

hw

1. Capítulo «Teoria axiomática dos conjuntos»: até §«Mais axiomas»
2. Π15.10; Π15.11; Π15.12; Π15.13
3. Sejam 𝒫, 𝒬 posets. Mostre como definir ordens para tornar posets também os:
   1. P⊎Q (ache umas 2 aqui)
   2. P×Q (ache umas 3 aqui)
   3. (P→Q) [o que tu precisa mesmo aqui?]
4. Ache um critério para estabelecer qual seria a definição certa para o P×Q, e elabore também sobre o P⊎Q.
5. Capítulo «Posets; reticulados»: estude a §«Mapeametos» e resolva seus exercícios.

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) para reticulados distributivos.
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.

Medley CFR2 em um universo paralelo

• relações bem fundadas e indução
• noções de computabilidade
• números computáveis
• ordinais e sua aritmética
• cardinais e sua aritmética
• álgebras booleanas e álgebras Heyting
• conjuntos estruturados interessantes (topologia, espaços métricos, normados, grafos, σ-algebras, espaços de medida …)
• axiomas de escolha
• comparabilidade de cardinalidades
• a hipótese do continuum
• fundamentos baseados em categorias e teorias dos tipos
• programação relacional (logic programming)
• bancos de dados relacionais