Lógica E Jogos

Índice:

Lógica E Jogos
Lógica E Jogos

Vídeo: Lógica E Jogos

Vídeo: Lógica E Jogos
Vídeo: 7 JOGOS PARA SABER COMO ESTÁ O SEU RACIOCÍNIO [ IncrivelMente Curiosa ] 2024, Março
Anonim

Navegação de entrada

  • Conteúdo da Entrada
  • Bibliografia
  • Ferramentas Acadêmicas
  • Pré-visualização do Friends PDF
  • Informações sobre autor e citação
  • De volta ao topo

Lógica e Jogos

Publicado pela primeira vez em 27 de julho de 2001; revisão substantiva sex 16 ago 2019

Jogos entre dois jogadores, do tipo em que um jogador vence e um perde, tornou-se uma ferramenta familiar em muitos ramos da lógica durante a segunda metade do século XX. Exemplos importantes são jogos semânticos usados para definir a verdade, jogos alternativos usados para comparar estruturas e jogos de diálogo para expressar (e talvez explicar) provas formais.

  • 1. Jogos na história da lógica
  • 2. Jogos lógicos
  • 3. Jogos Semânticos para Lógica Clássica
  • 4. Jogos semânticos com informações imperfeitas
  • 5. Jogos semânticos para outras lógicas
  • 6. Jogos de idas e vindas
  • 7. Outros jogos da teoria dos modelos

    • 7.1 Forçando jogos
    • 7.2 Jogos cortados e escolhidos
    • 7.3 Jogos na árvore de duas funções sucessoras
  • 8. Jogos de Diálogo, Comunicação e Prova
  • Bibliografia

    • Jogos na História da Lógica
    • Jogos para ensinar lógica
    • Jogos lógicos
    • Jogos Semânticos para Lógica Clássica
    • Jogos semânticos com informações imperfeitas
    • Jogos semânticos para outras lógicas
    • Jogos para trás e para a frente
    • Outros jogos de modelos teóricos
    • Jogos de Diálogo, Comunicação e Prova
  • Ferramentas Acadêmicas
  • Outros recursos da Internet
  • Entradas Relacionadas

1. Jogos na história da lógica

Os links entre lógica e jogos remontam a um longo caminho. Se alguém pensa em um debate como uma espécie de jogo, então Aristóteles já fez a conexão; seus escritos sobre silogismo estão intimamente entrelaçados com seu estudo dos objetivos e regras do debate. O ponto de vista de Aristóteles sobreviveu ao nome medieval comum da lógica: dialética. Em meados do século XX, Charles Hamblin reviveu o vínculo entre o diálogo e as regras do bom raciocínio, logo após Paul Lorenzen conectar o diálogo a fundamentos construtivos da lógica.

Existem laços estreitos entre jogos e ensino. Escritores ao longo do período medieval falam dos diálogos como uma maneira de "ensinar" ou "testar" o uso do raciocínio sólido. Temos pelo menos dois livros didáticos de lógica do início do século XVI que o apresentam como um jogo para um aluno individual, e The Game of Logic (1887), de Lewis Carroll, é outro exemplo do mesmo gênero. Também existem muitos exemplos modernos, embora provavelmente não tenha havido continuidade suficiente para justificar a fala de uma tradição de ensinar lógica pelos jogos.

A teoria matemática dos jogos foi fundada no início do século XX. Embora nenhum vínculo matemático com a lógica tenha surgido até a década de 1950, é impressionante quantos dos pioneiros da teoria dos jogos também são conhecidos por suas contribuições à lógica: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo e outros. Em 1953, David Gale e Frank Stewart fizeram conexões frutíferas entre teoria dos jogos e jogos. Logo depois, Leon Henkin sugeriu uma maneira de usar jogos para fornecer semântica para idiomas infinitos.

A primeira metade do século XX foi uma era de crescente rigor e profissionalismo em lógica, e para a maioria dos lógicos daquele período o uso de jogos em lógica provavelmente teria parecido frívolo. O intuicionista LEJ Brouwer expressou essa atitude quando acusou seus oponentes de fazer com que a matemática "degenerasse em um jogo" (como David Hilbert o citou em 1927, citado em van Heijenoort 1967). Hermann Weyl (citado em Mancosu 1998) usou a noção de jogos para explicar a metamatemática de Hilbert: as provas matemáticas acontecem como peças de um jogo sem sentido, mas podemos ficar de fora do jogo e fazer perguntas significativas sobre ele. Os jogos de linguagem de Wittgenstein provocaram pouca resposta dos lógicos. Mas, na segunda metade do século, o centro de gravidade da pesquisa lógica mudou das fundações para as técnicas,e a partir de 1960, os jogos eram usados cada vez mais frequentemente em documentos lógicos.

No início do século XXI, tornou-se amplamente aceito que jogos e lógica andam juntos. O resultado foi uma enorme proliferação de novas combinações de lógica e jogos, principalmente em áreas onde a lógica é aplicada. Muitos desses novos desenvolvimentos surgiram originalmente do trabalho em pura lógica, embora hoje eles sigam suas próprias agendas. Uma dessas áreas é a teoria da argumentação, onde os jogos formam uma ferramenta para analisar a estrutura dos debates.

A seguir, vamos nos concentrar nos jogos que estão mais intimamente associados à lógica pura.

2. Jogos lógicos

Do ponto de vista da teoria dos jogos, os principais jogos que os lógicos estudam não são de todo típicos. Eles normalmente envolvem apenas dois jogadores, geralmente têm duração infinita, os únicos resultados estão vencendo e perdendo e nenhuma probabilidade é atribuída a ações ou resultados. O essencial mais simples de um jogo lógico é o seguinte.

Existem dois jogadores. Em geral, podemos chamá-los de (forall) e (existir). As pronúncias 'Abelard' e 'Eloise' remontam a meados dos anos 80 e fixam os jogadores como homens e mulheres, facilitando a referência: a jogada dela, a jogada dele. Outros nomes são de uso comum para os jogadores em determinados tipos de jogo lógico.

Os jogadores jogam escolhendo elementos de um conjunto (Omega), chamado de domínio do jogo. Como eles escolhem, eles constroem uma sequência

[a_0, a_1, a_2, / ldots)

de elementos de (Omega). Sequências infinitas de elementos de (Omega) são chamadas de peças de teatro. Sequências finitas de elementos de (Omega) são chamadas de posições; eles gravam onde uma peça pode ter chegado por um certo tempo. Uma função (tau) (a função turn ou a função player) leva cada posição (mathbf {a}) para (existir) ou (forall); se (tau (mathbf {a}) = / existe), isso significa que quando o jogo atingir (mathbf {a}), o jogador (existente) fará a próxima escolha (e da mesma forma com (forall)). As regras do jogo definem dois conjuntos (W _ { forall}) e (W _ { existe}) consistindo em posições e jogadas, com as seguintes propriedades: se uma posição (mathbf {a}) está em (W _ { forall}), assim como qualquer jogada ou posição mais longa que comece com (mathbf {a}) (e da mesma forma com (W _ { existe}));e nenhuma reprodução está em (W _ { forall}) e (W _ { existe}). Dizemos que o jogador (forall) vence uma jogada (mathbf {b}) e que (mathbf {b}) é uma vitória para (forall), se (mathbf {b}) está em (W _ { forall}); se alguma posição (mathbf {a}) que é um segmento inicial de (mathbf {b}) estiver em (W _ { forall}), então dizemos que o jogador (forall) já vence em (mathbf {a}). (E da mesma forma com (existe) e (W _ { existe}).) Portanto, para resumir, um jogo lógico é uma 4-tupla ((Omega, / tau), (W_ { forall}), (W _ { existe})) com as propriedades que acabamos de descrever.então dizemos que o jogador (forall) já vence em (mathbf {a}). (E da mesma forma com (existe) e (W _ { existe}).) Portanto, para resumir, um jogo lógico é uma 4-tupla ((Omega, / tau), (W_ { forall}), (W _ { existe})) com as propriedades descritas acima.então dizemos que o jogador (forall) já vence em (mathbf {a}). (E da mesma forma com (existe) e (W _ { existe}).) Portanto, para resumir, um jogo lógico é uma 4-tupla ((Omega, / tau), (W_ { forall}), (W _ { existe})) com as propriedades descritas acima.

Dizemos que um jogo lógico é total se cada jogada estiver em (W _ { forall}) ou (W _ { existe}), para que não haja empates. A menos que se faça uma exceção explícita, sempre se assume que os jogos lógicos são totais. (Não confunda ser total com a propriedade muito mais forte de ser determinado - veja abaixo.)

É apenas por conveniência matemática que a definição acima espera que o jogo continue até o infinito, mesmo quando um jogador venceu em alguma posição finita; não há interesse em nada que aconteça após a vitória de um jogador. Muitos jogos lógicos têm a propriedade de que, em cada jogada, um dos jogadores já venceu em alguma posição finita; Dizem que jogos desse tipo são bem fundamentados. Uma condição ainda mais forte é a existência de um número finito (n), de modo que, em cada jogada, um dos jogadores já venceu pela (n) - quinta posição; neste caso, dizemos que o jogo tem duração finita.

Uma estratégia para um jogador é um conjunto de regras que descrevem exatamente como esse jogador deve escolher, dependendo de como os dois jogadores escolheram nas jogadas anteriores. Matematicamente, uma estratégia para (forall) consiste em uma função que assume cada posição (mathbf {a}) com (tau (mathbf {a}) = / forall) em um elemento (b) de (Omega); pensamos nisso como uma instrução para (forall) escolher (b) quando o jogo atingir a posição (mathbf {a}). (Da mesma forma com uma estratégia para (existe).) Diz-se que uma estratégia para um jogador está ganhando se esse jogador vencer todas as jogadas em que ele ou ela usar a estratégia, independentemente do que o outro jogador faça. No máximo, um dos jogadores tem uma estratégia vencedora (pois, caso contrário, os jogadores poderiam jogar suas estratégias vitoriosas um contra o outro e ambos venceriam,contradizendo que (W _ { forall}) e (W _ { existe}) não têm peças em comum). Ocasionalmente, encontramos situações em que parece que dois jogadores têm estratégias vencedoras (por exemplo, nos jogos de forçar abaixo), mas uma inspeção mais detalhada mostra que os dois jogadores estão de fato jogando jogos diferentes.

