Trabalho Trabalho
Exerc´ 1 ıcio Exerc´ ıcio 1-1. Defina Seq(C) como o conjunto de todas as sequˆncias finitas de elementos do e conjunto C. Por exemplo, se C = {1, 2, 3}, ent˜o a sequˆncia 1.2.1 ∈ Seq(C). Demonstre que se A a e
´ um conjunto cont´vel, ent˜o o conjunto de todas as suas sequˆncias Seq(A) ´ tamb´m cont´vel. e a a e e e a Exerc´ ıcio 1-2. (dado em sala de aula!) Prove por indu¸˜o que qualquer n´mero natural ca u pode ser representado por uma soma de n´meros Fibonacci distintos. Por exemplo, 10 = 8 + 2; u 15 = 8 + 5 + 2. Veja http://en.wikipedia.org/wiki/Zeckendorf’s_theorem
Exerc´ ıcio 1-3. (dado em sala de aula!) Prove o teorema da consequˆncia l´gica: Teorema: e o
Para quaisquer f´rmulas G, F1 , . . . , Fn , temos que F1 , . . . , Fn G se e somente se (F1 ∧ F2 ∧ o · · · ∧ Fn ) ⇒ G.
Exerc´ ıcio 1-4. (dado em sala de aula!)
G ≡ H, ent˜o F [G] ≡ F [H]. a Exerc´ ıcio 1-5. (dado em sala de aula!) e quais as suas consequˆncias. e Exerc´ ıcio 1-6.
Prove o teorema da substitui¸˜o por indu¸˜o: Se ca ca
Explique o que diz o teorema de elimina¸˜o de cortes ca Explique com as suas pr´prias palavras o que significa corretude e completude. o Exerc´ ıcio 1-7. Quest˜o Bˆnus (1 ponto) No dia do exame, quem quiser pode-se candidaa o tar a responder esta quest˜o. Se responder corretamente, receber´ 2 pontos na pr´xima lista de a a o exerc´ ıcios: Prove que existem conjuntos incont´veis, quer dizer, que n˜o tem um isomorfismo com o a a conjunto dos n´meros naturais. u Dica: Veja a argumento de diagonaliza¸˜o de Cantor descrito no link abaixo: ca http://en.wikipedia.org/wiki/Cantor’s_diagonal_argument