Princípio de Markov

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde novembro de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.
Nuvola apps important.svg
A tradução deste artigo ou se(c)ção está abaixo da qualidade média aceitável.
É possível que tenha sido feita por um tradutor automático ou por alguém que não conhece bem o português ou a língua original do texto. Caso queira colaborar com a Wikipédia, tente encontrar a página original e melhore este artigo conforme o guia de tradução.

O principio de Markov, cujo o nome advém do matemático Andrei Markov Jr, filho do também reputado matemático Andrei Markov Sn, é uma tautologia que não é válida por lógica intuicionista mas pode ser justificada por meio de construtivismo. Existem muitas formulações equivalente ao príncipio de Markov.

Definição[editar | editar código-fonte]

Em linguagem da teoria da computabilidade (teoria da computação), o príncipio de Markov é a expressão da reivindicação que se é impossível que um algoritmo que não termine, então irá terminar. Isto é equivalente à reivindicação de que se um conjunto e o seu complementar são ambos recursivamente enumeráveis, então o conjunto é recursivo.

Na lógica de predicados, se P é um predicado sobre os números naturais, é expresso como:

(\forall n (P(n) \vee \neg P(n))) \wedge (\neg \forall n \neg P(n)) \rightarrow (\exists n\;P(n)).

Isto é, se P é recursivo, e não pode ser falso por cada número natural n, então é verdade para algum some n. (Na generalidade, um predicado P sobre um qualquer dominio é chamado recursivo se por cada x no dominio, ou P (x) é verdadeiro, ou P (x) é falso, o que não é sempre o caso do construtivismo.)

É equivalente, na linguagem de aritmética de Heyting a:

\neg \neg \exists n\;f(n)=0 \rightarrow \exists n\;f(n)=0,

por cada f uma função computável aos números naturais.

É equivalente, na linguagem da análise real, aos seguintes princípio:

  • Por cada número real x, se é contraditório que x é igual a 0, então terá de existir y  ∈  Q tal que 0  < y < |x|, muitas vezes expresso por se dizer que x é separado (sugerido do inglês Apartness relation) de, ou construtivamente diferente de , 0.
  • Por cada número real x, se é contraditório que x é igual a  0, então terá de existir y  ∈ R tal que xy = 1.


Realizabilidade[editar | editar código-fonte]

Realizabilidade (sugerido do inglês Realizability) pode ser usado para justificar o princípio de Markov: um realizador é um operador μ que consecutivamente analisa se P(0), P(1), P(2),\dots é verdade. Porque P não é falso em todo o sítio, a procura não pode durar para sempre. Usando lógica clássica podemos concluir que a procura termina, nomeadamente no valor onde P existe.

Realizabilidade modificada não justifica o princípio de Markov, mesmo se a lógica clássica é usada na meta-teoria (sugerida do inglês meta-theory): não existe realizador na linguagem de cálculo lambda simplesmente tipado tal como esta linguagem não é Turing completo e ciclos arbitários não pode ser definidos nela.


Regra de Markov[editar | editar código-fonte]

Regra de Markov é a formulação do princípio de Markov como regra. Declara que \exists n\;P(n) é derivável logo que \neg \neg \exists n\;P(n) é, por cada P recursivo. O matemático de lógica Harvey Friedman mostrou que que a regra de Markov é uma regra admissível em lógica intuicionista, aritmética de Heyting, e muitos outras teorias intuicionistas[1] , usando a Tradução de Friedman.


Princípio de Markov fraco[editar | editar código-fonte]

Uma forma fraca do princípio de Markov pode ser expressa em linguagem de análise como:

\forall x\in\mathbb{R}\ (\forall y\in\mathbb{R}\ \neg\neg(0<y) \vee \neg\neg(y<x)) \to 0<x.

Esta forma pode ser justificada por Luitzen Egbertus Jan Brouwer, nos seus príncipios da continuidade, onde a forma mais forte os contradiz. Logo isto pode ser dericada do intuicionismo, realizabilidade, e racionalismo clássico, em cada caso por diferentes razões, mas este princípio não é valido no sentido lato contrutivista de Bishop.[2]


Referências[editar | editar código-fonte]

  1. Harvey Friedman. Classically and Intuitionistically Provably Recursive Functions. In Scott, D. S. and Muller, G. H. Editors, Higher Set Theory, Volume 699 of Lecture Notes in Mathematics, Springer Verlag (1978), pp. 21–28.
  2. Ulrich Kohlenbach, "On weak Markov's principle". Mathematical Logic Quarterly (2002), vol 48, issue S1, pp. 59–65.


Ligações externas[editar | editar código-fonte]