Diz-se que um jogo é determinado se um ou outro jogador tem uma estratégia vencedora. Existem muitos exemplos de jogos que não são determinados, como Gale e Stewart mostraram em 1953, usando o axioma da escolha. Essa descoberta levou a importantes aplicações da noção de determinação nos fundamentos da teoria dos conjuntos (ver entrada em grandes cardeais e determinação). Gale e Stewart também se mostraram um importante teorema que leva seu nome: todo jogo bem fundamentado é determinado. Segue-se que todo jogo de comprimento finito é determinado - um fato já conhecido por Zermelo em 1913. (Uma afirmação mais precisa do teorema de Gale-Stewart é essa. Diz-se que um jogo (G) será encerrado se (existe) vence todas as jogadas de (G) nas quais ela ainda não perdeu em nenhuma posição finita. O teorema afirma que todo jogo fechado é determinado. A prova do teorema é basicamente fácil: vamos chamar uma posição vencedora para (forall) se ele tiver uma estratégia vencedora a partir dessa posição. Suponha que (forall) não tenha uma estratégia vencedora no jogo, ou seja, no início a posição não está ganhando por (forall). Se a primeira jogada for uma jogada de (forall), depois da jogada, a posição ainda não está ganhando para ele. Se a primeira jogada é uma jogada de (existe), ela deve ter uma jogada após a qual a posição ainda não está ganhando por (forall), pois, caso contrário, a posição anterior teria ganhado por (forall). O jogo continua desta maneira infinitamente muitos movimentos através de posições que não estão ganhando por (forall). Como o jogo está fechado, (existe) vence.)Suponha que (forall) não tenha uma estratégia vencedora no jogo, ou seja, no início a posição não está ganhando por (forall). Se a primeira jogada for uma jogada de (forall), depois da jogada, a posição ainda não está ganhando para ele. Se a primeira jogada é uma jogada de (existe), ela deve ter uma jogada após a qual a posição ainda não está ganhando por (forall), pois, caso contrário, a posição anterior teria ganhado por (forall). O jogo continua desta maneira infinitamente muitos movimentos através de posições que não estão ganhando por (forall). Como o jogo está fechado, (existe) vence.)Suponha que (forall) não tenha uma estratégia vencedora no jogo, ou seja, no início a posição não está ganhando por (forall). Se a primeira jogada for uma jogada de (forall), depois da jogada, a posição ainda não está ganhando para ele. Se a primeira jogada é uma jogada de (existe), ela deve ter uma jogada após a qual a posição ainda não está ganhando por (forall), pois, caso contrário, a posição anterior teria ganhado por (forall). O jogo continua desta maneira infinitamente muitos movimentos através de posições que não estão ganhando por (forall). Como o jogo está fechado, (existe) vence.)Se a primeira jogada é uma jogada de (existe), ela deve ter uma jogada após a qual a posição ainda não está ganhando por (forall), pois, caso contrário, a posição anterior teria ganhado por (forall). O jogo continua desta maneira infinitamente muitos movimentos através de posições que não estão ganhando por (forall). Como o jogo está fechado, (existe) vence.)Se a primeira jogada é uma jogada de (existe), ela deve ter uma jogada após a qual a posição ainda não está ganhando por (forall), pois, caso contrário, a posição anterior teria ganhado por (forall). O jogo continua desta maneira infinitamente muitos movimentos através de posições que não estão ganhando por (forall). Como o jogo está fechado, (existe) vence.)

Assim como na teoria clássica dos jogos, a definição dos jogos lógicos acima serve como um cavalo de roupas no qual podemos nos apegar a outros conceitos. Por exemplo, é comum ter algumas leis que descrevem quais elementos de (Omega) estão disponíveis para um jogador escolher em um determinado movimento. Estritamente, esse refinamento é desnecessário, porque as estratégias vencedoras não são afetadas se decretarmos que um jogador que infringe a lei perde imediatamente; mas para muitos jogos essa maneira de vê-los parece antinatural. Abaixo, veremos outros recursos extras que podem ser adicionados aos jogos.

As definições de jogo e estratégia acima eram puramente matemáticas. Então eles deixaram de fora o que provavelmente é a característica mais importante dos jogos, que é que as pessoas os jogam (pelo menos metaforicamente). Os jogadores pretendem vencer e, estudando as estratégias abertas a eles, estudamos qual comportamento é racional para uma pessoa com um objetivo específico. Na maioria dos jogos, existem vários jogadores, para que possamos estudar o que é uma resposta racional ao comportamento de outra pessoa. Ao restringir os movimentos dos jogadores e possíveis estratégias, podemos estudar a racionalidade limitada, em que um agente precisa tomar decisões racionais sob condições de informação, memória ou tempo limitados.

Em resumo, os jogos são usados para modelar a racionalidade e a racionalidade limitada. Isso é independente de qualquer conexão com a lógica. Mas algumas lógicas foram projetadas para estudar aspectos do comportamento racional e, nos últimos anos, tornou-se cada vez mais comum vincular essas lógicas a jogos adequados. Veja a Seção 5 ('Jogos semânticos para outras lógicas') e sua bibliografia.

Mas até recentemente, os jogos lógicos eram conectados ao comportamento racional de uma maneira bem diferente. Aparentemente, a lógica em questão não tinha conexão direta com o comportamento. Mas lógicos e matemáticos perceberam que algumas idéias poderiam ser mais intuitivas se fossem vinculadas a possíveis objetivos. Por exemplo, em muitas aplicações de jogos lógicos, a noção central é a de uma estratégia vencedora para o jogador (existe). Freqüentemente, essas estratégias (ou a existência delas) são equivalentes a algo de importância lógica que poderia ter sido definido sem o uso de jogos - por exemplo, uma prova. Mas parece-se que os jogos dão uma definição melhor porque, literalmente, fornecem alguma motivação: (existe) está tentando vencer.

Isso levanta uma questão que não é de muito interesse matematicamente, mas deve preocupar os filósofos que usam jogos lógicos. Se queremos que a motivação de (existente) em um jogo (G) tenha algum valor explicativo, precisamos entender o que é alcançado se (existir) vencer. Em particular, devemos ser capazes de contar uma história realista de uma situação em que algum agente chamado (existir) está tentando fazer algo inteligível, e fazê-lo é a mesma coisa que vencer no jogo. Como Richard Dawkins disse, levantando a questão correspondente para os jogos evolutivos de Maynard Smith,

Todo o objetivo de nossa pesquisa … é descobrir um ator adequado para desempenhar o papel principal em nossas metáforas de propósito. Nós … queremos dizer: 'É para o bem de …'. Nossa busca neste capítulo é o caminho certo para completar essa frase. (The Extended Phenotype, Oxford University Press, Oxford 1982, página 91.)

Para referência futura, chamemos isso de questão de Dawkins. Em muitos tipos de jogos lógicos, é claramente mais difícil responder do que os pioneiros desses jogos perceberam. (Marion 2009 discute mais a questão de Dawkins.)

3. Jogos Semânticos para Lógica Clássica

No início dos anos 30, Alfred Tarski propôs uma definição de verdade. Sua definição consistia em uma condição necessária e suficiente para que uma sentença na linguagem de uma teoria formal típica fosse verdadeira; sua condição necessária e suficiente usava apenas noções da sintaxe e da teoria dos conjuntos, juntamente com as noções primitivas da teoria formal em questão. De fato, Tarski definiu a relação mais geral 'fórmula (phi (x_1, / ldots, x_n)) é verdadeira para os elementos (a_1, / ldots, a_n)' a verdade de uma sentença é o caso especial em que (n = 0). Por exemplo, a questão de saber se

'Para todos (x) existe (y) tal que R ((x, y))' é verdadeiro

reduz à questão de saber se o seguinte vale:

Para todo objeto (a), a sentença 'Existe (y) tal que R ((a, y))' é verdadeira.

Por sua vez, reduz-se a:

Para todo objeto (a) existe um objeto (b), de modo que a frase 'R ((a, b))' seja verdadeira.

Neste exemplo, isso é o que a definição da verdade de Tarski nos levará.

No final da década de 1950, Leon Henkin percebeu que podemos intuitivamente entender algumas frases que não podem ser tratadas pela definição de Tarski. Tomemos, por exemplo, a frase infinitamente longa

Para todos (x_0) existe (y_0) tal que para todos (x_1) existe (y_1) tal que… R ((x_0, y_0, x_1, y_1, / ldots)).

A abordagem de Tarski falha porque a série de quantificadores no início é infinita e nunca chegaríamos ao fim de removê-los. Em vez disso, sugeriu Henkin, devemos considerar o jogo em que uma pessoa (forall) escolhe um objeto (a_0) para (x_0) e, em seguida, uma segunda pessoa (existir) escolhe um objeto (b_0) para (y_0), então (forall) escolhe (a_1) para (x_1, / existe) escolhe (b_1) para (y_1) e assim por diante. Uma jogada deste jogo é uma vitória para (existe) se e somente se a sentença atômica infinita

(R (a_0, b_0, a_1, b_1, / ldots))

é verdade. A frase original é verdadeira se, e somente se, o jogador (existir) tiver uma estratégia vencedora para este jogo. Estritamente Henkin usou o jogo apenas como uma metáfora, e a condição de verdade que ele propôs foi que a versão esquemática da frase fosse verdadeira, ou seja, que houvesse funções (f_0, f_1, / ldots) tais que, para todas as opções de (a_0, a_1, a_2) etc. temos

(R (a_0, f_0 (a_0), a_1, f_1 (a_0, a_1), a_2, f_2 (a_0, a_1, a_2), / ldots).)

