Questão se uma certa teoria de primeira ordem é completa

Anderson Nakano

unread,

Dec 11, 2019, 6:56:20 AM12/11/19

to LOGICA-L

Bom dia, pessoal, tudo bem? Estou quebrando a cabeça em um problema, e gostaria de saber se alguém da lista conseguiria me dar uma mãozinha.

Considerem a seguinte teoria de primeira ordem, formada pelos axiomas:

∀x¬Rxx ,

∀x∃yRxy,

∀x∃yRyx,
∀x∀y(¬Rxy ∨ ∀z(¬Ryz ∨ Rxz)),
∀x∀y(Rxy ∨ ∀z(Ryz ∨ ¬Rxz)).

Essa teoria só tem modelos de cardinalidade infinita (isso eu consigo provar). Eu gostaria de provar (se isso for verdade, é claro), que essa teoria é completa. Pensei em aplicar o teste de Łoś–Vaught, mas ainda não consegui. Se alguém tiver um tempo e encontrar uma resposta, agradeço desde já!

Abraço a todos,

Anderson

Henrique Lecco

unread,

Dec 11, 2019, 9:09:38 AM12/11/19

to LOGICA-L

Como seu vocabulário é finito e não tem símbolos de função, você pode usar jogos de Ehrenfeucht-Fraïssé.

Conhece essa técnica?

Rodrigo Freire

unread,

Dec 11, 2019, 10:51:23 AM12/11/19

to Anderson Nakano, LOGICA-L

Talvez tenha perdido algo, mas do jeito que está toda ordem linear estrita sem extremos é modelo da sua teoria. Em particular, os inteiros com a ordem natural e os racionais com a ordem natural são modelos. Mas essas estruturas não são elementarmente equivalentes, portanto a teoria não é completa.

Em 11 de dez de 2019, à(s) 08:56, Anderson Nakano <anderso...@gmail.com> escreveu:

--
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 ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/3a2bb515-dffe-4554-8237-91460e65986f%40dimap.ufrn.br.

Henrique Lecco

unread,

Dec 11, 2019, 10:59:42 AM12/11/19

to LOGICA-L

Acabamos respondendo por e-mail e daí não veio por aqui.
Mas realmente essa foi uma boa justificativa. No livro que sugeri (Basic Model Theory, do Doets), ele explica as hipóteses que você precisa pra que seja completa e mostra isso usando jogos. Acho bem bacana, vale a leitura (é bem clássico, aliás).

Anderson Nakano

unread,

Dec 11, 2019, 11:03:03 AM12/11/19

to LOGICA-L, anderso...@gmail.com

Oi, Rodrigo, tudo bem?

Muito obrigado pela resposta.

Forte abraço,

Anderson

Em quarta-feira, 11 de dezembro de 2019 12:51:23 UTC-3, Rodrigo Freire escreveu:

Talvez tenha perdido algo, mas do jeito que está toda ordem linear estrita sem extremos é modelo da sua teoria. Em particular, os inteiros com a ordem natural e os racionais com a ordem natural são modelos. Mas essas estruturas não são elementarmente equivalentes, portanto a teoria não é completa.

Em 11 de dez de 2019, à(s) 08:56, Anderson Nakano <anderso...@gmail.com> escreveu:

Bom dia, pessoal, tudo bem? Estou quebrando a cabeça em um problema, e gostaria de saber se alguém da lista conseguiria me dar uma mãozinha.

Considerem a seguinte teoria de primeira ordem, formada pelos axiomas:
∀x¬Rxx ,
∀x∃yRxy,
∀x∃yRyx,
∀x∀y(¬Rxy ∨ ∀z(¬Ryz ∨ Rxz)),
∀x∀y(Rxy ∨ ∀z(Ryz ∨ ¬Rxz)).

Essa teoria só tem modelos de cardinalidade infinita (isso eu consigo provar). Eu gostaria de provar (se isso for verdade, é claro), que essa teoria é completa. Pensei em aplicar o teste de Łoś–Vaught, mas ainda não consegui. Se alguém tiver um tempo e encontrar uma resposta, agradeço desde já!

Abraço a todos,

Anderson

--
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 logi...@dimap.ufrn.br.

Anderson Nakano

unread,

Dec 11, 2019, 12:25:12 PM12/11/19

