2012/07/17 by Vera Koponen, Koponen, Vera
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #math.LO #msc:03B99 #msc:03C99 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.4067
This paper has been withdrawn by the author, because a new, more extensive, version has been written together with another author. I intend to submit the new version (with a coauthor)
arxiv created 2013/04/12 · arxiv updated 2013/04/15
A condition, in two variants, is given such that if a property P satisfies this condition, then every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The result is used to prove that for a number of natural properties P speaking about automorphism groups, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The basic idea underlying the results and examples presented here is that, using results from random graph theory, it is possible to construct a countable first-order theory T such that every model of T has a very rich automorphism group, but every finite subset of T has a model which is rigid.