Mas essa condição se traduz imediatamente no idioma dos jogos; as funções Skolem (f_0) etc. definem uma estratégia vencedora para (existir), dizendo a ela como escolher à luz das escolhas anteriores por (forall). (Veio à tona algum tempo depois que CS Peirce já havia sugerido explicar a diferença entre 'todo' e 'algum' em termos de quem escolhe o objeto; por exemplo, em sua segunda conferência da Conferência de Cambridge de 1898.)

Logo após o trabalho de Henkin, Jaakko Hintikka acrescentou que a mesma idéia se aplica a conjunções e disjunções. Podemos considerar uma conjunção '(phi / wedge / psi)' como uma afirmação universalmente quantificada que expressa 'Cada uma das frases (phi, / psi) vale', portanto deve ser para o jogador (forall) para escolher uma das frases. Como Hintikka colocou, para jogar o jogo (G (phi / wedge / psi), / forall) escolhe se o jogo deve prosseguir como (G (phi)) ou como (G (psi)). Da mesma forma, as disjunções tornam-se afirmações existencialmente quantificadas sobre conjuntos de frases e marcam os movimentos onde o jogador (existe) escolhe como o jogo deve prosseguir. Para trazer quantificadores para o mesmo estilo, ele propôs que o jogo (G (forall x / phi (x))) prossiga da seguinte maneira: o jogador (forall) escolhe um objeto e fornece um nome (a) por issoe o jogo prossegue como (G (phi (a))). (E da mesma forma com quantificadores existenciais, exceto que (existe) escolhe.) Hintikka também fez uma sugestão engenhosa para introduzir negação. Cada jogo G tem um jogo duplo que é o mesmo que G, exceto que os jogadores (forall) e (existe) são transpostos nas regras de jogo e nas regras de vitória. O jogo (G (neg / phi)) é o dual de (G (phi)).

Pode-se provar que, para qualquer sentença de primeira ordem (phi), interpretada em uma estrutura fixa (A), o jogador (existe) possui uma estratégia vencedora para o jogo de Hintikka (G (phi)) se e somente se (phi) for verdadeiro em (A) no sentido de Tarski. Duas características dessa prova são interessantes. Primeiro, se (phi) é qualquer sentença de primeira ordem, o jogo (G (phi)) tem um comprimento finito e, portanto, o teorema de Gale-Stewart nos diz que é determinado. Inferimos que (existe) tem uma estratégia vencedora em exatamente um de (G (phi)) e seu dual; então ela tem uma estratégia vencedora em (G (neg / phi)) se e somente se ela não tiver uma em (G (phi)). Isso cuida da negação. Segundo, se (existir) tiver uma estratégia vencedora para cada jogo (G (phi (a))), depois de escolher uma dessas estratégias (f_a) para cada (a),ela pode agrupá-los em uma única estratégia vencedora para (G (forall x / phi (x))) (ou seja, 'Espere e veja qual elemento (a / forall) escolhe e, em seguida, jogue (f_a) '). Isso cuida da cláusula para quantificadores universais; mas o argumento usa o axioma da escolha e, de fato, não é difícil ver que a afirmação de que as definições de verdade de Hintikka e Tarski são equivalentes é equivalente ao axioma da escolha (dados os outros axiomas da teoria dos conjuntos de Zermelo-Fraenkel).e, de fato, não é difícil perceber que a afirmação de que as definições de verdade de Hintikka e Tarski são equivalentes é equivalente ao axioma da escolha (dados os outros axiomas da teoria dos conjuntos de Zermelo-Fraenkel).e, de fato, não é difícil perceber que a afirmação de que as definições de verdade de Hintikka e Tarski são equivalentes é equivalente ao axioma da escolha (dados os outros axiomas da teoria dos conjuntos de Zermelo-Fraenkel).

É intrigante termos aqui duas teorias de quando uma frase é verdadeira, e as teorias não são equivalentes se o axioma da escolha falhar. De fato, o motivo não é muito profundo. O axioma da escolha é necessário não porque a definição de Hintikka usa jogos, mas porque pressupõe que as estratégias são determinísticas, ou seja, que são funções de valor único, não dando ao usuário opções de escolha. Uma maneira mais natural de traduzir a definição de Tarski em termos de jogo é usar estratégias não determinísticas, às vezes chamadas de quase-estratégias (veja Kolaitis 1985 para detalhes). (No entanto, Hintikka 1996 insiste que a explicação correta de 'verdadeiro' é aquela que utiliza estratégias determinísticas, e que esse fato justifica o axioma da escolha).

As implementações em computador desses jogos de Hintikka provaram ser uma maneira muito eficaz de ensinar os significados das frases de primeira ordem. Um desses pacotes foi projetado por Jon Barwise e John Etchemendy em Stanford, chamado 'Tarski's World'. Independentemente, outra equipe da Universidade de Omsk construiu uma versão russa para uso em escolas para crianças superdotadas.

Na versão publicada de suas palestras de John Locke em Oxford, Hintikka, em 1973, levantou a questão de Dawkins (veja acima) para esses jogos. Sua resposta foi que se deveria olhar para os jogos de linguagem de Wittgenstein, e os jogos de linguagem para entender quantificadores são aqueles que giram em torno de busca e descoberta. Nos jogos lógicos correspondentes, deve-se pensar em (existe) como eu e (forall) como uma natureza hostil que nunca pode ser invocada para apresentar o objeto que eu quero; para ter certeza de encontrá-lo, preciso de uma estratégia vencedora. Essa história nunca foi muito convincente; a motivação da natureza é irrelevante e nada no jogo lógico corresponde à busca. Em retrospecto, é um pouco decepcionante que ninguém tenha se dado ao trabalho de procurar uma história melhor. Pode ser mais útil pensar em uma estratégia vencedora para (existe) em (G (phi)) como um tipo de prova (em um sistema infinitário adequado) de que (phi) é verdadeira.

Mais tarde, Jaakko Hintikka estendeu as idéias desta seção em duas direções, a semântica da linguagem natural e a jogos de informações imperfeitas (veja a próxima seção). O nome Semântica Teórica dos Jogos, GTS, passou a ser usado para cobrir essas duas extensões.

Os jogos descritos nesta seção se adaptam quase trivialmente à lógica de várias classificações: por exemplo, o quantificador (forall x _ { sigma}), onde (x _ { sigma}) é uma variável de classificação (sigma), é uma instrução para o player (forall) escolher um elemento da classificação (sigma). Isso nos dá imediatamente os jogos correspondentes para a lógica de segunda ordem, se pensarmos nos elementos de uma estrutura como um tipo, nos conjuntos de elementos como um segundo tipo, nas relações binárias como um terceiro e assim por diante. Daqui resulta que também temos, rotineiramente, regras de jogo para os quantificadores mais generalizados; podemos encontrá-los traduzindo primeiro os quantificadores generalizados em lógica de segunda ordem.

4. Jogos semânticos com informações imperfeitas

Nesta e na próxima seção, veremos algumas adaptações dos jogos semânticos da seção anterior para outras lógicas. Em nosso primeiro exemplo, a lógica (a lógica favorável à independência de Hintikka e Sandu 1997, ou, mais brevemente, a lógica IF) foi criada para se ajustar ao jogo. Veja a entrada sobre lógica amigável à independência e Mann, Sandu e Sevenster 2011 para contas mais completas dessa lógica.

Os jogos aqui são os mesmos da seção anterior, exceto pelo fato de abandonarmos a suposição de que cada jogador conhece o histórico anterior da jogada. Por exemplo, podemos exigir que um jogador faça uma escolha sem saber que escolhas o outro jogador fez em certos movimentos anteriores. A maneira clássica de lidar com isso dentro da teoria dos jogos é fazer restrições às estratégias dos jogadores. Por exemplo, podemos exigir que a função de estratégia que diz a (existir) o que fazer em uma etapa específica seja uma função cujo domínio seja a família de possíveis opções de (forall) apenas em seus primeiro e segundo movimentos; essa é uma maneira de expressar que (existe) não sabe como (forall) escolheu em seus terceiros e posteriores movimentos. Dizem que jogos com restrições desse tipo nas funções estratégicas são de informação imperfeita,em oposição aos jogos de informação perfeita na seção anterior.

Para criar uma lógica que se encaixa nesses jogos, usamos a mesma linguagem de primeira ordem da seção anterior, exceto que uma notação é adicionada a alguns quantificadores (e possivelmente também a alguns conectivos), para mostrar que o Skolem funciona para esses quantificadores (ou conectivos) são independentes de determinadas variáveis. Por exemplo, a frase

[(forall x) (existe y / / forall x) R (x, y))

é lido como: “Para todo (x) existe (y), não depende de (x), de modo que (R (x, y))”.

Há três comentários importantes a fazer sobre a distinção entre informações perfeitas e imperfeitas. A primeira é que o teorema de Gale-Stewart é válido apenas para jogos de informação perfeita. Suponha, por exemplo, que (forall) e (existir) joguem o jogo a seguir. Primeiro, (forall) escolhe um dos números 0 e 1. Então (existe) escolhe um desses dois números. O jogador (existe) vence se os dois números escolhidos forem iguais e, caso contrário, o jogador (forall) vence. Exigimos que (existe), quando ela faz sua escolha, não saiba o que (tudo) escolheu; então uma função Skolem para ela será uma constante. (Este jogo corresponde à sentença IF acima com (R) lida como igualdade, em uma estrutura com um domínio que consiste em 0 e 1.) É claro que o jogador (existe) não possui uma estratégia de vitória constante,e também esse jogador (forall) não tem uma estratégia vencedora. Portanto, este jogo é indeterminado, embora seu comprimento seja de apenas 2.

Um corolário é que a justificativa de Hintikka para ler a negação como dualização ('jogadores trocam de lugar'), em seus jogos pela lógica de primeira ordem, não é transferida para a lógica IF. A resposta de Hintikka foi que a dualização era o significado intuitivo correto da negação, mesmo no caso de primeira ordem, de modo que nenhuma justificação é necessária.

O segundo comentário é que já em jogos de informação perfeita, pode acontecer que as estratégias vencedoras não usem toda a informação disponível. Por exemplo, em um jogo de informações perfeitas, se o jogador (existir) tiver uma estratégia vencedora, ela também terá uma estratégia vencedora em que as funções da estratégia dependem apenas das opções anteriores de (forall). Isso ocorre porque ela pode reconstruir seus próprios movimentos anteriores usando suas funções estratégicas anteriores.

