The Model Theory Of Dedekind Algebras George Weaver

1. INTRODUCTION One of the more striking accomplishments of foundational studies prior to 1930 was the characterization of various mathematical systems uniquely up to isomorphism (see Corcoran [1980]). Among the first systems to receive such a characterization is the sequence of the positive integers. Both Dedekind and Peano provided characterizations of this system in the late 1880's. Dedekind's characterization commenced by considering B, a nonempty set, and h, a "similar transformation" on B (i.e. an injective unary function on B). In deference to Dedekind, the ordered pair B = (B,h) is called a Dedekind algebra. While the study of Dedekind algebras can naturally be viewed as a continuation of Dedekind's work, the focus here is different. Rather than investigating whether a particular Dedekind algebra (the sequence of the positive integers) is characterizable, we proceed by investigating conditions on Dedekind algebras which imply that they are characterizable. In the following we review some of the results obtained in the model theory of Dedekind algebras and discuss some of their consequences. These results are stated without proofs. Weaver [1997a] and [1997b] provide the details of these proofs. Attention is restricted here to the model theory of the second order theories of Dedekind algebras. Weaver [1998] focuses on the model theory of the first order theories of these algebras. 2. CONFIGURATIONS Given a Dedekind algebra B = (B,h_{B}), A_{B} is the transitive closure of h_{B}. When (a,b) A_{B}, a is said to be an ancestor of b in B. When b is a member of B (the domain of B), A_{B}(b) is the set of ancestors of b in B. The set A is the configuration of b in B provided A is the unique smallest subset of B such that b is a member of A, A is closed under h_{B} and all of b's ancestors in B are in A. A is a configuration in B provided A is the configuration of some element of B. Each configuration is a Kette (or chain) in Dedekind's sense, but, there are chains which are not configurations. When A is a configuration in B, B[A] is that subalgebra of B generated by A. B[A] is a countable Dedekind algebra and A is its domain. B[A] is also called a configuration of B. The configurations of B partition B. Hence, B can be decomposed into a family of disjoint, countable subalgebras. The configuration A is a progression provided there is b in A such that b has no ancestors. When A is a progression, b is unique and is called the origin of A. A is a bigression provided each member of A has ¿0 ancestors in B; and A is a loop in B provided some member of A is its own ancestor. All loops are finite. For all n, A is an nloop iff A is a loop and of cardinality n. As subalgebras, progressions are isomorphic to the sequence of the positive integers, bigressions are isomorphic to the sequence of the integers and nloops are isomorphic to the quotient mod n of the sequence of the integers. The classification of configurations into progressions, bigressions and nloops is exhaustive and mutually exclusive. The configuration signature of the Dedekind algebra B (s(B)(0) is a cardinalvalued function on omega such that s(B)(0) is the cardinal number of the set of progressions in B; s(B)(1) is the cardinal number of the set of bigressions in B; and, for n>=2, s(B)(n) is the cardinal number of the set of (n1)loops in B. The structure of a Dedekind algebra is uniquely determined by its configuration signature. THEOREM 1: Two Dedekind algebras are isomorphic iff their configuration signatures are identical. 3. CHARACTERIZABLE DEDEKIND ALGEBRAS L_{2} is the second order language whose only nonlogical constant is a unary functional constant. L_{2} contains individual, set, nary relational (n >= 2) and nary functional (n >= 1) variables. A monounary algebra is an algebra of the form B = (B,h_{B}) where B is a nonempty set and h_{B} is a unary function on B. Each Dedekind algebra is a monounary algebra. Each monounary algebra is interpreted in L_{2} in the "standard" way. The (second order) theory of a monounary algebra is the set of all sentences in L_{2} true on the algebra. Two monounary algebras are (second order) equivalent iff they have the same second order theory. A familiar application of the axiom of substitution shows that there are Dedekind algebras which are equivalent but of different cardinalities (hence, nonisomorphic). A monounary algebra is (second order) characterizable provided there is a subset of the theory of the algebra all of whose models are isomorphic. Such an algebra is (second order) finitely characterizable provided there is a finite subset of the theory of the algebra all of whose models are isomorphic. Since there are Dedekind algebras of different cardinalities which are equivalent, there are Dedekind algebras which are not characterizable. It follows from Theorem 1 that there are also Dedekind algebras of the same cardinality which are equivalent but not isomorphic. For each cardinal b, let b+ be the cardinal successor of b. Let a be a cardinal greater than or equal to ¿ _{(2¿0)}+. The number of isomorphism types of Dedekind algebras of cardinality a is strictly greater than 2^{¿0} by Theorem 1. Since L_{2} is countable, there are Dedekind algebras of cardinality a which are equivalent but not isomorphic. From the perspective of Theorem 1, the problem of characterizing a Dedekind algebra is that of fixing its configuration signature in L_{2} in the sense of finding a set of sentences in L_{2} all of whose models are Dedekind algebras and have the given configuration signature. As configuration signatures are cardinalvalued functions, it is natural to consider cardinals which are characterizable in L_{2}. The cardinal b is (second order) characterizable provided there is f, a sentence in L_{2}, such that a monounary algebra is a model of f iff the domain of the algebra is of cardinality b. All nonzero finite cardinals are characterizable as is the cardinal ¿_{0}. Further, if the cardinal b is characterizable, then b^{+} and 2^{b} are also. Notice that the cardinal zero is not characterizable. The configuration signature of a Dedekind algebra B is said to be (second order) describable provided for each n in omega, s(B)(n) is either zero or second order characterizable. THEOREM 2: If the configuration signature of a Dedekind algebra is describable, then the algebra is characterizable. It follows from Theorem 2 that all countable Dedekind algebras (hence all configurations) are characterizable. Thus, the sequence of positive integers is characterizable. It also follows from Theorem 2 and Theorem 1 that there are 2^{¿0} nonisomorphic Dedekind algebras which are characterizable. Since L_{2} is countable, some of these are not finitely characterizable. Consider the problem of distinguishing the finitely characterizable Dedekind algebras from those which are merely characterizable. One natural choice for a condition to distinguish between such algebras is that of having a configuration signature which is eventually constant. Call s(B) eventually constant provided there is an n in omega such that for all m > n, s(B)(m) = s(B)(n). THEOREM 3: If the configuration signature of a Dedekind algebra is describable and eventually constant, then the algebra is finitely characterizable. It follows from Theorem 3 that all configurations (as subalgebras) are finitely characterizable. Hence, that the sequence of the positive integers is finitely characterizable. Further, all countable models of the first order theory of the sequence of the positive integers are finitely characterizable. Similar remarks apply to those uncountable models of that theory whose cardinality is characterizable. 4. ISOMORPHISM PROBLEMS There are two kinds of Dedekind algebras which are not characterizable. Those which are equivalent to algebras in a different cardinality and those which are equivalent to but not isomorphic to an algebra of the same cardinality. In the following, we consider Dedekind algebras of the first kind which are not of the second kind (i.e. those which are characterizable except for cardinality). Let G be any class of monounary algebras. The isomorphism problem for G is the problem of whether or not all equivalent members of G are isomorphic. The isomorphism problem for G has a positive solution provided all equivalent members of G are isomorphic. The isomorphism problem for G has a negative solution provided there are members of G which are equivalent but not isomorphic. There are classes of systems whose isomorphism problem is unsolvable in the sense that there are models of ZFC in which the problem has a negative solution and models of ZFC in which the problem has a positive solution (see Ajtai [1979]). Notice that a Dedekind algebra is characterizable iff the isomorphism problem for the class of all algebras equivalent to the given algebra has a positive solution. Let D be the class of Dedekind algebras. The isomorphism problem for D has a negative solution. Let b be a nonzero cardinal. D[b] is the class of Dedekind algebras of cardinality b. If b >= ¿_{(2¿0)}+, the isomorphism problem for D[b] has a negative solution. Let k be the least nonzero cardinal which is not characterizable. By Theorem 2, if b < k, then D[b] has a positive solution. There are ¿0 cardinals b such that b >= k and the isomorphism problem for D[b] has a positive solution. THEOREM 4: The isomorphism problem for D[k], D[k^{+}], D[k^{++}] etc. all have positive solutions. 5. HOMOGENEOUS, UNIVERSAL AND HOMOGENEOUSUNIVERSAL DEDEKIND ALGEBRAS Continuing the study of Dedekind algebras which are characterizable except for cardinality, we consider homogeneousuniversal Dedekind algebras. A subalgebra, A, of the Dedekind algebra B is a small subalgebra of B provided the cardinality of the domain of A is strictly smaller than the cardinality of the domain of B. Let B be an infinite Dedekind algebra. B is homogeneous provided any isomorphism between small subalgebras of B can be extended to an automorphism on B. Every countably infinite Dedekind algebra is homogeneous. Uncountable homogeneous Dedekind algebras can be defined in terms of configuration signatures. THEOREM 5: Assume that b is an uncountable cardinal and that B is a Dedekind algebra of cardinality b. B is homogeneous iff s(B)(0) = 0 and for all n >= 1, either s(B)(n) is finite or s(B)(n) = b. It follows from Theorem 5 that there are homogeneous Dedekind algebras in each uncountable cardinality. By Theorem 1, there are nonisomorphic homogeneous Dedekind algebras in each infinite cardinality. By Theorem 2, if B is a homogeneous Dedekind algebra of cardinality b, and b is second order characterizable, then B is characterizable. Finally, notice that if B is an uncountable homogeneous Dedekind algebra, h_{B} is a bijection on B. The infinite Dedekind algebra B is universal in D provided every member of D of cardinality less than or equal to the cardinality of B is isomorphic to a subalgebra of B . Dedekind algebras which are universal in D can be described in terms of their configuration signatures. THEOREM 6: Assume that b is an infinite cardinal and that B is a Dedekind algebra of cardinality b. B is universal in D iff for all n = 1, s(B)(n) = b. It follows from Theorem 6 that there are Dedekind algebras universal in D in each infinite cardinal b. By Theorem 1, if b is an infinite cardinal, there are Dedekind algebras of cardinality b which are universal in D but not isomorphic. Finally, notice that the configuration signature of a Dedekind algebra which is universal in D is eventual constant. Hence, if the value the configuration signature at zero is either zero or second order characterizable and the cardinality of the algebra is also second order characterizable, then the algebra is finitely characterizable. The infinite Dedekind algebra B is homogeneousuniversal provided B is homogeneous and universal in D. If B is countably infinite, B is homogeneousuniversal iff for all n >= 1, s(B)(n) = ¿_{0}. By Theorem 1, there are ¿_{0} isomorphism types of countably infinite homogeneousuniversal Dedekind algebras. However, since the configuration signature of a countably infinite homogeneousuniversal Dedekind algebra is describable and eventually constant, all such algebras are finitely characterizable. The uncountable homogeneousuniversal Dedekind algebras can be described in terms of their configuraiton signatures. THEOREM 7: Assume that b is an uncountable cardinal and B is a Dedekind algebra of cardinality b. B is homogeneousuniversal iff s(B)(0) = 0 and for all n >= 1, s(B)(n) = b. It follows from Theorem 7 that there are homogeneous universal Dedekind algebras in all uncountable cardinals. By Theorem 1, all uncountable homogeneousuniversal algebras of the same cardinality are isomorphic. And, by Theorem 3, if b is an uncountable characterizable cardinal, and B is a homogeneousuniversal Dedekind algebra of cardinality b, then B is finitely characterizable. Since the cardinal number of any monounary algebra which is finitely characterizable is characterizable, an uncountable homogeneousuniversal Dedekind algebra of cardinality b is finitely characterizable iff b is characterizable. A class of monounary algebras is a (second order) finitary class provided there is a finite set of sentences in L_{2} whose models are exactly the members of the class. THEOREM 8: Each of the following are finitary classes: (1) the class of all uncountable homogeneousuniversal Dedekind algebras; (2) the class of all uncountable homogeneous Dedekind algebras; and (3) the class of all uncountable Dedekind algebras which are universal in D. 6. QUASICHARACTERIZABILITY Since the class of uncountable homogeneousuniversal Dedekind algebras is a finitary class, for each such algebra there is a subset of its theory all of whose models of the same cardinality are isomorphic. Generalizing from this situation, a monounary algebra is (second order) quasicharacterizable provided there is a subset of the theory of the algebra all of whose models of the same cardinality are isomorphic. Notice that if a Dedekind algebra is quasicharacterizable, then it is characterizable except for cardinality. A monounary algebra is (second order) quasifinitely characterizable provided there is a finite subset of the theory of the algebra all of whose models of the same cardinality are isomorphic. The uncountable models of the first order theory of the positive integers are quasifinitely characterizable. Every uncountable homogeneousuniversal Dedekind algebra is quasifinitely characterizable. Since there are such algebras in all uncountable powers, some of them are not characterizable. Hence, there are quasicharacterizable Dedekind algebras which are not characterizable. Since the number of quasicharacterizable algebras of a fixed cardinality is less than or equal to 2^{¿0} and the number of nonisomorphic Dedekind algebras of cardinality b(b >= ¿_{(2¿0)}+) is > 2^{¿0}, there are Dedekind algebras which are not quasicharacterizable. The following theorem together with Theorem 1 and Theorem 5 imply that there are Dedekind algebras which are quasicharacterizable but not quasifinitely characterizable. THEOREM 9: All uncountable homogeneous Dedekind algebras are quasicharacterizable. It follows from Theorem 1 and Theorem 5 that there are 2^{¿0} nonisomorphic homogeneous Dedekind algebras in each uncountable cardinality. Since L_{2} is countable, no more than ¿0 of these are quasifinitely characterizable. There is a condition on the signatures of these algebras which implies that they are quasifinitely characterizable. THEOREM 10: Assume that B is an uncountable homogeneous Dedekind algebra. If s(B) is eventually constant, B is quasifinitely characterizable. The above condition, while sufficient, is not necessary. There are uncountable homogeneous Dedekind algebras which are quasifinitely characterizable but whose configuration signatures are strictly increasing. By Theorem 1 and Theorem 6, when b >= ¿_{(2¿0)}+ there are Dedekind algebras of cardinality b which are universal in D but not quasicharacterizable. Further, when b >= ¿_{¿1}, there are Dedekind algebras of cardinality b which are universal in D but not quasifinitely characterizable. There is a sufficient condition for a Dedekind algebra universal in D to be quasifinitely characterizable. THEOREM 11: Assume that b is an uncountable cardinal and that B is a Dedekind algebra of cardinality b which is universal in D. If s(B)(0) is either 0, b or second order characterizable, B is quasifinitely characterizable. When B is any uncountable quasifinitely characterizable Dedekind algebra, the theory of B is completely determined by a finite set of sentences and the set of all sentences in L_{2} which are true on B but contain no nonlogical constants. A sentence in L_{2} is pure provided the unary functional constant in L_{2} does not occur in f. The pure theory of a monounary algebra is the collection of all pure sentences in L_{2} which are true on the algebra. THEOREM 12: Assume that B is any uncountable Dedekind algebra and that T is a finite subset of the theory of B all of whose models of the same cardinality are isomorphic. If f is a sentence in L_{2}, f is true on B iff f is a logical consequence of the union of T and the pure theory of B. When f is a pure sentence in L_{2}, and b is a nonzero cardinal, either f is true on all monounary algebras of cardinality b or f is false on all monounary algebras of cardinality b. When b' is a nonzero cardinal b and b' are (second order) indistinguishable provided for all f, a pure sentence in L_{2}, f is true on all monounary algebras of cardinality b iff f is true on all monounary algebras of cardinality b'. The cardinal b is (second order) minimal provided b is the only cardinal indistinguishable from b. All characterizable cardinals are minimal. Assume that B is an uncountable Dedekind algebra of cardinality b and that B is quasifinitely characterizable. By Theorem 12, if b is minimal, B is characterizable. Assume that B is homogeneousuniversal. By Theorem 8, the class of uncountable homogeneousuniversal models is a finitary class. By Theorem 7, there are homogeneousuniversal Dedekind algebras in each uncountable cardinal. And, by Theorem 1 and Theorem 7, homogeneousuniversal Dedekind algebras of the same cardinality are isomorphic. Hence, B is characterizable iff b is minimal. Assume that T is a finite subset of the theory of B all of whose models of the same cardinality are isomorphic. If A is any algebra of cardinality a which is equivalent to B, then a and b are indistinguishable. Hence, by Theorem 12, if A is a model of T, A and B are equivalent iff a and b are indistinguishable. Hence, uncountable homogeneousuniversal Dedekind algebras are equivalent iff their cardinalities are indistinguishable. Assume that T has models in all uncountable cardinalities. The class of models of T has the following LöwenheimSkolem property: if b is an uncountable cardinal and B is a model of T of cardinality b, then for all cardinals a, if a and b are indistinguishable, there is A, a model of T of cardinality a, which is equivalent to B. It follows that the class of uncountable homogeneousuniversal Dedekind algebras has the LöwenheimSkolem property. However, D does not have this property. 7. OPEN QUESTIONS There are a number of questions suggested by the above which to the author's knowledge are open. Here we briefly discuss four of them. 7.1 Does every finitely characterizable Dedekind algebra have a describable signature? When the above question is restricted to uncountable homogeneousuniversal algebras the answer is yes. In general, the cardinality of any finitely characterizable algebra is characterizable. By Theorem 7, the configuration signature of an uncountable homogeneousuniversal Dedekind algebra is describable iff the cardinality of the algebra is characterizable. Hence, every uncountable homogeneousuniversal Dedekind algebra which is finitely characterizable has a describable signature. However, the above consequence of Theorem 7 does not hold in general. It follows from results of Garland [1969] that the cardinal ¿_{¿1} is characterizable. Since L_{2} is countable, the class of characterizable cardinals is countably infinite. Thus, there are nonzero cardinals strictly less than ¿_{¿1} which are not characterizable. 7.2 Does every characterizable Dedekind algebra have a describable signature? Even special cases of this problem look difficult. Recall that uncountable homogeneousuniversal Dedekind algebras are characterizable iff their cardinalities are minimal and finitely characterizable iff their cardinalities are characterizable. Hence, every characterizable uncountable homogeneousuniversal Dedekind algebra has a describable signature iff every minimal cardinal is charcterizable. 7.3 Is there a condition on the action of describable configuration signatures which is both necessary and sufficient for finite characterizability? The condition that the configuration signature is eventually constant is sufficient but not necessary. There are finitely characterizable Dedekind algebras whose configuration signatures are describable and strictly increasing. 7.4 Assume that b is a cardinal strictly less than ¿_{(2¿0)}+. Does the isomorphism problem for D[b] have a positive solution? This question is related to the second question above. If every characterizable Dedekind algebra has a describable signature, then there are cardinals b strictly less than ¿_{(2¿0)}+ whose isomorphism problem has a negative solution. Recall that k is the first nonzero cardinal which is not characterizable. k is strictly less than ¿_{(2¿0)}+. Further, there are characterizable cardinals strictly between k and ¿_{(2¿0)}+ (e.g. ¿_{¿1)}. Let a be such a cardinal. Assume that every characterizable Dedekind algebra has a describable signature. For b > k there are members of D[b] whose signatures are not describable. By assumption, they are not characterizable. Any algebra equivalent to an algebra in D[a] is of cardinality a. Hence, there are members of D[a] which are equivalent but not isomorphic. 
References 1. Ajtai, M. [1979] "Isomorphism and Higher Order Equivalence" Annals of Mathematical Logic 16 181203. 2. Corcoran, J. [1980] "Categoricity" History and Philosophy of Logic 1 187207. 3. Garland, S. [1967] Second Order Cardinal Characterizability Doctoral Dissertation, Department of Mathematics University of California, Berkeley 4. Weaver G. [1997a] Dedekind Algebras Submitted [1997b] Homogeneous and Universal Dedekind Algebras Studia Logica (forthcoming). [1998] The First Order Model Theory of Dedekind Algebras Submitted 