Is there a model of ZFC inside which ZFC does not have a model?
47 views
Skip to first unread message
Joao Marcos
Jun 15, 2016, 1:18:53 PM6/15/16
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
Partilho uma pergunta interessante, com respostas instrutivas:
Is there a model of ZFC inside which ZFC does not have a model?
http://math.stackexchange.com/questions/1826423/is-there-a-model-of-zfc-inside-which-zfc-does-not-have-a-model
JM
Is there a model of ZFC inside which ZFC does not have a model?
http://math.stackexchange.com/questions/1826423/is-there-a-model-of-zfc-inside-which-zfc-does-not-have-a-model
JM
Samuel Gomes
Jun 15, 2016, 11:04:28 PM6/15/16
to LOGICA-L
... Essencialmente (e por favor me corrijam se eu estiver sendo excessivamente simplista), em ZFC temos
Consistência de ZFC <---> "Sentença de Gödel"
onde "Sentença de Gödel" é a asserção de ZFC que declara sua própria não-demonstrabilidade.
Ou seja, a sentença que nos garante o Primeiro Teorema de Incompletude (por não ser nem demonstrável nem refutável)
acaba dando o Segundo Teorema de Incompletude de graça (afinal, a tal sentença que não podemos nem demonstrar nem refutar
é equivalente à própria consistência do sistema). Esse aspecto do Segundo Teorema de Incompletude ser consequência imediata (da demonstração) do
Primeiro não é muito comentada por aí...
Aí, é só usar o Teorema de Completude para conseguir os tais modelos onde não há modelos.
É muito divertido isso tudo, com certeza...
Atés,
[]s Samuel
Consistência de ZFC <---> "Sentença de Gödel"
onde "Sentença de Gödel" é a asserção de ZFC que declara sua própria não-demonstrabilidade.
Ou seja, a sentença que nos garante o Primeiro Teorema de Incompletude (por não ser nem demonstrável nem refutável)
acaba dando o Segundo Teorema de Incompletude de graça (afinal, a tal sentença que não podemos nem demonstrar nem refutar
é equivalente à própria consistência do sistema). Esse aspecto do Segundo Teorema de Incompletude ser consequência imediata (da demonstração) do
Primeiro não é muito comentada por aí...
Aí, é só usar o Teorema de Completude para conseguir os tais modelos onde não há modelos.
É muito divertido isso tudo, com certeza...
Atés,
[]s Samuel
Walter Alexandre Carnielli
Jun 15, 2016, 11:26:39 PM6/15/16
to logi...@dimap.ufrn.br
Oi Samuel,
O fato de o Segundo Teorema de Incompletude ser consequência imediata do
Primeiro é, sim, bem conhecido por aí...
Abs
Walter
O fato de o Segundo Teorema de Incompletude ser consequência imediata do
Primeiro é, sim, bem conhecido por aí...
Abs
Walter
Samuel Gomes
Jun 16, 2016, 12:16:49 AM6/16/16
to LOGICA-L
Oi Walter,
Nos centros de Lógica, creio que sim ! Mas em textos de pura divulgação científica, endereçados a matemáticos iniciantes, digamos, os dois teoremas de incompletude são "vendidos" como se fossem dois resultados correlatos, porém não tão próximos - e isso do segundo ser consequência direta do primeiro, então, isso nem sequer é cogitado...
Claro que o buraco pode ser colocado mais embaixo: Acho que 99 por cento dos matemáticos não sabem o que diz o teorema da completude mesmo !
Isso causa situações estranhas. Um matemático tende a dizer que dois teoremas são equivalentes se assumindo o enunciado de um, prova-se o outro, e vice-versa - por exemplo, o teorema da função implícita e o da função inversa são equivalentes, nesse sentido.
Devido ao fato da minha formação ter sido feita toda em Matemática, esse jargão não me choca. Porém, um dia um colega que tem um conhecimento um pouco mais aprofundado de Lógica me chamou a atenção:
- Isso é besteira. Todos os teoremas que demonstramos são equivalentes entre si.
... Só quem entende o que diz o teorema da completude teria clareza disso.
Até,
[]s. Samuel
Nos centros de Lógica, creio que sim ! Mas em textos de pura divulgação científica, endereçados a matemáticos iniciantes, digamos, os dois teoremas de incompletude são "vendidos" como se fossem dois resultados correlatos, porém não tão próximos - e isso do segundo ser consequência direta do primeiro, então, isso nem sequer é cogitado...
Claro que o buraco pode ser colocado mais embaixo: Acho que 99 por cento dos matemáticos não sabem o que diz o teorema da completude mesmo !
Isso causa situações estranhas. Um matemático tende a dizer que dois teoremas são equivalentes se assumindo o enunciado de um, prova-se o outro, e vice-versa - por exemplo, o teorema da função implícita e o da função inversa são equivalentes, nesse sentido.
Devido ao fato da minha formação ter sido feita toda em Matemática, esse jargão não me choca. Porém, um dia um colega que tem um conhecimento um pouco mais aprofundado de Lógica me chamou a atenção:
- Isso é besteira. Todos os teoremas que demonstramos são equivalentes entre si.
... Só quem entende o que diz o teorema da completude teria clareza disso.
Até,
[]s. Samuel
Hermógenes Oliveira
Jun 16, 2016, 2:58:32 AM6/16/16
to logi...@dimap.ufrn.br
Dankness asked
> Yes.
> Recall that by the Completeness Theorem, having a model and being
> consistent are the same thing. Also, by Incompleteness, ZFC doesn't
> prove its own consistency. Finally, ZFC can prove the Soundness
> Theorem - that an inconsistent theory has no models!
> So - assuming ZFC has a model - ZFC is consistent. If ZFC is
> consistent, then ZFC can't prove "ZFC is consistent." By completeness,
> this means there's a model of ZFC satisfying "ZFC is inconsistent."
> Since ZFC proves the Soundness Theorem, this model must think that ZFC
> has no model!
Algém teria a bondade de esclarecer o que significam "modelos pensantes"
e por quê o teorema de *completude* está sendo invocado para *ZFC*?
--
Hermógenes Oliveira
> Is there a model of ZFC inside which ZFC does not have a model?
Noah Schweber answered:
> Yes.
> Recall that by the Completeness Theorem, having a model and being
> consistent are the same thing. Also, by Incompleteness, ZFC doesn't
> prove its own consistency. Finally, ZFC can prove the Soundness
> Theorem - that an inconsistent theory has no models!
> So - assuming ZFC has a model - ZFC is consistent. If ZFC is
> consistent, then ZFC can't prove "ZFC is consistent." By completeness,
> this means there's a model of ZFC satisfying "ZFC is inconsistent."
> Since ZFC proves the Soundness Theorem, this model must think that ZFC
> has no model!
Algém teria a bondade de esclarecer o que significam "modelos pensantes"
e por quê o teorema de *completude* está sendo invocado para *ZFC*?
--
Hermógenes Oliveira
Francisco Antonio Doria
Jun 16, 2016, 3:12:22 AM6/16/16
to logi...@dimap.ufrn.br
Essas propriedades estranhas aparecem a toda hora, e inesperadamente. Recentemente Newton e eu provamos o seguinte - já me referi a esse resultado: seja S um sistema formal (pode ser ZFC) com um conjunto r.e. de teoremas, ``bastante aritmética,'' linguagem de 1a ordem, consistente, etc. Então S + S é \Sigma_1-sound prova que S não tem uma prova de P<NP. Isso não quer dizer que a prova não exista; significa apenas que S + S é \Sigma_1-sound não consegue fazer com que S a veja.
--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/db691fb5-73dc-43f8-9709-29eb384d9422%40dimap.ufrn.br.
fad
ahhata alati, awienta Wilushati
ahhata alati, awienta Wilushati
Francisco Antonio Doria
Jun 16, 2016, 3:29:22 AM6/16/16
to logi...@dimap.ufrn.br
Sistemas formais são coisa muito estranha. Parecem inocentinhos, mas...
Marcelo Finger
Jun 16, 2016, 6:48:52 AM6/16/16
to logi...@dimap.ufrn.br
Oi Samuel.
É muito divertido isso tudo, com certeza...
Exatamente o que eu pensei :-)
[]s
--
Marcelo Finger
Departament of Computer Science, IME
University of Sao Paulo
http://www.ime.usp.br/~mfinger
Departament of Computer Science, IME
University of Sao Paulo
http://www.ime.usp.br/~mfinger
Samuel Gomes
Jun 16, 2016, 7:23:22 AM6/16/16
to LOGICA-L
Oi Hermógenes,
--> A coisa dos "modelos pensantes" é simplesmente um jargão. Dizer que um modelo M "pensa" uma certa asserção phi é simplesmente
dizer que M modela phi, i.e., que phi é válida em M, que phi é verificada em M.
Exemplo: por Lowenheim-Skolem "pra baixo", a teoria dos reais (em primeira ordem) tem modelo enumerável. Então podemos ter uma
estrutura enumerável M no qual todas as sentenças sobre os reais são válidas, quando relativizadas a M (existe x = existe x em M, para todo x =
para todo x em M, e assim por diante).
O que choca inicialmente as pessoas é: como pode existir um modelo enumerável de algo que é não-enumerável ? Esse seria o tal do
Paradoxo de Skolem...
Pois é, o que ocorre é que o tal modelo enumerável "pensa" que é não-enumerável. Pois todas as funções que
sobrejetam os naturais em M estão FORA do modelo: eu olhando de fora sei que ele é enumerável, mas "lá dentro" as tais
funções que o enumeram não estão, essas funções não pertencem a M. "Na opinião dele", ele é enumerável - pois a sentença "Não existe bijeção entre a estrutura
e os naturais" é verificada, é válida lá.
(É a velha historinha de que a formiguinha que está andando sobre a mesa não consegue enxergar a terceira dimensão: ela "pensa" que
o mundo é bidimensional, porque o modelo onde ela vive é assim).
--> você pergunta "por quê" estamos usando o Teorema de Completude para ZFC, então não tenho certeza
se realmente a sua pergunta é sobre "por quê" ou "como", então vou aproveitar a oportunidade para
dar respostas rápidas para ambas...
"Por quê ?": se a pergunta foi essa, talvez você esteja confundindo completude SEMÂNTICA (= "se é consistente, tem modelo") com
completude SINTÁTICA (="toda sentença pode ser provada ou refutada").
ZFC = ZFC de primeira ordem aí no nosso contexto, portanto, por ser uma teoria de primeira ordem, vale o Teorema de Completude para
ZFC - o que dá a completude semântica de ZFC. Notar que
"Se é consistente, tem modelo" é um enunciado equivalente a "Consequências semânticas são consequências sintáticas"
(aqui estou falando como lógico; se eu estivesse falando como matemático, eu possivelmente diria que os dois teoremas acima
são equivalentes, hehe, mas na verdade sabemos que são dois enunciados equivalentes para o mesmo teorema, digamos)
As recíprocas são o Teorema da Correção (Soundness), cujos enunciados equivalentes são
"Se tem modelo, é consistente" <=====> "Consequências sintáticas são consequências semânticas"
(o que é mesmo o lado fácil: se phi é uma consequência sintática de T (i.e., se T prova phi), então a correção do sistema
garante que phi vai ser válida em todos os modelos de T (i.e., phi é consequência semântica de T))
... Ou seja, o Teorema de Completude garante a completude semântica de ZFC com primeira ordem, enquanto que
o Teorema de Incompletude mostrou a incompletude sintática de ZFC.
--> "Como": Seja Con(ZFC) a declaração de que ZFC é consistente (que eu comentei na outra mensagem ser equivalente à
Sentença de Gödel).
Então, pelo primeiro ou pelo segundo teorema de incompletude, meio que tanto faz porque no fundo é a mesma
coisa,
ZFC não prova Con(ZFC) - ou seja, Con(ZFC) não é consequência sintática de ZFC. ("Claro que na verdade não prova nem refuta, mas sigamos só disso")
Por Completude, se não é consequência sintática então não é consistência semântica.
Então não é verdade que Con(ZFC) seja válido em todos os modelos de ZFC.
Portanto, existe um modelo de ZFC no qual Con(ZFC) não é válido. Esse é um tal modelo que "pensa que não existe" - pois, dentro dele,
a asserção "existem modelos de ZFC" (que é equivalente a "ZFC é consistente", por Soundness + Completeness) não é verificada.
... Notar que, também por completude, deverão existir modelos de ZFC onde Con(ZFC) é válido e também deverão
existir modelos de ZFC onde Con(ZFC) não é válido ("se todos os modelos concordassem, existiria uma prova", essencialmente é isso
que Completude diz). Aí podemos aplicar Soundness e chegar em Con(Con(ZFC)) e Con(não Con(ZFC)), ou seja,
Con(ZFC) é independente de ZFC.
... Espero que ajude,
Até,
--> A coisa dos "modelos pensantes" é simplesmente um jargão. Dizer que um modelo M "pensa" uma certa asserção phi é simplesmente
dizer que M modela phi, i.e., que phi é válida em M, que phi é verificada em M.
Exemplo: por Lowenheim-Skolem "pra baixo", a teoria dos reais (em primeira ordem) tem modelo enumerável. Então podemos ter uma
estrutura enumerável M no qual todas as sentenças sobre os reais são válidas, quando relativizadas a M (existe x = existe x em M, para todo x =
para todo x em M, e assim por diante).
O que choca inicialmente as pessoas é: como pode existir um modelo enumerável de algo que é não-enumerável ? Esse seria o tal do
Paradoxo de Skolem...
Pois é, o que ocorre é que o tal modelo enumerável "pensa" que é não-enumerável. Pois todas as funções que
sobrejetam os naturais em M estão FORA do modelo: eu olhando de fora sei que ele é enumerável, mas "lá dentro" as tais
funções que o enumeram não estão, essas funções não pertencem a M. "Na opinião dele", ele é enumerável - pois a sentença "Não existe bijeção entre a estrutura
e os naturais" é verificada, é válida lá.
(É a velha historinha de que a formiguinha que está andando sobre a mesa não consegue enxergar a terceira dimensão: ela "pensa" que
o mundo é bidimensional, porque o modelo onde ela vive é assim).
--> você pergunta "por quê" estamos usando o Teorema de Completude para ZFC, então não tenho certeza
se realmente a sua pergunta é sobre "por quê" ou "como", então vou aproveitar a oportunidade para
dar respostas rápidas para ambas...
"Por quê ?": se a pergunta foi essa, talvez você esteja confundindo completude SEMÂNTICA (= "se é consistente, tem modelo") com
completude SINTÁTICA (="toda sentença pode ser provada ou refutada").
ZFC = ZFC de primeira ordem aí no nosso contexto, portanto, por ser uma teoria de primeira ordem, vale o Teorema de Completude para
ZFC - o que dá a completude semântica de ZFC. Notar que
"Se é consistente, tem modelo" é um enunciado equivalente a "Consequências semânticas são consequências sintáticas"
(aqui estou falando como lógico; se eu estivesse falando como matemático, eu possivelmente diria que os dois teoremas acima
são equivalentes, hehe, mas na verdade sabemos que são dois enunciados equivalentes para o mesmo teorema, digamos)
As recíprocas são o Teorema da Correção (Soundness), cujos enunciados equivalentes são
"Se tem modelo, é consistente" <=====> "Consequências sintáticas são consequências semânticas"
(o que é mesmo o lado fácil: se phi é uma consequência sintática de T (i.e., se T prova phi), então a correção do sistema
garante que phi vai ser válida em todos os modelos de T (i.e., phi é consequência semântica de T))
... Ou seja, o Teorema de Completude garante a completude semântica de ZFC com primeira ordem, enquanto que
o Teorema de Incompletude mostrou a incompletude sintática de ZFC.
--> "Como": Seja Con(ZFC) a declaração de que ZFC é consistente (que eu comentei na outra mensagem ser equivalente à
Sentença de Gödel).
Então, pelo primeiro ou pelo segundo teorema de incompletude, meio que tanto faz porque no fundo é a mesma
coisa,
ZFC não prova Con(ZFC) - ou seja, Con(ZFC) não é consequência sintática de ZFC. ("Claro que na verdade não prova nem refuta, mas sigamos só disso")
Por Completude, se não é consequência sintática então não é consistência semântica.
Então não é verdade que Con(ZFC) seja válido em todos os modelos de ZFC.
Portanto, existe um modelo de ZFC no qual Con(ZFC) não é válido. Esse é um tal modelo que "pensa que não existe" - pois, dentro dele,
a asserção "existem modelos de ZFC" (que é equivalente a "ZFC é consistente", por Soundness + Completeness) não é verificada.
... Notar que, também por completude, deverão existir modelos de ZFC onde Con(ZFC) é válido e também deverão
existir modelos de ZFC onde Con(ZFC) não é válido ("se todos os modelos concordassem, existiria uma prova", essencialmente é isso
que Completude diz). Aí podemos aplicar Soundness e chegar em Con(Con(ZFC)) e Con(não Con(ZFC)), ou seja,
Con(ZFC) é independente de ZFC.
... Espero que ajude,
Até,
[]s Samuel
On Wednesday, June 15, 2016 at 2:18:53 PM UTC-3, Joao Marcos wrote:
Francisco Antonio Doria
Jun 16, 2016, 7:42:31 AM6/16/16
to logi...@dimap.ufrn.br
Ou seja: como a incompletude, esses outros resultados estranhos têm consequências fora da lógica.
--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/e2a686f9-f6b3-4e1b-8d8f-0158d95bad74%40dimap.ufrn.br.
Hermógenes Oliveira
Jun 16, 2016, 9:16:48 AM6/16/16
to logi...@dimap.ufrn.br
Samuel Gomes escreveu:
> Oi Hermógenes,
Oi, Samuel. Obrigado pelos esclarecimentos! Ainda tenho algumas
questões, se não for abusar demais da sua paciência (e da lista).
> --> A coisa dos "modelos pensantes" é simplesmente um jargão. Dizer
> que um modelo M "pensa" uma certa asserção phi é simplesmente
> dizer que M modela phi, i.e., que phi é válida em M, que phi é
> verificada em M.
Hum. Acho o jargão meio esquisito, mas tudo bem.
Então, baseado nas suas explicações abaixo, a frase "this model must
think that ZFC has no model" significa que um certo modelo M de ZFC
modela, ou satisfaz, a sentença gödeliana ⌜φ⌝ que "expressa" a
inconsistência de ZFC. É isso?
> Exemplo: por Lowenheim-Skolem "pra baixo", a teoria dos reais (em
> primeira ordem) tem modelo enumerável. Então podemos ter uma estrutura
> enumerável M no qual todas as sentenças sobre os reais são válidas,
> quando relativizadas a M (existe x = existe x em M, para todo x = para
> todo x em M, e assim por diante).
>
> O que choca inicialmente as pessoas é: como pode existir um modelo
> enumerável de algo que é não-enumerável ? Esse seria o tal do Paradoxo
> de Skolem...
>
> Pois é, o que ocorre é que o tal modelo enumerável "pensa" que é
> não-enumerável. Pois todas as funções que sobrejetam os naturais em M
> estão FORA do modelo: eu olhando de fora sei que ele é enumerável, mas
> "lá dentro" as tais funções que o enumeram não estão, essas funções
> não pertencem a M. "Na opinião dele", ele é enumerável - pois a
> sentença "Não existe bijeção entre a estrutura e os naturais" é
> verificada, é válida lá.
Imagino que aqui você quis dizer: "Na opinião dele, ele *não* é
enumerável — pois a sentença "Não existe bijeção entre a estrutura e os
> (É a velha historinha de que a formiguinha que está andando sobre a
> mesa não consegue enxergar a terceira dimensão: ela "pensa" que
> o mundo é bidimensional, porque o modelo onde ela vive é assim).
>
> --> você pergunta "por quê" estamos usando o Teorema de Completude
> para ZFC, então não tenho certeza
> se realmente a sua pergunta é sobre "por quê" ou "como", então vou
> aproveitar a oportunidade para
> dar respostas rápidas para ambas...
>
> "Por quê ?": se a pergunta foi essa, talvez você esteja confundindo
> completude SEMÂNTICA (= "se é consistente, tem modelo") com
> completude SINTÁTICA (="toda sentença pode ser provada ou refutada").
De fato, eu estava pensando em completude sintática.
Quando o Noah Schweber começou uma frase com "by completeness" e a frase
seguinte com "by incompleteness", minha cabeça girou...
Por isso, prefiro chamar o primeiro teorema de Gödel de teorema de
*indecidibilidade*, pois, caso contrário, sempre acabo metendo os pés
pelas mãos com a distinção que você faz acima.
> [...]
causa da dissolução do jargão, sua explicação não soa tão misteriosa.
Além do jargão, algo que me escapou na resposta do Noah e que ficou mais
claro na sua é como usar consistência, que Gödel mostrou como codificar
para dentro da teoria, e completude semântica (consistência ≡ existência
de modelo) para "expressar" noções como "(não) tem modelo" dentro da
teoria.
Agora, devo admitir que essa conversa toda de "modelo pensante" e
"modelo de ZFC dentro do qual ZFC não tem modelo", me soa *muito*
suspeita: terminologia, alegações e asserções tão misteriosas (eu diria
até mesmo místicas) para expressar algo tão simples. Deve ser por isso
que eu fujo de teoria dos modelos que nem o diabo da cruz...
> ... Espero que ajude,
Ajudou bastante. Obrigado, novamente.
Abraços,
--
Hermógenes Oliveira
> Oi Hermógenes,
Oi, Samuel. Obrigado pelos esclarecimentos! Ainda tenho algumas
questões, se não for abusar demais da sua paciência (e da lista).
> --> A coisa dos "modelos pensantes" é simplesmente um jargão. Dizer
> que um modelo M "pensa" uma certa asserção phi é simplesmente
> dizer que M modela phi, i.e., que phi é válida em M, que phi é
> verificada em M.
Então, baseado nas suas explicações abaixo, a frase "this model must
think that ZFC has no model" significa que um certo modelo M de ZFC
modela, ou satisfaz, a sentença gödeliana ⌜φ⌝ que "expressa" a
inconsistência de ZFC. É isso?
> Exemplo: por Lowenheim-Skolem "pra baixo", a teoria dos reais (em
> primeira ordem) tem modelo enumerável. Então podemos ter uma estrutura
> enumerável M no qual todas as sentenças sobre os reais são válidas,
> quando relativizadas a M (existe x = existe x em M, para todo x = para
> todo x em M, e assim por diante).
>
> O que choca inicialmente as pessoas é: como pode existir um modelo
> enumerável de algo que é não-enumerável ? Esse seria o tal do Paradoxo
> de Skolem...
>
> Pois é, o que ocorre é que o tal modelo enumerável "pensa" que é
> não-enumerável. Pois todas as funções que sobrejetam os naturais em M
> estão FORA do modelo: eu olhando de fora sei que ele é enumerável, mas
> "lá dentro" as tais funções que o enumeram não estão, essas funções
> não pertencem a M. "Na opinião dele", ele é enumerável - pois a
> sentença "Não existe bijeção entre a estrutura e os naturais" é
> verificada, é válida lá.
enumerável — pois a sentença "Não existe bijeção entre a estrutura e os
naturais" é verificada, é válida lá."
Ou eu perdi alguma sutileza?
> (É a velha historinha de que a formiguinha que está andando sobre a
> mesa não consegue enxergar a terceira dimensão: ela "pensa" que
> o mundo é bidimensional, porque o modelo onde ela vive é assim).
>
> --> você pergunta "por quê" estamos usando o Teorema de Completude
> para ZFC, então não tenho certeza
> se realmente a sua pergunta é sobre "por quê" ou "como", então vou
> aproveitar a oportunidade para
> dar respostas rápidas para ambas...
>
> "Por quê ?": se a pergunta foi essa, talvez você esteja confundindo
> completude SEMÂNTICA (= "se é consistente, tem modelo") com
> completude SINTÁTICA (="toda sentença pode ser provada ou refutada").
Quando o Noah Schweber começou uma frase com "by completeness" e a frase
seguinte com "by incompleteness", minha cabeça girou...
Por isso, prefiro chamar o primeiro teorema de Gödel de teorema de
*indecidibilidade*, pois, caso contrário, sempre acabo metendo os pés
pelas mãos com a distinção que você faz acima.
> [...]
>
> ZFC não prova Con(ZFC) - ou seja, Con(ZFC) não é consequência
> sintática de ZFC. ("Claro que na verdade não prova nem refuta, mas
> sigamos só disso")
>
> Por Completude, se não é consequência sintática então não é
> consistência semântica.
>
> Então não é verdade que Con(ZFC) seja válido em todos os modelos de
> ZFC.
>
> Portanto, existe um modelo de ZFC no qual Con(ZFC) não é válido. Esse
> é um tal modelo que "pensa que não existe" - pois, dentro dele, a
> asserção "existem modelos de ZFC" (que é equivalente a "ZFC é
> consistente", por Soundness + Completeness) não é verificada.
>
> ... Notar que, também por completude, deverão existir modelos de ZFC
> onde Con(ZFC) é válido e também deverão existir modelos de ZFC onde
> Con(ZFC) não é válido ("se todos os modelos concordassem, existiria
> uma prova", essencialmente é isso que Completude diz). Aí podemos
> aplicar Soundness e chegar em Con(Con (ZFC)) e Con(não Con(ZFC)), ou
> ZFC não prova Con(ZFC) - ou seja, Con(ZFC) não é consequência
> sintática de ZFC. ("Claro que na verdade não prova nem refuta, mas
> sigamos só disso")
>
> Por Completude, se não é consequência sintática então não é
> consistência semântica.
>
> Então não é verdade que Con(ZFC) seja válido em todos os modelos de
> ZFC.
>
> Portanto, existe um modelo de ZFC no qual Con(ZFC) não é válido. Esse
> é um tal modelo que "pensa que não existe" - pois, dentro dele, a
> asserção "existem modelos de ZFC" (que é equivalente a "ZFC é
> consistente", por Soundness + Completeness) não é verificada.
>
> ... Notar que, também por completude, deverão existir modelos de ZFC
> onde Con(ZFC) é válido e também deverão existir modelos de ZFC onde
> Con(ZFC) não é válido ("se todos os modelos concordassem, existiria
> uma prova", essencialmente é isso que Completude diz). Aí podemos
> seja, Con(ZFC) é independente de ZFC.
Achei a sua explicação bem melhor do que a do Noah. Ademais, talvez por
causa da dissolução do jargão, sua explicação não soa tão misteriosa.
Além do jargão, algo que me escapou na resposta do Noah e que ficou mais
claro na sua é como usar consistência, que Gödel mostrou como codificar
para dentro da teoria, e completude semântica (consistência ≡ existência
de modelo) para "expressar" noções como "(não) tem modelo" dentro da
teoria.
Agora, devo admitir que essa conversa toda de "modelo pensante" e
"modelo de ZFC dentro do qual ZFC não tem modelo", me soa *muito*
suspeita: terminologia, alegações e asserções tão misteriosas (eu diria
até mesmo místicas) para expressar algo tão simples. Deve ser por isso
que eu fujo de teoria dos modelos que nem o diabo da cruz...
> ... Espero que ajude,
Ajudou bastante. Obrigado, novamente.
Abraços,
--
Hermógenes Oliveira
Joao Marcos
Jun 16, 2016, 12:50:38 PM6/16/16
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
> "Por quê ?": se a pergunta foi essa, talvez você esteja confundindo
> completude SEMÂNTICA (= "se é consistente, tem modelo") com
> completude SINTÁTICA (="toda sentença pode ser provada ou refutada").
Mas no segundo sentido (assumindo que, para eliminar inteiramente a
> completude SEMÂNTICA (= "se é consistente, tem modelo") com
> completude SINTÁTICA (="toda sentença pode ser provada ou refutada").
semântica desta conversa, por "refutação de S" estamos nos referindo à
"demonstração de ~S") nem mesmo a própria teoria correspondente à
*lógica clássica de primeira ordem* seria completa, né?
JM
Samuel Gomes
Jun 16, 2016, 1:51:05 PM6/16/16
to LOGICA-L
Olás,
Hermógenes: ali eu digitei errado mesmo, o que eu quis dizer era que "o modelo enumerável pensa que é não-enumerável". A gente fala
tanto de enumerável e não-enumerável que em algum momento acaba pensando numa coisa e escrevendo outra...
Você disse:
********************************************
Hermógenes: ali eu digitei errado mesmo, o que eu quis dizer era que "o modelo enumerável pensa que é não-enumerável". A gente fala
tanto de enumerável e não-enumerável que em algum momento acaba pensando numa coisa e escrevendo outra...
Você disse:
********************************************
Então, baseado nas suas explicações abaixo, a frase "this model must
think that ZFC has no model" significa que um certo modelo M de ZFC
modela, ou satisfaz, a sentença gödeliana ⌜φ⌝ que "expressa" a
inconsistência de ZFC. É isso?
********************************************
É isso, precisamente.
Disse também:
***************************************************************************************
É isso, precisamente.
Disse também:
***************************************************************************************
Achei a sua explicação bem melhor do que a do Noah. Ademais, talvez por
causa da dissolução do jargão, sua explicação não soa tão misteriosa.
***************************************************************************************
... Na verdade a minha explicação é essencialmente a dele, eu só quis
deixar mais claro onde se usa completeness, soundness, essas coisas.
João Marcos:
************************************************************************************
... Na verdade a minha explicação é essencialmente a dele, eu só quis
deixar mais claro onde se usa completeness, soundness, essas coisas.
João Marcos:
************************************************************************************
Mas no segundo sentido (assumindo que, para eliminar inteiramente a
semântica desta conversa, por "refutação de S" estamos nos referindo à
"demonstração de ~S") nem mesmo a própria teoria correspondente à
*lógica clássica de primeira ordem* seria completa, né?
************************************************************************************
... Imagino que aí tenha gente que consiga explicar melhor do que eu,
mas essencialmente os teoremas de incompletude necessitam de um
pouco de Aritmética, não ? Então, só pegando a Lógica de primeira ordem,
não vejo (pelo menos não agora de imediato) como justificar uma incompletude
sintática.
Deixe-me fazer a boa velha pesquisa no Google...
Colocando no Google
"first order logic is sintactically incomplete"
vem uma página de um artigo de Bealer e Monnich no Handbook of Philosophical Logic, vol.10, que diz que (no meio de uma discussão
muito maior sobre intensionalidade e extensionalidade):
"... a straightforward adaptation of the proof of Godel's theorem we can show that first-order logic with identity and a copula is essentially incomplete..."
Bem, então a Aritmética não seja tão imprescindível assim (para a incompletude), mas algo a mais (no caso aí, a tal da cópula) seja necessário. Deixo esta discussão
para os mais entendidos !
Atés,
... Imagino que aí tenha gente que consiga explicar melhor do que eu,
mas essencialmente os teoremas de incompletude necessitam de um
pouco de Aritmética, não ? Então, só pegando a Lógica de primeira ordem,
não vejo (pelo menos não agora de imediato) como justificar uma incompletude
sintática.
Deixe-me fazer a boa velha pesquisa no Google...
Colocando no Google
"first order logic is sintactically incomplete"
vem uma página de um artigo de Bealer e Monnich no Handbook of Philosophical Logic, vol.10, que diz que (no meio de uma discussão
muito maior sobre intensionalidade e extensionalidade):
"... a straightforward adaptation of the proof of Godel's theorem we can show that first-order logic with identity and a copula is essentially incomplete..."
Bem, então a Aritmética não seja tão imprescindível assim (para a incompletude), mas algo a mais (no caso aí, a tal da cópula) seja necessário. Deixo esta discussão
para os mais entendidos !
Atés,
[]s Samuel
On Wednesday, June 15, 2016 at 2:18:53 PM UTC-3, Joao Marcos wrote:
Hermógenes Oliveira
Jun 16, 2016, 3:19:56 PM6/16/16
to logi...@dimap.ufrn.br
Samuel Gomes escreveu:
> Olás,
Olá.
> Hermógenes: [...]
Novamente, obrigado pela resposta.
> João Marcos:
>
> *****************************************************************************
A lógica de primeira ordem pura, na sua formulação padrão, é obviamente
incompleta (sintaticamente), pois, dada uma variável proposicional p,
não é possível obter uma demonstração ou refutação de p.
A questão da completude sintática só faz mesmo sentido quando temos uma
teoria formal na qual a lógica de primeira ordem é calibrada para
própositos aritméticos (matemáticos). Por exemplo, na aritmética de
Peano, onde não há variáveis proposicionais e todas as sentenças
atômicas são compostas usando a constante 0, a função sucessor S e
demais funções artiméticas. Ou em ZF, onde as sentenças atômicas tratam
de conjuntos e suas relações de pertinência. Em outras palavras, na AP
todos os termos e variáveis estão para números, a igualdade e os
predicados se aplicam a números. Analogamente para ZF, mas com
conjuntos.
Para teorias aritméticas (matemáticas), faz sentido esperar que, dada
uma sentença qualquer A, A ou ¬A seja demonstrável, pois não há nenhuma
sentença contingente.
Estou sendo ingênuo? Ou não entendi direito a pergunta do João Marcos?
--
Hermógenes Oliveira
> Olás,
Olá.
> Hermógenes: [...]
Novamente, obrigado pela resposta.
> João Marcos:
>
> *****************************************************************************
> Mas no segundo sentido (assumindo que, para eliminar inteiramente a
> semântica desta conversa, por "refutação de S" estamos nos referindo à
> "demonstração de ~S") nem mesmo a própria teoria correspondente à
> *lógica clássica de primeira ordem* seria completa, né?
> *****************************************************************************
>
> semântica desta conversa, por "refutação de S" estamos nos referindo à
> "demonstração de ~S") nem mesmo a própria teoria correspondente à
> *lógica clássica de primeira ordem* seria completa, né?
> *****************************************************************************
>
> ... Imagino que aí tenha gente que consiga explicar melhor do que eu,
> mas essencialmente os teoremas de incompletude necessitam de um pouco
> de Aritmética, não ? Então, só pegando a Lógica de primeira ordem, não
> vejo (pelo menos não agora de imediato) como justificar uma
> incompletude sintática.
Ué. Eu pensei a coisa muito mais simples do que isso:
> mas essencialmente os teoremas de incompletude necessitam de um pouco
> de Aritmética, não ? Então, só pegando a Lógica de primeira ordem, não
> vejo (pelo menos não agora de imediato) como justificar uma
> incompletude sintática.
A lógica de primeira ordem pura, na sua formulação padrão, é obviamente
incompleta (sintaticamente), pois, dada uma variável proposicional p,
não é possível obter uma demonstração ou refutação de p.
A questão da completude sintática só faz mesmo sentido quando temos uma
teoria formal na qual a lógica de primeira ordem é calibrada para
própositos aritméticos (matemáticos). Por exemplo, na aritmética de
Peano, onde não há variáveis proposicionais e todas as sentenças
atômicas são compostas usando a constante 0, a função sucessor S e
demais funções artiméticas. Ou em ZF, onde as sentenças atômicas tratam
de conjuntos e suas relações de pertinência. Em outras palavras, na AP
todos os termos e variáveis estão para números, a igualdade e os
predicados se aplicam a números. Analogamente para ZF, mas com
conjuntos.
Para teorias aritméticas (matemáticas), faz sentido esperar que, dada
uma sentença qualquer A, A ou ¬A seja demonstrável, pois não há nenhuma
sentença contingente.
Estou sendo ingênuo? Ou não entendi direito a pergunta do João Marcos?
--
Hermógenes Oliveira
Samuel Gomes
Jun 16, 2016, 3:25:24 PM6/16/16
to LOGICA-L
Oi Hermógenes,
Como eu disse, tem gente melhor do que eu na comunidade pra discutir isso (Doria, Rodrigo Freire, entre outros).
Eu sempre pensei em incompletude a partir de um pouquinho de Aritmética. Para a lógica de primeira ordem, sempre pensei
em termos da outra completude (a semântica).
Seu argumento com variáveis proposicionais aparentemente procede, mas não seria o caso
de se pensar em demonstrações/refutações do fecho universal de fórmulas que tenham pelo menos algum símbolo relacional ou funcional ?
Como eu disse, tem gente melhor do que eu na comunidade pra discutir isso (Doria, Rodrigo Freire, entre outros).
Eu sempre pensei em incompletude a partir de um pouquinho de Aritmética. Para a lógica de primeira ordem, sempre pensei
em termos da outra completude (a semântica).
Seu argumento com variáveis proposicionais aparentemente procede, mas não seria o caso
de se pensar em demonstrações/refutações do fecho universal de fórmulas que tenham pelo menos algum símbolo relacional ou funcional ?
Atés,
[]s Samuel
On Wednesday, June 15, 2016 at 2:18:53 PM UTC-3, Joao Marcos wrote:
Famadoria
Jun 16, 2016, 3:50:17 PM6/16/16
to logi...@dimap.ufrn.br
Colapso de cardinais: vc vê na prova, direitinho, essas aplicações que existem ou não, conforme o modelo.
Sent from my iPhone
> --
> Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google.
> Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/87h9ctl1e0.fsf%40camelot.oliveira.
Sent from my iPhone
> Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google.
> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
> Para postar neste grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
> Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/87h9ctl1e0.fsf%40camelot.oliveira.
Joao Marcos
Jun 16, 2016, 3:59:22 PM6/16/16
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
PessoALL:
Eu também diria que há aqui gente muito mais competente do que eu para
falar sobre tudo isto (e sobre qualquer outra coisa a respeito da qual
eu possa falar). Faço contudo um esclarecimento breve. Se pensamos
em *teorias* como conjuntos de fórmulas fechados sob derivabilidade,
então as teorias clássicas proposicionais são ("sintaticamente")
completas no sentido de Post. Estas coisas são bem conhecidas e estão
discutidas, por exemplo, no artigo do Zach, "Completeness before
Post".
No caso clássico *de primeira ordem*, contudo, isto não vale em geral.
Aparentemente este resultado aparece pela primeira vez no livro
clássico de Hilbert & Ackermann de 1928. Vale notar que a "completude
sintática" equivale à "completude de Post", a saber, a propriedade de
uma teoria não poder ser dedutivamente estendida sem se tornar
inconsistente. Há em Teoria dos Modelos um critério útil para a
completude de Post, dado pelo chamado "Teste de Łoś–Vaught" (a saber,
para a "completude sintática" é suficiente uma teoria ser satisfatível
sem ter modelos finitos e também ser categórica para algum cardinal
com cardinalidade maior ou igual à cardinalidade da linguagem).
* * *
Sei que com estas observações já vou mudando o rumo da discussão
original, mas uma mensagem da FOM que eu mencionei aqui há duas
semanas trata de alguns pontos históricos interessantes sobre as
várias "completudes":
https://groups.google.com/a/dimap.ufrn.br/d/msg/logica-l/VGpLWarJiYM/zoxKzN5yAgAJ
Logo no primeiro parágrafo de sua mensagem, o Franks chama a atenção
para as evidências de que Hilbert estaria interessado quase que
exclusivamente no conceito de "Post-completeness" ("completude
sintática"), tendo deixado a completude semântica mais ou menos de
lado. (É preciso tomar cuidado, contudo, com o fato de que o termo
"Post-completeness" também é às vezes usado para algo bem diferente, a
saber, para a *completude funcional*, também conhecida mais
propriamente como "expressive completeness".)
* * *
Abraços,
Joao Marcos
2016-06-16 16:19 GMT-03:00 Hermógenes Oliveira
<hermogene...@student.uni-tuebingen.de>:
Eu também diria que há aqui gente muito mais competente do que eu para
falar sobre tudo isto (e sobre qualquer outra coisa a respeito da qual
eu possa falar). Faço contudo um esclarecimento breve. Se pensamos
em *teorias* como conjuntos de fórmulas fechados sob derivabilidade,
então as teorias clássicas proposicionais são ("sintaticamente")
completas no sentido de Post. Estas coisas são bem conhecidas e estão
discutidas, por exemplo, no artigo do Zach, "Completeness before
Post".
No caso clássico *de primeira ordem*, contudo, isto não vale em geral.
Aparentemente este resultado aparece pela primeira vez no livro
clássico de Hilbert & Ackermann de 1928. Vale notar que a "completude
sintática" equivale à "completude de Post", a saber, a propriedade de
uma teoria não poder ser dedutivamente estendida sem se tornar
inconsistente. Há em Teoria dos Modelos um critério útil para a
completude de Post, dado pelo chamado "Teste de Łoś–Vaught" (a saber,
para a "completude sintática" é suficiente uma teoria ser satisfatível
sem ter modelos finitos e também ser categórica para algum cardinal
com cardinalidade maior ou igual à cardinalidade da linguagem).
* * *
Sei que com estas observações já vou mudando o rumo da discussão
original, mas uma mensagem da FOM que eu mencionei aqui há duas
semanas trata de alguns pontos históricos interessantes sobre as
várias "completudes":
https://groups.google.com/a/dimap.ufrn.br/d/msg/logica-l/VGpLWarJiYM/zoxKzN5yAgAJ
Logo no primeiro parágrafo de sua mensagem, o Franks chama a atenção
para as evidências de que Hilbert estaria interessado quase que
exclusivamente no conceito de "Post-completeness" ("completude
sintática"), tendo deixado a completude semântica mais ou menos de
lado. (É preciso tomar cuidado, contudo, com o fato de que o termo
"Post-completeness" também é às vezes usado para algo bem diferente, a
saber, para a *completude funcional*, também conhecida mais
propriamente como "expressive completeness".)
* * *
Abraços,
Joao Marcos
2016-06-16 16:19 GMT-03:00 Hermógenes Oliveira
<hermogene...@student.uni-tuebingen.de>:
Famadoria
Jun 16, 2016, 4:02:28 PM6/16/16
to logi...@dimap.ufrn.br
Bell, Set Theory, 2005, p. 109.
Sent from my iPhone
Sent from my iPhone
--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/7463a84a-c180-4e43-90c5-58a0d675598e%40dimap.ufrn.br.
Reply all
Reply to author
Forward
0 new messages