Quando Hintikka usou as funções de Skolem como estratégias em seus jogos para a lógica de primeira ordem, ele fez com que as estratégias para um jogador dependessem apenas dos movimentos anteriores do outro jogador. (Uma função Skolem para (existe) depende apenas de variáveis quantificadas universalmente.) Como os jogos eram jogos de informação perfeita, não houve perda nisso, pelo segundo comentário acima. Mas quando ele mudou para a lógica IF, o requisito de que as estratégias dependessem apenas dos movimentos do outro jogador realmente fez a diferença. Hodges 1997 mostrou isso revisando a notação, de modo que, por exemplo, ((existe y / x)) significa: “Existe (y) independente de (x), independentemente de qual jogador escolheu (x).

Considere agora a frase

[(forall x) (existe z) (existe y / x) (x = y),)

jogado novamente em uma estrutura com dois elementos 0 e 1. O jogador (existe) pode ganhar da seguinte maneira. Para (z), ela escolhe o mesmo que o jogador (forall) escolheu para (x); então, para (y), ela escolhe o mesmo que escolheu para (z). Essa estratégia vencedora funciona apenas porque neste jogo (existe) pode se referir a suas próprias escolhas anteriores. Ela não teria uma estratégia vencedora se o terceiro quantificador fosse ((existe y / xz)), novamente porque qualquer função Skolem para esse quantificador teria que ser constante. A maneira como (existe) passa informações para si mesma, referindo-se à sua escolha anterior, é um exemplo do fenômeno da sinalização. John von Neumann e Oskar Morgenstern o ilustraram com o exemplo de Bridge, onde um único jogador consiste em dois parceiros que precisam compartilhar informações usando seus movimentos públicos para sinalizar um ao outro.

O terceiro comentário é que há um deslocamento entre a idéia intuitiva de informação imperfeita e a definição da teoria do jogo em termos de estratégias. Intuitivamente, informações imperfeitas são um fato sobre as circunstâncias em que o jogo é jogado, não sobre as estratégias. Esse é um assunto muito complicado e continua a levar a mal-entendidos sobre FI e lógicas semelhantes. Tomemos, por exemplo, a frase

[(existe x) (existe y / x) (x = y),)

novamente reproduzido em uma estrutura com os elementos 0 e 1. Intuitivamente, pode-se pensar que se (existir) não puder lembrar no segundo quantificador o que ela escolheu no primeiro, então ela dificilmente poderá ter uma estratégia vencedora. Mas, na verdade, ela é muito fácil: 'Sempre escolha 0'!

Comparado com a lógica de primeira ordem, a lógica IF está ausente de um componente que a semântica do jogo não fornecerá. A semântica do jogo nos diz quando uma frase é verdadeira em uma estrutura. Mas se usarmos uma fórmula com (n) variáveis livres, o que a fórmula expressa sobre as (n) - tuplas ordenadas de elementos da estrutura? Na lógica de primeira ordem, definiria um conjunto deles, isto é, uma relação (n) - ária na estrutura; a definição da verdade de Tarski explica como. Existe uma definição semelhante para fórmulas arbitrárias da lógica IF? Acontece que existe uma para a lógica ligeiramente diferente introduzida por Hodges 1997, e leva a uma definição de verdade no estilo de Tarski para a linguagem dessa lógica. Com um pequeno ajuste, essa definição de verdade também pode ser feita para se ajustar à lógica SE. Mas para essas duas novas lógicas há um problema:em vez de dizer quando uma atribuição de elementos para liberar variáveis torna uma fórmula verdadeira, dizemos que quando um conjunto de atribuições de elementos para liberar variáveis torna a fórmula verdadeira. Väänänen 2007 fez dessa idéia a base de uma série de novas lógicas para o estudo da noção de dependência (ver entrada na lógica da dependência). Nestas lógicas, a semântica é definida sem jogos, embora a inspiração original venha do trabalho de Hintikka e Sandu.

Nas lógicas de Väänänen, é fácil ver por que precisamos de conjuntos de atribuições. Ele tem uma fórmula atômica que expressa '(x) depende de (y)'. Como podemos interpretar isso em uma estrutura, por exemplo, a estrutura dos números naturais? Não faz sentido perguntar, por exemplo, se 8 é dependente de 37. Mas se tivermos um conjunto X de pares ordenados de números naturais, faz sentido perguntar se em X o primeiro membro de cada par é dependente do segundo; a resposta Sim significaria que existe uma função (f) de modo que cada par ((a, b)) em X tenha a forma ((f (b), b)).

5. Jogos semânticos para outras lógicas

Estruturas do tipo a seguir dão origem a jogos interessantes. A estrutura (A) consiste em um conjunto (S) de elementos (que chamaremos de estados, acrescentando que eles são freqüentemente chamados de mundos), uma relação binária (R) em (S) (nós deve ler (R) como seta) e uma família (P_1, / ldots, P_n) de subconjuntos de (S). Os dois jogadores (forall) e (existir) jogam G em (A), começando no estado (s) que lhes é dado, lendo uma fórmula lógica adequada (phi) como um conjunto de instruções para jogar e ganhar.

Assim, se (phi) for (P_i), o jogador (existir) vence de uma só vez se (s) estiver em (P_i) e, caso contrário, o jogador (forall) vence de uma vez só. As fórmulas (psi / wedge / theta, / psi / vee / theta) e (neg / psi) se comportam como nos jogos de Hintikka acima; por exemplo, (psi / wedge / theta) instrui o jogador (forall) a escolher se o jogo deve continuar como (psi) ou (theta). Se a fórmula (phi) for (Box / psi), o jogador (forall) escolherá uma flecha de (s) para um estado (t) (ou seja, um estado (t) tal que o par ((s, t)) esteja na relação (R)), e o jogo prossiga a partir do estado (t) de acordo com as instruções (psi). A regra para (Diamond / psi) é a mesma, exceto que o jogador (existe) faz a escolha. Finalmente, dizemos que a fórmula (phi) é verdadeira em s em A se o jogador (existir) tiver uma estratégia vencedora para este jogo com base em (phi) e começando em (s).

Esses jogos são da lógica modal da mesma maneira que os jogos de Hintikka, da lógica de primeira ordem. Em particular, eles são uma maneira de fornecer uma semântica para a lógica modal e concordam com a semântica usual do tipo Kripke. É claro que existem muitos tipos e generalizações de lógica modal (incluindo lógicas estreitamente relacionadas, como lógicas temporal, epistêmica e dinâmica), e, portanto, os jogos correspondentes têm muitas formas diferentes. Um exemplo de interesse é a lógica teórica por computador de Matthew Hennessy e Robin Milner, usada para descrever o comportamento dos sistemas; aqui as setas vêm em mais de uma cor, e mover-se ao longo de uma seta de uma cor específica representa a execução de uma 'ação' específica para alterar o estado. Outro exemplo é o mais poderoso modal (mu) - cálculo de Dexter Kozen, que possui operadores de ponto fixo;veja o capítulo 5 de Stirling 2001.

Uma característica interessante desses jogos é que, se um jogador tiver uma estratégia vencedora de alguma posição em diante, essa estratégia nunca precisará se referir a nada que aconteceu no início do jogo. É irrelevante que escolhas foram feitas anteriormente, ou mesmo quantos passos foram dados. Portanto, temos o que os cientistas da computação às vezes chamam de estratégia vencedora "sem memória".

Na "lógica dos jogos" relacionada, proposta por Rohit Parikh, os jogos que nos movem entre os estados são o assunto e não uma maneira de dar uma definição da verdade. Estes jogos têm muitos aspectos interessantes. Em 2003, a revista Studia Logica publicou uma edição dedicada a eles, editada por Marc Pauly e Parikh.

As influências da economia e da ciência da computação levaram vários lógicos a usar a lógica para analisar a tomada de decisão sob condições de ignorância parcial. (Veja, por exemplo, o artigo sobre lógica epistêmica.) Existem várias maneiras de representar estados de conhecimento. Uma é tomá-los como estados ou mundos no tipo de estrutura modal que mencionamos no início desta seção. Outra é usar a lógica IF ou uma variante dela. Como essas abordagens estão relacionadas? Johan van Benthem 2006 apresenta algumas reflexões e resultados sobre essa questão muito natural. Veja também os artigos de Johan van Benthem, Krister Segerberg, Eric Pacuit e K. Venkatesh e suas referências, na Parte IV 'Lógica, Agência e Jogos' de Van Benthem, Gupta e Parikh 2011 e a entrada sobre lógica para analisar jogos para um amostra de trabalhos recentes nessa área.

6. Jogos de idas e vindas

Em 1930, Alfred Tarski formulou a noção de duas estruturas (A) e (B) sendo elementarmente equivalentes, ou seja, que exatamente as mesmas sentenças de primeira ordem são verdadeiras em (A) como são verdadeiras em (B). Em uma conferência em Princeton, em 1946, ele descreveu essa noção e expressou a esperança de que seria possível desenvolver uma teoria que fosse "tão profunda quanto as noções de isomorfismo etc. agora em uso" (Tarski, 1946).

Uma parte natural de tal teoria seria uma condição puramente estrutural necessária e suficiente para que duas estruturas fossem elementarmente equivalentes. Roland Fraïssé, um franco-argelino, foi o primeiro a encontrar uma condição necessária e suficiente utilizável. Foi redescoberto alguns anos depois pelo lógico cazaque AD Taimanov e foi reformulado em termos de jogos pelo lógico polonês Andrzej Ehrenfeucht. Os jogos agora são conhecidos como jogos de Ehrenfeucht-Fraïssé ou, às vezes, como jogos de vaivém. Eles se tornaram uma das idéias mais versáteis da lógica do século XX. Eles se adaptam frutuosamente a uma ampla gama de lógicas e estruturas.

