Abrir menu principal

Lista de teorias de primeira ordem

artigo de lista da Wikimedia
Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações (desde dezembro de 2013). Ajude a melhorar este artigo inserindo fontes.

Na lógica, uma teoria de primeira ordem é um conjunto de fórmulas que fazem sentido em uma linguagem de primeira ordem. Inúmeras teorias da matemática como a teoria dos anéis, a teoria dos grupos e as teorias dos conjuntos são teorias de primeira ordem.


Índice

DefiniçõesEditar

Uma teoria de primeira ordem T tem como base uma linguagem de primeira ordem  , tal que a teoria será um conjunto específico de fórmulas bem-formadas de  , fórmulas essas chamadas de axiomas.

De acordo com a teoria dos modelos, cada objeto matemático é um modelo de uma assinatura Σ de linguagem  . Dado um conjunto de modelos de uma mesma assinatura, uma teoria é um conjunto de axiomas não-lógicos que são satisfeitos por todos esses modelos.

Seja α uma fórmula, dizemos que α é um teorema de T, denotado por T ⊢ α sse α pode ser demonstrada a partir de T. Também é dito como α é consequência lógica de T. O conjunto de tódos os teoremas de T é chamado de Th(T).

PropriedadesEditar

Uma teoria T pode ser:

  • Axiomática, se há um procedimento recursivo que caracterize seus axiomas;
  • Finitamente axiomatizada, se tem um número finito de axiomas não-lógicos;
  • Axiomatizával, se há alguma teoria axiomática T* tal que Th(T*) = Th(T);
  • Fechada, se Th(T) = T. Ou seja, se T só tem a si própria como consequência;
  • Consistente, se não é o caso de existir uma fórmula φ em qualquer linguagem, tal que φ e ¬φ sejam ambos teoremas de T.
  • Completa, se para toda fórmula α de  , ou α é um teorema de T ou ¬α o é;
  • Trivial, se toda fórmula α de   é um teorema de T;
  • Decidível, se há um algoritmo que decida se uma fórmula α de   é ou não é um teorema de T;
  • Satisfatível, se existe um modelo para todas as fórmulas da teoria. Pelo Teorema da completude de Gödel, satisfatível é equivalente a consistente;
  • Categórica, se é consistente e todos os seus modelos são finitos e isomórficos.


Apesar de ter vários modelos, uma teoria T tem o que se chama de interpretação pretendida. Por exemplo, a aritmética de Peano nos naturais. Um modelo que seja isomórfico à interpretação pretendida é chamado de modelo padrão.


GruposEditar

Seja * uma operação definida em um conjunto G. Dizemos que o par (G, *) é um grupo se e somente se:

  • O conjunto G é fechado sobre a operação *, isto é
 
  • A operação * é associativa, ou seja, ∀g, h, kG, (g * h) * k = g * (h * k);
 
  • Existe um elemento identidade eG para *, ou seja,
 
  • Para todo elemento gG existe um único elemento inverso iG, isto é,
 


Os grupos abelianos são um caso particular de grupos em que a operação * é comutativa em G, isto é,

 

Por exemplo:

  • (Z, +): os inteiros com adição;


Outros tipos de grupos são:

  • Grupos Simétricos;
  • Grupos Alternadores;
  • Grupos Diedrais;
  • Grupos Cíclicos.


GrafosEditar

Um grafo é um par G = (V,R), onde V é um conjunto finito e R é um conjunto de conjunto de pares ordenados (x,y) onde x e y são elementos de V, chamados de vértices do grafo. Os elementos de R são as arestas do grafo, e podem ser representados como R(x, y), interpretado como "há uma aresta de x até y".

Um grafo é definido pelos seguintes axiomas:

  • Simetria:
 
  • Anti-reflexividade:
 

Alguns matemáticos usam a palavra "grafo" em um sentido diferente e admitem a possibilidade de um vértice ser adjacente a si mesmo; uma aresta que une um vértice a se mesmo é chamado de laço. Também se admite mais de uma aresta com as mesmas extremidades; tais arestas são chamadas de arestas paralelas.

Para se referir a primeira definição de Grafo com mais clareza, é usada a expressão grafo simples. Para se referir a um grafo que pode ter arestas e laços múltiplos, é empregada a palavra multigrafo.

Um passeio em um grafo que atravessa cada aresta uma única vez, é chamado de trilha eureliana. Se, além disso, a trilha começa e termina no mesmo vértice o passeio é chamado um tour eureliano. Finalmente, se um grafo tem um tour eureliano , dizemos que o grafo é um grafo eureliano;


Relações de EquivalênciaEditar

Seja A um conjunto e ≡ uma relação de equivalência sobre A. Para cada aA podemos construir o conjunto de todos os elementos xA que são equivalentes ao elemento a. Indicaremos tal conjunto por [a], isto é: [a] = {xA : xa}.

As relações de equivalência satisfazem os axiomas:

  • Reflexividade;
 
  • Simetria;
 
  • Transitividade;
 

