On compactness of logics that can express properties of symmetry or connectivity

Basic properties of first-order languages and structures (03C07) Models with special properties (saturated, rigid, etc.) (03C50) Abstract model theory (03C95) Automorphism groups of groups (20F28)

Abstract: 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 or connectivity, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. We also give an example of a logic that extends first-order logic, has the compactness property and can express the property "the cardinality of the automorphism group is at most

2^{a l e p h_{0}}

".

Review text

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} \).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: On compactness of logics that can express properties of symmetry or connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350211)