Em um jogo de vaivém, existem duas estruturas (A) e (B), e dois jogadores que são comumente chamados de Spoiler e Duplicador. (Os nomes devem-se a Joel Spencer no início dos anos 90. Mais recentemente, Neil Immerman sugeriu Samson e Delilah, usando as mesmas iniciais; isso coloca Spoiler como o jogador masculino (forall) e Duplicador como a mulher (existe).) Cada etapa do jogo consiste em uma jogada de Spoiler, seguida por uma jogada de Duplicator. O Spoiler escolhe um elemento de uma das duas estruturas e o Duplicator deve escolher um elemento da outra estrutura. Portanto, após (n) etapas, duas sequências foram escolhidas, uma de (A) e uma de (B):

[(a_0, / ldots, a_ {n-1}; b_0, / ldots, b_ {n-1}).)

Esta posição é uma vitória para o Spoiler se, e somente se, alguma fórmula atômica (de uma das formas '(R (v_0, / ldots, v_ {k-1}))' ou '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'ou' (v_0 = v_1) 'ou uma dessas variáveis diferentes) é satisfeita por ((a_0, / ldots, a_ { n-1})) em (A), mas não por ((b_0, / ldots, b_ {n-1})) em (B) ou vice-versa. A condição para o Duplicator vencer é diferente nas diferentes formas do jogo. Na forma mais simples, (EF (A, B)), uma jogada é uma vitória para o Duplicador se, e somente se nenhuma parte inicial, for uma vitória para o Spoiler (ou seja, ela vence se não perdeu por nenhum fase finita). Para cada número natural (m) existe um jogo (EF_m (A, B)); neste jogo, o Duplicador vence após (m) etapas, desde que ela ainda não tenha perdido. Todos esses jogos são determinados pelo teorema de Gale-Stewart. Diz-se que as duas estruturas (A) e (B) são equivalentes consecutivas se o Duplicador tiver uma estratégia vencedora para (EF (A, B)), e equivalente m se ela tiver uma estratégia vencedora para (EF_m (A, B)).

Pode-se provar que se (A) e (B) são (m) - equivalentes a todo número natural (m), então eles são elementarmente equivalentes. De fato, se Eloise tiver uma estratégia vencedora (tau) no jogo Hintikka G ((phi)) em (A), onde o aninhamento dos escopos quantificadores de (phi) terá Na maioria dos níveis m, e o Duplicator possui uma estratégia vencedora (varrho) no jogo (EF_m (A, B)), as duas estratégias (tau) e (varrho) podem ser compostas em uma estratégia vencedora de Eloise em G ((phi)) em (B). Por outro lado, uma estratégia vencedora para Spoiler em (EF_m (A, B)) pode ser convertida em uma sentença de primeira ordem verdadeira em exatamente um de (A) e (B), e em que o aninhamento de escopos quantificadores tem no máximo (m) níveis. Portanto, temos nossa condição necessária e suficiente para equivalência elementar e um pouco mais além.

Se (A) e (B) são equivalentes, então certamente eles são elementares equivalentes; mas, na verdade, a equivalência entre duas partes acaba sendo igual à equivalência elementar em uma lógica infinitária que é muito mais expressiva do que a lógica de primeira ordem. Existem muitos ajustes no jogo que dão outros tipos de equivalência. Por exemplo, Barwise, Immerman e Bruno Poizat descreveram independentemente um jogo no qual os dois jogadores tinham exatamente (p) numerados seixos cada; cada jogador deve rotular suas escolhas com uma pedra e as duas opções na mesma etapa devem ser rotuladas com pedras contendo o mesmo número. À medida que o jogo avança, os jogadores ficam sem pedras e, portanto, terão que reutilizar pedras que já foram usadas. A condição para o Spoiler vencer em uma posição (e todas as posições subseqüentes) é a mesma de antes, exceto que apenas os elementos com etiquetas nessa posição contam. A existência de uma estratégia vencedora para o Duplicator neste jogo significa que as duas estruturas concordam com sentenças que usam no máximo variáveis (p) (permitindo que essas variáveis ocorram inúmeras vezes).

A teoria por trás dos jogos de vaivém usa muito poucas suposições sobre a lógica em questão. Como resultado, esses jogos são uma das poucas técnicas teóricas de modelos que se aplicam tanto às estruturas finitas quanto às infinitas, e isso os torna uma das pedras angulares da ciência da computação teórica. Pode-se usá-los para medir a força expressiva das linguagens formais, por exemplo, linguagens de consulta de banco de dados. Um resultado típico pode dizer, por exemplo, que um determinado idioma não pode distinguir entre 'par' e 'ímpar' provaríamos isso encontrando, para cada nível (n) de complexidade das fórmulas da linguagem, um par de estruturas finitas para as quais o Duplicator possui uma estratégia vencedora no jogo de vaivém do nível (n), mas uma das estruturas possui um número par de elementos e a outra possui um número ímpar. Os semânticos de línguas naturais consideraram os jogos alternativos úteis para comparar os poderes expressivos dos quantificadores generalizados. (Veja, por exemplo, Peters e Westerståhl, Seção IV de 2006).

Há também um tipo de jogo de vaivém que corresponde à nossa semântica modal acima, da mesma maneira que os jogos de Ehrenfeucht-Fraïssé correspondem à semântica de jogos de Hintikka para lógica de primeira ordem. Os jogadores começam com um estado (s) na estrutura (A) e um estado (t) na estrutura (B). O Spoiler e o Duplicador se movem alternadamente, como antes. Cada vez que ele se move, Spoiler escolhe se move em (A) ou em (B) e, em seguida, o Duplicador deve se mover na outra estrutura. Sempre é feita uma mudança avançando ao longo de uma seta a partir do estado atual. Se entre eles os dois jogadores acabaram de se mudar para um estado (s) 'em (A) e um estado (t)' em (B), e algum predicado (P_i) permanece em apenas um de (s) ´ e (t) ´, o Duplicador perde de uma só vez. Além disso, ela perde se não houver flechas disponíveis para ela avançar;mas se Spoiler descobrir que não há flechas disponíveis para ele se mover em qualquer estrutura, o Duplicator vence. Se os dois jogadores jogam este jogo com os estados iniciais (s) em (A) e (t) em (B), e ambas as estruturas têm apenas muitos estados, então pode-se mostrar que o Duplicator possui uma estratégia vencedora se, e somente se, as mesmas frases modais forem verdadeiras em (s) em (A) como são verdadeiras em (t) em (B).

Existem muitas generalizações desse resultado, algumas delas envolvendo a seguinte noção. Seja (Z) uma relação binária que relaciona estados de (A) com estados de (B). Então chamamos (Z) uma bisimulação entre (A) e (B) se o Duplicator pode usar (Z) como uma estratégia de vitória não determinística no jogo de vaivém entre (A) e (B) onde o primeiro par de movimentos dos dois jogadores é escolher seus estados iniciais. Na ciência da computação, a noção de bisimulação é crucial para a compreensão de (A) e (B) como sistemas; expressa que os dois sistemas interagem com seu ambiente da mesma maneira que um com o outro, passo a passo. Mas um pouco antes dos cientistas da computação introduzirem a noção, essencialmente o mesmo conceito apareceu na tese de doutorado de Johan van Benthem sobre a semântica da lógica modal (1976).

7. Outros jogos da teoria dos modelos

Os jogos lógicos nesta seção são ferramentas de matemáticos, mas eles têm alguns recursos conceitualmente interessantes.

7.1 Forçando jogos

Os jogos de forçar também são conhecidos pelos teóricos descritivos dos conjuntos como jogos de Banach-Mazur; veja as referências de Kechris ou Oxtoby abaixo para obter mais detalhes sobre os antecedentes matemáticos. Os teóricos do modelo os usam como uma maneira de construir estruturas infinitas com propriedades controladas. No caso mais simples (forall) e (existir) jogam o chamado Jogo de Existência de Modelo, onde (existe) afirma que uma sentença fixa (phi) tem um modelo enquanto (forall) afirma que ele pode derivar uma contradição de (phi). No começo, um conjunto contável infinito (C) de novos símbolos constantes (a_0, a_1, a_2) etc é corrigido. (existe) defende uma disjunção escolhendo uma disjunção e uma declaração existencial escolhendo uma constante de (C) como testemunha. (forall) pode desafiar uma conjunção escolhendo um conjunto,e uma declaração universal escolhendo uma testemunha arbitrária de (C). (existe) vence se nenhuma frase atômica contraditória for reproduzida. (existe) possui uma estratégia vencedora (uma Propriedade de consistência é uma maneira de descrever uma estratégia vencedora) se e somente se (phi) tiver um modelo. Por outro lado, se (forall) tiver uma estratégia vencedora, a árvore (que pode ser tornada finita) de todas as jogadas contra sua estratégia vencedora está relacionada a uma prova do estilo Gentzen da negação de (phi). Esse método de análise de sentenças está intimamente relacionado ao método de Beth dos quadros semânticos e ao Jogo Dialógico (consulte a Seção 8).se (forall) tiver uma estratégia vencedora, a árvore (que pode ser tornada finita) de todas as jogadas contra sua estratégia vencedora está relacionada a uma prova no estilo Gentzen da negação de (phi). Esse método de análise de sentenças está intimamente relacionado ao método de Beth dos quadros semânticos e ao Jogo Dialógico (consulte a Seção 8).se (forall) tiver uma estratégia vencedora, a árvore (que pode ser tornada finita) de todas as jogadas contra sua estratégia vencedora está relacionada a uma prova no estilo Gentzen da negação de (phi). Esse método de análise de sentenças está intimamente relacionado ao método de Beth dos quadros semânticos e ao Jogo Dialógico (consulte a Seção 8).

Para esboçar a idéia do jogo geral de forçar, imagine que uma equipe infinitamente infinita de construtores esteja construindo uma casa (A). Cada construtor tem sua própria tarefa a realizar: por exemplo, instalar um banheiro ou colocar um papel de parede no hall de entrada. Cada construtor tem infinitas chances de entrar no site e adicionar uma quantidade finita de material à casa; esses slots para os construtores são intercalados para que todo o processo ocorra em uma sequência de etapas contadas pelos números naturais.

