|
10
|
|
edited Nov 2 2011 at 21:20 |
I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My attempts were unsuccessful.
This is an exercise from the (wider) model theory book written by Hodges (Encyclopedia of Mathematics and its Applications, Volume 42 - Model Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
It's easy to see that proving the following will suffice: (*) given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).
thanks for the help!
|
|
|
|
|
9
|
|
edited Nov 2 2011 at 20:48 |
I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My attempts were unsuccessful.
This is an exercise from the (wider) model theory book written by Hodges (Encyclopedia of Mathematics and its Applications, Volume 42 - Model Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
It's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).
thanks for the help!
|
|
|
|
|
8
|
|
edited Nov 2 2011 at 20:31 |
I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My attempts were unsuccessful.
This is an exercise from the (wider) model theory book written by Hodges (Encyclopedia of Mathematics and its Applications, Volume 42 - Model Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
It's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).
thanks for the help!
|
|
|
|
7
|
|
edited Nov 2 2011 at 20:26 |
showing Showing that every satisfiable sentence with at most two variables has a finite model
I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My attempts were unsuccessful.
This is an exercise from the (wider) model theory book written by Hodges (Encyclopedia of Mathematics and its Applications, Volume 42 - Model Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
It's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).
|
|
|
|
|
6
|
|
edited Nov 2 2011 at 20:25 |
i I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. my My attempts were unsuccessful.
this This is an exercise from the wider (wider) model thoery theory book written by Hodges (ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONSEncyclopedia of Mathematics and its Applications, Volume 42 - model theoryModel Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
it's It's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles(between A and B).
thanks for the help =]
|
|
|
|
|
5
|
|
edited Nov 2 2011 at 20:23 |
I i have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My my attempts were unsuccessful.This
this is an exercise from the (wider) wider model theory thoery book written by Hodges (Encyclopedia of Mathematics and its ApplicationsENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS, Volume 42 - Model Theorymodel theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.It's
it's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).
thanks for the help =]
|
|
|
|
|
4
|
|
edited Nov 2 2011 at 20:23 |
i I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. my My attempts were unsuccessful.
this This is an exercise from the wider (wider) model thoery theory book written by Hodges (ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONSEncyclopedia of Mathematics and its Applications, Volume 42 - model theoryModel Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
it's It's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles(between A and B).
thanks for the help =]
|
|
|
|
|
3
|
|
edited Nov 2 2011 at 20:22 |
i have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. my attempts were unsuccessful.
this is an exercise from the wider model thoery book written by Hodges (ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS, Volume 42 - model theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
it's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).
thanks for the help =]
|
|
|
|
|
2
|
|
edited Nov 2 2011 at 19:54 |
in model theory, how can i prove showing that every satisfiable sentence with at most two variables has a finite model ?
i have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model, but . my attempts were unsuccessful..unsuccessful.
this is an exercise from the wider model thoery book written by Hodges (ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS, Volume 42 - model theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
it's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles.
thanks for the help =]
|
|
|
|
|
1
|
|
asked Nov 2 2011 at 19:16 |
in model theory, how can i prove that every satisfiable sentence with at most two variables has a finite model ?
i have tried to prove that every satisfiable sentence with at most two variables has a finite model, but my attempts were unsuccessful...
this is an exercise from the wider model thoery book written by Hodges (ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS, Volume 42 - model theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.
it's easy to see that proving the following problem will suffice: given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles.
|
|
|
