LEIC-FEUP 2001/2002
Teoria da Computação 2
Teoria de Conjuntos
Axiomas de Cantor para a Teoria dos Conjuntos
Paradoxo de Russell
Axiomas de Zermelo-Frankel
Referência:
Language, Proof and Logic
Jon Barwise e John Etchemendy, 1999
Capítulo: 15
1
Linguagem de 1ª ordem da teoria de conjuntos
n
Teoria de conjuntos: linguagem universal nas ciências
–
n
útil na modelização de estruturas muito diversas
Abordagem
–
–
Partir da noção intuitiva de conjunto
identificar 2 princípios básicos que a caracterizam
n
n
–
–
–
axioma da extensionalidade
axioma da compreensão
explorar consequências lógicas dos axiomas
mostrar inconsistência dos axiomas
rever axiomas para os da teoria de conjuntos moderna
Teoria de Conjuntos-2
Cristina Ribeiro/ Gabriel David
1 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Teoria dos conjuntos de Cantor
Georg Cantor(1845-1918)
Matemático que desenvolveu a sua actividade na Alemanha
Trabalha na definição dos números reais e estuda a cardinalidade dos conjuntos
Desenvolve primeira teoria dos conjuntos infinitos
n
Conceito intuitivo de conjunto
–
–
n
Conjunto: colecção de coisas (elementos)
Linguagem de 1ª ordem: 2 símbolos de relação =, ∈
Domínio de discurso: pode ter outros objectos que não conjuntos
–
–
Set(x)
predicado para a propriedade x é conjunto
2 tipos de variáveis
n
n
n
a, b, c, … conjuntos
x, y, z, … quaisquer objectos do domínio
Em vez de ∀x ∃y (Set(y) ∧ x∈ y) escreve-se ∀x ∃a (x∈ a)
Teoria de Conjuntos-3
Axiomas de Cantor
n
Axioma da extensionalidade
n
n
n
Um conjunto é completamente determinado pelos seus elementos
Se os conjuntos a e b têm os mesmos elementos, a=b
∀a ∀b [∀x (x∈ a ↔ x∈ b) → a=b]
Implicações
–
Identidade de um conjunto não depende da forma de o descrever
Exemplo: conjunto dos primos entre 6 e 12
conjunto das soluções da equação x2 - 18x +77 = 0
{7,11}
n
Nota
–
–
Axioma seria inaceitável numa teoria de propriedades.
2 propriedades podem verificar-se para exactamente os mesmos
objectos e serem distintas
Teoria de Conjuntos-4
Cristina Ribeiro/ Gabriel David
2 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Axiomas de Cantor
n
Axioma da compreensão
–
–
n
Toda a propriedade determina um conjunto
Para uma propriedade P, existe o conjunto de todos os objectos para
os quais se verifica P
Propriedades: fórmulas de 1ª ordem
–
Para cada fórmula P(x) considera-se o axioma
∃a ∀x [x∈ a ↔ P(x)]
Existe um conjunto cujos elementos são exactamente os objectos que verificam P(x)
–
–
Expressão não é axioma mas “esquema de axiomas”: existe 1 para
cada wff P(x)
P(x) pode ter variáveis z1, … zn para além de x: quantificação
implícita é universal
∀z1…∀zn ∃a ∀x [x∈ a ↔ P(x)]
Teoria de Conjuntos-5
Explorar axiomas
n
Teorema 1:
–Conjunto de objectos que satisfazem P(x) é único
∀z1…∀zn ∃!a ∀x [x∈ a ↔ P(x)]
Prova:
Compreensão: existe pelo menos 1 conjunto de objectos que
satisfazem P(x)
Falta prova que existe no máximo 1
a e b: conjuntos que verificam P(x)
∀x [x∈ a ↔ P(x)]
∀x [x∈ b ↔ P(x)]
Então ∀x [x∈ a ↔x∈ b] e pela extensionalidade a=b
n
Conjunto de objectos que satisfazem P(x):
{x| P(x)}
Teoria de Conjuntos-6
Cristina Ribeiro/ Gabriel David
3 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Conjuntos singulares e vazio
n
1 só objecto x satisfaz P(x)
–
–
–
n
Pelo axioma da compreensão: existe conjunto a cujo único
elemento é x
a = {x}
distinguir objecto x de conjunto singular que contém x
Nenhum objecto satisfaz P(x)
–
–
–
conjunto vazio
existe 1 no máximo
notação: ∅, {}, {x| x ≠ x}, ...
Teoria de Conjuntos-7
Subconjuntos
n
Definição: Para os conjuntos a e b
a subconjunto de b se todo o elemento de a é elemento de b
n
a⊆ b
–abreviatura
de
∀x [x∈ a →x∈ b]
–novo símbolo de relação binária, introduzido por um axioma
∀a∀b [a ⊆ b ↔ ∀x (x∈ a →x∈ b)]
s
Teorema 3: Para conjuntos a e b, a=b sse a ⊆ b e b ⊆ a
∀a∀b (a = b ↔ a ⊆ b ∧ b ⊆ a)
→ a=b e e b são o mesmo conjunto, cada elemento de a é elemento de b e vice-versa
← a ⊆ b e b ⊆ a Extensionalidade: basta provar que a e b têm os mesmo
elementos; decorre da premissa: cada elemento de a é elemento de b e vice-versa
Teoria de Conjuntos-8
Cristina Ribeiro/ Gabriel David
4 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Intersecção e união
n
Definições: a e b conjuntos arbitrários
n
1. A intersecção de a e b, a ∩ b, é o conjunto cujos elementos são
exactamente os objectos que pertencem a a e a b
1. A união de a e b, a ∪ b, é o conjunto cujos elementos são
exactamente os objectos que pertencem a a ou a b
Poderemos provar que existem os conjuntos a ∩ b e a ∪ b?
s
Teorema 4: Para todo o par de conjuntos a e b, existe 1 e 1 só
conjunto c cujos elementos são objectos em a e em b
∀a∀b∃!c ∀x [x∈c ↔ (x∈a ∧ x∈b)]
Prova: (prova condicional geral)
Sejam a e b conjuntos arbitrários
Compreensão: c= {x| x∈a ∧ x∈b} existe o conjunto pretendido
Extensionalidade: c é único
Teoria de Conjuntos-9
Intersecção e união
s
Teorema 5: Para todo o par de conjuntos a e b, existe 1 e 1 só
conjunto c cujos elementos são objectos em a ou em b
∀a∀b∃!c ∀x [x∈c ↔ (x∈a ∨ x∈b)]
Prova:
a e b conjuntos arbitrários
Compreensão: c= {x| x∈a ∨ x∈b} existe o conjunto pretendido
Extensionalidade: c é único
n
Estatuto de ∩ e ∪ na linguagem
–
–
abreviaturas de descrições
n a ∩ b é “ o conjunto cujos elementos são exactamente os
objectos que são elementos de a e de b”
novos símbolos de função binários: definições são novos axiomas
Teoria de Conjuntos-10
Cristina Ribeiro/ Gabriel David
5 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Conjuntos de conjuntos
n
s
Pelo axioma da compreensão: conjuntos de conjuntos podem
ser formados arbitrariamente
Teorema 7: Para quaisquer objectos x e y existe 1 único conjunto
a={x,y}
∀x∀y∃!a ∀w [w∈a ↔ (w=x ∨ w=y)]
Prova:
Existência: propriedade P(z) é z=x ∨ z=y
conjunto {z| P(z)} tem x e y como únicos elementos
Unicidade: pelo axioma da extensionalidade
s
Teorema 8: Para todo o objecto x existe o conjunto singular {x}
Prova:
Aplicar o Teorema 7 para x=y
Teoria de Conjuntos-11
Representar ordenação
n
n
n
Conjuntos não são ordenados
O par ordenado <x,y> pode ser representado pelo conjunto
{{x}, {x,y}}
Representação verifica propriedade fundamental dos pares
<x,y> = <u,v> → (x=u ∧ y=v)
n
A partir de pares ordenados
–
–
–
ternos e outros tuplos
relações
funções
Teoria de Conjuntos-12
Cristina Ribeiro/ Gabriel David
6 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Conjunto das partes de um conjunto
s
Teorema 10: Para todo o conjunto b existe 1 único conjunto cujos
elementos são exactamente os subconjuntos de b
Prova:
Compreensão: existe c= {x| x ⊆ b}
Extensionalidade: c é único
℘b = {a | a ⊆ b}
n
Exemplo
b= {2,3}
℘b = {∅, {2}, {3}, {2,3}}
Teoria de Conjuntos-13
Propriedades de ℘b
s
Teorema 11: Sendo a e b conjuntos
1. b ∈ ℘b
2. ∅ ∈ ℘b
3. a ⊆ b sse ℘a ⊆ ℘b
n
Conjunto pode ter subconjuntos que são elementos:
n
Ex: { Blop, {Blop}}
Teoria de Conjuntos-14
Cristina Ribeiro/ Gabriel David
7 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Propriedades de ℘b
s
Teorema 12: Para todo o conjunto b, não se verifica ℘b ⊆
b
“um conjunto não pode ter todos os seus subconjuntos como elementos”
Prova:
b: conjunto arbitrário
Constrói-se subconjunto de b que não é elemento de b
c= {x| x∈b ∧ x ∉ x}
c ⊆ b pela definição de c, logo c ∈ ℘b pela definição de ℘b
Para mostrar que c ∉ b: Supor c∈ b
Por casos: c∈c ou c ∉ c
Se c∈ c: pela definição, c é elemento de b que não pertence a c; então c ∉
c
Se c ∉ c: c é elemento de b que verifica a condição de definição de c;
então c∈c
Por contradição: ℘b ⊆ b é falso
Teoria de Conjuntos-15
Conjunto de Russell
s
Teorema 13 (conjunto de Russell para b): Para todo o conjunto
b, o conjunto
{x| x∈b ∧ x ∉ x}
é subconjunto de b mas não elemento de b.
n
s
Falha na axiomatização: pode provar-se a negação do
Teorema 12
Teorema 14: Existe um conjunto c tal que ℘c ⊆ c
Prova:
b: conjunto arbitrário
Axioma da compreensão: existe conjunto universal (V)
c= {x| x = x}
todo o subconjunto de c é elemento de c, logo ℘c é subconjunto de c.
Teoria de Conjuntos-16
Cristina Ribeiro/ Gabriel David
8 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Paradoxo de Russell
n
Onde reside a contradição?
Z= {x| x∈ V ∧ x ∉ x} conjunto de Russell para o conjunto universal
Teorema 9 prova que Z é elemento de Z sse Z não é elemento de Z
n
É o paradoxo de Russell
–
n
Mostra que a axiomatização da noção intuitiva de conjunto é
inconsistente
Problema está no Axioma da Compreensão
¬∃c ∀x [x∈ c ↔ x ∉ x]
Afirmação verdadeira que contradiz o axioma da compreensão
n
Intuitivamente
–
Alguns predicados têm extensões “excessivas” para serem tratadas
como um objecto matemático
Teoria de Conjuntos-17
Nova axiomatização
n
Predicados com extensões excessivas
–
–
n
Evitar a inconsistência - regra de formação de conjuntos
–
–
n
Colecção de todos os conjuntos
Colecção dos conjuntos que não se contêm como elementos
de um conjunto a e uma propriedade P(x) podemos formar
{x | x∈ a ∧ P(x)}
se a não é conjunto excessivo um seu subconjunto também não
Axioma da separação
–
∀a∃b ∀x [x∈ b ↔ (x∈ a ∧ P(x))]
É restrito demais: exclui usos legítimos do axioma da comprensão
n
n
não pode provar-se a existência da união
não pode provar-se a existência do conjunto das partes
Teoria de Conjuntos-18
Cristina Ribeiro/ Gabriel David
9 - T. Conjuntos
LEIC-FEUP 2001/2002
Teoria da Computação 2
Axiomas de Zermelo-Frankel
1. Extensionalidade
2. Separação
3. Par não ordenado: para quaisquer 2 objectos existe um conjunto que os tem
como elementos
4. União: Dado um conjunto a de conjuntos, a união dos elementos de a é um
conjunto ∀a∃b ∀x [x∈b ↔ ∃c∈a (x∈c)]
5. Conjunto das partes
6. Infinito: existe o conjunto de todos os números naturais
7. Substituição: Para todo o conjunto a e operação F que define um objecto único
para cada x em a, existe o conjunto {F(x) | x∈ a}
Se ∀x∈ a ∃!y∈ b P(x,y) então existe b= {y | ∃x∈ a P(x,y)}
8. Escolha: Sendo f uma função com domínio não vazio a tal que, para cada x∈ a,
f(x) é um conjunto não vazio, então existe uma função g com domínio a tal
que, para cada x∈ a, g(x) ∈ f(x).
9. Regularidade
Nenhum conjunto tem uma intersecção não vazia com cada um dos seus
elementos
∀b[b≠∅ → ∃y∈ b (y∩ b= ∅)]
Teoria de Conjuntos-19
Cristina Ribeiro/ Gabriel David
10 - T. Conjuntos