Sumários
T_9
30 Abril 2025, 09:30 • Mário Jorge Edmundo
Funções básica são computáveis; adição e multiplicação são computáveis; composição; definição por casos; minimização, minimização limitada; subtração, Pair, Left, Right; a função beta de Godel; sequências; recursão; recursão primitiva; funções recursivas primitivas, funções recursivas; relações recursivas (resp. recursivas primitivas); função de Ackermann; as funções / relações recursivas (resp. primitivas recursivas) são funções computáveis / relações decidíveis.
T_8
16 Abril 2025, 09:30 • Mário Jorge Edmundo
Definição informal de relação decidível e função computável, nota sobre função característica e gráfico; tese de Church-Turing; A teoria Q de Robinson, termos fechados e Q, variáveis limitadas por termos fechados, fórmulas decididas corretamente por Q, fecho para conectivos e quantificadores limitados; fórmulas Delta zero, Q decide corretamente fórmulas Delta zero; conjuntos e funções definíveis, relações Q-decidíveis e funções Q-computáveis (representabilidade); definição informal de relação semi-decidível e função semi-computável; fórmulas semi-decididas corretamente por Q, relações Q-semi-decidíveis e funções Q-semi-computáveis (representabilidade fraca).
T_7
9 Abril 2025, 09:30 • Mário Jorge Edmundo
Eliminação de quantificadores (EQ), conjunções básicas, critério para EQ; EQ e completude; exemplos (conjuntos infinitos, ordens densas e sem extremidades, grupos abelianos divisíveis e livres de torsão, espaços vectoriais infinitos, grupos abelianos divisíveis e ordenados); referência ao teorema de Tarski-Seidenberg.
T_6
2 Abril 2025, 09:30 • Mário Jorge Edmundo
Equivalência elementar, isomorfismo e equivalência elementar; completude, exemplos; completude e consequência lógica; completude e modelos; kappa-categoricidade, teste de Vaught para a completude; exemplos (conjuntos infinitos, ordens lineares densas sem extremidade, espaços vetoriais infinitos, corpos algebricamente fechados de característica 0 ou p).
T_5
26 Março 2025, 09:30 • Mário Jorge Edmundo
As regras de inferência do sistema formal de demonstração Dedução Natural; propriedades da igualdade; exemplos de demonstrações em DN; DN é correto; em DN adição de testemunhas preserva a consistência; consistência maximal e dedução; fecho para conectivos e quantificadores; teorema de completude de Godel para DN; teorema da compacidade (outra vez).