1972/09/01 by C. Ward Henson · 91 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Automorphism #Binary relation #Cardinality (data modeling) #Categorical variable #Combinatorics #Computer science #Countable set #Decidability #Discrete mathematics #Graph #Graph isomorphism #Homogeneous #Isomorphism (crystallography) #Line graph #Logic, Reasoning, and Knowledge #Mathematics #Undecidable problem
paper · doi:10.2307/2272734
published in Journal of Symbolic Logic 37(3), 494-500 (Cambridge University Press)
openalex publication_date 1972/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
A relational structure of cardinality ℵ 0 is called homogeneous by Fraissé [1] if each isomorphism between finite substructures of can be extended to an automorphism of . In §1 of this paper it is shown that there are isomorphism types of such structures for the first order language L 0 with a single (binary) relation symbol, answering a question raised by Fraissé. In fact, as is shown in §2, a family of nonisomorphic homogeneous structures for L 0 can be constructed, each member of which satisfies the following conditions (where U is the homogeneous, ℵ 0 -universal graph, the structure of which is considered in [4]): (i) The relation R of is asymmetric ( R ∩ R −1 = ∅); (ii) If A is the domain of and S is the symmetric relation R ∪ R −1 , then ( A, S ) is isomorphic to U . That is, each may be regarded as the result of assigning a unique direction to each edge of the graph U . Let T 0 be the first order theory of all homogeneous structures for L 0 which have cardinality ℵ 0 . In §3 (which can be read independently of §2) it is shown that T 0 has complete extensions (in L 0 ), each of which is ℵ 0 -categorical. Moreover, among the complete extensions of T 0 are theories of arbitrary (preassigned) degree of unsolvability. In particular, there exists an undecidable, ℵ 0 -categorieal theory in L 0 , which answers a question raised by Grzegorczyk [2], [3]. It follows from Theorem 6 of [3] that there are ℵ 0 -categorical theories of partial orderings which have arbitrarily high degrees of unsolvability. This is in sharp contrast to the situation for linear orderings, which were the motivation for Fraissé's early work. Indeed, as is shown in [10], every ℵ 0 -categorical theory of a linear ordering is finitely axiomatizable. (W. Glassmire [12] has independently shown the existence of theories in L 0 which are all ℵ 0 -categorical, and C. Ash [13] has independently shown that such theories exist with arbitrary degree of unsolvability.)