Non-Standard Axioms for Various Math Structures 2

This is part of a series in which we investigate non-standard axiomatizations of various math structures. The previous post in the series was concerned with single equational axioms for equational classes. In this post, we are inspired by a particularly elegant characterization of (abstract) Boolean algebras, and we consider whether similar “Boolean algebra-like” characterizations can be given for other common structures.

To motivate this discussion, we recall that we can characterize abstract Boolean algebras as:

Theorem. A structure $S$ is an abstract Boolean algebra if and only if every statement true of the specific abstract Boolean algebra $\{0,1\}$ is true of $S$ .

We may generalize this form: given a class $C$ of structures, can we find a “representative” $c\in C$ such that any statement $\lambda$ is true of every member of $C$ if and only if it is true of $c$ ? For which $C$ is this possible, and can we develop formulas to allow us to calculate a suitable $c$ given $C$ ?

In this post, we will call $c$ a representative. (I am not sure whether this terminology should be standard if there isn’t standard terminology already, since it seems to evoke representation theory which may not be equivalent. But at the moment, I don’t have a good alternative term.) Hence, the question is the existence and calculation of representatives of given classes of structures.

I imagine that in order to study this more generally, I’d need to learn more universal algebra. But can we do this for specific cases? For example, the class of all groups?

I suspect that something will be implied about isomorphism to representatives — specifically, it wouldn’t be surprising to find that $c$ is a representative of $C$ if and only if every member of $C$ is isomorphic to $c$ . If that’s the case, then this just reduces to isomorphic classification, which immediately resolves the question for most well-known structures.

Let’s set about proving this. For simplicity, we’ll focus on $C$ as a class of algebras. (It stands to reason that a reasonable next extension could be $C$ as a class of models of a set of first-order axioms, so basically adding on relations.)

Actually, this is patently not true: it would imply that every abstract Boolean algebra is isomorphic to $\{0,1\}$ , which is very much false — in fact, this exploration shows that there exists an abstract Boolean algebra of any infinite cardinality. Thus, this is false.

OK, so the question of representatives won’t be resolved by isomorphism itself. Does this show that isomorphism is a stronger condition than simply “all statements true of one structure are true of the other”? While this is certainly implied by the existence of an isomorphism (just apply the isomorphism properties to the operations/relations in the signature inductively, assuming all statements are finite length), is the converse true as well? The idea that “all statements true of one structure are true of the other” is a common motivation for the concept of isomorphism, but if the converse fails then it might be important to clarify this properly in teaching (i.e., this has implications in education.)

Upon second thought, a potential converse to that doesn’t by itself contradict the isomorphism-representative disproof, since a representative need only “contain” the statements true about all members of $C$ . This doesn’t contradict that certain members of $C$ would have statements that other members don’t; in fact, this is par for the course in most well-known classes $C$ that we would study. (In fact, in a way, the entire point of studying $C$ would be to yield common results about its different members, which would be superfluous in some sense if all members of $C$ turned out to be isomorphic to a representative, and hence to each other.) Thus, we have two questions now:

For what classes $C$ do representatives exist, and can we calculate them?
Is it true that, given two structures which satisfy the same statements, must they be isomorphic? Or to formalize this better, say for first-order statements: if $L$ is a first-order language and $M_1$ and $M_2$ are models of $L$ , and if for every statement $\lambda$ in the language of $L$ we have that $\lambda$ is true for $M_1$ if and only if it is true for $M_2$ , then must $M_1$ and $M_2$ be isomorphic?

It remains to investigate these further.

—

Another related question arises from a re-interpretation of the theorem that motivated this exploration. We can alternatively define an abstract Boolean algebra to be any structure that satisfies all statements true for the specific abstract Boolean algebra $\{0,1\}$ . Now, when thinking about how teach certain concepts in abstract algebra like rings and groups, I’ve found myself motivating them by saying that rings are defined by the set of properties common to both numbers (say real numbers, $\mathbb{R}$ ) and matrices, and similarly groups are defined by the set of properties common to both numbers and sets of symmetries. Indeed, when the properties under consideration are just commutativity/associativity/identity/inverse (what I consider to be the “typical” axioms), then this motivation works great. But is this actually true in a deeper sense as well? In order words, can we say that a first-order statement is true about all rings if and only if it is true for both the ring of real numbers and the ring of matrices? (Or, more precisely, true for $\mathbb{R}$ and the ring of $n\times n$ real matrices for any $n$ ? Actually, in this case since $1\times 1$ matrices are isomorphic to the real numbers, the condition would be true for the ring of $n\times n$ real matrices for any $n\geq 1$ .) Can we offer a similar characterization of groups?

