Teoria dos conjuntos

Charles Morgan*

Capítulo 6. Lógica matemática: uma introdução super-rápida e algumas aplicações à teoria dos conjuntos.

6.1. Línguas (formais) da ordem primeira. Neste cápitulo vamos dar uma olhada muito breve sobre lógica matemática para explicar que foi significado no fim do §4.4. quando falamos que algumas coisas, por exemple (HCG), não são mostrável na sistema ZF nem são mostrável os contrários. Este consideração da lógica matématica ajuderá explicar o que quer dizer falar que pode demonstrar que alguma coisa não é mostrável. O chave para isso é a relação entre que é demonstrável e que é verdadeiro. Este não é nada místico, nem filosofico, mas é uma coisa matemática porque pelo verdadeiro queremos dizer verdadeiro num modelo duma coleção dos axiomas. Botâ-lo num outro modo, é a relação matemática entre sintaxe e semântica. Este assunto é chamado a teoria de modelos. Talvez vai paracer formal no início mas é muito efetivo. Um exemplo recente do poder do assunto é o trabalho célebre de Udi Hrushovski na área da teoria dos números/geometria algebraica aritmética usando métodos da teoria dos modelos. Para pegar mais sobre a teoria de modelos veja o livro de van Dalen para uma explicação mais completo da material desta seção, e posso recomendar os livros Wilfrid Hodges, A shorter model theory, Cambridge University Press(?), 1996(?), ou Bruno Poizat, A course in model theory, Springer, 2000 (ou a versão original em francês, Bruno Poizat, Cours de théorie de modèles, Nur al-Mantiq wal Ma’rifah, Lyons, 1985, que pode pegar do Poizat se mesmo). Infelizmente não tem qualquer livro no português sobre o assunto. E tem um esboço bom e acessível do trabalho de Hrushovski no Ehud Hrushovski, Geometric Model Theory, Documenta Mathematica, Extra Volume, ICM 1998, I, pp. 281-302.

Definição. Uma língua L para lógica da ordem primeira é feito de:

(i) um conjunto enumerável dos variávais v_{0}, v_{1},… (escritos como x, y, z,… quando queremos); (ii) um conjunto dos símbolos para funções f, g,… do várias “áridades” – um símbolo para uma função 0-ária é um símbolo para um constante c; (iii) um conjunto dos símbolos para relações R, S,… do várias áridades, e um símbolo especial = (que é binária); (iv) algumas ligações lógicas: &, ou, ⟶, ¬, ⊥;

(v) quantificadores ∀, ∃; (vi) sinais de pontuação como (, ), ..

Os termos de L são definidos pela uma definição recursiva.

(i) Qualquer variável v é um termo; (ii) se f é um símbolo para um função n-ária e t_{0},…, t_{n−1} são termos, então f(t_{0}, …, t_{n−1}) é um termo também.

Definamos os variáveis livres de um termo t, VL(t) pelo (i) VL(v) = {v } se v é um variável, e (ii) VL(f(t_{0}, …, t_{n−1})) = VL(t_{0}) ∪ … VL(t_{n−1}).

* versão 1.1, 15/12/00 Os fórmulas de L são definidos pela uma definição recursiva junto com a definição dos variáveis livres.

(i) Se R é um símbolo para uma relação n-ária e t_{0},…, t_{n−1} são termos, então R(t_{0}, …, t_{n−1}) é um fórmula. VL(R(t_{0}, …, t_{n−1})) = VL(t_{0}) ∪ … VL(t_{n−1}). (Estes fórmulas são chamados fórmulas atômicos.) (ii) Se ϕ e ψ são fórmulas, então ϕ & ψ, ϕ ou ψ, ϕ ⟶ ψ, ¬ϕ, ⊥ são fórmulas também. VL(ϕ & ψ) = VL(ϕ ou ψ) = VL(ϕ ⟶ ψ) = VL(ϕ) ∪ VL(ψ), VL(¬ϕ) = VL(ϕ) e VL(⊥) = ∅. (iii) Se ϕ é um fórmula e x ∈ VL(ϕ), então ∀x ϕ e ∃x ϕ é um fórmula também. VL(∀xϕ) = VL(∃xϕ) = VL(ϕ) \ {x}.

Então os variáveis livres de um fórmula ϕ são os variáveis “sobre qual ϕ fala alguma coisa.” Um fórmula ϕ é um frase se VL(ϕ) = ∅. Escreva ϕ(x̄) se x̄ é o fio x_{0},…, x_{n−1} e ϕ é um formula tal que VL(ϕ) ⊆ {x_{0}, …, x_{n−1} }.

Nota. Podemos definir todos as ligações e quantificadores usando so ou, ¬ e ∃ – que economizer no tempo mas tarde – se definimos ϕ & ψ = ¬(¬ϕ ou ¬ψ), ϕ ⟶ ψ = (¬ϕ ou ψ), ⊥= ¬(ϕ ou ¬ϕ) e ∀x ϕ = ¬∃x (¬ϕ).

Também precisamos uma definição de como substituir um termo em vez de um variável num termo ou num fórmula. Temos que ter cuidado com isso para preservar o sentido pretentido dum fórmula, porque se, por exemplo, ϕ é ∃y (y = x) e t = f(y) queremos que o resultado da substitução do t em vez de x não é ∃y (y = f(y)) mas ∃z (z = f(y)).

Então s[t/x], ϕ[t/x], o resulatado da substitução do t para x, é definido pela recursão:

v_{i}[t/x]  = t se x = v_{i}, e
= v_{i} senão;
f(s_{0}, …, s_{n−1})[t/x] = f(s_{0}[t/x], …, s_{n−1}[t/x]);
R(s_{0}, …, s_{n−1})[t/x] = R(s_{0}[t/x], …, s_{n−1}[t/x]);
(¬ϕ)[t/x]  = ¬(ϕ[t/x]);
⊥ [t/x]  =⊥;
(ϕ & ψ)[t/x]  = ϕ[t/x] & ψ[t/x];
(ϕ ou ψ)[t/x]  = ϕ[t/x] ou ψ[t/x];
(ϕ ⟶ ψ)[t/x]  = ϕ[t/x] ⟶ ψ[t/x];
(∀y ϕ)[t/x]  = ∀yϕ se x = y,
= ∀y (ϕ[t/x]) se y ≠ x e y ∉ VL(s), e
= ∀z ((ϕ[z/y])[t/x]) se y ≠ x e y ∈ VL(s), onde z

é uma escolha de alguma coisa z ∉ VL(s) ∪ VL(ϕ);

(∃y ϕ)[t/x]  = ∃yϕ se x = y,
= ∃y (ϕ[t/x]) se y ≠ x e y ∉ VL(s), e
= ∃z ((ϕ[z/y])[t/x]) se y ≠ x e y ∈ VL(s), onde z

é uma escolha de alguma coisa z ∉ VL(s) ∪ VL(ϕ).

A relação |– de derivação sintática vem de pensar sobre arvores de dedução com hipóteses nas folhas e a conclusão na base, feito das deduções “primativas.”

Formalmente definimos |– pela recursão. A definição é para fórmulas ϕ (uma conclusão) pela recursão na estrutura de ϕ e para qualquer conjunto dos fórmulas Γ (os hipóteses), na mesma hora.

No inicio temos Γ|– ϕ se ϕ ∈ Γ;

e: se Γ|– ϕ e Γ|– ψ,  então Γ|– ϕ & ψ;
se Γ|– ϕ & ψ,  então Γ|– ϕ;
se Γ|– ψ & ψ,  então Γ|– ψ;
ou: se Γ|– ϕ,  então Γ|– ϕ ou ψ;
se Γ|– ψ,  então Γ|– ϕ ou ψ;
se Γ|– ψ ou ψ, Γ ∪ {ϕ}|– χ e Γ ∪ {ψ }|– χ,  então Γ|– χ;
implicação: se Γ ∪ {ϕ}|– ψ,  então Γ|– ϕ ⟶ ψ;
se Γ|– ϕ ⟶ ψ e Γ|– ϕ,  então Γ|– ψ;
não/falso: se Γ ∪ {ϕ}|– ⊥,  então Γ|– ¬ϕ;
se Γ|– ⊥,  então Γ|– ϕ para qualquer ϕ;
se Γ|– ϕ e Γ|– ¬ϕ,  então Γ|– ⊥;
se Γ ∪ {¬ϕ}|– ⊥,  então Γ|– ϕ;
tudo: se Γ|– ϕ(x) e x ∉ ⋃{VL(ψ) | ψ ∈ Γ},  então Γ|– ∀x ϕ(x);
se Γ|– ∀x ϕ(x) e t é um termo,  então Γ|– ϕ[t/x];
existe: se Γ|– ϕ[t/x],  então Γ|– ∃x ϕ(x);
se Γ|– ∃x ϕ(x) e Γ ∪ {ϕ(y)}|– ψ e y ∉ VL(ψ), então Γ|– ψ.
igualidade: se s é um termo,  então Γ|– s = s;
se Γ|– s = t e Γ|– ϕ[s/x],  então Γ|– ϕ[t/x].

E porque na definição da introdução do tudo não falamos só que “se Γ|– ϕ(x) e x ∉ ⋃{VL(ψ) | ψ é usado na demonstração do ϕ(x) do Γ & ψ ∈ Γ}, então Γ|– ∀x ϕ(x),” temos que juntar que:

se Δ ⊆ Γ e Δ|– ϕ, então Γ|– ϕ.

Definição. Γ é consistente se Γ |̸– ⊥. Equivalentemente Γ é consistente se não existe um ϕ tal que Γ|– ϕ & ¬ϕ. As vezes escrevemos Con(Γ) para querer dizer que Γ é consistente.

Depois de todos estas definições eu deveria dar algumas exemplos. Porque agora estou muito atrasado vou evitar fazer isso.

Definição. Sejam L uma língua da primeria ordem, Γ uma coleção das frases e ϕ uma frase no L. d é uma derivação do ϕ de Γ se d é um liste (ou fio) finito dos fórmulas, ϕ_{0}, …, ϕ_{n} para alguma n < ω, com ϕ = ϕ_{n} e tal que para cada m ≤ n temos ou ϕ_{m} ∈ Γ ou ϕ_{m} pode ser obtido pela aplicando uma das cláusulas basicas da definição do |– para {ϕ_{i} | i < m}.

6.2. Modelos é as teoremas de completude e de compacidade.

Vamos escrever Γ ⟹ ϕ para nossa noção matemática informal de ϕ segue do Γ. (Por exemple muitos vezes no curso até agora temos mostrado que ZF ⟹ ϕ para ϕ uma frase sobre conjuntos.) É claro da definição do |– que se Γ|– ϕ, então Γ ⟹ ϕ. Agora vamos introduzir uma noção de “segue semânticamente.”

Definição. Seja L uma língua da ordem primeira como no §6.1. M é uma estrutura para L se M = (M, f^{M}, g^{M}, …, R^{M}, S^{M}, …) onde M é um conjunto, f^{M}, g^{M},… são funções tal que f^{M} : ^{n}M ⟶ M se f é n-ário, e R^{M}, S^{M},… são relações sobre M com R^{M} ⊆ ^{n}M se R é n-ário.

Agora vamos definir quando uma estrutura pensa que uma frase é verdadeira.

Definição. Seja L uma língua da ordem primeira e M é uma estrutura para L. Seja ϕ uma frase no L. Definamos ϕ é verdadeiro no M, escrevendo M ⊧ ϕ pela recursão sobre a forma do ϕ.

M ⊧ R(a_{0}, …, a_{n−1}) se e só se (a_{0}, …, a_{n−1}) ∈ ^{n}M;
M ⊧ ϕ & ψ  se e só se M ⊧ ϕ e M ⊧ ψ;
M ⊧ ϕ ou ψ  se e só se M ⊧ ϕ ou M ⊧ ψ;
M ⊧ ¬ϕ  se e só se M |̸= ϕ;
M ⊧ ϕ ⟶ ψ  se e só se M |̸= ϕ ou M ⊧ ψ;
M ⊧ ∃x ϕ(x)  se e só se existe a ∈ M e M ⊧ ϕ(a);
M ⊧ ∀x ϕ(x)  se e só se para cada a ∈ M temos que M ⊧ ϕ(a).

Nota. Sejam L uma língua da ordem primeira e M é uma estrutura para L. Então M |̸=⊥ pela definição do ⊧.

Por exemplo, se L = {e, ., ^{−1} }, a língua da teoria dos grupos, e M ⊧ (∀x x.x^{−1} = e = x^{−1}.x) & (∀x x.e = x = e.x) & (∀x∀y ∀z (x.y).z = x.(y.x)) (logo M é um grupo), então pode ser ou não que M ⊧ ∀x∀y x.y = y.x, mas certamente M |̸= ∃x x.x^{−1} ≠ e.

Definição. Γ ⊧ ϕ se para todos estruturas M para a língua L temos que se M ⊧ ψ para cada ψ ∈ Γ, então M ⊧ ϕ.

Definição. M é um modelo de um conjunto de frases Γ para uma língua L se M é uma estrutura para L e M ⊧ ϕ para cada ϕ ∈ Γ. Escrevemos M ⊧ Γ.

É claro pela definição do ⊧ que se Γ ⟹ ϕ então Γ ⊧ ϕ. Logo temos o seguinte.

Proposição. (Teorema de saúde (“soundness” no inglês).) Se Γ|– ϕ, então Γ ⊧ ϕ.

Corolário. Se Γ, um conjunto das frases, tem um modelo, então Γ é consistente.

Demonstração. Se Γ não é consistente, então Γ|– ⊥, logo Γ ⊧⊥. Mas não existe estruturas M qualquer tal que M ⊧⊥, pelo definição de ⊧, então não existe qualquer estrutura M tal que M ⊧ Γ.

Mas também temos o inverso para a proposição.

Teorema de completude. Se Γ ⊧ ϕ, então Γ|– ϕ.

Isso é mais profundo, porque fala que tem uma tradução dum procedimento infinito (confirmindo que cada modelo do Γ, cada um do qual pode ser infinito, é um modelo do ϕ também) para um procedimento finito (uma derivação do ϕ de Γ). Para demonstrar a teorema é conveniente introduzir um par das definições.

Definição. Uma coleção das frases Δ numa língua L é uma teoria de tipo Henkin se sempre que ∃xϕ(x) ∈ Δ, existe um constante c ∈ L tal que Δ|– ∃xϕ(x) ⟶ ϕ(c). Então c é uma testemunha para a frase ∃xϕ(x).

Observação. Se Δ, numa língua L, é uma teoria de tipo Henkin, e Δ′ é uma coleção de frases na mesma língua L, Δ ⊆ Δ′, então Δ′ é uma teoria do tipo Henkin.

Definição. Se Δ é uma coleção das frases numa língua L e Δ ⊆ Δ′, uma coleção das frases numa lingua L′ com L ⊆ L′, falamos que Δ′ é uma extensão conservadora de Δ se Δ|– ϕ se e só se Δ′|– ϕ para cada ϕ ∈ L. (E então Δ′ é consistente se Δ é consistente, porque ⊥∈ L e, logo, Δ′|– ⊥ se e só se Δ|– ⊥.)

Proposição. Se Δ é uma coleção das frases numa língua L, existe uma coleção das frases Δ′ numa lingua L′ tal que L ⊆ L′, Δ ⊆ Δ′, Δ′ é uma teoria do tipo Henkin e com Δ′ uma extensão conservadora de Δ (e com L′ = L + ω também).

Demonstração. Seja Γ qualquer coleção das frases numa língua K. Juntar constantes distintos c_{ϕ} para K para cada fórmula ϕ(x) com variável livre x no K para chegar no K^{∗} = K ∪ {c_{ϕ} | ϕ(x) ∈ L}. Seja Γ^{∗} = Γ∪{∃xϕ(x) ⟶ ϕ(c_{ϕ}) | Γ|– ∃xϕ(x)}. Vamos mostrar que Γ^{∗} é uma extensão conservadora de Γ.

Suponhmos que Γ^{∗}|– ψ para ψ ∈ K. Então existe n < ω e fórmulas ϕ_{i} para i < n tal que Γ ∪ {∃xϕ_{i}(x) ⟶ ϕ_{i}(c_{ϕ_{i}}) | i < n}|– ψ. Seja Γ^{m} = Γ ∪ {∃xϕ_{i}(x) ⟶ ϕ_{i}(c_{ϕ_{i}}) | i < m} para cada m ≤ n. Mostraramos que se Γ^{m+1}|– ψ temos que Γ^{m}|– ψ, para qualquer m < n, e,logo, pela indução, que Γ = Γ^{0}|– ψ. Se n = 0 não tem nada fazer. Então suponhamos que n ≠ 0 e seja m < n.

Se Γ^{m+1} = Γ^{m} ∪ {∃xϕ_{m}(x) ⟶ ϕ_{m}(c_{ϕ_{m}})}|– ψ, temos que Γ^{m}|– (∃xϕ_{m}(x) ⟶ ϕ_{m}(c_{ϕ_{m}})) ⟶ ψ. Então, temos que Γ^{m}|– ∃y(∃xϕ_{m}(x) ⟶ ϕ_{m}(y)) ⟶ ψ pela definição de |– , especificamente a regra para introdução dos quantificadores existenciais, porque c_{ϕ_{m}} ∉ K e, logo, não aparece nos fórmulas ϕ e ψ. Logo Γ^{m}|– (∃xϕ_{m}(x) ⟶ ∃y ϕ_{m}(y)) ⟶ ψ, e então Γ^{m}|– ψ.

Agora sejam Δ_{0} = Δ e L_{0} = L, sejam Δ_{i+1} = Δ_{i}^{∗}, L_{i+1} = L_{i}^{∗} para cada i < ω, e sejam Δ′ = ⋃{Δ_{i} | i < ω } e L′ = ⋃{L_{i} | i < ω }. Temos que Δ′ é uma extensão conservadora de Δ. E Δ′ é uma teoria de tipo Henkin porque se ∃xϕ(x) ∈ Δ temos que ∃xϕ(x) ∈ Δ_{i} para alguma i < ω e então (∃xϕ(x) ⟶ ϕ(c_{ϕ})) ∈ Δ_{i+1} ⊆ Δ.

Demonstração de teorema de completude. Seja Γ uma coleção das frases numa língua L, e ϕ um fórmula na língua L. Para demonstrar a teorema mostramos que se Γ |̸– ϕ tem um modelo de Γ ∪ {¬ϕ} (e então Γ |̸= ϕ).

Pela proposição, seja Γ′ uma teoria do tipo Henkin tal que Γ ∪ {¬ϕ} ⊆ Γ′ numa língua L′ com L ⊆ L′ e L′ = L + ω. Considerar o conjunto das coleções das frases Δ tal que Δ é na língua L′, Δ é consistente, e Γ′ ⊆ Δ, ordenado pelo Δ ≤ Δ^{∗} se Δ ⊆ Δ^{∗}. Cada cadeia na ordem tem um limite superior, então podemos usar a Lema de Zorn para escolhar uma teoria Γ_{max} que é maximal tal que Γ_{max} é na língua L′, Γ_{max} é consistente, e Γ′ ⊆ Γ_{max}. Nota que Γ_{max} é do tipo Henkin (pela observação). Também, se Γ_{max}|– ψ, temos que ψ ∈ Γ_{max} pela maximalidade de Γ_{max}; se ∃xψ(x) ∈ Γ_{max}, então temos um constante c ∈ L tal que ψ(c) ∈ Γ_{max}; se ψ ou χ ∈ Γ_{max} temos que ψ ∈ Γ_{max} ou χ ∈ Γ_{max}; e ¬ψ ∈ Γ_{max} se e só se ψ ∉ Γ_{max}.

Agora vamos usar os termos se mesmos na língua L′ como os elementos dum modelo para Γ_{max}. Deveria ficar certa cá que entende como estamos usando termos, coisas síntacticas, como objetos para formar uma estrutura semântica. Seja A = {t ∈ L′ | t é um termo no L′ }. Se f é um símbolo para uma função n-ária no L′, seja f^{A} : ^{n}A ⟶ A definido pelo f^{A}(t_{0}, …, t_{n−1}) = f(t_{0}, …, t_{n−1}), um termo também. E se R é um símbolo para uma relação n-ária no L′, define um subconjunto R^{A} do ^{n}A pelo (t_{0}, …, t_{n−1}) ∈ R^{A} se e só se (t_{0}, …, t_{n−1}) ∈ R.

Estamos perto ao fim da demonstração mas poderia ser que temos termos s, t tal que ‘s = t’ ∈ Γ_{max}, então temos que pegar o quociente de A sob este relação para chegar numa estructura para L′. Logo seja s ∼ t se ‘s = t’ ∈ Γ_{max} para s, t ∈ A, e seja [s] = {t ∈ A | t ∼ s} para s ∈ A. Formamos uma estrutura M pelo tomando M = {[s] | s ∈ A}, f^{M}([t_{0}], …, [t_{n−1}]) = [f(t_{0}, …, t_{n−1})] se f é um símbolo para uma função n-ária no L′, e ([t_{0}], …, [t_{n−1}]) ∈ R^{M} se e só se (t_{0}, …, t_{n−1}) ∈ R^{A} onde R é um símbolo para uma relação n-ária no L′. Temos que M = (M, f^{M}, …, R^{M}, …) é uma estructura para L′, e M ⊧ ψ se e só se ψ ∈ Γ_{max} para ψ ∈ L′ pela indução sobre a estrutura das frases, usando as observações que seguem da maximalidade de Γ_{max} na ultima frase do paragráfo primeiro desta demonstração. Logo N = (M, f^{M}, …, R^{M}, … | f ∈ L) é uma estructura para L e N ⊧ Γ ∪ {¬ϕ}.

Corolário. (Existência de modelos). Se Γ, um conjunto das frases, é consistente, então Γ tem um modelo. Além disso, se Γ é numa língua L e L = κ, então Γ tem um modelo N com N = ω + κ.

Demonstração. Se Γ não tem um modelo, então temos que M ⊧ Γ implica M ⊧ ϕ para qualquer ϕ. Logo Γ ⊧ ϕ para qualquer ϕ, logo Γ ⊧⊥. Então Γ|– ⊥ pela teorema.

Além disso, na demonstração da teorema chegamos num modelo N do Γ do qual os elementos são classes de equivalência dos termos da língua L′. Então N ≤ L′^{<ω} = L′ = L + ω = κ + ω.

Corolário. (Compacidade). Se Γ é um conjunto das frases e cada subconjunto finito Δ ⊆ Γ tem um modelo, então Γ tem um modelo também.

Demonstração. Se Γ não tem um modelo, então temos que Γ|– ⊥ pelo corolário sobre a existência de modelos. Mas se Γ|– ϕ temos que existe um Δ ⊆ Γ finito tal que Δ|– ϕ, para qualquer ϕ, porque demonstrações são finitárias. Então existe alguma Δ ⊆ Γ finito tal que Δ|– ⊥. Logo Δ não tem um modelo, uma contradição para o hipótese!

Exemplo. Seja L = {0, +, ., s, <, exp, =} uma língua da ordem primeira onde exp é binaría, seja N = (ω, 0^{N}, +^{N}, .^{N}, s^{N}, <^{N}, exp^{N}, =^{N}) onde exp(x, y) = x^{y}, e seja Γ o conjunto das frases que são verdadeiras sobre aritmética, i.e., para N (ou poderia tomar Γ ser os axiomas para a aritmética de Peano). Juntar um constante novo c para L, chegando no L′ = L ∪ {c}, e considerar Γ′ = Γ∪{s(s(… (s(0)))) < c | n < ω &s(s(… (s(0)))) é s aplicado n vezes para 0}. As frases novas no Γ′ \ Γ falam que n < c para cada n < ω porque n = 0 + 1 + 1 + … + 1 n vezes.

Afirmo que Γ′ tem um modelo. Demonstração: se Δ ⊆ Γ′ é finito temos que Δ \ Γ é finito, então existe alguma m_{Δ} < ω tal que para cada frase da forma n < c (i.e. da forma s(s(… (s(0)))) < c com n aplicacões do s, formalmente) tal que n < c ∈ Δ temos que n ≤ m_{Δ}. Logo Δ tem um modelo N = (ω, 0^{N}, +^{N}, .^{N}, s^{N}, <^{N}, exp^{N}, =^{N}, c_{Δ}^{N}), onde c_{Δ}^{N} é qualquer número natural maior que m_{Δ}. Logo Γ′ tem um modelo pelo teorema de compactidade, e o modelo é um modelo para aritmética que é não-normal porque tem números naturais infinitos, então o modelo não é N.

Exemplo. (Analyse “não-padrão”.) Nos origems de calcúlo, que pode argumentar razoávelmente foi o início de todo matemática moderna, Newton e Liebniz e os seguidaores deles falavam e racionaciavam sobre quantidades infinitamentes pequenhos e infinitamentes grandes para chegar nos resultados deles. No sieclo 19^{o} ninguem conseguiu no fornecendo uma formalização satisfatória destas raciocinações, e com tempo caiem do favor, sendo reposto para o método do ϵ-δ de Kronecker como sendo “mais seguro.” Agora, pela teorema de compacidade podemos recobrir a possibilidade de usar estas intuições originais de Newton e Liebniz.

Seja L = {+, −, ., <, 0, 1} e seja T o conjunto das frases verdadeiras sobre os reis com a estrutura esperada, (R, +^{R}, −^{R}, .^{R}, <^{R}, 0^{R}, 1^{R}), nesta língua. Seja L′ = L∪{c}, onde c é um símbolo novo para um constante, e seja Γ = T ∪{O < c < y & y.(1+1 …+1) | 1+1+…+1 é a suma de 1 n vezes & n < ω }. Como no exemplo prévio Γ tem um modelo, vamos falar R^{∗}, em qual existe um c tal que 0 < c e c < 1/n para cada número natural n, isso é tal que c é infintessimal. Nota que porque ∀x ∃yx.y = 1 ∈ T temos elementos infinitos do R^{∗} também.

Corolário. (Extensão por definicões.) Suponhamos que L é uma língua, Γ um conjunto das frases para L. (i) Se ϕ(x̄) é um fórmula, sejam L′ = L ∪ {R_{ϕ} } e Γ′ = Γ ∪ {∀x̄ (ϕ(x̄) ⟷ R_{ϕ}(x̄))}. Então para cada ψ ∈ L temos que Γ′ ⊧ ψ se e só se Γ ⊧ ψ. (ii) Se ϕ(x̄, y) é um fórmula e Γ|– ∀x̄ ∃!y ϕ(x̄, y), sejam L′ = L ∪ {f_{ϕ} } e Γ′ = Γ ∪ {∀x̄ ∀y (ϕ(x̄, y) ⟷ f_{ϕ}(x̄) = y)}. Então para cada ψ ∈ L temos que Γ′ ⊧ ψ se e só se Γ ⊧ ψ.

Demonstração. “⟸” é trivial em cada caso. “⟹”: Seja M um modelo para Γ. É trivial expandir M para uma estrutura M′ para L′ que é um modelo, no caso (i), para Γ′ pelo interpretando R_{ϕ} ser o que ϕ escolha no M, i.e., pelo tomando R_{ϕ}^{M′} = {ā ∈ M | M ⊧ ϕ(ā)}, e, similarmente, no caso (ii) pelo tomando f_{ϕ}^{M′}(ā) = o único b tal que M ⊧ ϕ(ā, b). Agora, se temos ψ ∈ L e Γ′ ⊧ ψ então temos que M′ ⊧ ψ (pela teorema de saúde), logo M ⊧ ψ, logo Γ ⊧ ψ (pela teorema de completude).

Nota. Pelo corolário temos que podemos fazer uma seqüência finita das extensões duma língua por definicões.

6.3. Modelos de fragmentos da teoria dos conjuntos.

Nesta seção veremos que tem modelos de vários fragmentos de ZF. Isso é, que podemos mostrar dos axiomas de ZF que existem modelos destes fragmentos. Na verdade os modelos dos fragmentos que consideramos são razoávelmente fácil definir.

ZF\{Infinidade} (= ZF-I). (V_{ω}, ∈) ⊧ ZF - I. Pode ver isso fácilmente, confirmando os axiomas um por um. (E é claro que (V_{ω}, ∈) |̸= Infinidade.) Logo ZF|– Con(ZF-I).

ZF\{Reposição ou coleção} (= Z). Pode mostrar fácilmente, confirmando os axiomas um por um, que para cada ordinal λ do tipo limite tal que ω < λ temos (V_{λ}, ∈) ⊧ Z. No outro lado, como vimos na §1.7, (V_{ω+ω}, ∈) |̸= “Coleção ” porque, por exemplo, {ω + n | n ∈ ω } é a imagem duma Função sobre o conjunto ω, mas não é um membro do V_{ω+ω}. (Ou porque tem mais que ω + ω bem-ordems que são membros do V_{ω+ω}, então V_{ω+ω} |̸= Φ se Φ é a teorema que fala que cada bem-ordem é isomorfico para um ordinal numa moda que preserva a ordem.) (Logo ZF|– Con(Z).)

ZF\{Conjuntos de potência} (= ZF-P). Se κ é um cardinal regular seja H_{κ} = {x | FT(x) < κ}. De novo, pode confimar que H_{κ} ⊧ ZF-P. Nota que H_{ω_{1}} |̸= “Conjuntos de potência” porque, por exemplo, V_{ω+1} = P(V_{ω}) ∉ H_{ω_{1}} (equivalentemente, V_{ω+2} ⊈ H_{ω_{1}}). (Logo ZF|– Con(ZF-P).)

Pode perguntar se tem modelos de outros fragmentos de ZF. Já vimos nos exercícios 11, 13 e 14 do capítulo 1 várias dependencias entre axiomas, e este reduze o número das perguntas interessantes. Todavia, ainda podemos perguntar se existem modelos de ZF\{Fundação}, e mesmo se existem modelos de todo de ZF. Embora na proxima seção mostraramos que não podemos demonstrar que existem tais modelos como uma conseqüência da teorema de incompletude.

6.4. Teorema de incompletude.

A teorema de incompletude, tanto quanto a teorema de completude, é uma teorema geral sobre coleções de frases numa língua da ordem primeira. Aplica para uma variedade ampla de coleções de frases (ou teorias) e não tem nada a ver especificamente com a teoria dos conjuntos (além de, com certeza, ZF sendo um destas coleções. outros).

Teorema de incompletude. (Gödel, 1931) Se T é uma teoria razoável (numa língua L), então T |̸– Con(T).

Nota lingüística. O nome da teorema de incompletude vem do fato que mostra que T é uma teoria incompleto, isso é que não tem a propreidade que ou demonstra ϕ ou demonstra ¬ϕ para todas frases ϕ no L. Na contramão, a teorema de completude tem tal nome porque mostra que dedução na l’ogica da primeira ordem é completo no sentido que se ϕ é verdadeiro no cada modelo do T, então tem um derivação de ϕ do T na lógica da primeira ordem. Então, apesar de soar um pouco estranho talvez, não tem problemas nenhums falar, por exemplo, que a teorema de completude e a teorema de incompletude são verdadeiras para uma teoria T.

Razoável aqui quer dizer que: (a) podemos exprimir Con(T) no L, (b) T é consistente, (c) podemos fazer bastante combinatoria no T para codificar as manipulações de lógica dentro de T e decodificâlos, e (d) T é recursivo – devo explicar que este quer dizer.

Precisamos de (a) porque T só pode demonstra frases no L, logo sem (a) a conclusão da teorema seria incomprehensível. Também precisamos de (b) para esperar mostrar a teorema porque se T não é consistente temos que T |– ⊥, e, então T demonstra qualquer frase. Especificamente, T |– Con(T). Explicamos (c) e (d) mais completamente abaixo, mas esta formulação vaga de (c) jd́á uma pista para como exprimir Con(T) no L.

Exemplos de teorias ‘razoáveis.’ Se são consistentes, a coleção de todos os verdadeiros sobre (N, +, ., s, exp, 0, 1) e a aritmetica de Peano são razoáveis. Se são consistentes, ZF e ZF-I-P-Fundação são razoáveis. Muitas teorias de analyse onde tem a função de sine, e então pode definir os números naturais, são razoável se é consistente.

Explicação de (c) na definição de razoável. Se T é razoável podemos mostrar de T que podemos achar representações de várias coisas síntaticais sobre L e T pelo termos no L: os símbolos do L, os termos no L, os fórmulas no L e as demonstrações do T no L. Se a é um pedaço da sintaxe escrevemos #(a) para o termo que representa a. As vezes chamamos estes termos códigos.

Também, podemos achar um fórmula Dem(x, y) e uma função definivel Subst(x, y) no L tal que d é uma demonstração de ϕ do T se e só se T |– Dem(#(d), #(ϕ)), e ϕ[a/x] = ψ se e só se T |– Subst(#(ϕ), a) = #(ψ).

Primeiro suponhamos que T é razoável neste sentido, e mostramos como demonstrar a teorema. Depois veremos como fazer a codificação para algumas teorias especificas.

Demonstração da teorema de incompletude. Observe que se ϕ(x) é um fórmula temos que T |– “Subst(#(ϕ), #(ϕ)) = #(ψ)” se ψ = ϕ[#(ϕ)/x], isto é, se ψ é o fórmula que ganhamos se substituimos o termo que representa ϕ se mesmo em vez do variável livre x do ϕ. Considere o fórmula ¬∃y Dem(y, Subst(z, z)), = χ(z), vamos falar. Então, para qualquer fórmula ϕ, temos que T |– χ(#(ϕ)) se e só se não existe um demonstração de ϕ(#(ϕ) do T. Logo, porque χ se mesmo é um fórmula, temos que T |– χ(#(χ)) se e só se não existe um demonstração de χ(#(χ) do T.

Mas agora se T |– χ(#(χ)) temos que d demonstra χ(#(χ)) para alguma demonstração d, e então T |– Dem(#(d), #(χ(#(χ))). Logo T |– ∃yDem(y, #(χ(#(χ))). Logo T |– ¬(χ(#(χ))). Então T é inconsistente.

E se T |– ¬(χ(#(χ))) temos que T |– ∃yDem(y, #(χ(#(χ))). Assumindo que T é consistente existe uma demonstração d tal que T |– Dem(#(d), #(χ(#(χ))). Logo T |– χ(#(χ)) e temos que T é inconsistente de novo.

Se escrevemos Con(T) para ¬∃y Dem(#(y), #(z ≠ z)) e se formalizamos a argumentação dentro do T temos que T |– Con(T) ⟶ (χ(#(χ)). Logo T |– Con(T) implica T |– (χ(#(χ)), e então T não é consistente. (Fim da demonstração da teorema.)

T deve ser recursivo porque precisamos ter que “d é uma demonstração de ϕ de T ” e “ϕ[a/x] = ψ” são recursivos, e então temos que existem fórmulas no L que definem Dem e Subst, e porque para fazer a formalização também precisamos saber que para asserções sobre demonstrações e substituções podemos usar os fórmulas no L para escrever frases equivalentes no L.

Codificação.

Ainda ser feitos sobre minha explicação da teorema de incompletude:

• Falar exactamente qual manipulações precisamos ter o poder fazer no (c).

• Explicar como fazer a formalização de argumentação dentro do T (em cima so falo que “pode”).

• Explicar porque faço tudo essa codificação recursivamente/Explicar mas exactamente porque precisamos que T é recursivo.

• Dar referências. (G.Takeuti, Proof Theory, North Holland, 1969, pp. 73-81.)

Seja L = {f^{i} | i < ω } ∪ {R^{i} | i < ω } ∪ {=}. Porque fórmulas são fios finitos dos símbolos e demonstrações são arvores finitos dos fórmulas precisaramos que T dá para nós o poder manipular fios de codigos para símbolos e codigos para fios dos símbolos. Então uma parte da definição de “razoável” é que podemos definir funções f_{n} para cada n < ω e π_{m}^{n} para cada m < n < ω no L tal que podmemos mostrar do T que π_{m}^{n}(f_{n}(x_{0}, …, x_{n−1})) = x_{m}. Então f_{n} funciona como se ele permite nós fazer “n-tuplos” e π_{m}^{n} funciona como se ele permite nós recobrir o m^{o} elemente dum “n-tuplo” para cada n < ω e m < n. Para evitar confusão é bom pedir que rge(f_{n}) ∩ rge(f_{m}) = ∅ se m ≠ n. Preciso disso nesta presentação ou não?

Definimos #(t), #(ϕ) para termos t e fórmulas ϕ ∈ L pela indução na estrutura do t, ϕ.

Então sejam ⟨t_{i} | i < ω ⟩ termos na língua L. Sejam #(&) = t_{1}, #(¬) = t_{3}, #(∃) = t_{5}, #(() = t_{7}, #()) = t_{9}, #(,) = t_{11} #(=) = t_{13}, #(v_{i}) = t_{2i}, #(f^{i}) = t_{4i+15}, e #(R^{i}) = t_{4i+17} para i < ω.

Já vimos que #(v_{i}) = t_{2i}. Se i < ω, f^{i} é um símbolo para uma função k-ária e s_{0},…, s_{k−1} são termos no L, temos que #(f^{i}(v_{j_{0}}, …, v_{j_{k−1}})) = f_{k+3}(t_{4i+15}, t_{7}, #(s_{2j_{0}}), …, #(s_{2j_{k−1}}), t_{9}).

Se i < ω, R^{i} é um símbolo para uma relção k-ária e s_{0}, …, s_{k−1} são termos no L temos que #(R^{i}(v_{j_{0}}, …, v_{j_{k−1}})) = f_{k+3}(t_{4i+17}, t_{7}, #(s_{2j_{0}}), …, #(s_{2j_{k−1}}), t_{9}). Se ϕ é um fórmula temos que #(¬ϕ) = f_{4}(t_{3}, t_{7}, #(ϕ), t_{9}). Se ϕ e ψ são fórmulas temos que #(ϕ & ψ) = f_{3}(#(ϕ), t_{1}, #(ψ)). E se ϕ(x) é um fórmula com x um variável livre, temos que #(∃xϕ(x)) = f_{2}(t_{5}, #(ϕ(x))).

Então para um fórmula ϕ ∈ L temos #(ϕ) é um termo de L. Se d é uma demonstração de ϕ do T, então d é um arvore finito, então um fio dos fios, então podemos definir #(d), um termo no L também. Hmmm. Nunca expliquei que são arvores (finitos), nem dei as ilustrações para derivação para mostrar que demonstrações são arvores.

Exemplos. No ZF(−I−P−Fnd) podemos simplesmente usar f_{n}(x_{0}, …, x_{n−1}) = (x_{0}, …, x_{n−1}) e t_{i} = i para i < ω, porque se x_{0},…, x_{n−1} ∈ V_{ω} temos que (x_{0}, …, x_{n−1}) ∈ V_{ω} também.

No aritmética de Peano temos que fazer um pouco mais. f_{n}(x_{0}, …, x_{n−1}) = . . .. Deveria acabar com este parte da demonstração.

6.5. Aplições da teorema de incompletude para ZF.

Teorema. Se ZF é consistente não podemos demonstrar, apenas do ZF, que existe um modelo de ZF.

Demonstração. É fácil ver que ZF é “razoável” porque podemos fazer as manipulações dos fios finitos no ZF e os axiomas do ZF são um conjunto recursivo. Então a teorema é imediata da teorema de incompletude. (Hmmm. Deveria explicar como os axiomas são um conjunto e, então podem ser recursivos ou não.)

Teorema. ZF|– Con(ZF−{Fundação}) ⟶ Con(ZF).

Demonstração. Seja U um modelo de ZF−{Fundação}. Podemos construir a hierarquia dos V_{α}s sem usando fundação – lembrar que vimos depois a construção da hierarquia dos V_{α}s na §2.7 que o axioma de fundação é equivalente para falar que ∀x ∃α ∈ On x ∈ V_{α}. Então, construir a hierarquia dentro do U e seja V o resultado. Usando o fato, que pode confirmir simplesmente pela indução na estrutura de fórmulas, que se x ∈ V e ϕ(y) é um fórmula, então x∩{y | ϕ(y)}∩V = x∩{y | ϕ^{V} (y)}∩U, onde ϕ^{V} (y) é ϕ com todos os quantificadores correndo sobre V, podemos confirmar que V ⊧ ZF. Então Con(ZF−{Fundação}) implica Con(ZF). Logo ZF|– Con(ZF−{Fundação}) ⟶ Con(ZF).

Corolário. Não podemos mostrar do ZF que existe um modelo do ZF−{Fundação}.

Demonstração. Imediato da teorema e da teorema de incompletude.

6.6. Construtabilidade e forçando. Agora podemos explicar mais exatamente o que quer dizer as observações no fim de §4.3, por exemplo, que não pode mostrar do ZF que AE é verdadeiro nem que não é verdadeiro.

Teorema. (Gödel, 1938) Con(ZF) ⟹ Con(ZF + AE + HCG).

Teorema. (Cohen, 1963) Con(ZF) ⟹ Con(ZF + ¬AE), e Con(ZF) ⟹ Con(ZF + AE + 2^{ℵ_{0}} = ℵ_{α+1}) para qualquer ordinal α.

Mas exprimindo coisas neste modo, como sobre consistência, talvez não dá uma impressão certa do material da teoria dos conjuntos em geral e destas teoremas especificamente. É melhor entender estas teoremas no mesmo modo que as demonstrações delas: como falandas que se temos um modelo em qual tal e tal coisas são verdadeiras, então podemos mudar para um outro modelo onde tal e tal outras coisas são verdadeiras. Isso é um exemplo de uma tema central na teoria dos conjuntos, porque a teoria se interesse, após das coisas inicias nos capítulos 1-4, nas relações entre modelos da teoria (do ZF) e nas coisas quem acontecem dentro coleções especificos dos modelos do ZF. (Embora, claro, inclusive se interesse nas propriedades de modelos especificos (coleções do tamanho um) e da coleção de todos modelos (as conseqüências síntaticas do ZF, pela a teorema do completude).) Este não deveria ser uma surpresa grande: a teoria dos grupos se interesse nas relacões entre grupos também com propriedades de coleções dos grupos, e a teoria dos espaços topologicos se interesse nas relações entre espaços também com propriedades de (coleções dos) espaços. Só tem que lembrar que nestes exemplos últimos os modelos das teorias são grupos e espaços respectivamente, enquanto no caso da teoria dos conjuntos os modelos não são chamados ‘conjuntos’ mas ‘modelos da teoria dos conjuntos,’ ou, como falamos na seção §1.4, ‘universos’ (modelos são universos porque se M ⊧ ZF temos que M ⊧ ∀x ∃α ∈ On^{M} x ∈ V_{α}^{M}).

Construtabilidade. A idéia inicial da demonstração da teorema de Gödel é parecida para a idéia da demonstraçao que damos no fim de §6.5 que se temos um modelo de ZF−Fundação podemos chegar num modelo de ZF. Este vez, começamos com qualquer modelo M de ZF e definimos dentro de M um modelo mas magro, L, com L ⊆ M e, neste caso, com do ZF + AE + HCG, On^{L} = On^{M}. Fazemos isso pelo definindo L como um hierarquia, como V, mas nas niveis do tipo sucessor augmentando a coleção até este nivel só com subconjuntos definíveis dele em vez de todos os subconjuntos.

Definição. Pela recursão sobre On^{M} define L_{0} = ∅, L_{λ} = ⋃{L_{α} | α < λ} para ordinais λ do tipo limite, e L_{α+1} = {x ⊆ L_{α} | ∃ϕ(y_{0}, …, y_{n−1}, z) ∈ LST tal que x = {a | ∃b_{0}, …, b_{n−1} ∈ L_{α} (L_{α}, ∈ ∩(L_{α} × L_{α})) ⊧ ϕ(b_{0}, …, b_{n−1}, a)}}. Seja L = ⋃{L_{α} | α ∈ On^{M} }.

A teorema de Gödel é, na verdade, que para qualquer M temos que L ⊧ ZF + AE + HCG. E além disso que se M, N são modelos de ZF com On^{M} ⊆ On^{N}, temos que L_{On^{M}}^{N} = L^{M}, então, especificamente, L ⊧ V = L. Mas a demonstração que o modelo L tem estas propriedades é mais súbtil. Para ver mais sobre isso veja capítulo 7.

Forçando. Para mostrar que podemos mudar dum modelo de ZF + AE + HCG para um modelo do ZF + AE em qual, por exemplo, HC fale usamos uma técnica, forçando, para expandir o modelo para chegar, neste caso, num modelo com mais subconjuntos de ω. A técnica é muito parecida para fazer uma extensão álgebraica para um campo na álgebra: fazemos um extensão formal pelo um não-conhecido, e depois tomamos um quociente. (No fato, pode mostrar que isso não é só uma analogia boa, mas tem um sentido técnico em qual forçando e fazendo extensões álgebraicas são instâncias da mesma construção categorica.)

Os livros de Kunen^{1} e Kanamor^{2} são do dois lugares ótimos para pegar mais informação sobre forçando, e sobre as proximas pasos na teoria dos conjuntos mais geralmente. Talvez um cápitulo 8 destes notas também.

6.7. Modelos de todo do ZF.

Notar que a conseqüência da teorema de incompletude no §6.5 não fala que não existem modelos de ZF, só que não pode mostrar dos axiomas de ZF sozinhos que existem modelos. Já vimos no §6.3 que V_{λ} ⊧ ZF − {Coleção} para qualquer ordinal λ do tipo limite com ω < λ e que V_{ω} ⊧ ZF − {Infinidade}. Pode confirmir pelas mesmas demonstrações juntos a seguinte.

Teorema. Se κ é um cardinal que é inacessível fortemente, temos V_{κ} ⊧ ZF.

Observação. (Paradoxo de Skolem). Se ZF é consistente pelo corolário ultimo na §6.2 ele tem um modelo, falamos M, enumerável. Logo P(ω)^{M}, ω_{1}^{M}, … são enumeráveis. Isso não é um paradoxo na verdade porque apesar de podemos contar, por exemplo, P(ω)^{M} fora do modelo e ver que este conjunto, que é um conjunto de subconjuntos do ω é enumerável, (para “pessoas”“morando”) dentro M não tem qualquer bijeção do ω para P(ω)^{M}, e, logo, dentro do M não pode enumerar P(ω).

Não obstante que, pela teorema de incompletude aplicada para a teoria ZF, não pode mostrar dos axiomas de ZF que existem cardinais que são inacessíveis fortementes, a afirmação que existem tais cardinais é uma afirmação interessante e as vezes útil sobre (modelos de) ZF. Embora que formalmente isso e suposições similares são fortelecendos do ZF, na prática – o punto o mais importante – não parece qualquer razão supor que são diferentes de, por exemplo, fortelecendo a teoria da aritmética de Peano com a suposição que esta teoria não é inconsistente. No contrário, na verdade, a exploração das suposições deste tipo forma uma parte muito produtiva da teoria dos conjuntos e, logo, da matemática. (Veja, particularmente, o livro de Kanamori.) Acabamos este capítulo com um exemplo deste fenômeno sobre exponenciação dos cardinais.

Definição. Para qualquer δ < ω_{1}, a declaração que um cardinal κ é κ+δ+1-forte é um fortelecendo de falar que κ é inacessível fortemente e que κ é compacto fracamente. (Quer dizer que existe um injeção i : V ⟶ M tal que M ⊆ V, On^{M} = On^{V}, se ϕ(x) ∈ LTC e a ∈ V temos que V ⊧ ϕ(a) se é so se M ⊧ ϕ(i(a)), i(α) = α para cada α < κ, κ < i(κ) e V_{κ+δ+1} ⊆ M. Não deveria esperar entender agora porque este definição é mais ou menos natural, nem mesmo como formulá-la como uma suposição sobre conjuntos e não sobre classes como fizemos aqui. Veja o livro do Kanamori para estes detalhes.)

A razão para introduzuir a definição aqui é que podemos usá-la para dar a declaraç certa da teorema seguinte annunciada no fim da seção §4.4 – do qual a demonstração é uma raciocinação esperto que usa forçando.

Teorema. (Gitik-Magidor, 1989) Seja ω ≤ δ < ω_{1}. Con(ZF + AE + ∃κ tal que κ é κ + δ + 1-forte) ⟹ Con(ZF + AE + 2^{ℵ_{n}} = ℵ_{n+1} para todos n < ω, e 2^{ℵ_{ω}} = ℵ_{δ+1}.)

1 Ken Kunen, Set theory: an introduction to independence proofs, North-Holland, 1980. Não é ainda impresso, mas

pode consultar uma cópia na biblioteca.

2 Aki Kanamori, The Higher Infinite, Springer, 1996.