FEUP / LEIC
TEORIA DA COMPUTAÇÃO II
TEORIA DOS CONJUNTOS
1 {15-1} Igualdade de conjuntos. As afirmações seguintes são verdadeiras ou falsas?
Prove a sua resposta.
a) {7,8,9} = {7,8,10}
b) {7,8,9,10} = {7,8,10,9}
c) {7,8,9,9} = {7,8,9}
2 {15-5} Prova Formal. No ficheiro de exercícios Exercise 15.5 pede-se uma prova
formal do passo principal da prova da Proposição 1. Complete a prova, sem utilizar
nenhuma das regras Con. (Nota: O símbolo ∈ encontra-se no menu.)
3 {15.8} Extensão. Suponha que a1 e a2 são conjuntos, cada um dos quais com apenas
um elemento, a Torre dos Clérigos. Mostre que a1=a2.
4
{15.9} Unicidade do conjunto vazio. Prove, informalmente, que há apenas um
conjunto vazio. (Sugestão: utilize o axioma da Extensionalidade.)
5
{15.11} Conjunto vazio. Prove informalmente o seguinte teorema: para todo o
conjuntos a, φ ⊆ a.
6 {15-12} Prova Formal. No ficheiro de exercícios Exercise 15.12 pede-se uma prova
formal da Proposição 2, relativa à relação de subconjunto. Complete a prova, sem
utilizar nenhuma das regras Con. (Nota: O símbolo ⊆ encontra-se no menu.)
7 {15-60} Conjunto das partes. Prove ou arranje um contra-exemplo para cada uma das
seguintes conjecturas:
a) Para qualquer conjunto b, φ ⊆ ℘b.
b) Para qualquer conjunto b, b ⊆ ℘b.
c) Para quaisquer conjuntos a e b, ℘(a ∪ b) = ℘a ∪ ℘b.
d) Para quaisquer conjuntos a e b, ℘(a ∩ b) = ℘a ∩ ℘b.
8 {15-61} Conjunto de Russell. Determine o conjunto de Russell para cada um dos
conjuntos seguintes:
a) {∅}
b) Um conjunto que satisfaz a={a}.
c) Um conjunto {1,a} em que a={a}.
d) O conjunto de todos os conjuntos.
9 {15-63} Axiomas de Zermelo-Frankel. Use os axiomas da separação e da
extensionalidade para provar que, se existe algum conjunto, existe o conjunto vazio.
10 {15-64} Axiomas de Zermelo-Frankel. Verifique a afirmação de que os teoremas 213 se podem provar usando os axiomas ZFC. (Algumas das provas serão triviais, uma
vez que correspondem a fórmulas que foram introduzidas como axiomas).
CRISTINA RIBEIRO
CONJUNTOS - 1