FOM: the satisfiable sentences are NOT an r.e. set

[Martin Davis]

At 02:20 PM 8/29/00 +0100, Roger Bishop Jones wrote:
>... I would
>guess that the satisfiable sentences are also recursively enumerable.

Of course, they are not.
         A is satisfiable <=> -A is not valid
So the satisfiable sentences are the complement of a complete r.e. set and 
hence not r.e.

Martin Davis



                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com