2017.1 FMC2, turmas de Thanos

Mailing list archive (members only)

Horários:246T56 [16h50–18h30] (t1: T)
246N12 [18h45–20h25] (t2: N)
Sala de aulas:A308 (T & N)
Sala do prof:A225
Contato:thanos@imd.ufrn.br
Horário de atendimento:mande email para marcar
Monitoria/TA:fmc.imd.ufrn.br
Turmas anteriores:2016.1

Prerequisitos

Prerequisito ter aprendido bem e profundamente o conteudo de FMC1. Sem mandar bem nesses assuntos, não faz sentido se matricular em FMC2. (Obs.: mandar bempassar.)

Então—ANTES de começar—é bom estudar os:

  1. How to prove it, de Velleman (1, 2, 3, 6) [pode achar no LibGen—link na bibliografia]
  2. Das minhas notas (em progresso) Matemática fundacional para computação, os capítulos:
    • Indução
    • Teoría elementar de números
    • Congrüências
    • Combinatória enumerativa
  3. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

(Obs.: estudarler.)

Conteúdo

Conteúdo transversal
Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e provas. A linguagem da teoria de conjuntos. Definições pelo recursão – provas por indução. Demonstrações diretas e indiretas, refutações.
Conjuntos, Funções, e Relações
Conjuntos, sua notação, suas operações, e seus leis. Uniões disjuntas, famílias e partições. Tuplas ordenadas e produto cartesiano. As operações unitárias de união e interseção. As relações de subconjunto, e de pertencer. Multiconjuntos e sequências. Funções, o conceito de função e suas propriedades. Intensão x extensão. Domínio, codomínio. Imagem, pre-imagem. Funções totais e parciais, injetivas, sobrejetivas, bijetivas. Aridade. Função constante, função identidade, projeções, funções características. Funções recursivas; recursão mutual. A notação de λ-calculus. Funções x predicados. Relações e suas propriedades. Relações de equivalência, clásses de equivalência. Operações em relações, inversão, composição, fechos.
Elementos de Álgebra abstrata
Conjuntos com estrutura. Operações. Grupos, subgrupos, aneis, monoides. Demonstrações com o uso de identidades algébricas. Homomorfísmos. Álgebras booleanas.
Elementos de Teoria de Conjuntos
Enumerações e conceito intuitivo de cardinalidade. Paradoxos e os axiomas Zermelo–Fraenkel. Representações de matemática (traduções). Os números naturais; axiomas Peano.
Elementos de Teoria de Ordem
Ordens parciais, totais, densas, bem-fundadas. Diagramas de Hasse. Elementos notáveis (majorantes, máximos, supremos). Conjuntos ordenados, reticulados, reticulados completos. Construções de conjutos ordenados. Dualidade. Ordens canônicas, ordens lexicográficas. Monotonicidade. Teoremas de ponto fixo. Reticulados como álgebras. Conjuntos bem-ordenados. Indução bem-fundada.
Aplicações e outros assuntos
Tipos de dados algébricos. Relações bem-fundadas e indução transfinita. Números ordinais. Limites de computação. Noções de decidibilidade e de semi-decidibilidade. λ-calculus, lógica combinatória. Elementos de teoria dos tipos. Noções de semántica de linguagens de programação. Y-combinator, fixpoints e recursão. Axiom of choice e suas conseqüências. Lógicas não-clássicas, elementos de lógica intuitionística e de lógica linear.

Bibliografia

(Conhece o libgen.io?)