Para mostrar que a casa pode ser construída por ordem, precisamos mostrar que cada construtor separadamente pode realizar sua tarefa designada, independentemente do que os outros construtores fazem. Então, imaginamos cada construtor como jogador (existe) em um jogo em que todos os outros jogadores são agrupados como (forall), e pretendemos provar que (existe) tem uma estratégia vencedora para isso. jogos. Quando provamos isso para cada construtor separadamente, podemos imaginá-los indo para o trabalho, cada um com sua própria estratégia vencedora. Todos eles vencem seus respectivos jogos e o resultado é uma casa bonita.

Mais tecnicamente, os elementos da estrutura (A) são fixados antecipadamente, digamos como (a_0, a_1, a_2) etc., mas as propriedades desses elementos devem ser definidas pela peça. Cada jogador se move lançando um conjunto de instruções atômicas ou negativas sobre os elementos, sujeito apenas à condição de que o conjunto que consiste em todas as declarações lançadas até agora deve ser consistente com um conjunto fixo de axiomas escritos antes do jogo. (Portanto, jogar uma sentença atômica negada (neg / phi) tem o efeito de impedir que qualquer jogador adicione (phi) posteriormente.) No final da peça conjunta, o conjunto de sentenças atômicas jogado em tem um modelo canônico, e esta é a estrutura (A); existem maneiras de garantir que ele seja um modelo do conjunto fixo de axiomas. Diz-se que uma possível propriedade P de (A) é aplicável se um construtor que recebe a tarefa de tornar P verdadeiro de (A) possui uma estratégia vencedora. Um ponto central (devido essencialmente a Ehrenfeucht) é que a conjunção de um conjunto contável e infinito de propriedades aplicáveis é novamente aplicável.

Vários teoremas de Löwenheim-Skolem da teoria dos modelos podem ser provados usando variantes do jogo de forçar. Nessas variantes, não construímos um modelo, mas um submodelo de um determinado modelo. Começamos com um grande modelo (M) para uma sentença (ou um conjunto de sentenças contáveis) (phi). Então listamos as sub-fórmulas de (phi) e cada jogador possui uma sub-fórmula com uma variável livre para atender. A tarefa do jogador é garantir que, assim que os parâmetros das subfórmulas ocorram no jogo, e haja uma testemunha da verdade da fórmula no grande modelo, uma dessas testemunhas seja reproduzida. Quando o jogo termina, um submodelo contável de (M) foi construído de maneira a satisfazer (phi).

O nome 'forçar' vem de uma aplicação de idéias relacionadas por Paul Cohen para construir modelos de teoria dos conjuntos no início dos anos 1960. Abraham Robinson adaptou-o para criar um método geral para a construção de estruturas contáveis, e Martin Ziegler introduziu o cenário do jogo. Mais tarde, Robin Hirsch e Ian Hodkinson usaram jogos relacionados para resolver algumas questões antigas sobre álgebras de relacionamento.

Forçar jogos é um exemplo saudável a ter em mente quando se pensa na questão de Dawkins. Eles nos lembram que, em jogos lógicos, não é necessário pensar nos jogadores como opostos.

7.2 Jogos cortados e escolhidos

No tradicional jogo de cortar e escolher, você pega um pedaço de bolo e o divide em dois pedaços menores; então eu escolho um dos pedaços e como, deixando o outro para você. Este procedimento deve pressionar você para cortar o bolo de maneira justa. Os matemáticos, sem entender bem o objetivo do exercício, insistem em iterá-lo. Assim, eu faço você cortar o pedaço que escolhi em dois, depois escolho um desses dois; então você corta esse pedaço novamente, e assim por diante indefinidamente. Alguns matemáticos ainda mais mundanos fazem com que você corte o bolo em muitos pedaços, em vez de dois.

Esses jogos são importantes na teoria das definições. Suponha que tenhamos uma coleção (A) de objetos e uma família (S) de propriedades; cada propriedade corta (A) no conjunto desses objetos que possuem a propriedade e no conjunto daqueles que não possuem. Deixe (existe) cortar, começando com o conjunto inteiro (A) e usando uma propriedade em (S) como uma faca; deixe (forall) escolher uma das partes (que são subconjuntos de (A)) e devolva a (existir) para cortar novamente, mais uma vez usando uma propriedade em (S); e assim por diante. Deixe (existir) perder assim que (forall) escolher uma peça vazia. Dizemos que ((A, S)) tem classificação no máximo (m) se (forall) tiver uma estratégia que garanta que (existir) perca antes dela (m) - th movimento. A classificação de ((A, S)) fornece informações valiosas sobre a família de subconjuntos de (A) definíveis pelas propriedades em (S).

Variações deste jogo, permitindo que uma peça seja cortada em infinitas partes menores, são fundamentais no ramo da teoria dos modelos, chamado teoria da estabilidade. Em termos gerais, uma teoria é "boa" no sentido da teoria da estabilidade se, sempre que adotamos um modelo (A) da teoria e (S) o conjunto de fórmulas de primeira ordem em uma variável livre com parâmetros de (A), a estrutura ((A, S)) possui uma classificação 'pequena'. Uma variação diferente é exigir que, em cada etapa, (existe) se divida em duas partes que sobreviveram às etapas anteriores e, novamente, ela perca assim que um dos fragmentos de corte estiver vazio. (Nesta versão (forall) é redundante.) Com essa variação, a classificação de ((A), S) é chamada de dimensão Vapnik-Chervonenkis; essa noção é usada na teoria do aprendizado computacional.

7.3 Jogos na árvore de duas funções sucessoras

Imagine uma árvore que foi construída em níveis. No nível inferior, há um nó raiz único, mas um ramo esquerdo e um ramo direito surgem dele. No próximo nível, existem dois nós, um em cada ramo, e de cada um deles um ramo esquerdo e um direito crescem. Portanto, no próximo nível, há quatro nós e, novamente, a árvore se ramifica à esquerda e à direita em cada um desses nós. Continuada até o infinito, essa árvore é chamada de árvore de duas funções sucessoras (a saber, sucessora esquerda e sucessora direita). Tomando os nós como elementos e introduzindo dois símbolos de função para o sucessor esquerdo e direito, temos uma estrutura. Um poderoso teorema de Michael Rabin afirma que existe um algoritmo que nos dirá, para cada sentença monádica de segunda ordem (phi) na linguagem apropriada para essa estrutura,se (phi) é ou não verdadeiro na estrutura. ('Segunda ordem monádica' significa que a lógica é como de primeira ordem, exceto que também podemos quantificar sobre conjuntos de elementos - mas não sobre relações binárias sobre elementos, por exemplo).

O teorema de Rabin tem inúmeras consequências úteis. Por exemplo, Dov Gabbay usou-o para provar a decidibilidade de algumas lógicas modais. Mas a prova de Rabin, usando autômatos, era notoriamente difícil de seguir. Yuri Gurevich e Leo Harrington, e independentemente Andrei Muchnik, encontraram provas muito mais simples nas quais o autômato é um jogador em um jogo.

Este resultado de Rabin é um dos vários resultados influentes que conectam jogos com autômatos. Outro exemplo são os jogos de paridade que são usados para verificar propriedades de sistemas modais. Veja, por exemplo, Stirling (2001), capítulo 6; Bradfield e Stirling (2006) discutem jogos de paridade para o cálculo modal (mu).

8. Jogos de diálogo, comunicação e prova

Vários textos medievais descrevem uma forma de debate chamada obrigação. Havia dois disputantes, Opponens e Respondens. No início de uma sessão, os disputantes concordariam com um 'positum', normalmente uma declaração falsa. O trabalho de Respondens era dar respostas racionais às perguntas da Opponens, assumindo a verdade do positum; acima de tudo, ele tinha que evitar se contradizer desnecessariamente. O trabalho da Opponens era tentar forçar os Respondens a entrar em contradições. Portanto, sabemos amplamente a resposta para a pergunta de Dawkins, mas não sabemos as regras do jogo! Os livros medievais descrevem várias regras que os disputantes devem seguir. Mas essas regras não são regras estipuladas do jogo; são diretrizes que os manuais derivam de princípios de raciocínio sólido com a ajuda de exemplos.(Paulo de Veneza justifica uma regra pela prática de "grandes lógicos, filósofos, geômetros e teólogos".) Em particular, estava aberto a um professor de obrigações para descobrir novas regras. Essa abertura implica que obrigações não são jogos lógicos em nosso sentido.

Nem todo mundo concorda com a frase anterior. Por exemplo, Catarina Dutilh Novaes (2007, 6) faz uma defesa detalhada da visão de que as obrigações apresentam “um caso notável de similaridade conceitual entre um referencial teórico medieval e um moderno”. Mas, seja qual for a opinião que adotemos sobre essa questão, esses debates inspiraram uma importante linha de pesquisa moderna em jogos lógicos.

Imagine (existe) fazendo um exame oral na teoria da prova. O examinador dá a ela uma sentença e a convida a começar a provar. Se a sentença tiver a forma

(phi / vee / psi)

então ela tem o direito de escolher uma das frases e dizer 'OK, eu vou provar essa'. (De fato, se o examinador é um intuicionista, ele pode insistir que ela escolha uma das sentenças para provar.) Por outro lado, se a sentença for

(phi / wedge / psi)

então, o examinador, sendo um examinador, pode muito bem escolher um dos conjuntos e convidá-lo a provar esse. Se ela sabe como provar a conjunção, certamente sabe como provar a conjunção.

O caso de (phi / rightarrow / psi) é um pouco mais sutil. Ela provavelmente desejará começar assumindo (phi) para deduzir (psi); mas há algum risco de confusão, porque as frases que ela escreveu até agora são todas coisas a serem provadas e (phi) não é algo a ser provado. O examinador pode ajudá-la dizendo 'Eu assumo (phi) e vamos ver se você pode chegar a (psi) a partir daí'. Nesse ponto, há uma chance de que ela veja uma maneira de chegar a (psi) deduzindo uma contradição de (phi); então ela pode virar a mesa para o examinador e convidá-lo a mostrar que sua suposição é consistente, com o objetivo de provar que não é. A simetria não é perfeita: ele estava pedindo que ela mostrasse que uma frase é verdadeira em todos os lugares, enquanto ela o convidava a mostrar que uma frase é verdadeira em algum lugar. No entanto, podemos ver uma espécie de dualidade.

