Prove that the class of dense linear orders cannot be axiomatized by purely universal sentenes [closed]

1

$begingroup$

That is, prove that there is no set $T$ of purely universal sentences such that for every structure $A$ over the signature ${leq}$, $A$ is a dense linear order iff $Amodels T$.

logic first-order-logic predicate-logic model-theory axioms

share|cite|improve this question

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

asked Jan 26 at 9:28

GonzaloGonzalo

112

$endgroup$

closed as off-topic by Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon Feb 2 at 20:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Given a model of such a theory, consider whether a substructure must be a model as well.
  $endgroup$
  – Jishin Noben
  Jan 26 at 9:36
  

  
  
  
  

add a comment | 

1

$begingroup$

That is, prove that there is no set $T$ of purely universal sentences such that for every structure $A$ over the signature ${leq}$, $A$ is a dense linear order iff $Amodels T$.

logic first-order-logic predicate-logic model-theory axioms

share|cite|improve this question

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

asked Jan 26 at 9:28

GonzaloGonzalo

112

$endgroup$

closed as off-topic by Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon Feb 2 at 20:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Given a model of such a theory, consider whether a substructure must be a model as well.
  $endgroup$
  – Jishin Noben
  Jan 26 at 9:36
  

  
  
  
  

add a comment | 

1

1

1

$begingroup$

That is, prove that there is no set $T$ of purely universal sentences such that for every structure $A$ over the signature ${leq}$, $A$ is a dense linear order iff $Amodels T$.

logic first-order-logic predicate-logic model-theory axioms

share|cite|improve this question

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

asked Jan 26 at 9:28

GonzaloGonzalo

112

$endgroup$

That is, prove that there is no set $T$ of purely universal sentences such that for every structure $A$ over the signature ${leq}$, $A$ is a dense linear order iff $Amodels T$.

logic first-order-logic predicate-logic model-theory axioms

logic first-order-logic predicate-logic model-theory axioms

share|cite|improve this question

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

asked Jan 26 at 9:28

GonzaloGonzalo

112

share|cite|improve this question

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

asked Jan 26 at 9:28

GonzaloGonzalo

112

share|cite|improve this question

share|cite|improve this question

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

edited Jan 26 at 10:20

Taroccoesbrocco

5,64271840

5,64271840

asked Jan 26 at 9:28

GonzaloGonzalo

112

asked Jan 26 at 9:28

GonzaloGonzalo

112

asked Jan 26 at 9:28

GonzaloGonzalo

112

112

closed as off-topic by Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon Feb 2 at 20:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon Feb 2 at 20:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Cesareo, José Carlos Santos, Adrian Keister, mrtaurho, Pierre-Guy Plamondon

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Given a model of such a theory, consider whether a substructure must be a model as well.
  $endgroup$
  – Jishin Noben
  Jan 26 at 9:36
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Given a model of such a theory, consider whether a substructure must be a model as well.
  $endgroup$
  – Jishin Noben
  Jan 26 at 9:36
  

  
  
  
  

2

2

$begingroup$
Given a model of such a theory, consider whether a substructure must be a model as well.
$endgroup$
– Jishin Noben
Jan 26 at 9:36

$begingroup$
Given a model of such a theory, consider whether a substructure must be a model as well.
$endgroup$
– Jishin Noben
Jan 26 at 9:36

add a comment | 

1 Answer
1

active

oldest

votes

3

$begingroup$

Suppose there was such a set $T$. Clearly $(mathbb{Q}, le) models T$, as it is a dense linear order.

$(mathbb{Z}, le)$ is a substructure of $(mathbb{Q}, le)$ so $T$ also holds in this, because purely universal sentences stay true on subsets: $(mathbb{Z}, le) models T$.

But $(mathbb{Z}, le)$ is not a dense linear order, which contradicts the assumption on $T$.

share|cite|improve this answer

edited Jan 26 at 15:36

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why the purely universal sentences are true on subsets?
  $endgroup$
  – Gonzalo
  Jan 26 at 11:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
  $endgroup$
  – Henno Brandsma
  Jan 26 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for the clarification
  $endgroup$
  – Gonzalo
  Jan 26 at 12:33
  

  
  
  
  

add a comment | 

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

3

$begingroup$

Suppose there was such a set $T$. Clearly $(mathbb{Q}, le) models T$, as it is a dense linear order.

