20th WCP: The Model Theory Of Dedekind Algebras

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 non-empty 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 n-loop 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 n-loops are isomorphic to the quotient mod n of the sequence of the integers. The classification of configurations into progressions, bigressions and n-loops is exhaustive and mutually exclusive.

The configuration signature of the Dedekind algebra B (s(B)(0) is a cardinal-valued 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 (n-1)-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₂ is the second order language whose only non-logical constant is a unary functional constant. L₂ contains individual, set, n-ary relational (n >= 2) and n-ary functional (n >= 1) variables. A mono-unary algebra is an algebra of the form B = (B,h_B) where B is a non-empty set and h_B is a unary function on B. Each Dedekind algebra is a mono-unary algebra. Each mono-unary algebra is interpreted in L₂ in the "standard" way. The (second order) theory of a mono-unary algebra is the set of all sentences in L₂ true on the algebra. Two mono-unary 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, non-isomorphic).

A mono-unary 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₂ 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₂ in the sense of finding a set of sentences in L₂ all of whose models are Dedekind algebras and have the given configuration signature. As configuration signatures are cardinal-valued functions, it is natural to consider cardinals which are characterizable in L₂. The cardinal b is (second order) characterizable provided there is f, a sentence in L₂, such that a mono-unary algebra is a model of f iff the domain of the algebra is of cardinality b. All non-zero finite cardinals are characterizable as is the cardinal ¿₀. 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 non-isomorphic Dedekind algebras which are characterizable. Since L₂ 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 mono-unary 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 non-zero 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 non-zero 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 HOMOGENEOUS-UNIVERSAL DEDEKIND ALGEBRAS

Continuing the study of Dedekind algebras which are characterizable except for cardinality, we consider homogeneous-universal 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 non-isomorphic 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 homogeneous-universal provided B is homogeneous and universal in D. If B is countably infinite, B is homogeneous-universal iff for all n >= 1, s(B)(n) = ¿₀. By Theorem 1, there are ¿₀ isomorphism types of countably infinite homogeneous-universal Dedekind algebras. However, since the configuration signature of a countably infinite homogeneous-universal Dedekind algebra is describable and eventually constant, all such algebras are finitely characterizable.

The uncountable homogeneous-universal 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 homogeneous-universal 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 homogeneous-universal algebras of the same cardinality are isomorphic. And, by Theorem 3, if b is an uncountable characterizable cardinal, and B is a homogeneous-universal Dedekind algebra of cardinality b, then B is finitely characterizable. Since the cardinal number of any mono-unary algebra which is finitely characterizable is characterizable, an uncountable homogeneous-universal Dedekind algebra of cardinality b is finitely characterizable iff b is characterizable.

A class of mono-unary algebras is a (second order) finitary class provided there is a finite set of sentences in L₂ whose models are exactly the members of the class.

THEOREM 8: Each of the following are finitary classes:

(1) the class of all uncountable homogeneous-universal 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. QUASI-CHARACTERIZABILITY

Since the class of uncountable homogeneous-universal 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 mono-unary algebra is (second order) quasi-characterizable 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 quasi-characterizable, then it is characterizable except for cardinality. A mono-unary algebra is (second order) quasi-finitely 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 quasi-finitely characterizable.

Every uncountable homogeneous-universal Dedekind algebra is quasi-finitely characterizable. Since there are such algebras in all uncountable powers, some of them are not characterizable. Hence, there are quasi-characterizable Dedekind algebras which are not characterizable. Since the number of quasi-characterizable algebras of a fixed cardinality is less than or equal to 2^¿0 and the number of non-isomorphic Dedekind algebras of cardinality b(b >= ¿_(2¿0)+) is > 2^¿0, there are Dedekind algebras which are not quasi-characterizable. The following theorem together with Theorem 1 and Theorem 5 imply that there are Dedekind algebras which are quasi-characterizable but not quasi-finitely characterizable.

THEOREM 9: All uncountable homogeneous Dedekind algebras are quasi-characterizable.

It follows from Theorem 1 and Theorem 5 that there are 2^¿0 non-isomorphic homogeneous Dedekind algebras in each uncountable cardinality. Since L₂ is countable, no more than ¿0 of these are quasi-finitely characterizable. There is a condition on the signatures of these algebras which implies that they are quasi-finitely characterizable.

THEOREM 10: Assume that B is an uncountable homogeneous Dedekind algebra. If s(B) is eventually constant, B is quasi-finitely characterizable.

The above condition, while sufficient, is not necessary. There are uncountable homogeneous Dedekind algebras which are quasi-finitely 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 quasi-characterizable. Further, when b >= ¿_¿1, there are Dedekind algebras of cardinality b which are universal in D but not quasi-finitely characterizable. There is a sufficient condition for a Dedekind algebra universal in D to be quasi-finitely 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 quasi-finitely characterizable.

When B is any uncountable quasi-finitely characterizable Dedekind algebra, the theory of B is completely determined by a finite set of sentences and the set of all sentences in L₂ which are true on B but contain no non-logical constants. A sentence in L₂ is pure provided the unary functional constant in L₂ does not occur in f. The pure theory of a mono-unary algebra is the collection of all pure sentences in L₂ 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₂, 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₂, and b is a non-zero cardinal, either f is true on all mono-unary algebras of cardinality b or f is false on all mono-unary algebras of cardinality b. When b' is a non-zero cardinal b and b' are (second order) indistinguishable provided for all f, a pure sentence in L₂, f is true on all mono-unary algebras of cardinality b iff f is true on all mono-unary 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 quasi-finitely characterizable. By Theorem 12, if b is minimal, B is characterizable. Assume that B is homogeneous-universal. By Theorem 8, the class of uncountable homogeneous-universal models is a finitary class. By Theorem 7, there are homogeneous-universal Dedekind algebras in each uncountable cardinal. And, by Theorem 1 and Theorem 7, homogeneous-universal 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 homogeneous-universal 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öwenheim-Skolem 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 homogeneous-universal Dedekind algebras has the Löwenheim-Skolem 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 homogeneous-universal 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 homogeneous-universal Dedekind algebra is describable iff the cardinality of the algebra is characterizable. Hence, every uncountable homogeneous-universal 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₂ is countable, the class of characterizable cardinals is countably infinite. Thus, there are non-zero 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 homogeneous-universal Dedekind algebras are characterizable iff their cardinalities are minimal and finitely characterizable iff their cardinalities are characterizable. Hence, every characterizable uncountable homogeneous-universal 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 non-zero 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.