On compactness of logics that can express properties of symmetry or connectivity (Q2350211)

One of the main aims of abstract model theory is the search for extensions of first-order logic which have a good expressive power, nevertheless retaining some good model-theoretical properties. Needless to say, usually these are two (often competing) sides of the same coin; for example, the compactness theorem allows us to construct non-standard models, say, of arithmetics. But this means that any logic satisfying the compactness theorem has not a sufficient expressive power to characterize the standard model of arithmetics. Severe limitations to the program are imposed by the Lindström theorem [\textit{P. Lindström}, Theoria 35, 1--11 (1969; Zbl 0206.27202)] proving that no proper extension of first-order logic can satisfy both the compactness and the downward Löwenheim-Skolem theorems. On the other hand, there are examples of proper extensions of first-order logic satisfying the (full) compactness theorem, e.g. [\textit{S. Shelah}, Trans. Am. Math. Soc. 204, 342--364 (1975; Zbl 0322.02010)], and there are very natural examples of logics which are countably compact; see, e.g. [\textit{G. Fuhrken}, Fund. Math. 54, 291--302 (1964; Zbl 0166.26001); \textit{R. L. Vaught}, Fund. Math. 54, 303--304 (1964; Zbl 0137.00901)]. Recall that a logic is countably compact if every finitely satisfiable countable set of sentences has a model. Further information about abstract model theory can be found in [\textit{J. Barwise} (ed.) and \textit{S. Feferman} (ed.), Model-theoretic logics. (Parts A--C). New York etc.: Springer-Verlag (1985; Zbl 0587.03001); Model-theoretic logics. (Parts D--F). New York etc.: Springer-Verlag (1985; Zbl 0587.03002)]. Along the above lines of research, a rather general condition is considered; if some property \(P\) satisfies this condition and some logic \(L\) extends first-order logic and can express \(P\), then \(L\) is not countably compact. Examples and applications are presented dealing with extensions of first-order logic in which various properties related to groups of automorphisms can be expressed. The paper deals also with connectivity, in a sense similar to the graph theoretical notion. For example, it is proved that one gets a logic which is not countably compact if first-order logic is extended by adding a sentence expressing ``the automorphism group is countable''. The same holds for sentences expressing one of the following properties: ``the automorphism group is finite'', more generally, ``the automorphism group has cardinality belonging to \(\Omega\)'', where \( \Omega\) is any set of cardinals all of which are below \(2^ { \aleph_0}\), ``the automorphism group is finitely generated'', ``the automorphism group is countably generated'' and ``the automorphism group is finitely presentable''. If logics are required to be closed under negation, the above logics do not have a proof system which is both sound and complete. Two proofs are given of the above (and other) results. First, the results are obtained as corollaries of a general theorem stated in terms of notions having a graph-theoretical flavor and whose proof uses graph-theoretical previously known results. Then in Section 5, it is explained how to get more direct proofs which do not rely on graph theory. Finally, in another direction, the authors show that countable compactness is preserved if first-order logic is extended by adding a sentence which asserts ``the automorphism group has cardinality \(\leq 2 ^{\aleph_0} \)''.