O conjunto [a] nunca é vazio, pois a propriedade reflexiva garante que a ∈ [a]. O conjunto [a] é denominado classe de equivalência, que também pode ser denotada por cl(a) ou  .


Álgebras BooleanasEditar

Seja B um conjunto com dois elementos distintos, 0 e 1, duas operações binárias, + e , uma operação unária ¬. Então, B é dito uma álgebra booleana se valem os seguintes axiomas, onde a, b e c são elementos quaisquer de B :

  • Comutatividade;
 
  • Distributividade;
 
  • Identidade;
 
  • Complemento;
 

Os operadores da álgebra booleana podem ser representados de várias formas. É freqüente serem simplesmente escritos como E, OU e NÃO, porém são mais comuns os seus equivalentes em inglês: AND, OR e NOT.

DualidadeEditar

A dual de qualquer declaração em uma álgebra booleana B é a declaração obtida pela troca das operações e + e de seus elementos identidade, 0 e 1, na declaração original.

Por exemplo, a expressão

 

é dual de

 

Observe a simetria dos axiomas em uma álgebra booleana B. Isto é, o dual do conjunto dos axiomas de B é o próprio conjunto de axiomas. Conseqüentemente, vale o princípio da dualidade em B.

O Princípio da Dualidade afirma que o dual de qualquer teorema em uma álgebra booleana também é um teorema. Ou seja, se qualquer declaração é conseqüência dos axiomas em uma álgebra booleana, então a declaração dual também é uma conseqüência dos axiomas.

OrdemEditar

Sejam A um conjunto e RA×A uma relação em A. Diz-se que R é uma relação de ordem parcial se:

  • R for reflexiva, onde aRa para todo aA. Ou seja, se todos os elementos se relacionarem com si próprios.
  • R for anti-simétrica, ou seja, R é tal que se aRb e bRa então a=b.
  • R for transitiva, onde aRb e bRc implicam que aRc.

Ex: As relações (N, ≤), (℘(A), ⊆), (R, =) são de ordem parcial.

Uma relação diz-se ordem total ou linear se for uma ordem parcial e for total, ou seja, para todo a e b em A é verdade que aRb ou bRa (ou ambos).

Ex: A relação (N, ≤) é de ordem total.


Conjunto bem-ordenadoEditar

Um conjunto é A dito bem-ordenado se todo subconjunto de A tem primeiro elemento.

Um exemplo clássico é o conjunto dos números naturais com a ordem usual ≤.

  • Um conjunto bem ordenado é linearmente ordenado. De fato, se a,bA, então {a,b} tem um primeiro elemento; logo, a e b são ordenáveis.
  • Todo subconjunto de um conjunto bem-ordenado é por si só bem-ordenado.
  • Se A é bem ordenado e B é isomorfo a A, então B é bem-ordenado.
  • Todos os conjuntos finitos linearmente ordenados com o mesmo número n de elemento são bem-ordenados, e todos são isomorfos entre si.
  • Todo elemento aA, que não é um último elemento, tem um sucessor imediato.

Anéis e corposEditar

A assinatura dos anéis tem duas constantes 0 e 1, duas funções binárias, + e ⋅, e, opcionalmente, uma função unária inversa -1.

Seja A um conjunto com as seguintes operações internas:

  e  

(A, +, ⋅) é um anel se ∀a,b,c; ∈ A se valem as propriedades:

  • Associatividade:
 
 
  • Comutatividade:
 
  • Elemento neutro de +:
 
  • Elemento inverso ou complemento de +:
 
  • Distributividade:
 
 


Se a multiplicação, ⋅, dos anéis é comutativa, temos um anel comutativo, se a multiplicação tem elemento neutro, temos um anel com identidade.

Um corpo é um anel comutativo em que todo elemento diferente de 0 possui um elemento inverso da multiplicação. Um anel comutativo com unidade e sem divisores de zero é chamado de corpo se:

 

Os corpos são importantes objetos de estudo na álgebra visto constituirem uma generalização útil de muitos sistemas numéricos, como os números racionais, os reais e os complexos.


Principais tipos de corpos:

  • Corpo finito: é um corpo em que o conjunto dos elementos é finito.
  • Corpo ordenado: é um corpo no qual existe uma relação de ordem total, e suas operações binárias são compatíveis com essa relação de ordem. Um corpo é ordenado se satisfaz as seguintes condições:
    • A soma e o produto de elementos positivos são positivos;
    • Dado aA, exatamente uma das três alternativas seguintes ocorre: ou a = 0, ou aA ou -aA.

ReferênciasEditar

SCHEINERMAN, Edward R. Matemática Discreta - Uma Introdução. São Paulo: Thomson, 2003. ISBN 8522102910.

LIPSCHUTZ, Seymour; LIPSON, Marc. Teorias e Problemas de Matemática Discreta, 2ª edição. São Paulo: Bookman, 2004. ISBN 0070380457.

Números reais(arquivo em pdf), por Gláucio Terra.

Modelos(arquivo em pdf), por Luiz Henrique de A. Dutra e Cezar A. Mortari.

Ver tambémEditar