Idéias desse tipo estão por trás dos jogos dialéticos de Paul Lorenzen. Ele mostrou que, com uma certa quantidade de empurrões e empurrões, pode-se escrever regras para o jogo que possuam a propriedade que (existe) tenha uma estratégia vencedora se, e somente se, a frase com a qual ela é apresentada no início for uma teorema da lógica intuicionista. Em um gesto para os debates medievais, ele chamou (existe) o Proponente e o outro jogador, o Oponente. Quase como nas obrigações medievais, o Oponente vence levando o Proponente a um ponto em que os únicos movimentos disponíveis para ela são flagrantes autocontradições.

Lorenzen alegou que seus jogos forneciam justificativas para a lógica intuicionista e clássica (ou, em suas palavras, os tornaram "gerechtfertigt", Lorenzen (1961,196)). Infelizmente, qualquer "justificativa" envolve uma resposta convincente à pergunta de Dawkins, e isso Lorenzen nunca forneceu. Por exemplo, ele falou de movimentos como 'ataques', mesmo quando (como a escolha do examinador em (phi / wedge / psi) acima) eles parecem mais ajuda do que hostilidade.

A lógica dialógica de entrada fornece uma descrição mais completa dos jogos de Lorenzen e várias variantes mais recentes. Em sua forma atual (janeiro de 2013), evita as alegações de Lorenzen sobre justificar lógicas. Em vez disso, descreve os jogos como fornecendo semântica para a lógica (um ponto com o qual Lorenzen certamente concordaria) e acrescenta que, para entender as diferenças entre as lógicas, pode ser útil comparar sua semântica.

Desse ponto de vista, os jogos de Lorenzen permanecem como um paradigma importante do que os recentes teóricos da prova chamam de semântica das provas. Uma semântica de provas dá um "significado" não apenas à noção de prova, mas a cada passo separado de uma prova. Responde à pergunta 'O que alcançamos ao fazer esse movimento específico na prova?' Durante a década de 1990, vários trabalhadores no final lógico da ciência da computação procuraram jogos que se sustentassem na lógica linear e em alguns outros sistemas de prova da mesma maneira que os jogos de Lorenzen na lógica intuicionista. Andreas Blass, e mais tarde Samson Abramsky e colegas, deram jogos que correspondiam a partes da lógica linear, mas no momento da redação ainda não possuímos uma correspondência perfeita entre jogo e lógica. Este exemplo é particularmente interessante porque a resposta à pergunta de Dawkins deve fornecer uma interpretação intuitiva das leis da lógica linear, algo que essa lógica precisa muito. Os jogos de Abramsky et al. conte uma história sobre dois sistemas em interação. Mas, embora ele tenha começado com jogos em que os jogadores se revezam educadamente, Abramsky posteriormente permitiu que os jogadores agissem 'de maneira assíncrona e distribuída', notando um ao outro apenas quando quisessem. Esses jogos não estão mais no formato normal de jogos lógicos e sua interpretação na vida real gera uma série de novas perguntas. Mas enquanto ele começava com jogos em que os jogadores se revezam educadamente, Abramsky mais tarde permitiu que eles agissem 'de maneira distribuída e assíncrona', notando um ao outro apenas quando quisessem. Esses jogos não estão mais no formato normal de jogos lógicos e sua interpretação na vida real gera uma série de novas perguntas. Mas enquanto ele começava com jogos em que os jogadores se revezam educadamente, Abramsky mais tarde permitiu que eles agissem 'de maneira distribuída e assíncrona', notando um ao outro apenas quando quisessem. Esses jogos não estão mais no formato normal de jogos lógicos e sua interpretação na vida real gera uma série de novas perguntas.

Giorgi Japaridze propôs uma 'lógica de computabilidade' para o estudo da computação. Sua sintaxe é lógica de primeira ordem, com alguns itens extras remanescentes da lógica linear. Sua semântica é em termos de jogos semânticos com algumas características incomuns. Por exemplo, nem sempre é determinado qual jogador fará o próximo movimento. A noção de funções estratégicas não é mais adequada para descrever os jogadores; em vez disso, Japaridze descreve maneiras de ler o segundo jogador (player (existe) em nossa notação) como um tipo de máquina de computação. Mais informações estão em seu site.

Outro grupo de jogos da mesma família geral que os de Lorenzen são os jogos de prova de Pavel Pudlak 2000. Aqui o Oponente (chamado Provador) está no papel de advogado em um tribunal, que sabe que o Proponente (chamado Adversário) é culpado de alguma ofensa. O proponente insistirá que ele é inocente e está preparado para contar mentiras para se defender. O objetivo do oponente é forçar o proponente a contradizer algo que o proponente está registrado como disse anteriormente; mas o oponente mantém o registro e (como nos jogos de pedrinha acima) às vezes ele precisa retirar itens do registro por falta de espaço ou memória. A questão importante não é se o Oponente tem uma estratégia vencedora (presume-se desde o início que ele tenha uma), mas quanta memória ele precisa para seu registro. Esses jogos são um dispositivo útil para mostrar limites superior e inferior nos comprimentos das provas em vários sistemas de provas.

Outro tipo de jogo lógico que permite mentiras é o Jogo com Mentiras, de Ulam. Aqui, um jogador pensa em um número em um determinado intervalo. O objetivo do segundo jogador é descobrir qual é esse número, fazendo ao primeiro jogador perguntas sim / não; mas o primeiro jogador pode contar um número fixo de mentiras em suas respostas. Como nos jogos de Pudlak, certamente existe uma estratégia vencedora para o segundo jogador, mas a questão é o quanto esse jogador tem que trabalhar para vencer. A medida desse tempo não é espaço ou memória, mas tempo: quantas perguntas ele precisa fazer? Cignoli et al. O capítulo 5 de 2000 relaciona esse jogo à lógica de muitos valores.

Voltando por um momento a Lorenzen: ele não conseguiu distinguir entre diferentes posturas que uma pessoa poderia adotar em uma discussão: declarar, assumir, conceder, consultar, atacar, comprometer-se. Se é realmente possível definir todas essas noções sem pressupor alguma lógica é um ponto discutível. Mas não importa; um refinamento dos jogos de Lorenzen nesse sentido poderia servir como uma abordagem para a lógica informal e, especialmente, para a pesquisa que visa sistematizar as estruturas possíveis de argumentos informais sólidos. Nesta frente, veja Walton e Krabbe 1995. Os trabalhos de Bench-Capon e Dunne 2007 também são relevantes.

Bibliografia

Alguns dos documentos seminais de Henkin e Lorenzen, e alguns dos citados abaixo, aparecem na coleção Métodos Infinitísticos (Atas do Simpósio de Fundamentos da Matemática, Varsóvia, 2 a 9 de setembro de 1959), Oxford: Pergamon Press, 1961 Os editores não têm nome.

Jogos na História da Lógica

  • Dutilh Novaes, Catarina, 2007, Formalizando teorias lógicas medievais: Suppositio, Consequentiae and Obligationes, Nova York: Springer-Verlag.
  • Hamblin, Charles, 1970, Fallacies, Londres: Methuen.
  • Hilbert, David, 1967, “Die Grundlagen der Mathematik”, traduzido como “Os fundamentos da matemática”, em Jean van Heijenoort (ed.), De Frege a Gödel, Cambridge Mass.: Harvard University Press, pp. 464-479.
  • Paul de Veneza, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (ed.), Nova York: Academia Britânica e Oxford University Press, 1988.
  • Weyl, Hermann, 1925–7, “Die heutige Erkenntnislage in der Mathematik”, traduzido como “A atual situação epistemológica da matemática” em Paolo Mancosu, De Brouwer a Hilbert: o debate sobre os fundamentos da matemática na década de 1920, Nova York: Oxford University Press, 1988, pp. 123-142.
  • Zermelo, Ernst, 1913, "Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels", em EW Hobson e AEH Love (eds.), Anais do Quinto Congresso Internacional de Matemáticos, Volume II, Cambridge: Cambridge University Press.

Jogos para ensinar lógica

  • Barwise, Jon e John Etchemendy, 1995, The Language of First-Order Logic, incluindo Tarski's World 3.0, Cambridge: Cambridge University Press.
  • Carroll, Lewis, 1887, The Game of Logic, Londres: Macmillan.
  • Dienes, Zoltan P. e EW Golding, 1966, Learning Logic, Logical Games, Harlow: Educational Supply Association.
  • Havas, Katalin, 1999, “Aprendendo a pensar: lógica para crianças”, em Anais do XX Congresso Mundial de Filosofia (Volume 3: Filosofia da Educação), David M. Steiner (ed.), Bowling Green Ohio: Bowling Green State University Philosophy, pp. 11–19.
  • Nifo, Agostino, 1521, Dialética Ludicra (Lógica como um jogo), Florença: Bindonis.
  • Weng, Jui-Feng, com Shian-Shyong Tseng e Tsung-Ju Lee, 2010, “Ensinando lógica booleana através do ajuste de regras de jogo”, IEEE Transactions, Learning Technologies, 3 (4): 319–328. [Usa jogos do Pac-Man para ensinar lógica booleana a estudantes do ensino médio.]

Jogos lógicos

  • Gale, David e FM Stewart, 1953, “Jogos infinitos com informações perfeitas”, em Contribuições para a Teoria dos Jogos II (Anais de Estudos Matemáticos 28), HW Kuhn e AW Tucker (eds.), Princeton: Princeton University Press, pp. 245–266.
  • Kechris, Alexander S., 1995, Teoria dos conjuntos descritivos clássicos, Nova York: Springer-Verlag.
  • Marion, Mathieu, 2009, “Por que jogar jogos lógicos?”, Em Ondrej Majer, Ahti-Veikko Pietarinen e Tero Tulenheimo eds., Games: Unifying Logic, Language and Philosophy, Nova York: Springer-Verlag, pp. 3-25.
  • Osbourne, Martin J. e Ariel Rubinstein, 1994, A Course in Game Theory, Cambridge: MIT Press.
  • Väänänen, Jouko, 2011, Models and Games, Cambridge: Cambridge University Press.
  • van Benthem, Johan, 2011, Dinâmica lógica da informação e interação, Cambridge: Cambridge University Press, 2011.
  • –––, 2014, Logic in games, Cambridge, MA: MIT Press.