We can actually encompass this question under the concept of representatives above by generalizing the concept of a representative from an element of the class to a subset (or actually, a subclass.) Specifically, given a class of structures $C$ , we can define a representative to be a subclass $C'\subseteq C$ such that for any statement $\lambda$ , $\lambda$ is true for every member of $C$ if and only if it is true for every member of $C'$ . Can we study this further?

In fact, I imagine now that we could even consider the class of all representatives of a class. For example, given $C$ , clearly $C$ itself is a representative of $C$ . This evokes analogies to generating sets for structures like groups; the question would then be to determine properties and characterizations of “generating sets”, in order to provide methods to calculate suitable representatives for given $C$ . In an informal sense, if we can find smaller-size representatives, that’s better.

So with this framework, the question for rings would be rephrased as: is the set of rings of all matrices (which is a set, since it is bijective with $\mathbb{Z}_+$ ) a representative for the class of all rings? A similar question for groups could be: is the class of all groups of symmetries plus the group of real numbers a representative for the class of all groups?

It remains to study these questions.

—

EDIT (03/07/2023): A couple of additions. First, by our current definition, if $C'$ is a representative of $C$ then $C'$ is a representative of any subclass of $C$ too that contains $C'$ . This doesn’t actually permit an alternative characterization of $C$ on its own. We need something stronger for that: we define $C'\subseteq C$ to be a representative of $C$ if $C$ is the class of all structures which satisfy every statement that is true for all members of $C'$ . It is only with that definition that we can say for example that if the set of rings of $n\times n$ matrices is a representative of the class of all rings, then we can define a ring to be a structure which satisfies every property of addition and multiplication for matrices. In general, if we have say a first-order language, call it $L$ , and we have classes $C'\subseteq C$ of models of $L$ , then $C'$ being a representative of $C$ is the same as starting with just $C'$ and defining $C$ to be the class of all models of $L$ that satisfy every statement true for all members of $C'$ .

We note that this concept is a generalization of the idea of a real-closed field: indeed, the field of real numbers is a representative of the class of real-closed fields. I haven’t seen terminology yet in the literature associated to this definition of a representative, but as I mentioned above, at some point it would make sense to replace this term.

Also, we can shed some light on the question of the class of symmetry groups being a representative of the class of all groups, using Cayley’s Theorem. (This is not the conjecture made above, which included the group of real numbers too, but just focusing on the class of symmetry groups seems to be more aligned with how group theory is traditionally motivated in education.) Cayley’s Theorem states that any group is isomorphic to a subgroup of a symmetry group. Thus, let $C$ be the class of all subgroups of symmetry groups; then, if we construct equivalence classes of groups by isomorphism, it follows that this is equivalent to $C$ — explicitly, the class of isomorphism-equivalence classes of groups is in bijection with $C$ . (Actually, do concepts like equivalence classes and bijections apply to general classes, including proper classes? It seems very much so, but I’d need to learn more class theory to be absolutely sure.) Hence, $C$ is a representative of the class of all groups. (Explicitly: let $G$ be a group and let $\lambda$ be a first-order statement in the language of group operations $L$ . If $\lambda$ is true of every member of $C$ , then since $G$ is isomorphic to some member of $C$ , it must be true for $G$ too. Furthermore, if $M$ is some model of $L$ , and if $M$ satisfies every statement true for all members of $C$ , then clearly the group axioms must be true for all members of $C$ , hence $M$ satisfies the group axioms and in fact is a group.)

So we’ve found a representative of the class of all groups that informally expresses the motivational focus on symmetry groups in defining groups. A further question could be: is the class of symmetry groups a representative of the class of all groups? Clearly, not every group is isomorphic to a symmetry group: indeed, there is a finite group of any size $n$ (namely, $\mathbb{Z}_n$ ), but any finite symmetry group must have size $n!$ . Also, a first-order statement that is true for a subgroup may not be true for the “full” group — for example, consider a normal subgroup of a non-abelian group. But is the converse true?

Let $\lambda$ be a first-order statement true about a group $G$ . Must $\lambda$ then be true for every subgroup of $G$ ? If this is the case, then we’d yield that every statement true for all symmetry groups is also true for all members of $C$ , hence true for all groups, so the class of symmetry groups would be a representative of the class of all groups.

We attempt to prove this. Assume for the sake of contradiction that $\lambda$ was true for $G$ but not for a subgroup $H$ of $G$ . Then, …

Actually, can we develop a counterexample? I’m thinking $\lambda$ can be $\exists a \left(a^2=a\right)$ , and we have a group with an idempotent element but with a subgroup that avoids idempotents. Actually, this doesn’t work because $e^2=e$ , but maybe we can modify this then. Specifically, if the language of group operations consists of binary multiplication, unary identity (satisfying $\forall a,b \left(e(a)=e(b)\right)$ ), and unary inverse, then we could try to have $\lambda$ as $\exists a \left(\left(a\neq e(a)\right)\land\left(a^2=a\right)\right)$ . Is this possible?