$(mathbb{Z}, le)$ is a substructure of $(mathbb{Q}, le)$ so $T$ also holds in this, because purely universal sentences stay true on subsets: $(mathbb{Z}, le) models T$.

But $(mathbb{Z}, le)$ is not a dense linear order, which contradicts the assumption on $T$.

share|cite|improve this answer

edited Jan 26 at 15:36

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why the purely universal sentences are true on subsets?
  $endgroup$
  – Gonzalo
  Jan 26 at 11:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
  $endgroup$
  – Henno Brandsma
  Jan 26 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for the clarification
  $endgroup$
  – Gonzalo
  Jan 26 at 12:33
  

  
  
  
  

add a comment | 

3

$begingroup$

Suppose there was such a set $T$. Clearly $(mathbb{Q}, le) models T$, as it is a dense linear order.

$(mathbb{Z}, le)$ is a substructure of $(mathbb{Q}, le)$ so $T$ also holds in this, because purely universal sentences stay true on subsets: $(mathbb{Z}, le) models T$.

But $(mathbb{Z}, le)$ is not a dense linear order, which contradicts the assumption on $T$.

share|cite|improve this answer

edited Jan 26 at 15:36

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why the purely universal sentences are true on subsets?
  $endgroup$
  – Gonzalo
  Jan 26 at 11:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
  $endgroup$
  – Henno Brandsma
  Jan 26 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for the clarification
  $endgroup$
  – Gonzalo
  Jan 26 at 12:33
  

  
  
  
  

add a comment | 

3

3

3

$begingroup$

Suppose there was such a set $T$. Clearly $(mathbb{Q}, le) models T$, as it is a dense linear order.

$(mathbb{Z}, le)$ is a substructure of $(mathbb{Q}, le)$ so $T$ also holds in this, because purely universal sentences stay true on subsets: $(mathbb{Z}, le) models T$.

But $(mathbb{Z}, le)$ is not a dense linear order, which contradicts the assumption on $T$.

share|cite|improve this answer

edited Jan 26 at 15:36

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

$endgroup$

Suppose there was such a set $T$. Clearly $(mathbb{Q}, le) models T$, as it is a dense linear order.

$(mathbb{Z}, le)$ is a substructure of $(mathbb{Q}, le)$ so $T$ also holds in this, because purely universal sentences stay true on subsets: $(mathbb{Z}, le) models T$.

But $(mathbb{Z}, le)$ is not a dense linear order, which contradicts the assumption on $T$.

share|cite|improve this answer

edited Jan 26 at 15:36

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

share|cite|improve this answer

share|cite|improve this answer

edited Jan 26 at 15:36

edited Jan 26 at 15:36

edited Jan 26 at 15:36

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

answered Jan 26 at 9:52

Henno BrandsmaHenno Brandsma

113k348123

113k348123

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why the purely universal sentences are true on subsets?
  $endgroup$
  – Gonzalo
  Jan 26 at 11:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
  $endgroup$
  – Henno Brandsma
  Jan 26 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for the clarification
  $endgroup$
  – Gonzalo
  Jan 26 at 12:33
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why the purely universal sentences are true on subsets?
  $endgroup$
  – Gonzalo
  Jan 26 at 11:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
  $endgroup$
  – Henno Brandsma
  Jan 26 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for the clarification
  $endgroup$
  – Gonzalo
  Jan 26 at 12:33
  

  
  
  
  

$begingroup$
Why the purely universal sentences are true on subsets?
$endgroup$
– Gonzalo
Jan 26 at 11:44

$begingroup$
Why the purely universal sentences are true on subsets?
$endgroup$
– Gonzalo
Jan 26 at 11:44

$begingroup$
@Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
$endgroup$
– Henno Brandsma
Jan 26 at 11:49

$begingroup$
@Gonzalo $forall x phi(x)$ holds for the larger set, so also for the smaller. Induct on the structure of the formula.
$endgroup$
– Henno Brandsma
Jan 26 at 11:49

$begingroup$
Thank you for the clarification
$endgroup$
– Gonzalo
Jan 26 at 12:33

$begingroup$
Thank you for the clarification
$endgroup$
– Gonzalo
Jan 26 at 12:33

add a comment | 

This page is only for reference, If you need detailed information, please check here