Lista de teorias de primeira ordem

Predefinição:Sem-notas 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.

Definições

Uma teoria de primeira ordem T tem como base uma linguagem de primeira ordem Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}_T} , tal que a teoria será um conjunto específico de fórmulas bem-formadas de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}_T} , fórmulas essas chamadas de axiomas.

De acordo com a teoria dos modelos, cada objeto matemático é um modelo de uma assinatura Σ de linguagem Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}_\Sigma} . 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).

Propriedades

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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}_\Sigma} , ou α é um teorema de T ou ¬α o é;
• Trivial, se toda fórmula α de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}_\Sigma} é um teorema de T;
• Decidível, se há um algoritmo que decida se uma fórmula α de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}_\Sigma} é 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.

Grupos

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 é

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall g, h \in G),\; (g * h) \in G}

• A operação * é associativa, ou seja, ∀g, h, k ∈ G, (g * h) * k = g * (h * k);

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall g, h, k \in G),\; (g * h) * k = g * (h * k)}

• Existe um elemento identidade e ∈ G para *, ou seja,

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall g \in G),\; (g * e) = (e * g) = g}

• Para todo elemento g ∈ G existe um único elemento inverso i ∈ G, isto é,

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall g \in G),\; (g * i) = (i * g) = e}

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

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall g, h \in G),\; (g * h) = (h * g)}

Por exemplo:

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

• ({0,1}, Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \oplus} ) : os valores binários com a operaçãoou exclusivo.

Outros tipos de grupos são:

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

Grafos

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:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x \forall y,\; R(x,y) \to R(y,x)}

• Anti-reflexividade:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x, \; \neg R(x,x)}

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ência

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

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

• Reflexividade;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x,\; [x \equiv x]}

• Simetria;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x\forall y,\; [(x \equiv y) \to (y \equiv x)]}

• Transitividade;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x\forall y\forall z,\; [((x \equiv y) \land (y \equiv z)) \to (x \equiv z)]}

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 Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{a}} .

Álgebras Booleanas

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;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a + b) = (b + a); \quad (a \cdot b) = (b \cdot a) }

• Distributividade;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \cdot (b + c) = (a \cdot b) + (a \cdot c); \quad a + (b \cdot c) = (a + b) \cdot (a + c) }

• Identidade;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a + 0) = a; \quad (a \cdot 1) = a }

• Complemento;

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a + \neg a) = 1; \quad (a \cdot \neg a) = 0 }

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.

Dualidade

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

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1 + a) \cdot (b + 0) = b}

é dual de

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0 \cdot a) + (b \cdot 1) = b}

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.

Ordem

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

• R for reflexiva, onde aRa para todo a ∈ A. 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-ordenado

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,b ∈ A, 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 a ∈ A, que não é um último elemento, tem um sucessor imediato.

Anéis e corpos

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:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (+) : (a,b) \to a + b} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle ( \cdot ) : (a, b) \to a \cdot b }

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

• Associatividade:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a + b) + c = a + (b + c) }

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a \cdot b ) \cdot c = a \cdot (b \cdot c) }

• Comutatividade:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a + b) = (b + a) }

• Elemento neutro de +:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists 0,\; (a + 0) = (0 + a) = a }

• Elemento inverso ou complemento de +:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall a \in A)(\exists (i) \in A), a + (i) = 0 }

• Distributividade:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \cdot (b + c) = (a \cdot b) + a (\cdot c) }

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b + c) \cdot a = (b \cdot a) + (c \cdot a) }

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:

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall a \in A : a \neq 0) (\exists b \in A), a \cdot b = 1 }

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 a ∈ A, exatamente uma das três alternativas seguintes ocorre: ou a = 0, ou a ∈ A ou -a ∈ A.

Referências

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ém

• Teoria dos grupos
• Teoria dos anéis
• Teoria dos corpos

• Teoria dos conjuntos
• Teoria dos grafos
• Álgebra booleana