Acesso mais rápido do que o navegador!
32 relações: Axiomas de Peano, Álgebra de Borel, Énuplo, Complementar, Conjunto, Conjunto recursivo, Conjuntos recursivamente enumeráveis, Espaço de Baire, Forma normal prenex, Função indicadora, Função recursiva primitiva, Grau de Turing, Hierarquia polinomial, Interseção, Lógica de segunda ordem, Lógica matemática, Máquina oráculo, Número natural, Problema da parada, Produto cartesiano, Projeção (matemática), Quantificação existencial, Quantificação universal, Redução de Turing, Redução por mapeamento, Relação de equivalência, Salto de Turing, Se e somente se, Teorema de Post, Teoria da computação, Teoria dos conjuntos, União (matemática).
Axiomas de Peano
Em lógica matemática, os axiomas de Peano, também conhecidos como os axiomas de Dedekind-Peano ou postulados de Peano, são um conjunto de axiomas para os números naturais apresentado pelo matemático italiano do século XIX Giuseppe Peano.
Novo!!: Hierarquia aritmética e Axiomas de Peano · Veja mais »
Álgebra de Borel
Em matemática, uma Álgebra de Borel ou \sigma-álgebra de Borel é qualquer conjunto em um espaço topológico que pode ser formado por abertos através das operações de união enumerável, interseção enumerável e diferença de conjuntos.
Novo!!: Hierarquia aritmética e Álgebra de Borel · Veja mais »
Énuplo
Énuplo (também conhecido como ênuplo, énupla, ênupla, n-tuplo, n-upla ou simplesmente tupla) é uma sequência ordenada de n elementos, que pode ser definida pela recursão do par ordenado.
Novo!!: Hierarquia aritmética e Énuplo · Veja mais »
Complementar
A área em vermelho é o complementar de ''A'' em ''U'', A^c~~~.
Novo!!: Hierarquia aritmética e Complementar · Veja mais »
Conjunto
Conjunto é um conceito-chave primitivo do ramo matemático da Teoria dos Conjuntos.
Novo!!: Hierarquia aritmética e Conjunto · Veja mais »
Conjunto recursivo
Na teoria da computabilidade, um conjunto de números naturais é chamado recursivo, computável ou decidível se existe um algoritmo que termina após uma quantidade finita de tempo e decide corretamente se um número pertence ou não ao conjunto.
Novo!!: Hierarquia aritmética e Conjunto recursivo · Veja mais »
Conjuntos recursivamente enumeráveis
Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se.
Novo!!: Hierarquia aritmética e Conjuntos recursivamente enumeráveis · Veja mais »
Espaço de Baire
Em matemática, sobretudo na análise funcional, um espaço de Baire é um conjunto de segunda categoria em si mesmo.
Novo!!: Hierarquia aritmética e Espaço de Baire · Veja mais »
Forma normal prenex
Na lógica proposicional existem duas formas normais: a forma normal conjuntiva e a forma normal disjuntiva.
Novo!!: Hierarquia aritmética e Forma normal prenex · Veja mais »
Função indicadora
Na matemática, a função indicadora de um conjunto é a função que indica se o elemento pertence ao conjunto, assumindo neste caso o valor 1, e 0 em caso contrário.
Novo!!: Hierarquia aritmética e Função indicadora · Veja mais »
Função recursiva primitiva
As funções recursivas primitivas são definidas através do uso da recursão primitiva e da Composição como operações centrais.
Novo!!: Hierarquia aritmética e Função recursiva primitiva · Veja mais »
Grau de Turing
Em ciência da computação e lógica matemática o grau de Turing ou grau de insolubilidade de um conjunto de números naturais mede o nível de insolubilidade algorítmica do conjunto.
Novo!!: Hierarquia aritmética e Grau de Turing · Veja mais »
Hierarquia polinomial
No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo.
Novo!!: Hierarquia aritmética e Hierarquia polinomial · Veja mais »
Interseção
Representação gráfica da interseção entre dois conjuntos Em teoria dos conjuntos, a, é um conjunto de elementos que, simultaneamente, pertencem a dois ou mais conjuntos, representado por ∩. Por exemplo, se o conjunto A possui os elementos e o conjunto B possui os elementos, então interseção do conjunto A com o conjunto B será igual a.
Novo!!: Hierarquia aritmética e Interseção · Veja mais »
Lógica de segunda ordem
Na lógica matemática, a lógica de segunda ordem é uma extensão da lógica de primeira ordem, onde a própria lógica de primeira ordem é uma extensão de lógica proposicional.
Novo!!: Hierarquia aritmética e Lógica de segunda ordem · Veja mais »
Lógica matemática
A lógica matemática é uma subárea da matemática que explora as aplicações da lógica formal para a matemática.
Novo!!: Hierarquia aritmética e Lógica matemática · Veja mais »
Máquina oráculo
Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão.
Novo!!: Hierarquia aritmética e Máquina oráculo · Veja mais »
Número natural
Um número natural é um número inteiro não negativo \. Em alguns contextos, número natural é definido como um número inteiro positivo, sendo também o zero considerado como um número natural (mesmo não sendo positivo e sim nulo/neutro): \. O conjunto dos números naturais é, comumente, denotado pelo símbolo \mathbb.
Novo!!: Hierarquia aritmética e Número natural · Veja mais »
Problema da parada
Na teoria da computabilidade o experimento mental do problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir.
Novo!!: Hierarquia aritmética e Problema da parada · Veja mais »
Produto cartesiano
Em matemática, dados dois conjuntos X e Y, o produto cartesiano (ou produto direto) desses dois (escrito como X × Y) é o conjunto de todos os pares ordenados, cujo primeiro termo pertence a X; e o segundo, a Y. O produto cartesiano recebe seu nome de René Descartes, cuja formulação da geometria analítica deu origem a este conceito.
Novo!!: Hierarquia aritmética e Produto cartesiano · Veja mais »
Projeção (matemática)
Em matemática, uma projecção num conjunto X é uma aplicação p:X\rightarrow X idempotente.
Novo!!: Hierarquia aritmética e Projeção (matemática) · Veja mais »
Quantificação existencial
Na lógica de predicados, um quantificador existencial é a predicação de uma propriedade ou relação para, pelo menos, um elemento do domínio.
Novo!!: Hierarquia aritmética e Quantificação existencial · Veja mais »
Quantificação universal
Na lógica de predicados, a quantificação universal é uma formalização da noção de que algumas coisas são verdadeiras para todas as coisas, ou para todas as coisas relevantes.
Novo!!: Hierarquia aritmética e Quantificação universal · Veja mais »
Redução de Turing
Na Teoria da Computação, a redução de Turing de um problema A para um problema B, nomeado após Alan Turing, é uma redução que resolve A, assumindo que B já é conhecido.
Novo!!: Hierarquia aritmética e Redução de Turing · Veja mais »
Redução por mapeamento
Na teoria da computabilidade e teoria da complexidade computacional, uma redução por mapeamento é uma redução que converte instâncias de um problema de decisão em instâncias de um outro problema de decisão.
Novo!!: Hierarquia aritmética e Redução por mapeamento · Veja mais »
Relação de equivalência
As 52 relações de equivalência em um conjunto de 5 elementos representadas por matrizes lógicas 5 × 5 (campos coloridos, incluindo aqueles em cinza claro, representam os uns; campos brancos por zeros.) Os índices de linha e coluna de células não brancas são os elementos relacionados, enquanto as cores diferentes, exceto cinza claro, indicam as classes de equivalência (cada célula cinza claro é sua própria classe de equivalência). Na matemática, uma relação de equivalência é uma relação binária que é reflexiva, simétrica e transitiva.
Novo!!: Hierarquia aritmética e Relação de equivalência · Veja mais »
Salto de Turing
Em teoria da computabilidade, o Salto de Turing ou Operador de Salto de Turing, nomeado por Alan Turing, é um operador que designa para cada problema de decisão um sucessivo problema de decisão mais difícil que tem a propriedade é não-decidível por uma Máquina Oráculo com um oráculo para.
Novo!!: Hierarquia aritmética e Salto de Turing · Veja mais »
Se e somente se
Se e somente se, ou se e só se (abreviado, sse), em matemática, lógica e filosofia, é uma forma de expressão para um teorema: Se A então B, e se B então A; ou A se e somente se B. O correspondente símbolo lógico é \Leftrightarrow.
Novo!!: Hierarquia aritmética e Se e somente se · Veja mais »
Teorema de Post
Na teoria da computação, o Teorema de Post,em homenagem à Emil Post, descreve a conexão entre hierarquia aritmética e os graus de Turing.
Novo!!: Hierarquia aritmética e Teorema de Post · Veja mais »
Teoria da computação
A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação.
Novo!!: Hierarquia aritmética e Teoria da computação · Veja mais »
Teoria dos conjuntos
conjuntos. Teoria dos conjuntos ou de conjuntos é o ramo da lógica matemática que estuda conjuntos, que (informalmente) são coleções de elementos.
Novo!!: Hierarquia aritmética e Teoria dos conjuntos · Veja mais »
União (matemática)
Indicação da união entre os conjuntos A e B Em teoria dos conjuntos, a união de dois ou mais conjuntos é o conjunto dos elementos que pertencem a pelo menos um destes conjuntos.
Novo!!: Hierarquia aritmética e União (matemática) · Veja mais »