(Por enquanto simultaneamente incompleta e redundante.)

  • Velleman: How to prove it (1.3, 1.4, 2.3, 4, 5, 7)
  • Moschovakis: Notes on set theory (1, 2, 3–5, 6–7)
  • Goldrei: Classic set theory, for guided independent study (4, 7, 8)
  • Birkhoff & Mac Lane: A survey of modern algebra (1.11; 1.1–1.5, 1.10, 1.12)
  • Mac Lane & Birkhoff: Algebra (1.1–1.3)
  • Pinter: A book of abstract algebra (2–5, 6, 12, 17)
  • Herstein: Topics in Algebra (2.1–2.5 [skip # and *])
  • Davey & Priestley: Introduction to lattices and order (1, 2)
  • Loomis & Sternberg: Advanced Calculus (0)
  • Simmons: Introduction to topology and modern analysis (1)
  • Munkres: Topology (1)
  • Eu: Matemática fundacional para computação (minhas notas em progresso)

Auxiliar

Dicas

Provas

Provinha 0

Unidade 1

Unidade 2

Unidade 3

Prova de recuperação

Uma prova sobre todo o conteudo da disciplina, comum para todos.

Pontos extra

Unidade 1

T N
Eric 3 Pedro Neto 1
André 8 Hugo 5
Franklin 4 Josenaldo 4
Gabriel 3 Jaimerson 5
Lucas M. 2 Bianca 4
Shirley 4 Louise 2
Claudio Lima 2 Tyrone 1
Daniel Barbosa 1 Maradona 1

Unidade 2

T N
Luan 5 Hugo 10
André 13Josenaldo 11
Shirley 4 Louise 3
Luis Eduardo F. 4 Maradona 1
Claudio Lima 2 Jaimerson 14
Eric 9 Bianca 6
P. H. Almeida 2 João 1
Gabriel 2 Danielle 2
Natália 1
Daniel Barbosa 1
Lucas M. 7

Unidade 3

T N
Lucas M. 25Bianca 12
Luis Eduardo F. 1 Hugo 12
Gabriel 11Josenaldo 13
André 18Jaimerson 12
Eric 13Louise 8
Natália 5
Shirley 7

Homework

01/01/2017

  1. Estude os itens nos prerequisitos: resolve os problemas nesses capítulos do Velleman e das minhas notas, e resolva as minhas provas de FMC1 2016.2 (e estude seus gabaritos).

20/02/2017

  1. Resolva os exercícios e os exemplos do Velleman, cap.1.

24/02/2017

  1. Usando a notação BNF, defina as fbfs da lógica de primeira ordem
  2. Resolva os exercícios e os exemplos do Velleman, cap.2.

06/03/2017 – 10/03/2017

  1. Resolva todos exercícios e os exemplos do Velleman, cap.1.
  2. Resolva todos exercícios e os exemplos do Velleman, cap.2 que não involvem símbolos que não encontramos nas aulas.
  3. Resolva todos exercícios e os exemplos do Velleman, cap.3 que não involvem símbolos que não encontramos nas aulas.
  4. Resolva os exercícios e os exemplos do Velleman, cap.6 que não involvem símbolos que não encontramos nas aulas.

10/03/2017 – 13/03/2017

Seja A um conjunto, e An uma seqüência de subconjuntos de A. Sejam:
A* = ⋃i=0j=i Aj
A* = ⋂i=0j=i Aj

  1. Como descreveria os elementos dos A* e A*?
  2. É verdade que um desses conjuntos é subconjunto do outro? São iguais? São disjuntos?

17/03/2017

  1. Sejam: f : A → B, g : B → C, h : C → D. É verdade que h∘(gf) = (hg)∘f ?

17/03/2017 – 22/03/2017

  1. Pinter: Capítulo 6, com os exercícios nos: A, B, C(1–3), D(1–5), F, G.
  2. Moschovakis: Capítulo 1, com todos os problemas (x1.1–8).
  3. Velleman: Todos os exercícios/exemplos/problemas dos 1.3, 1.4, 2.3, 3.1–3.5.

27/03/2017

  1. Moschovakis: Capítulo 1, com todos os problemas (x1.1–8).
  2. Generalize a questão do plicker de |A|=3 para |A|=n
  3. Experimente com as construções que viermos: o que tu pode concluir sobre as funções construidas sabendo propriedades dos seus componentes e vice-versa?
  4. Seja B o conjunto de pessoas que moram no Brasil; seja E o conjunto dos estados do Brasil.
    Considere s : BE a função definida pela regra: s(b) = o estado onde b mora
    Considere g : EB a função definida pela regra: g(x) = o governador do estado x
    Quais são os fixpoints da função (g∘s)?
    Qual seria um nome bom para a (g∘s), e qual seu "tipo" (dom/cod)?
  5. Desenha um diagrama cuja comutatividade será equivalente com a afirmação sequinte: «o endomapa f no A é idempotente»

29/03/2017

  1. Explique a direção oposta da currificação (decurrificação): começando com uma F:A→(BC), mostre como construir uma «equivalente» f:(A×B)→C.

03/04/2017 – 05/04/2017

  1. Escreva claramente como definir uma partição dum conjunto A, dada uma relação de equivalência ~ no A, e vice versa. Prove tuas afirmações.
  2. Prove formalmente que a relação do plicker do dia (03/04/2017) não é transitiva.
  3. Seja R uma relação binária num conjunto A. O.s.s.e.:
    (i) R é uma relação de equivalência (ii) R é reflexiva e circular (iii) R é reflexiva e triangular
  4. Seja m natural. Prove que a relação binária nos inteiros definida pela
    a ~m b sse ab (mod m)
    é uma relação de equivalência. Qual é a partição correspondente nos inteiros?
  5. Seja f:XY e defina a relação binária no X pela x~x' sse f(x)=f(x'). Mostre que ~ é uma relação de equivalência e descreva as classes da correspondente partição. O que podemos concluir se f é injetora?
  6. Estude o capítulo 12 de Pinter, e resolva todos os problemas nos A,B,C,E.

17/04/2017 – 19/04/2017

  1. Todos os racionais são algébricos
  2. Ache uma estrategia para ganhar no jogo de imortais onde o jogador precisa adivinhar o s∈ℕ2 que seu oponente escolheu.

19/04/2017 – 05/05/2017

  1. O conjunto de irracionais é contável?
  2. Estudem (e resolvam problemas etc.) dos: Velleman, cap. 7; Goldrei, cap. 6; Moschovakis, cap. 2; …ou qualquer outra fonte preferem nesse assunto
  3. Moschovakis, cap 2: prove/resolve as: ex2.5, prop2.7, ex2.8, ex2.9, problemas x2.1–x2.8.
  4. Como podemos casar todas as pessoas no planeta imaginário?

03/05/2017 – 05/05/2017

  1. Responda na pergunta «existe maior..?» que deixamos na aula (ou seja: prob x2.8 de Moschovakis).
  2. Responda na pergunta do plicker (ou seja: probs x2.3 e x2.6 de Moschovakis).

13/05/2017

  1. Pinter, cap. 2: estudem e resolvem todos os problemas!

15/05/2017

  1. Pinter, cap. 3: estudem e resolvem todos os problemas!
  2. Para cada uma das operações * = ∩,∪,△,\, verifique se o powerset (℘A; * ) é um grupo; é abeliano?

17/05/2017

  1. Seja A conjunto não vazio.
  2. Pinter, cap. 4: estudem e resolvem todos os problemas!

19/05/2017 – 24/05/2017

  1. Pinter, cap. 5: estudem e resolvem seus problemas nos A, B, C, e D.
  2. Pinter, cap. 7: estudem e resolvem os problemas nos A e B.
  3. Prove que: G cíclico ⇒ G abeliano, mas a implicação conversa não é válida.
  4. Prove que o grupo gerado por W é a interseção de todos os subgrupos de G que contenham o W>
  5. Prove que o {z∈ℂ | |z|=1 } é um subgrupo de ℂ\{0}.

26/05/2017

  1. Pinter, cap. 10: estudem e resolvem seus problemas nos A, B, e C.

31/05/2017

  1. Pinter, cap. 13: estudem e resolvem seus problemas nos A, B, C, D, e E.
  2. Pinter, cap. 15: estudem e resolvem seus problemas nos A, B, C, D, e E.

02/06/2017

  1. Pinter, cap. 14: estudem e resolvem seus problemas nos A, B, C, D, e G.

05/06/2017

  1. Goldrei, cap. 4: leiam as secções 4.1–4.3 (até as definições na p. 78) e resolvem todos os exercícios que parecem nessas páginas
  2. Moschovakis, cap.3: leiam até o 3.9 (p. 24) resolvendo os exercícios

12/06/2017

  1. Goldrei, cap. 4: leiam as secções 4.3–4.4 e resolvam todos os exercícios
  2. Moschovakis, cap.3: leiam até o 3.17, resolvam todos os exercícios até lá; resolvem os problemas: x3.1; x3.2
  3. Moschovakis, cap.4: leiam até o 4.18, resolvam todos os exercícios até lá; resolvam os problemas: x4.1; x4.2; x4.22–x4.24; (os x4.4–x4.9 servem bem para revisar uns assuntos da Unidade 1 para a 4a prova!)

16/06/2017

  1. Goldrei, cap. 4: leiam as secções 4.3–4.4 e resolvam todos os exercícios
  2. Moschovakis, cap.3: leiam até o 3.17, resolvam todos os exercícios até lá; resolvem os problemas: x3.1; x3.2
  3. Nos naturais definam formalmente: as funções de adição, multiplicação, e exponenciação; a relação de ≤
  4. Mostrem num sistema Peano, cada nN ou é o 0, ou ele é sucessor de algum natural
  5. Mostrem que a φ que definimos entre os dois sistemas Peano é um monomorfismo
  6. Um cliente chegou e quer os inteiros. Como atenderiam ele?
    (Começam pensando o que seria um pedido razoável do cliente; ou seja: qual seria sua especificação?)
  7. Um cliente chegou e quer os racionais. Como atenderiam ele?
    (Começam pensando o que seria um pedido razoável do cliente; ou seja: qual seria sua especificação?)
  8. Usando o ZF9, mostram que não podemos ter cadeias infinitas: x1϶x2϶x3϶x4϶ …

19/06/2017

  1. Resolvem os exercícios e problemas das minhas notas
  2. Goldrei: Theorem 5.1, p.108–109
  3. Davey & Priestley: Prove o Lemma 1.30; resolve os exercícios: 1.1, 1.2, 1.3, 1.4, 1.5, 1.13, 1.17

21/06/2017

  1. Estude do Davey & Priestley: cap.2 até Definição 2.12 (pp.33–41).
  2. Resolvam todos os problemas da Prova 3 de 2016.1
  3. Resolva do Davey & Priestley: exercícios: 1.7, 1.8, 1.9, 1.10, 1.11, 1.12, 1.18, 1.23
  4. Resolva do Davey & Priestley: exercícios: 2.1–2.5, 2.6(i)
  5. Goldrei: Estude secção 7.3, exercícios 7.27, 7.30, 7.31, 7.36, 7.38

Histórico de aulas

13/02/2017: Apresentação

  • Apresentação dos assuntos principais
  • Definições e afirmações: erros comuns
  • Aridade
  • Variáveis livres e ligadas

15/02/2017: Provinha 0

  • Provinha 0

17/02/2017: Sermão e correção

  • Sermão sobre a Provinha 0
  • Correção

20/02/2017: Lógica proposicional

  • Linguagens formais
  • Alfabetos, espressões, construtores, símbolos de pontuação
  • Arvores sintáticas
  • A linguagem de lógica proposicional (sentencial): sintaxe e semántica
  • Definições recursivas
  • L0: (wffs da) linguagem da lógica proposicional
  • A linguagem de expressões de aritmética (com numerais e/ou variáveis)
  • Traduções de português e de português matemático para lógica proposicional e vice versa
  • «meta-»: metalinguagem, metavariáveis, etc.

24/02/2017: Lógica de primeira-ordem

  • A notação BNF
  • Termos da L1
  • L1: (wffs da) linguagem de primeira ordem
  • Traduções de português e de português matemático para lógica de primeira ordem e vice versa
  • Abreviações comuns
  • A ordem de quantificadores importa (quando?)

06/03/2017: Lógica; Estrategias de provas; Conjuntos

  • Lógica
    • Definições recursivas de conjuntos, BNF, arvores sintáticas: revisão
    • Abreviações de fórmulas
    • Leis de equivalências lógicas
    • “Enterrando” todas as negações em frente de fórmulas atômicas
  • Estrategias de prova
    • Provas diretas
    • Prova por casos
    • Prova por absurdo
    • Prova por indução
  • Conjuntos
    • Conceito e notação
    • Noções primitivas: ser conjunto, pertencer (∈)
    • Conjuntos, seqüências, multisets
    • Set comprehension (Set-builder notation)
    • Conjuntos e funções como “black boxes”
    • Intensão vs extensão
    • Igualdade entre conjuntos: A = B
    • Relações entre conjuntos e como as definir
    • As relações binárias: =, ⊆, ⊇, ⊊, ⊋
    • Operações entre conjuntos e dois jeitos de as definir
    • As operações binárias: ∩, ∪, \
    • A operação unária de complemento: ~

08/03/2017: Conjuntos

  • Diagramas de Venn e suas limitações
  • Homogeneidade e heterogeneidade de conjuntos
  • Diferença simétrica (△)
  • Produto cartesiano (×)
  • An: definição “direta” e recursiva
  • Powerset (℘)
  • O conjunto vazio Ø: definição e suas propriedades

10/03/2017: Conjuntos

  • Provando iqualdades entre conjuntos
  • Sinónimos de “conjunto”: família, colecção, etc.
  • Seqüências de conjuntos
  • Generalizando as operações de união e intersecção: as operações unárias ⋂, ⋃
  • Aplicando (e iterando) as ℘, ⋂ e ⋃ no Ø

13/03/2017: Lógica; Conjuntos

  • Lógica
  • Conjuntos
    • Intuição sobre os ⋂, ⋃, e ℘ e as {, }
    • ⋂ e ⋃ com subscripts (mais notações)
    • Família de conjuntos indexada por algum conjunto I: {Ai | iI}
    • Exemplos: Os conjuntos Ap e Fp de todos os ancestrais e todos os filhos de p, respeitivamente.
    • Traduzindo afirmações da linguagem natural para relações entre conjuntos e vice-versa
    • Conjuntos disjuntos
    • Cardinalidade de conjuntos finitos e propriedades
    • Um teorema de igualdade de conjuntos:
      Suponha que A, B ≠ Ø.
      A×B = B×AA = B.
    • Como usar um fato do tipo D≠Ø em nossas provas: «Seja dD
  • Análise
    • Uma diferença importantíssima entre os operadores Σ e ⋃ e seus indices: um somatório infinito não é nem associativo nem comutativo!
    • Riemann's rearrangement theorem

17/03/2017: Conjuntos; Funções

  • Conjuntos
    • Intervalos de reais, suas intersecções e uniões arbitrárias
    • Terminar a prova do teorema anterior sobre A×B = B×A em dois jeitos: prova direta, e prova pelo absurdo
  • Funções
    • Conceito, notação, “definição”
    • Domínio e codomínio
    • Intensão vs extensão
    • Igualdade: f = g
      Quaisquer duas das:
      • dom(f) = dom(g)
      • para todo x ∈ dom(f), f(x) = g(x)
      • para todo x ∈ dom(g), f(x) = g(x)
    • Diagramas internos e externos
    • Injetora, Sobrejetora, Bijetora
    • Composição

20/03/2017: Conjuntos; Funções

  • Conjuntos
    • Os operadores binários ∪ e ∩ como açucar sintático (definido pelos operadores unários ⋃ e ⋂ respeitivamente).
    • Conjuntos disjuntos dois-a-dois («pairwise disjoint»): definição com e sem índices
  • Funções
    • Notação e intuição sobre funções injetoras, sobrejetoras, e bijetoras
    • O lei da associatividade da composição: h∘(gf) = (hg)∘f; prova e intuição
    • Composição como operação associativa
    • Como construir possíveis contraexemplos
    • Usando propriedades da gf para deduzir propriedades das f e g
    • Como definir funções e notação relevante
    • Como não definir funções: erros comuns
    • A notação de λ-calculus
    • Identidade, constante, caraterística
    • Aplicação parcial e «buracos»: com –, •, etc.; com lambdas (λ)
    • Aplicação parcial como black box

22/03/2017: Prova 1.1

24/03/2017: Sermão

  • Resolução das provas
  • Erros comuns
  • Erros inaceitáveis
  • O lei da identidade da composição: 1Bf = f = f∘1A; prova e intuição

27/03/2017: Funções

  • (Co)domínio vazio e função vazia
  • Diagramas comutativos: como expressar os dois leis da composição
  • Iteração de função: fn (ideia e definição recursiva)
  • Composição como operação: comparação com multiplicação nos inteiros
  • Sinônimos de «função»: mapa, mapeamento, ...
  • Quantas funções tais que...?
  • Endomapas: fixpoints; idempotência
  • Construindo funções:
    • restrição: definição e propriedades
    • união: hipoteses necessárias para definir
    • produto: ideia, definição, black box
  • Imagem; pre-imagem: ideia/noção, definições dos conjuntos f[A] e f–1[B], e suas propriedades
  • Aplicação como operação
  • Produto cartesiano como black box

29/03/2017: Funções

  • Resolução de dos exercícios: #4 e #5 do homework 27/03/2017.
  • Função inversa; definição, notação
  • Justificação da notação ambigua: f–1[A]
  • Involução: f = f–1
  • Conjuntos de funções (function space): (AB), BA
  • |(AB)| = ?; |(AB)| = ?
  • Funções de ordem superior: noção, exemplos
  • Currificação: de f:(A×B)→C para F:A→(BC); com função epônima (com nome); com função anônima (usando λ); com black-boxes

31/03/2017: Relações

  • Funções
    • Currificação
    • Aplicação parcial
    • Currificação e multiplicação/exponenciação de inteiros
    • Cardinalidades entre finitos A,B,C, e os conjuntos ((A×B)→C) e (A→(BC))
    • λ-calculus e «execução» de funções
    • λab.ab vs. λba.ab
    • Dois diferentes papeis dos ( ): agrupamento; aplicação de função em argumento
    • Ligantes de variáveis:
      • x_ ; ∀x_
      • ∫_dx ; Dx_
      • Σi_ ; Πi_
      • j_ ; ⋂j_
      • { _ | P(x) } ; { x∈A | _ }
      • λx._
    • Comparação: sin(x), sin, sin(–); x2, λx.x2, (–)2
    • Gráfico de função
      • Graph(f): definição
      • Considerando funções no (AB), qual seria o domínio e o codomínio da Graph?
  • Relações
    • Noção, relações como black-boxes
    • Comparação com funções
    • Definindo relações: com frases, usando outras relações e funções
    • Aplicação parcial em relações
    • Exemplos de fórmulas bem formadas, e «mal-tipadas» (ill-typed)

03/04/2017: Relações

  • Igualdade
  • Truth set
  • Relações binárias e notações alternativas
  • Propriedades de relações binárias num conjunto A
    • reflexiva; irreflexiva
    • simétrica, asimétrica, antisimétrica
    • transitiva
    • circular; triangular ou right-euclidean; left-euclidean
    • total; tricótoma
  • Relações de equivalência; classes de equivalência
  • Partições de conjunto
  • Seja ε real com 0<ε<1. Definimos nos reais a relação ~ com: x~y sse (xy)²<ε.
    Ela é simétrica? Reflexiva? Transitiva?

07/04/2017: Conjuntos; Funções; Relações

  • Conjuntos, Tuplas, Funções
    • tuplas como noções primitivas: igualdade, tamanho, tupla vazia
    • projeções: πi
    • An revisitado
    • função vazia: «a» ou «uma»?
    • função de aridade 0: «a» ou «uma»?
    • Unit type e os tipos void e int da C, como (co)domínios de funções matemáticas
  • Relações
    • Relações de equivalência, classes de equivalência, conjunto quociente: exemplos no ℝ2 e no conjunto P de pessoas
    • Construindo relações
    • Composição entre relações (e entre funções)
    • Composição usando black boxes
    • Relações como grafos direcionados
    • Relações como generalização de função
    • Duas relações no conjunto de seqüências infinitas de naturais (ℕ→ℕ): são relações de equivalência?

10/04/2017: Tuples; Relações; Bancos de Dados

  • Tuples
    • projeções: πi
  • Relações
    • Fechos (reflexivo, simétrico, transitivo, circular, etc.)
    • Composição como operador
    • Exponenciação de relações: Rn
    • Relações recursivamente definidas
    • Recursão mutual: Even/Odd
  • Aplicações
    • Bancos de dados

12/04/2017: Lógica; Paradigmas de programação; Programação Lógica

  • Lógica
    • Semântica
    • Mundos em L0: valuação e sua extenção recursiva
    • Tautologias no L0
    • Mundos em L1: estruturas, e valuação de variáveis
    • Tautologias no L1
    • Emulando constantes por funções
    • Emulando funções por relações
  • Linguagens de programação
    • Paradigmas: imperativos vs declarativos
  • Programação Lógica

17/04/2017: Lógica; Relações; História; Cantor

  • Lógica
    • Modelos
    • Como provar que duas formulas da L1 (não) são equivalentes
    • Independência de axiomas: o 5o axioma de Euclides
  • Relações
    • A ordem de aplicação de fechos (transitivo, reflexivo, simétrico, etc.) numa relação, importa?
  • História
    • Grecia antiga: a irracionalidade de √2 e sua importáncia: existência de irracionais
    • Irracionalidade de e e π
    • Números algébricos e transcendentais
    • √n é algebrico
    • todos os racionais são algébricos
    • Liouville: existem números transcendentais! (Construiu os «Liouville numbers»)
    • e e π são transcendentais
    • Fourier series
  • Cantor
    • Melhorando seu teorema sobre as Fourier series
    • Pontos de acumulação e conjunto derivado
    • As primeiras ideias de comparar o tamanho de conjuntos infinitos
    • O que significa contar?
    • Como podemos comparar o tamanho de dois conjuntos finitos?
    • Como podemos comparar o tamanho de dois conjuntos infinitos?
    • O que significa cardinalidade de um conjunto A? A notação de cardinalidade A de Cantor
    • |ℕ| = |ℤ|
    • Estrategias para garantir vitoria no jogo de imortais «adivinhe o s que eu estou pensando» se…:
      • s∈ℕ
      • s∈ℤ

19/04/2017: Cantor

  • Jogo de imortais com conjuntos «aparentemente» maiores—so que não:
    • ℕ²; ℤ²; ℕk;
    • fℕ; ℘ffℕ;
    • A*;
    • *;
    • ℤ[x]; ℚ[x];
    • ⋃{ Cn | n∈ℕ }
  • Stratificação dos palpites
  • A dupla abstração de cardinalidade do Cantor
  • Bijeções como outros nomes dos elementos dum conjunto
  • Variação de jogo: quando o jogador pode (ou não) repetir seus palpites
  • O primeiro argumento diagonal de Cantor
  • Um conjunto incontável: [0,1]
  • O segundo argumento diagonal de Cantor
  • Definições:
    • Equinumerosidade: conjuntos equinúmeros (A =c B)
    • O conjunto n = {0, 1, …, n–1}
    • Conjunto finito, infinito, contável/(d)enumerável, incontável
    • Kleene star
  • A relação =c é uma relação de equivalência

24/04/2017: Equinumerosidade

  • Revisão: o fim dos 1800's, AC e DC (Antes Cantor e Depois Cantor)
  • Os argumentos diagonais de Cantor
  • Duas definições equivalentes de AcB
  • Uma definição errada de A<cB
  • A relação ≤c parece ser relação de ordem.. parcial? total?
  • Casamentos infinitos

26/04/2017: Equinumerosidade

  • Casamentos infinitos: a solução
  • O teorema Schröder–Bernstein e suas aplicações
  • Procurando bijeções entre intervalos de reais
  • Números racionais e irracionais
  • O conjunto dos racionais é contável
  • O conjunto dos irracionais é incontável
  • Números algébricos e transcendentais
  • Definições equivalentes; definições erradas
  • O conjunto dos algébricos é contável
  • O conjunto dos transcendentais é incontável
  • A =c B
  • Quais operações “respeitam” as cardinalidades?

03/05/2017: Equinumerosidade

  • Recap: todos os conjuntos que temos encontrado e classificado até agora entre contáveis e incontáveis
  • Representação dos números reais no [0,1] em forma 0,... para varias bases: interpretação geometrica na linha como instruções
  • O Cantor set e a prova que é incontável
  • O teorema de Cantor: A <cA
  • Uma infinidade contável de «infinidades diferentes»:
    ℕ <c ℘ℕ <c ℘℘ℕ <c ℘℘℘ℕ <c
  • ℝ =c2 =cn =c
  • Tem algum conjunto «maior»?
  • Os cardinais: ℵ0 (aleph 0), 𝖈 (continuum)
  • As perguntas grantes: Principle of Cardinal Comparability, Continuum Hypothesis, Generalized Continuum Hypothesis

05/05/2017: Equinumerosidade

  • Recap: o teorema de Cantor e suas conseqüências
  • Não existe cardinalidade máxima
  • T >c Tn para todo n∈ℕ
  • Provas por indução
  • Provas de equinumerosidade com e sem o teorema Schröder–Bernstein
  • Entre dois reais existe racional
  • Codificações em números
  • Uma carta de Cantor para Dedekind
  • A resposta de Dedekind

08/05/2017: Prova 1.2

10/05/2017: Resolução das provas

  • Probabilidade de escolher irracional dos reais em [0,1]
  • A frase «tende ao…»
  • Resolução da Prova 1.2-clubs
  • Resolução da Prova 1.2-spades

12/05/2017: Aplicações; História; Algebra abstrata

  • Aplicação: teoria de medida
    • teoria de medida: Borel, Lebesgue, Baire
    • Generalização de comprimento, probabilidadem e integração
    • Por que a probabilidade de escolher x racional, escolhendo entre o [0,1] é 0?
  • Aplicação: Computabilidade
    • Quantos programas diferentes existem?
    • Funções computáveis; números computáveis
    • Números definíveis
    • Limitações de computação
  • História: de Euclides para Galois
    • Geometria Euclideana
    • Construções com régua e compasso
    • Construções impossíveis
    • Fórmulas para as raizes de polinómios de grau 5 ou superior
    • Wantzel (provas de impossibilidade de resolver)
    • Galois e suas ideias
  • Algebra abstrata
    • Conjuntos estruturados
    • Abusos notacionais
    • Operações e propriedades

15/05/2017: Teoria de grupos

  • Conjuntos estruturados: carrier set + estrutura; assinatura
  • Structure-preserving functions; respeitar as operações
  • -morfismos: homo-; mono-; epi-; iso-; auto-
  • Exemplos de -morfismos
  • A(S) e S3
  • Notações para representar elementos de Sn: completa e com cíclos
  • Duas definições equivalentes de grupo
  • Grupos abelianos
  • Grupos aditivos e grupos multiplicativos
  • Exemplos de grupos
  • Os grupos simétricos Sn

17/05/2017: Teoria de grupos

  • Mais uma definição de grupo, com outra assinatura/estrutura
  • As potências an
  • Grupos de matrizes
  • As leis dos grupos e suas conseqüências; provamos:
    • unicidade de identidade
    • unicidade dos inversos
    • left-cancelation law
    • right-cancelation law
    • ax = ya não implica x = y
    • (a-1)-1 = a
    • (ab)-1 = b-1a-1

19/05/2017: Teoria de grupos

  • O ℘A com operação △ é um grupo abeliano
  • A operação \ não é associativa
  • Por quê (G3L) & (G3R) não implica automaticamente a (G3)
  • Definindo am para inteiro m
  • Propriedades de “exponenciação”
  • Ordem de grupo
  • Ordem de elemento em grupo
  • Subgrupo HG
  • Exemplos de subgrupos
  • Os subgrupos triviais {e} & G
  • ≤ é uma ordem parcial
  • Dois lémata: o que basta verificar para concluir que HG
  • Respeito de operação como diagrama comutativo

22/05/2017: Teoria de grupos

  • Subgrupos e ordens de grupo e de elemento
  • Exemplos de subgrupos: inteiros, permutações, complexos
  • O plano complexo e a interpretação geométrica das operações do ℂ
  • Interseção de subgrupos é subgrupo
  • A união não comporta tão bem!
  • Geradores de (sub)grupos <a> & <W> e suas definições alternativas
  • Definições top-down & bottom-up
  • Grupos cíclicos
  • Congruências: HG, a,bG: ab (mod H) é uma relação de equivalência
  • A congruência conhecida nos inteiros como caso especial da congruência em grupos

24/05/2017: Teoria de grupos

  • A partição atravez da congruência (mod H)
  • Right e left cosets
  • Teorema de Lagrange
  • indice de subgrupo H em grupo G
  • Existe Ginfinito com subgrupo não-trivial H com indice finita no G?

26/05/2017: Teoria de grupos

  • Por que right cosets e não left?
  • Ordens de elementos, de grupos e suas propriedades
  • O índice de H no G: (G:H) ou iG(H) e suas propriedades
  • Corolários do teorema de Lagrange
  • Subgrupos do S3
  • Definição de HK
  • HK, KHG?

29/05/2017: Teoria de grupos

  • Os grupos Zn e Zp com multiplicação e seus carrier sets.
  • Teoria de números revisited: teorema de Euler
  • Mais caraterizações de grupos
  • Investigando o HK
  • HK = KHHK ≤ G

31/05/2017: Teoria de grupos

  • Subgrupos normais: intuição
  • φN=Nφ ?
  • Umas definições equivalentes
  • De aH e HK para AB, g1ABgAg'Bg2-1, etc.
  • Conjugados de nN.
  • HH=H
  • Grupo quociente
  • Simetrias e grupos
  • Os grupos dihedrais Dn
  • Os D3, D4 e o diagrama dos seus subgrupos

02/06/2017: Teoria de grupos

  • (Homo)morfismos
  • Monomorfismos
  • Epimorfismos
  • Isomorfismos
  • Endomorfismos
  • Automorfismos
  • Morfismos entre conjuntos estruturados
  • Morfismos de grupos
  • Respeitar a operação do grupo garanta respeito à identidade e aos inversos
  • Exemplos
  • ≅ é uma relação de equivalência
  • φ : GG/N com φ(x) = Nx é um epimorfismo
  • Mais uma intuição sobre subgrupos normais

03/06/2017: Outras estruturas algébricas (×2)

  • Teoria de grupos
    • Revisão: morfismos e subgrupos normais
    • Kernel e Imagem de morfismos
    • O primeiro teorema de isomorfimos de grupos
  • Outras estruturas algébricas
    • Monoides
    • Aneis
    • Primeiras consequências das leis de anel
    • Domínios Integrais
    • Corpos
    • Homomorfísmos entre aneis

05/06/2017: Problems in Paradise: Cantor, Frege, Russell, Zermelo; ZF

  • Revisão: conjuntos, tuplas, relações, funções
  • Questões abertas na época:
    • Princípio da Comparabilidade de Cardinais
    • Continuum Hypothesis (C.H.)
    • Generalized Continuum Hypothesis (G.C.H.)
  • O paraiso de Cantor
  • Axioma de Extensionalidade e Princípio da Comprehensão Geral
  • O parádoxo de Russell (1902)
  • Russell: teoria de tipos
  • Zermelo: teoria axiomática de conjuntos ZF
  • Traduções de FOL para português e vice-versa
  • Axiomas vs. leis
  • Os axiomas ZFC
  • ZF1 e suas conseqüências
  • ZF2 e suas conseqüências
  • ZF3 e suas conseqüências
  • Com ZF1–ZF3 podemos construir apenas conjuntos com cardinalidade 0, 1, ou 2.
  • ZF4, sua interpração e uma comparação com o Princípio da Comprehensão Geral
  • Axiom vs. Esquema de axiomas

07/06/2017: ZF

  • Definições de: Ø; {–}; {–,–}; –∩–; –∪–; –\–; ℘–; ⋂–; ⋃–
  • ZF4 e suas conseqüências
  • ZF5 e suas conseqüências
  • Quais dos ZF1–ZF5 precisamos para garantir a existência de conjuntos de qualquer cardinalidade finita?
  • ZF6 e suas conseqüências
  • O paradoxo de Russell virando teorema: para cada conjunto A, existe algum r(A) fora do A. Ainda mais, r(A) ⊆ A.
  • Classes e classes próprias
  • O V é uma classe própria
  • Não podemos definir a operação ⋂Ø
  • Não podemos definir a operação ~ de complemento
  • Representação fiel de matemática dentro da teoria de conjuntos
  • Tuplas e produto cartesiano
  • O operador de par ordenado de Kuratowski

12/06/2017: ZF

  • Tuplas na ZF
  • União-disjunta na ZF
  • Relações na ZF
  • Funções na ZF
  • (Dedekind-)infinito na ZF
  • ZF7
  • A existência de quantos conjuntos infinitos é garantida pelos axiomas ZF1–ZF7?

09/06/2017: Prova 2

14/06/2017: ZF

  • (Weak) cardinal-assignment
  • Números cardinais e sua aritmética
  • Class-functions (operadores) e class-relations
  • Grupos e conjuntos estruturados na ZF
  • ZF7 e suas conseqüências
  • Axiomas de Peano
  • Existência e unicidade dos naturais
  • Top-down definições

14/06/2017: ZF

  • Existência e unicidade dos naturais: onde “roubamos”
  • Funções parciais
  • Teorema de recursão
  • Class-functions e fórmulas function-like
  • Bottom-up definições
  • ZF8 e suas conseqüências
  • ZF9 e suas conseqüências

19/06/2017 (1): ZFC

  • Família indexada por I
  • Produto e tuplas generalizados
  • Axiomas de escolha e suas conseqüências
  • Conseqüências controversiais
  • Resolução dos A e B Prova 2 do 2016.1

19/06/2017 (2): Teoria de Ordem

  • Bem-ordens
  • Poset
  • Exemplos
  • Diagramas Hasse
  • Up-sets, down-sets
  • 𝒪(P): O poset de todos os down-sets de P, ordenados por ⊆
  • x, ↓x
  • A, ↓A

21/06/2017 (1): Teoria de Ordem

  • order-preserving (monótona)
  • order-embedding
  • order-isomorfísmo
  • Construindo ordens
  • P
  • PQ
  • PQ
  • P×Q com pointwise e (anti)lexicográfica ordem
  • Números transfinitos: cardinais & ordinais
  • Números ordinais
  • Aritmética ordinal

21/06/2017 (2): Reticulados

  • sup/inf, lub/glb, join/meet
  • Reticulados
  • Reticulados algebricamente
  • Reticulados completos

22/06/2017: Reticulados; Revisão

23/06/2017: Prova 3

26/06/2017: Revisão I

  • Sermão
  • Resolução da Prova 3
  • Hypergame
  • Uma prova alternativa do teorema de Cantor

28/06/2017: Revisão II

  • Revisão
  • Resolução de provas antigas
  • Tirar dúvidas

30/06/2017: Prova 4

Last update: Sat Jul 1 01:55:32 -03 2017