Well, trivially we could say that $\{e\}$ is a subgroup of $G$ , so the existence of any idempotent beyond $e$ would yield our desired. But the vacuous-ness of this example seems like “cheating”: did we make a mistake somewhere?

To be certain, let’s try a less vacuous example. Take the additive group $\mathbb{Z}_6$ , and look at the subgroup generated by $2$ : $\{0,2,4\}$ . Neither of these elements satisfy $\lambda$ : in particular, $2(4)=8=2$ . But there exists $3\in\mathbb{Z}_6$ that is idempotent, which this subgroup avoids. This shows that our conjecture that every first-order statement true for $G$ must be true for all subgroups of $G$ is false.

It remains to study this. I suspect Cayley’s Theorem will play a useful role here too.

Also, it’s interesting to ask here whether the question depends on the operations in the language, since here we formed $\lambda$ based on having identity and inverse as part of the language. If the language consisted solely of multiplication, then does this change? How about in general for first-order languages and models of them?

—

EDIT (03/08/2023): Some more additions. First, let us emphasize that all the concepts discussed here depend fundamentally on what kinds of statements we consider in terms of whether they apply to $C$ or $C'$ . Implicitly, I’ve been assuming first-order statements. It actually seems from the Boolean algebra Wikipedia article that abstract Boolean algebras are defined by the equations (presumably, identities quantified as for-all in all variables) that hold for $\{0,1\}$ , which is a proper subset of the set of all first-order statements. Now, a definition based on equations may not be as general as we’d like, given that many commonly studied algebraic structures aren’t actually equational classes (like fields), but in general it is very important to specify precisely what kind of statement we consider in order for the definitions to be formalized. If we restrict to equations, then the counterexample above wouldn’t disprove the conjecture that an equation that holds for a group $G$ must hold for a subgroup $H$ of $G$ .

We could restrict this discussion to equational classes and equations at first to simplify and allow more progress in the beginning, and hopefully that could end up shedding some light on the corresponding questions for first-order theories and first-order statements.

Before we do that though, I’d like to go back to a point we discussed earlier about first-order-statement equivalence and isomorphism, which actually now seems quite subtle. I had initially thought that the existence of a representative element $c$ (not just a subclass) would imply that all members of the class would be isomorphic to $c$ , and I disproved that. In light of the abstract Boolean algebra characterization in terms of equations and not first-order statements, that disproof might not actually fully work, but nevertheless we can rescue it here. But after that, I had considered that this could imply that first-order-statement equivalence is weaker than isomorphism. Let us step through this more slowly.

Let us try to show that first-order-statement equivalence is weaker than isomorphism, by disproving the following conjecture: if $M_1$ and $M_2$ are two models of a first-order language $L$ such that for every $L$ -statement $\lambda$ , $\lambda$ is true for $M_1$ if and only if it is true for $M_2$ , then $M_1,M_2$ are isomorphic. We try to exhibit a counterexample: specifically, take a first-order language $L$ and consider the class $C$ of its models, and assume that $C$ has a representative element $c$ . Let $M_1=c$ and $M_2$ be some other element of $C$ , not isomorphic to $M_1$ . (At the time, since I had thought abstract Boolean algebras would satisfy all first-order statements true of $\{0,1\}$ , it was clear that such an $M_2$ could exist.) Since $M_1$ is a representative, if a first-order statement $\lambda$ is true of $M_1$ , then it must be true of all members of $C$ , and in particular it must be true of $M_2$ . But the converse isn’t necessarily true. If $\lambda$ is true of $M_2$ , then it may not be true of all members of $C$ , and thus it may not be true of $M_1$ . Thus, this isn’t necessarily a counterexample.

But we can actually resolve the isomorphism/first-order question anyway with the counterexample of real-closed fields. There, a field $K$ is defined to be a real-closed field if every first-order statement true of the real numbers is true of $K$ , and vice versa. As stated in the Wikipedia article, we can take $K$ to be the field of real algebraic numbers, which is not bijective with $\mathbb{R}$ and hence not isomorphic. The reason why this yields a successful counterexample is because the single elements of the class imply first-order statements on each other. The logic in the previous paragraph would only yield a successful counterexample if the class $C$ had two elements.

This inspires a question: is the field of real numbers actually a representative of the class of real-closed fields? Or are the real-closed fields a more restrictive class? In general, it looks like $C'$ being a representative of $C$ yields that $C$ is a wider class than the class of all structures that on their own each imply first-order-statement equivalence to all members of $C'$ . To better pose these questions, let’s introduce some more terminology and formalize things (note that we write these for general first-order statements, but we could easily write the analogous definitions and questions for just equations instead):