to LOGICA-L, anderso...@gmail.com

Rodrigo (e demais), uma questão:

Se eu adicionar à teoria um axioma de densidade: ∀x∀y(Rxy ⊃ ∃z(Rxz ∧ Rzy)), ela se torna uma teoria completa? Se não, você teria um exemplo de uma teoria completa com uma única relação binária que tenha apenas modelos infinitos (de preferência uma que contenha a teoria acima)?

Obrigado mais uma vez,

Anderson

Rodrigo Freire

unread,

Dec 11, 2019, 12:37:46 PM12/11/19

to Anderson Nakano, LOGICA-L

Oi Anderson,

A teoria das ordens lineares estritas, sem extremos e densas é sim completa, só tem modelos infinitos e contém a sua.

Abraço

Em 11 de dez de 2019, à(s) 14:25, Anderson Nakano <anderso...@gmail.com> escreveu:

--

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 ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/fd29aebb-a549-4ecc-aab1-38f5881af99d%40dimap.ufrn.br.

Anderson Nakano

unread,

Dec 11, 2019, 12:42:11 PM12/11/19

to LOGICA-L, anderso...@gmail.com

Oi, Rodrigo, obrigado mais uma vez.

Como eu provo que tal teoria é completa?

Abraço,

Anderson

Em quarta-feira, 11 de dezembro de 2019 14:37:46 UTC-3, Rodrigo Freire escreveu:

Oi Anderson,

A teoria das ordens lineares estritas, sem extremos e densas é sim completa, só tem modelos infinitos e contém a sua.

Abraço

Em 11 de dez de 2019, à(s) 14:25, Anderson Nakano <anderso...@gmail.com> escreveu:

Rodrigo (e demais), uma questão:

Se eu adicionar à teoria um axioma de densidade: ∀x∀y(Rxy ⊃ ∃z(Rxz ∧ Rzy)), ela se torna uma teoria completa? Se não, você teria um exemplo de uma teoria completa com uma única relação binária que tenha apenas modelos infinitos (de preferência uma que contenha a teoria acima)?

Obrigado mais uma vez,

Anderson

--
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 logi...@dimap.ufrn.br.

Rodrigo Freire

unread,

Dec 11, 2019, 12:51:33 PM12/11/19

to Anderson Nakano, LOGICA-L

Todos os modelos enumeráveis são isomorfos, então você pode usar o teste que você mencionou. É um resultado standard que dá para encontrar na literatura.

Em 11 de dez de 2019, à(s) 14:42, Anderson Nakano <anderso...@gmail.com> escreveu:

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 ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/4a64af54-0a69-425c-8f77-8ed11da311aa%40dimap.ufrn.br.

Carlos Gonzalez

unread,

Dec 12, 2019, 2:33:56 PM12/12/19

to Anderson Nakano, LOGICA-L, Carlos G González, Carlos González, Rodrigo Freire

Oi Anderson,

Pode ser usado o método back-and-forth de Cantor para provar que duas ordens densas enumeráveis sem extremos são isomorfas:

https://en.wikipedia.org/wiki/Back-and-forth_method. Lindo método.

Veja Chang-Keisler para as consequências disso.

Suponha que para uma teoria T todos os modelos enumeráveis são isomorfos. Se T não for completa, é consistente e existem extensões T+φ e T+ -φ com modelos não isomorfos, absurdo. (Usando Löwenheim -Skolem)

Veja alguns resultados sobre ordens densas no meu artigo:
http://matwbn.icm.edu.pl/ksiazki/fm/fm147/fm14712.pdf

Carlos

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/302F8AE3-2A3E-4FAC-B344-7F83B406CD9D%40gmail.com.

Anderson Nakano

unread,

Dec 12, 2019, 3:18:12 PM12/12/19

to LOGICA-L, anderso...@gmail.com, gonz...@gmail.com, filon...@yahoo.com, freir...@gmail.com

Oi, Carlos,

Muito obrigado pela referência. Vou dar uma olhada.

Abraço,

Anderson

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/4a64af54-0a69-425c-8f77-8ed11da311aa%40dimap.ufrn.br.

--
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 logi...@dimap.ufrn.br.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/302F8AE3-2A3E-4FAC-B344-7F83B406CD9D%40gmail.com.

Reply all

Reply to author

Forward