2016.1 FMC2, turma de Thanos

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):

• Classic set theory, for guided independent study de Derek Goldrei
• Notes on set theory de Yiannis Moschovakis

Sobre lógica

• Propositional and Predicate Calculus, de Derek Goldrei (capítulo 2, e secções 4.1-4.3)
• Mathematical Logic, a course with exercises, Vol. I, de René Cori e Daniel Lascar (partes dos capítulos 1 e 3)

Sobre ordem e reticulados

• Introduction to Lattices and Order, de B. Davey e H. Priestley

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 F₀ e F₁
    • á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 F₀, no F₁, 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

• Os axiomas ZFC

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, F₀, e F₁
• 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 F₀
• 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

• Resumo dos axiomas ZFC
• Prova 2'

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 a^b racional?
    • Prova clássica
    • Prova construtiva
  • Alguem dos π + e, πe é irracional?
    • Prova clássica (por enquanto... apenas!)
    • Prova construtiva... boa sorte ;)