Definition. Let $L$ be a first-order language and let $C$ be a class of models of $L$ . The first-order wide closure of $C$ is the class $W$ of models of $L$ such that $C$ is a representative of $W$ . The first-order narrow closure of $C$ is the class $N$ of all models of $L$ such that, for any $m\in N$ , a first-order $L$ -statement $\lambda$ is true of $m$ if and only if it is true of all members of $C$ .

(If there is confusion between whether we are using the first-order or equational definition, we can simply attach “first-order” or “equational” respectively as an adjective. Thus, we can instead speak of the “equational wide closure” or “equational narrow closure”, and so on.)

As our setup suggests, we (strongly) suspect that in general the narrow closure is a “strictly smaller” subclass of the wide closure, i.e. $N\subseteq W$ and $N\neq W$ . Let’s prove this explicitly just to practice and make sure we’re not missing any subtle points.

Basically, the difference between the narrow and wide closures is of the form $\forall m (P(C)\leftrightarrow P(m))$ versus $P(C)\leftrightarrow (\forall m P(m))$ . With this high-level view, it is obvious that the narrow closure is a subset of the wide closure: the narrow closure is the class of models first-order-statement equivalent to $C$ , while the wide closure also contains models that satisfy all the first-order statements true in $C$ , as well as possibly more. Explicitly: if $C$ is a class and $N,W$ are its narrow and wide closures respectively, and if $m\in N$ , then for any first-order statement $\lambda$ if $\lambda$ is true for $C$ then it is true for $m$ , so $m\in W$ . Hence, $N\subseteq W$ . It is also clear that the wide closure is in general strictly larger than the narrow closure: showing this is the same as showing that there exist models that satisfy all first-order statements true for $C$ as well as other first-order statements not true in $C$ . A quick example is the class of groups, for which a representative is the class of all symmetry groups and their subgroups (this is our $C$ ), and which also contains abelian groups that satisfy the first-order statement of the commutative property.

While this is a general result, we can ask whether for specific $C$ the wide closure is in fact equal to the narrow closure. If this is the case, then this would be a quite awesome result, similar in some analogous sense to the Fundamental Theorem of Algebra being true specifically for the real numbers. Thus, we can still ask: is the narrow closure of $\mathbb{R}$ (which by definition is the class of real-closed fields) equal to the wide closure of $\mathbb{R}$ ? Equivalently, is $\mathbb{R}$ a representative for the class of real-closed fields? Or put another way, does there exist a field that satisfies all first-order statements true in $\mathbb{R}$ and also some first-order statement not true in $\mathbb{R}$ ?

It remains to investigate this.

As a sidenote, the notion of elementary equivalence that I have just heard about is encompassed within these definitions; specifically, the narrow closure of the class of a single model $\{m\}$ is exactly the class of models elementarily equivalent to $m$ . However, for a class with more than one element, our definition seems to offer more extensible language.

Another sidenote that is more “meta”: the titles of posts in this series are somewhat inaccurate or at least incomplete, since some of my other explorations concern different kinds of axiomatizations too (like topology as an algebraic structure.) However, changing post names is not something I ever want to do, since that would change URLs and break links; instead, my approach is to just attach “EDIT” tags to indicate a new direction. That is in-line with my “stream of consciousness” style as I try to work through and figure things out in “real-time”; then, we can both chronicle the motivation and work, as well as have a final “round-up” summary later on for clearer communication. I also think this kind of inclusion of motivation is really useful for research purposes too; I will probably publish a post on that topic at some point.

Nevertheless, the upshot is that I could have many other explorations dealing with non-standard axiomatizations of commonly studied math structures which are not included in this series. But I will definitely move towards chronicling it all under one title or another.

Separately, I’d like to try to formalize and resolve a question I had posed earlier, about whether the operations used in the language matter when we have equivalent but differently stated axiomatizations of a given class. For example, groups can be axiomatized by just multiplication and first-order statements, or by multiplication, identity, inverse, and equations; as we can see from Working On It (as referenced in the first post of this series), they can alternatively be axiomatized by just division and equations (actually, a single equation.) Let us formalize this scenario in general (in terms of first-order statements, in such a way that equations and other subsets of first-order statements are encompassed too):

Conjecture. Let $L_1,L_2$ be first-order languages, let $A_1$ be a set of statements in the language of $L_1$ , and let $A_2$ be a set of statements in the language of $L_2$ . Assume that, for any model $(U,I_1)$ of $A_1$ (with $M$ the universe and $I_1$ the interpretation function), there exists a corresponding interpretation function $I_2$ on $U$ for the language $L_2$ , such that … (I will complete this at some time.)

This discussion is continued in a follow-up post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply