Capítulo VI. OPERAÇÕES BINÁRIAS

Kurt Godel

Kurt Gödel nasceu em 28 de abril de 1906 , em Brünn, Áustria-Hungria (hoje Brno, na República Tcheca) e faleceu em Princeton, EUA, 14 de Janeiro de 1978 . Foi filho de um gerente de fábrica têxtil. Em família, Kurt era conhecido por Der Herr Warum (Sr. Por quê?.

Em 1923, concluiu, com louvor, o curso fundamental na escola alemã de Brünn e embora tivesse excelente talento para linguagens, ele se aprofundou em História e Matemática. Seu interesse pela Matemática aumentou em 1920 , quando acompanhou Rudolf, seu irmão mais velho, que fora para Viena cursar a Escola de Medicina da Universidade de Viena.

Durante a adolescência, estudou Goethe, o Manual de Gabelsberger , a teoria das cores de Isaac Newton e as “Críticas” de Kant.

Em lógica matemática, os Teoremas da incompletude de Gödel são resultados provados em 1930 . O primeiro teorema afirma, de forma simplificada:.

“Em qualquer formalismo matemático consistente suficientemente e robusto para definir os conceitos de números naturais (da aritmética), existirá a possibilidade de formar uma afirmação indecidível, ou seja, não pode ser provada verdadeira nem falsa”.

O segundo teorema da incompletude de Gödel, provado por formalização do próprio primeiro teorema em si, enuncia-se:.

“Nenhum sistema consistente pode ser utilizado para provar a sua própria consistência”.

O resultado foi devastador para uma abordagem filosófica à matemática conhecida como Programa de Hilbert. David Hilbert propôs que a consistência de sistemas mais complexos, como análise real, poderiam ser provados em termos de sistemas mais simples. Assim, a consistência de toda a matemática seria reduzida à aritmética básica. O segundo teorema da incompletude de Gödel mostra que a aritmética básica não pode ser usada para provar sua própria consistência, portanto não pode ser usada para provar a consistência de nada mais forte.

6.1 RELAÇÃO DE ORDEM

6.1.1 Relação de ordem parcial.

Definição 6.1 Relação de ordem parcial.

Dada uma relação R  A  A, dizemos que R é de ordem parcial se, e somente se, R é reflexiva, anti-simétrica e transitiva.

Isto é:

1. (a, a)  R,  a  A

2. (a, b)  R  (b, a)  R  a = b

3. (a, b)  R  (b, c)  R  (a, c)  R

Se R é de ordem parcial em A, dizemos que A é um “conjunto parcialmente ordenado”.

Definição 6.2 Conjunto parcialmente ordenado.

Um conjunto A e uma relação R de ordem parcial em A , constituem um conjunto parcialmente ordenado.

Se uma relação R em A define um ordem parcial em A , então (a, b)  R denotamos por a b que se lê “a anterior ao elemento b”.

Exemplo 6.1

• Seja A uma família de conjuntos, a relação definida em A por x é subconjunto de y , é de ordem parcial.

• Seja A um subconjunto de números reais, a relação em A definida por x  y , é de ordem parcial em A , é chamado de ordem natural em A .

Figura 6.1:

Exemplo 6.2

Seja A = { 1, 2, 3, 4, 5 } . O diagrama da Figura (6.1) define um ordem parcial em A do seguinte modo: x y se, x = y ou se podemos ir de x até y no diagrama na direção ascendente indicada. Observe que 2 1, 4 1 e 5 3 .

Exemplo 6.3

Seja R a relação definida em os números naturais N por “x é múltiplo de y”, então R é um ordem parcial em N e temos 6 2, 15 3 e 17 17.

Observação 6.1

Para os conceitos de parcialmente ordenado se utilizam as seguintes notações:

• a b significa a b e a  b ; se lê “a estritamente anterior a b”.

• b a significa a b ; se lê “b supera a a”.

• b a significa a b ; se lê “b estritamente superior a a”

Definição 6.3 Elementos não comparáveis.

Dois elementos a e b de um conjunto parcialmente ordenado se dizem não comparáveis, se a b e b a

Isto é, se nenhum de eles precede ao outro. No Exemplo (6.3) os números 4 e 5 não são comparáveis.

Observação 6.2

Se uma relação R em um conjunto A é reflexiva, anti-simétrica e transitiva, então a relação recíproca R* é também reflexiva, anti-simétrica e transitiva.

Isto é, se R define um ordem parcial em A , então R* também define um ordem parcial em A , e se chama a ordem inversa.

Para resultados mais profundos a respeito de conjuntos parcialmente ordenados precisamos de uma nova ferramenta da teoria de conjuntos.

Observe que se {Ai} é uma família finita de conjuntos, para i  N, digamos então que uma condição necessária e suficiente para que seu produto cartesiano seja nulo é que pelo menos um dos Ai = . Isto mostra-se por indução sobre N.

A generalização para família infinitas da afirmação do parágrafo precedente é o seguinte axioma da teoria de conjuntos.

Axioma 6.1 Axioma de escolha (6º. axioma de Zermelo)

O produto cartesiano de uma família não vazia de conjuntos não vazios é não-vazio.

Em outras palavras, se {Bi} i é uma família finita de conjuntos não-vazios indexado por um conjunto  não-vazio, então existe uma família {bi}i tal que bi  Bi para cada i  .

6.1.2 Relação de ordem total.

Definição 6.4

Dada uma relação R  A  A , dizemos que R é de ordem total se, e somente se:

1. R é de ordem parcial.

2. (x, y)  R  (y, x)  R,  (x, y)  A  A .

Se R é uma relação de ordem total em A, dizemos que A é um conjunto totalmente ordenado por R. A palavra parcial utilizamos para definir ordem parcial em um conjunto A , isto pelo fato de alguns dos elementos de A não serem comparáveis. Por outro lado, se cada par de elementos de um conjunto parcialmente ordenado A são comparáveis, então dizemos que A é de ordem total.

Definição 6.5 Conjunto totalmente ordenado.

Um conjunto A parcialmente ordenado, com a propriedade adicional de a b, a = b ou a b para quaisquer dos elementos a, b  A , constituem um conjunto totalmente ordenado.

Exemplo 6.4

• A ordem parcial em qualquer conjunto A de números reais (com a ordem natural), é uma ordem total, isto do fato de dois números quaisquer serem comparáveis.

• Seja R a ordem parcial em A = { 1, 2, 3, 4, 5, 6 } definido por `` x divide a y ''. Então R não é uma ordem total em A , isto do fato 3 e 5 não serem comparáveis.

Exemplo 6.5

Consideremos o conjunto P(S) , e a relação R = {(A, B)  P(S)  P(S) /. A  B} não é de ordem total, isto pelo fato, que não satisfaz a propriedade simétrica, dado o par (A, B)  P(S)  P(S) pode acontecer A B  B A

Exemplo 6.6

Mostre que o conjunto T = { (a, b)  R2 /. a  b} é uma relação de ordem total no conjunto de números reais R.

Demonstração.

Com efeito, a  a,  a  r , logo (a, a)  T , a  R.

Se a  b  b  a  a = b , logo (a, b)  T  (b, a)  T  a = b .

Se a  b  b  c  a  c , logo (a, b)  T  (b, c)  T  (a, c)  T.

É verdade que a  b  b  a  (a, b)  R2 isto é, (a, b)  T  (b, c)  T,  (a, b)  R2 .

Portanto, T é uma relação de ordem total.