Semântica de jogos pra lógica básica
37 views
Skip to first unread message
Eduardo Ochs
Jun 4, 2022, 10:41:43 AM6/4/22
to logi...@dimap.ufrn.br
Oi todo mundo,
quando eu fiz Introdução à Análise - na início da graduação, há mil
anos atrás - o professor usou uma espécie de semântica de jogos pra
nos ensinar a interpretar expressões com quantificadores... e ele
conseguiu apresentar isso de um jeito brilhante - ele falou sobre as
idéias centrais como se elas fossem "óbvias" e depois nós fomos
descobrindo os detalhes à medida que nós fazíamos os exercícios do
livro de Análise...
Vocês fazem coisas parecidas? Quais são as referências preferidas de
vocês sobre usos _pedagógicos_ de semânticas de jogos pra ensinar
lógica básica?
Tou perguntando porque eu tou usando uma espécie de semântica de jogos
no meu curso de Cálculo 2 - tá aqui, principalmente no exercício 2,
nos slides 9 e 10,
http://angg.twu.net/LATEX/2022-1-C2-infs-e-sups.pdf#page=9
e tá funcionando muito bem, mas eu sei que eu tou reconstruindo de
forma improvisada coisas que foram publicadas em textos que eu nunca
li - e que eu gostaria de ler...
Grat =),
Eduardo Ochs
http://angg.twu.net/
http://angg.twu.net/2022.1-C2.html
http://angg.twu.net/2022.1-C3.html
quando eu fiz Introdução à Análise - na início da graduação, há mil
anos atrás - o professor usou uma espécie de semântica de jogos pra
nos ensinar a interpretar expressões com quantificadores... e ele
conseguiu apresentar isso de um jeito brilhante - ele falou sobre as
idéias centrais como se elas fossem "óbvias" e depois nós fomos
descobrindo os detalhes à medida que nós fazíamos os exercícios do
livro de Análise...
Vocês fazem coisas parecidas? Quais são as referências preferidas de
vocês sobre usos _pedagógicos_ de semânticas de jogos pra ensinar
lógica básica?
Tou perguntando porque eu tou usando uma espécie de semântica de jogos
no meu curso de Cálculo 2 - tá aqui, principalmente no exercício 2,
nos slides 9 e 10,
http://angg.twu.net/LATEX/2022-1-C2-infs-e-sups.pdf#page=9
e tá funcionando muito bem, mas eu sei que eu tou reconstruindo de
forma improvisada coisas que foram publicadas em textos que eu nunca
li - e que eu gostaria de ler...
Grat =),
Eduardo Ochs
http://angg.twu.net/
http://angg.twu.net/2022.1-C2.html
http://angg.twu.net/2022.1-C3.html
bruno.ramos.mendonca
Jun 5, 2022, 6:58:44 PM6/5/22
to LOGICA-L, eduardoochs
Olá, Eduardo:
Fiquei com a impressão que isso não é bem semântica de jogos, mas sim algo aproximado aos jogos de back and forth entre modelos. Oponente busca em um modelo de controle possíveis contra-exemplos ao modelo proposto pelo Proponente. Quando contra-exemplos não podem mais ser encontrados, P acertou: há *isomorfismo parcial* entre os modelos apresentados.
Abraços
Bruno
Eduardo Ochs
Jun 5, 2022, 7:17:26 PM6/5/22
to bruno.ramos.mendonca, LOGICA-L
Opa!!!!
Voce pode me mandar links sobre isso, ou mais keywords pra eu procurar?
Obrigado! =)
Eduardo
Voce pode me mandar links sobre isso, ou mais keywords pra eu procurar?
Obrigado! =)
Eduardo
bruno.ramos.mendonca
Jun 5, 2022, 7:28:17 PM6/5/22
to LOGICA-L, eduardoochs, LOGICA-L, bruno.ramos.mendonca
Olá, Eduardo:
Uma apresentação que eu gosto bastante é a que se encontra no livro Models and Games, de Vaananen (se encontra com facilidade uma cópia na internet). Lá ele mostra inclusive os vínculos entre esses jogos e condições de definibilidade em primeira ordem, tema que pode te interessar dado o seu objetivo pedagógico.
Abraços
Bruno
Eduardo Ochs
Jun 5, 2022, 8:35:03 PM6/5/22
to bruno.ramos.mendonca, LOGICA-L
As partes sobre back-and-forth são super bem escritas e super úteis
pro que eu tou fazendo sim! Obrigado!!! Mas ainda não consegui
encontrar as partes sobre definibilidade em primeira ordem... quando
você tiver acesso ao livro de novo você pode procurar e me mandar o
número da seção?
Grat =) =) =),
Eduardo Ochs
On Sun, 5 Jun 2022 at 20:28, bruno.ramos.mendonca
pro que eu tou fazendo sim! Obrigado!!! Mas ainda não consegui
encontrar as partes sobre definibilidade em primeira ordem... quando
você tiver acesso ao livro de novo você pode procurar e me mandar o
número da seção?
Grat =) =) =),
Eduardo Ochs
On Sun, 5 Jun 2022 at 20:28, bruno.ramos.mendonca
bruno.ramos.mendonca
Jun 6, 2022, 5:32:09 PM6/6/22
to LOGICA-L, eduardoochs, LOGICA-L, bruno.ramos.mendonca
Olá, Eduardo:
Minha memória me traiu um pouco, mas fui procurar e, na seção 4.4 do livro, ele mostra que uma série de exemplos de classes elementares não são definíveis. Para isso, ele prova que o pertencimento a essas classes não é preservado por isomorfismo parcial. O seu argumento nessa seção pressupõe a seguinte conexão entre definibilidade em primeira ordem e preservação de uma propriedade por jogos de back and forth.
No que segue, direi que A e B são r-parcialmente isomorfos se o Proponente tem uma estratégia vencedora em qualquer jogo de back and forth sobre A e B com no máximo r rounds. Além disso, direi que uma classe elementar K é definível se existe uma fórmula F de nossa linguagem formal tal que, para toda estrutura A, A satisfaz F see A \in K.
O seguinte fato vale.
1) Seja K uma classe de estruturas. Se K é definível por uma fórmula F de nossa linguagem com ranking quantificacional r, então, para algum m natural e para todo q maior ou igual a r, K=C_1\cup ... \cup C_m, em que C_i são classes de equivalência por q-isomorfismo parcial.
Demonstração. Pelo teorema das formas normais de Hintikka, para todo q maior ou igual a r, F é equivalente a uma disjunção P_1\vee ...\vee P_m em que cada P_i tem ranking quantificacional q. Pelo mesmo teorema, nós sabemos que cada P_i define uma classe de equivalência por q-isomorfismo parcial C_i. Logo, K=C_1\cup ... \cup C_m.
Ou seja, em algum sentido, a definibilidade de uma propriedade implica em sua preservação por isomorfismo parcial. E por isso é possível explorar a contrapositiva: se a propriedade não é preservada por isomorfismo parcial, então ela não é definível.
Minha memória me traiu um pouco, mas fui procurar e, na seção 4.4 do livro, ele mostra que uma série de exemplos de classes elementares não são definíveis. Para isso, ele prova que o pertencimento a essas classes não é preservado por isomorfismo parcial. O seu argumento nessa seção pressupõe a seguinte conexão entre definibilidade em primeira ordem e preservação de uma propriedade por jogos de back and forth.
No que segue, direi que A e B são r-parcialmente isomorfos se o Proponente tem uma estratégia vencedora em qualquer jogo de back and forth sobre A e B com no máximo r rounds. Além disso, direi que uma classe elementar K é definível se existe uma fórmula F de nossa linguagem formal tal que, para toda estrutura A, A satisfaz F see A \in K.
O seguinte fato vale.
1) Seja K uma classe de estruturas. Se K é definível por uma fórmula F de nossa linguagem com ranking quantificacional r, então, para algum m natural e para todo q maior ou igual a r, K=C_1\cup ... \cup C_m, em que C_i são classes de equivalência por q-isomorfismo parcial.
Demonstração. Pelo teorema das formas normais de Hintikka, para todo q maior ou igual a r, F é equivalente a uma disjunção P_1\vee ...\vee P_m em que cada P_i tem ranking quantificacional q. Pelo mesmo teorema, nós sabemos que cada P_i define uma classe de equivalência por q-isomorfismo parcial C_i. Logo, K=C_1\cup ... \cup C_m.
Ou seja, em algum sentido, a definibilidade de uma propriedade implica em sua preservação por isomorfismo parcial. E por isso é possível explorar a contrapositiva: se a propriedade não é preservada por isomorfismo parcial, então ela não é definível.
Abraços
Bruno
Reply all
Reply to author
Forward
0 new messages