2016.1 FMC2, turma de Thanos

Horário:246M34 [08h55–10h35]
Sala de aulas:B203
Sala do prof:A224 A224+, ou seja, A225
Contáto: thanos@tsouanas.org
Comentários anônimos (100% experimental)
Monitor: Rafael Oliveira Mendes
Horário de monitoria: 35T34 (14h55-16h30)
Sala de monitoria: A220

Voluntários

  • Unidade 1
    • Adelino (1)
    • Alessandre (1)
    • Giovanni (1)
    • Gustavo (3)
    • Rodrigo (3)
    • Yuri (2)
    • Yuri' (3)
  • Unidade 2
    • Giovanni (2)
    • Gilney (1)
    • Rodrigo (1)
    • Alessandre (1)
    • Gustavo (4)
    • Yuri' (2)
    • Thiago (1)
    • JV (1)
  • Unidade 3
    • Adelino (1)
    • Gustavo (4)
    • JV (1)
    • Thiago (1)
    • Giovanni (3)
    • Yuri (1)

Bonus points

  • Unidade 1
    • Yuri (0,25)
    • Elton (0,25)
    • Gustavo (0,15)
    • Thiago (0,05)
    • Rodrigo (0,10)
  • Unidade 2
    • Thiago (0,10)
    • Gustavo (0,40)
    • Pedro Arthur (0,20)
    • Giovanni (0,70)
    • Yuri' (0,20)
    • Joel (0,20)
    • Gilney (0,10)
  • Unidade 3
    • Rodrigo (0,10)
    • Giovanni (0,30)
    • Gustavo (0,30)
    • Elton (0,10)
    • JV (0,10)
    • Yuri (0,35)
    • Yuri' (0,20)
    • Thiago (0,10)
    • Gilney (0,15)
    • Irene (0,10)
    • Pedro Arthur (0,10)

Atividades / Exercícios / Problemas

Vocês podem mandar suas soluções pelo email (pode ser foto/scan de papel, ou arquivo PDF escrito em TeX/LaTeX/etc., mas não em Word/LibreOffice/etc.), ou entregar pessoalmente na aula em papel mesmo (opção bem melhor!).

  1. Problem set A (prazo: 12/02/2016, 08h55).
  2. Problem set B (prazo: 18/03/2016, 09h00) [Vale pontos!].

λ-calculus

  • Mostre que:
    • S(KS)K → B
    • SKK → I
  • Ache λ-termos que ``behavem'' como o ``not'', o ``or'', e o ``and''.

Exercisios dos livros de conjuntos

  • Moschovakis
    • Chap 1: todos
    • Chap 2: (menos a prova do 2.26), todos os ex & probs (os x2.9 e x2.10 precisam conhecimento de cálculo).
    • Chap 3: (menos a 3.18 e o x3.3)
    • Chap 4: (até 4.30) menos os problemas x4.17-20 e x4.26-27.
    • Chap 5: (menos: 5.10-5.12, 5.33 (a gente viu uma prova diferente para o 5.32)). Menos os problemas: x5.21, x5.26-27. Memorize o problema x5.28 (brincadeira).
  • Goldrei
    • 4.3 4.4 4.5 4.6 4.8 4.9 4.13 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.27 4.28 4.29 4.30 4.31 4.32 4.33 4.34 4.36 4.38 4.39 4.40 4.41 4.42 4.43 4.44 4.47 4.48

Bibliografia

Sobre teoria dos conjuntos (e ordens):

Sobre lógica

Sobre ordem e reticulados

Conteúdo (fluido)

Lógica matemática e provas
Lógica proposicional, Lógica de predicados Sintaxe e semântica Definições pelo recursão, provas por indução
Teoria ingenua dos conjuntos
Especificando coleções sem estrutura e seus membros. Relações e operações básicas. Enumerações e conceito intuitivo de cardinalidade. Uniões disjuntas, famílias e partições. Tuplas ordenadas e produto cartesiano.
Relações e funções
Equivalências, partições, fechos. Regras e gráficos (intensão x extensão). Domínio, imagem, parcialidade, restrição, e composição. Injetividade e sobrejetividade. Função constante, função identidade, projeções, funções características. Funções recursivas. Currying.
Teoria axiomática dos conjuntos
Paradoxos. Os axiomas ZFC. A teoria dos conjuntos como linguagem de matemática: definições de função, tupla ordenada, números naturais, etc. Indução, predicados, e funções recursivas.
Ordens
Diagramas de Hasse. Ordens parciais, totais, densas, bem-fundadas. Elementos notáveis (majorantes, máximos, supremos). Dualidade e monotonicidade. Ordens canônicas, ordens lexicográficas. Conjuntos ordenados, reticulados. Indução bem-fundada. Monotonicidade. Teoremas de ponto fixo. Aplicações em linguagens de programação. Números ordinais.
Elementos de Álgebra abstrata
Conjuntos com estrutura. Monoides. Grupos, subgrupos, homomorfísmos. Reticulados (de novo!) Álgebras booleanas. Demonstrações com o uso de identidades algébricas.
Aplicações e outros assuntos
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. Lógicas não-clássicas, elementos de lógica intuitionística e de lógica linear.

Provas

  • Prova 1 (01/04/2016)
    • Lógica (proposicional e de predicados)
      • fórmulas bem formadas de F0 e F1
      • árvores sintáticas de fórmulas
      • atribuações de valores
      • tabelas de valores
      • estruturas (``mundos'') e modelos
      • fórmulas equivalentes
      • negação de fórmulas, manipulação de quantificadores
      • conjuntos completos de conectivos
    • Definições recursivas (de conjuntos e de funções)
    • Provas pelo indução: no N, no F0, no F1, etc.
    • Teoria de conjuntos:
      • As operações e relações entre conjuntos (∪, ∩, \, ×, P, =, ⊆, etc.)
      • Os conjuntos N, Z, Q, R
      • Os números naturáis, intéiros, racionais, irracionais, reais, algebricos e transcedentais.
      • Funções (in/sobre/bijetoras), imagem, pre-imagem, domínio, contradomínio, etc.
      • Cardinalidade
      • Funções e relações como conjuntos de pares
      • O paradóxo do Russel
  • Prova 2 (13/05/2016)
    • Teoria de conjuntos
      • os axiomas ZFC
      • relações, funções, e funções parciais na ZFC
      • cardinais (weak)
      • os axiomas Peano e os naturais na ZFC (existência e uniqueness)
      • Teorema da recursão
      • String recursion
      • Currying
    • λ-calculus
      • O conjunto Λ de λ-termos
      • α, β, e η conversões
      • Booleanos e naturais no Λ
      • Combinators I, K, B, S
  • Prova 2' (23/05/2016)
    • O foco dessa prova pequena é:
      • os axiomas ZFC (ZF1-ZF9 + AC)!
      • relações, funções, e funções parciais na ZFC
      • os axiomas Peano e os naturais na ZFC (existência e uniqueness)
      • Teorema da recursão
    • Material para estudar e praticar o material novo usando o livro de Goldrei
      • study: pp.92-96, pp.104-109;
      • exercises: 4.39, 4.40, 4.41, 4.42, 4.48, 5.1, 5.2, 5.3, 5.4, 5.5, 5.9, 5.10, 5.11, 5.12, 5.13, 5.16(a-b)
  • Prova 3 (25/05/2016)-final

    Todas as aulas fazem parte da terceira prova.

  • Prova 4 (17/06/2016)

Notas

Histórico de aulas

03/02/2016

  • Conjuntos notáveis de números, N, Z, Q, R\Q, R.
  • Números racionais e irracionais: o √2 é irracional.
  • Números algébricos e transcendentais. Exemplos.
  • Funções injetoras, sobrejetoras, e bijetoras.
  • As primeiras idéias de Cantor sobre conjuntos.
  • Os conjuntos N e Z tem a mesma cardinalidade.

12/02/2016

  • Definições de relações de cardinalidade usando funções.
  • Operadores básicos entre conjuntos: união, interseção, diferença, complemento, produto cartesiano

15/02/2016

  • Operadores básicos dos conjuntos: definição de união e interseção de UM conjuntos
  • Q também tem a mesma cardinalidade que N: o primeiro argumento de diagonalização do Cantor
  • [0,1] tem cardinalidade maior que os outros: o segundo argumento de diagonalização do Cantor

17/02/2016

  • A primeira grande aplicação da teoria do Cantor em matemática:
    • o conjunto dos algébricos é contável
    • os transcendentais são incontáveis
    • logo, a maioria dos números reais são transcendentais

19/02/2016

  • Duas cartas
    • de Cantor para Dedekind (cadê o erro?)
    • de Russel para Frege
  • O axioma da extesionalidade
  • O axioma da compreensão
  • o paradoxo do Russel
  • a solução do Zermelo, o axioma da separação

22/02/2016

  • a cardinalidade dos programas corretos numa linguagem de programação
  • a cardinalidade do conjunto de funções de N para {0,1}
  • Mais uma grande aplicação da teoria dos conjuntos, em ciência da computação: limites da computação

24/02/2016

  • A resposta do Dedekind para Cantor
  • Mais definições de operadores de conjuntos: conjunto potência, interseção do conjunto vazio
  • Se A finito, |P(A)| = 2|A|
  • Teorema (Cantor): A <c P(A)
  • conseqüências: uma infinidade de infinidades
  • atividade: descrever um algoritmo que:
    • tem duas entradas: um programa p que calcula uma função f de N para N, e um número n.
    • se o programa p com a entrada n termina, retorna 1
    • senão, retorna 0

26/02/2016

  • uma representação geométrica da dízima (em qualquer base) dos números em [0,1]
  • o conjunto Δ das seqüências infinitas de 0 e 1, e o conjunto de Cantor
  • P(N) =c R ?
  • P(N) =c Δ ≤c R
  • Exercicio: se A =c B então P(A) =c P(B)

29/02/2016 - 09/03/2016 (flashback para FMC I)

  • Definições recursivas dos conjuntos N, F0, e F1
  • Provas por indução
  • Definições recursivas de funções
  • Introdução em programação funcional
  • Lógica proposicional
  • Lógica de predicados
  • Semântica, mundos, e modelos
  • Definições: Relações, funções parciais
  • Negação de fórmulas

11/03/2016

  • Uma aplicação em probabilidades: escolhendo aleatoriamente um racional no [0,1].
  • Voltando nos conjuntos: provando formalmente que se A =c B então P(A) =c P(B)

14/03/2016

  • (Finalmente:) A =c B então P(A) =c P(B)
  • P(N) ≤c R e R ≤c P(N)
  • Teorema de Schröder-Bernstein-Cantor
  • Os primeiros 3 axiomas da ZF.

16/03/2016

  • Teoria dos conjuntos como fundação e linguagem de matemática
  • Os primeiros 6 axiomas da ZF.
  • Definições de: ∅, {a, b}, {a}, {x ∈ s | P(x) }, a ⊆ b, a ∪ b, a ∩ b, a \ b, ℘a, a, (a,b), e a × b.

18/03/2016

  • Os primeiros 7 axiomas da ZF.
  • a

21/03/2016

  • Conjuntos de conectivos completos
  • Indução especializada para subconjuntos de F0
  • formulas em DNF

23/03/2016

25/03/2016

28/03/2016

Revisão (1)

30/03/2016

Revisão (2)

01/04/2016

Prova! Revisão (3)

04/04/2016

Prova 1

06/04/2016

Resolução da prova

08/04/2016

  • Introdução na semântica de linguagens
    • A linguagem dos numerais binários B
    • Definindo funções recursivas no B
    • Provando com indução propriedades dessas funções
  • O N* é contável.

11/04/2016

  • Um jeito diferente para definir o conjunto B dos numerais binários
    • Como definir o sucessor?
    • Como definir uma semântica?
  • Uma limitação sobre o esquema axiomático da separação
  • Currying: ((A x B) → C) =c (A → (B → C))

13/04/2016

  • Weak and strong cardinality assignments
  • Uma introdução em λ-calculus

15/04/2016

  • Mais λ-calculus, reduções α, β, η.
  • Os combinators I, K, B, S.

18/04/2016

  • Mais λ-calculus, valores booleanos.
  • Os axiomas de Peano
  • Conjuntos estruturados
  • Isomorfismos

20/04/2016

  • Os naturais na teoria de conjuntos
  • Existencia

22/04/2016

  • Os naturais na teoria de conjuntos
  • Os booleanos no λ-calculus

25/04/2016

  • Os naturais no λ-calculus

29/04/2016

  • String recursion: isempty, ++, reverse, prefix, ∈, find

04/05/2016

  • Mais string recursion: sum, prod, pointwise addition/multiplication, circle
  • Uniqueness dos naturais

06/05/2016

09/05/2016

11/05/2016 (3 aulas)

13/05/2016

Prova 2

16/05/2016

18/05/2016

20/05/2016 (2 aulas)

23/05/2016

25/05/2016

  • Correção de prova
  • Teoria de Ordem
    • Definição: ordem, poset, pre-ordem, ordem linear (total), cadéia
    • Diagramas Hasse
    • Exemplos

27/05/2016

30/05/2016

01/06/2016

  • Relações de equivalência
  • de pre-ordem para ordem

03/06/2016 (2 aulas)

  • operações em posets (adição, união)
  • flat posets, lifting
  • posets de numeros (como cadeias e como flat)
  • boa ordem
  • upper/lower bounds
  • supremum, infimum
  • lattices (reticulados)
  • exemplos

06/06/2016

  • resolução das questões da última provinha
  • o poset das funções parciais
  • ordens em strings, prefix
  • construções de posets: producto cartesiano, lifting, dual
  • upsets e downsets, o operador ``down'', O(P)

08/06/2016 (2 aulas)

  • Downsets dos N, Z, Q, R.
  • Complete lattices
  • sup e inf do vazio e do P (P poset).
  • mappings (funções) entre posets:
    • monotone (order-preserving)
    • moder embedding
    • moder-isomorphism
  • Well-orderings and ordinals
    • Zero, Successor and Limit points
    • Ordinal arithmetic
    • Finite and infinite ordinals
    • Como os ordinais contáveis aparecem

10/06/2016 (2 aulas)

  • Join e meet no (N;|)
  • Números ordinais (revisão)
  • Funções monotonicas, order-embeddings, order-ismorfismos (revisão)
  • Indução transfinita
  • Recursão transfinita e exemplos
    • adição de ordinais
    • as potencias "downwards" e "upwards" de um mapeamento monotonico definido num reticulado completo.
  • Fixpoints
  • Teorema Knaster-Tarski
  • Aplicação na definição de funções recursivas (no λ-calculus)
  • Elementos de teoria de tipos
  • Introdução no ismorfismo Curry-Howard
  • Lógica intuicionística e matemática construtiva
    • Existem a e b irracionais tais que ab racional?
      • Prova clássica
      • Prova construtiva
    • Alguem dos π + e, πe é irracional?
      • Prova clássica (por enquanto... apenas!)
      • Prova construtiva... boa sorte ;)

Last update: Sat Jun 18 14:43:39 BRT 2016