Jogos Semânticos para Lógica Clássica

  • Henkin, Leon, 1961, “Algumas observações sobre fórmulas infinitamente longas”, em Infinitistic Methods, op. cit., pp. 167-183.
  • Hintikka, Jaakko, 1973, Lógica, Jogos de Linguagem e Informação: Temas Kantianos na Filosofia da Lógica, Oxford: Clarendon Press.
  • Hintikka, Jaakko, 1996, The Principles of Mathematics Revisited, Nova York: Cambridge University Press. [Veja, por exemplo, as páginas 40, 82 sobre o axioma da escolha.]
  • Hodges, Wilfrid, 2001, “Elementary Predicate Logic 25: Skolem Functions”, em Dov Gabbay, e Franz Guenthner (eds.), Manual de Philosophical Logic I, 2ª edição, Dordrecht: Kluwer, pp. 86–91. [Prova de equivalência de jogo e semântica de Tarski.]
  • Kolaitis, Ph. G., 1985, "Game quantification", em J. Barwise e S. Feferman (orgs.), Model-Theoretic Logics, Nova York: Springer-Verlag, pp. 365-421.
  • Peirce, Charles Sanders, 1898, Raciocínio e a lógica das coisas: The Cambridge Conferences Lectures of 1898, ed. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Jogos semânticos com informações imperfeitas

  • Hintikka, Jaakko e Gabriel Sandu, 1997, “Semântica teórica dos jogos”, em Johan van Benthem e Alice ter Meulen (orgs.), Handbook of Logic and Language, Amsterdã: Elsevier, pp. 361-410.
  • Hodges, Wilfrid, 1997, “Semântica composicional para uma linguagem de informação imperfeita”, Logic Journal of the IGPL, 5: 539-563.
  • Janssen, Theo MV e Francien Dechesne, 2006, "Sinalização: um negócio complicado", em J. van Benthem et al. (eds.), A Era da Lógica Alternativa: Avaliando a Filosofia da Lógica e da Matemática Hoje, Dordrecht: Kluwer, pp. 223–242.
  • Mann, Allen L., Gabriel Sandu e Merlin Sevenster, 2011, Lógica Amiga da Independência: Uma Abordagem Teórica dos Jogos (London Mathematical Society Lecture Note Series 386), Cambridge: Cambridge University Press.
  • von Neumann, John e Oskar Morgenstern, 1944, Teoria dos Jogos e Comportamento Econômico, Princeton: Princeton University Press.
  • Väänänen, Jouko, 2007, Lógica de Dependência: Uma Nova Abordagem à Lógica Amigável à Independência, Cambridge: Cambridge University Press.

Jogos semânticos para outras lógicas

  • Bradfield, Julian e Colin Stirling, 2006, “Modal mu-calculi”, em P. Blackburn et al. (eds.), Handbook of Modal Logic, Amsterdã: Elsevier, pp. 721–756.
  • Dekker, Paul e Marc Pauly (orgs.), 2002, Journal of Logic, Language and Information, 11 (3): 287-387. [Edição especial sobre lógica e jogos.]
  • Hennessy, Matthew e Robin Milner, 1985, “Leis algébricas para indeterminismo e simultaneidade”, Journal of the ACM, 32: 137–162.
  • Parikh, Rohit, 1985, “A lógica dos jogos e suas aplicações”, em Marek Karpinski e Jan van Leeuwen (eds.), “Tópicos em Teoria da Computação”, Annals of Discrete Matemáticas, 24: 111–140.
  • Pauly, Marc e Rohit Parikh (eds.), 2003, Studia Logica, 72 (2): 163–256 [Edição especial sobre Game Logic.]
  • Stirling, Colin, 2001, Modal and Temporal Properties of Processes, Nova York: Springer-Verlag.
  • van Benthem, Johan, 2006, “A lógica epistêmica dos jogos de FI”, em Randall Auxier e Lewis Hahn (eds.), The Philosophy of Jaakko Hintikka, Chicago: Open Court, pp. 481–513.
  • van Benthem, Johan com Amitabha Gupta e Rohit Parikh, 2011, Prova, Computação e Agência, Dordrecht: Springer-Verlag.

Jogos para trás e para a frente

  • Blackburn, Patrick com Maarten de Rijke e Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press.
  • Doets, Kees, 1996, Teoria Básica do Modelo, Stanford: CSLI Publications e FoLLI.
  • Ebbinghaus, Heinz-Dieter e Jörg Flum, 1999, Finite Model Theory, 2ª edição, Nova York: Springer.
  • Ehrenfeucht, Andrzej, 1961, “Uma aplicação de jogos ao problema da completude para teorias formalizadas”, Fundamenta Mathematicae, 49: 129–141.
  • Grädel, Erich com Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema e Scott Weinstein, 2007, Finite Model Theory, Berlim: Springer-Verlag.
  • Libkin, Leonid, 2004, Elements of Finite Model Theory, Berlim, Springer-Verlag.
  • Otto, Martin, 1997, Lógica Variável Limitada e Estudo de Contagem-A em Modelos Finitos (Lecture Notes in Logic, 9), Berlin: Springer-Verlag.
  • Peters, Stanley e Dag Westerståhl, 2006, Quantificadores em Linguagem e Lógica, Oxford: Clarendon Press.
  • Tarski, Alfred, 1946, “Discurso na Conferência do Bicentenário da Universidade de Princeton sobre Problemas de Matemática (17 a 19 de dezembro de 1946)”, Hourya Sinaceur (ed.), Boletim de Lógica Simbólica, 6 (2000): 1–44.
  • van Benthem, Johan, 2001, "Correspondence Theory", em Dov Gabbay e Franz Guenthner (eds.), Handbook of Philosophical Logic III, 2ª edição, Dordrecht: Kluwer.

Outros jogos de modelos teóricos

  • Anthony, Martin e Norman Biggs, 1992, Teoria da Aprendizagem Computacional, Cambridge: Cambridge University Press. [Para a dimensão Vapnik-Chervonenkis.]
  • Gurevich, Yuri e Leo Harrington, 1984, “Árvores, autômatos e jogos”, em HR Lewis (ed.), Proceedings of the ACM Symposium on Theory of Computing, São Francisco: ACM, pp. 171–182.
  • Hirsch, Robin e Ian Hodkinson, 2002, Álgebras de Relação da Games, Nova York: Holanda do Norte.
  • Hodges, Wilfrid, 1985, Building Models by Games, Cambridge: Cambridge University Press.
  • Hodges, Wilfrid, 1993, Model Theory, Cambridge: Cambridge University Press.
  • Oxtoby, JC, 1971, Medida e Categoria, Nova York: Springer-Verlag.
  • Ziegler, Martin, 1980, "Algebraisch abgeschlossene Gruppen", em SI Adian et al. (eds.), Word Problems II: The Oxford Book, Amsterdã: Holanda do Norte, pp. 449-576.

Jogos de Diálogo, Comunicação e Prova

  • Abramsky, Samson e Radha Jagadeesan, 1994, "Jogos e plenitude para a lógica linear multiplicativa", Journal of Symbolic Logic, 59: 543-574.
  • Abramsky, Samson e Paul-André Melliès, 1999, “Jogos simultâneos e total plenitude”, em Anais do Décimo Quarto Simpósio Internacional de Lógica em Ciência da Computação, Computer Science Press do IEEE, pp. 431–442.
  • Bench-Capon, TJM e Paul E. Dunne, 2007, "Argumentation in artificial intelligence", Artificial Intelligence, 171: 619-641. [A introdução de uma rica coleção de artigos sobre o mesmo tema nas páginas 642–937.]
  • Blass, Andreas, 1992, “Uma semântica de jogos para lógica linear”, Annals of Pure and Applic Logic, 56: 183–220.
  • Cignoli, Roberto LO, Itala ML D'Ottaviano e Daniele Mundici, 2000, Fundamentos Algébricos do Raciocínio de Muitos Valores, Dordrecht: Kluwer.
  • Felscher, Walter, 2001, “Diálogos como fundamento da lógica intuicionista”, em Dov Gabbay e Franz Guenthner (orgs.), Handbook of Philosophical Logic V, 2ª edição, Dordrecht: Kluwer.
  • Hodges, Wilfrid e Erik CW Krabbe, 2001, “Dialogue foundations”, Proceedings of the Aristotelian Society (Volume Complementar), 75: 17–49.
  • Japaridze, Giorgi, 2003, “Introdução à lógica da computabilidade”, Annals of Pure and Applic Logic, 123: 1–99.
  • Lorenzen, Paul, 1961 "Ein dialogisches Konstruktivitätskriterium", em Infinitistic Methods, op. cit., 1961, pp. 193–200.
  • Pudlak, Pavel, 2000, "Provas como jogos", American Mathematics Monthly, 107 (6): 541-550.
  • Walton, Douglas N. e Erik CW Krabbe, 1995, Compromisso em Diálogo: Conceitos Básicos de Raciocínio Interpessoal, Albany: State University of New York Press.

Ferramentas Acadêmicas

ícone de homem de sep
ícone de homem de sep
Como citar esta entrada.
ícone de homem de sep
ícone de homem de sep
Visualize a versão em PDF desta entrada nos Amigos da Sociedade SEP.
ícone inpho
ícone inpho
Consulte este tópico de entrada no Internet Philosophy Ontology Project (InPhO).
ícone de papéis phil
ícone de papéis phil
Bibliografia aprimorada para esta entrada na PhilPapers, com links para o banco de dados.

Outros recursos da Internet

Recomendado: