Non-Standard Axioms for Various Math Structures 5

In this post, we continue the discussion from the previous in the series.

What is $Clo(C,c \rightarrow C)$ ? It is the class of all $c$ such that, if any statement is true about $c$ , then it is true for every member of $C$ . (Note that all statements in this post — and series — are assumed to be “bound statements,” in the sense that all variable occurrences are bound, as elaborated on in my exploration on equivalency of logical truth in models.) Thus, $c$ “contains” all statements in the “intersection” of statements across members of $C$ . In some informal sense, while $Clo(C,C \rightarrow c)$ is a sort of “upward” closure (where the $c$ can “contain” or more precisely satisfy statements not in $C$ too, as long as they satisfy those in $C$ ), $Clo(C,c \rightarrow C)$ is a sort of “downward” closure (where the $c$ must contain only statements true in $C$ , but they can neglect some statements too — they don’t have to satisfy everything true in $C$ .)

In some sense, gaining insight about both types of closures can reduce to the existence of models that satisfy “hand-picked” sets of statements. Given a set of statements $S$ , can we find models $c$ that satisfy only the statements in $S$ , and nothing else? Variants of this general form of the question can probably yield insights about both kinds of closures.

I suspect that this question would differ wildly depending on whether we talk about first-order or equational logic. Indeed, first-order logic would seem much less behaved due to its greater generality, and especially because for any first-order statement $\lambda$ , we can form the statement $\neg\lambda$ . Thus, if a model $c$ doesn’t satisfy $\lambda$ , then it must satisfy $\neg\lambda$ .

In fact, I’m pretty sure we can use this to show that $c$ can’t exist for first-order — in other words, first-order closures must always be empty. In that case, logical closure theory would reduce to the interesting case of equational closures, and we know from previous examples in the previous posts in the series that this is an interesting case. Let’s try to show the emptiness of closures for first-order, and let’s try to do it for any class $C$ (say any non-empty class, and maybe some other non-triviality restrictions, like that $C$ can’t be a singleton. Actually, let’s consider all the cases and address this question in general.)

Consider first the case $Clo(C,c \rightarrow C)$ . Assume $C$ is empty. Assume that $c$ exists. Then, for any statement $\lambda$ , if it is true for $c$ , then it must be true for all members of $C$ . But a statement can’t be true for all members of an empty set … actually, this gets down to vacuousness of definitions. So let’s ignore this case.

Next, assume $C$ is a singleton, $C = \left\{ d \right\}$ . Assume that $c$ exists. Then, for any statement $\lambda$ , if it is true for $c$ , then it must be true for $d$ . I’m pretty sure this implies that $c = d$ . Actually, no, $c$ and $d$ could be elementary equivalent, as is the case say for real-closed fields.

So actually, first-order closures aren’t in general empty. But what I think we can show is that for first-order, and $C$ nonempty, $Clo(C,c \rightarrow C) = Clo(C,C \rightarrow c) = Clo(C,c \leftrightarrow C)$ . In other words, for first-order, equivalence (of bound statement truth) is the only option. (And again, my intuition for this claim comes from negation of first-order statements.)

OK, so let’s try to show this. Let’s go back to the case of $Clo(C,c \rightarrow C)$ , and assume that $C$ is nonempty. Assume that $c \in Clo(C,c \rightarrow C)$ . We want to show that in fact any statement true about $C$ must be true about $c$ — the $C \rightarrow c$ implication. We have that for any statement $\lambda$ , if $\lambda$ is true for $c$ , then it is true for $C$ . Now, assume that a statement $\lambda$ is true for $C$ , and assume for the sake of contradiction that it isn’t true for $c$ . That means that $\neg\lambda$ is true for $c$ . But then that implies that $\neg\lambda$ is true for $C$ , and $\lambda$ is also true for $C$ , a contradiction. Hence, $Clo(C,c \rightarrow C) = Clo(C,c \leftrightarrow C)$ .

Exactly similar logic shows that $Clo(C,C \rightarrow c) = Clo(C,C \leftrightarrow c)$ . Let $c \in Clo(C,C \rightarrow c)$ . We have that for any statement, if it is true for $C$ , then it is true for $c$ . Now, assume for the sake of contradiction there was a statement $\lambda$ true in $c$ but not true in $C$ . Actually, here we can’t use the exact same argument, since it’s possible that $\lambda$ is true for some members of $C$ but not others; we just have that $\lambda$ isn’t true for all members of $C$ . Hopefully we can produce a particular member of $C$ (assuming $C$ is nonempty of course) that evokes a contradiction? We know that there exists $d \in C$ such that $\lambda$ isn’t true in $d$ . Thus, $\neg\lambda$ is true in $d$ . Ugh, but we can’t really go back to an implication on $c$ from this, since again the implication is based on statements that are true for all members of $C$ . So I actually suspect this equality isn’t true, that $Clo(C,C \rightarrow c)$ can be different from $Clo(C,C \leftrightarrow c)$ . Of course, we have the equality in the special case where $C$ is a singleton.

Note also that $Clo(C,C \leftrightarrow c)$ doesn’t exactly reduce to elementary equivalence — that term would only be applicable in the case that $C$ is a singleton. The term could be expanded to include elementary equivalence to a class of models, but since we’re already going to use the notation we introduced for the case of equational logic, no issue in just having the notation available in general.

—

Is $Clo(C,c \rightarrow C)$ similarly trivial for equational logic? Obviously, we can’t use the same negation argument as earlier. Actually, on second thought it seems plausible that this is nontrivial for equational logic — “holding” all the equations is more likely to be nontrivial than “holding all the first-order statements,” since equations are less general. Let’s try to come up with a nontrivial example of this.

Let’s look at abstract Boolean algebras. If $C$ is a singleton consisting of the Boolean algebra $\left\{ 0,1 \right\}$ , then we know that if $c$ is an abstract Boolean algebra, any equation that holds in $c$ would hold in $\left\{ 0,1 \right\}$ and thus $C$ . (EDIT, 04/27/2023: I’m not actually sure how I concluded this, and it looks like a mistake with conversive logic. If an equation is true of $\left\{ 0,1 \right\}$ then it is true of $c$ , but not necessarily vice versa. This casts into doubt the ensuing conjecture, which I anyway wasn’t able to prove.) Thus, $Clo\left( \left\{ 0,1 \right\},c \rightarrow C \right)$ actually contains all abstract Boolean algebras.

In fact, is this true in general? Are the “roles reversed” between the two closures? In other words, do we have that if $D = Clo(C,C \rightarrow c)$ , then $C = Clo(D,c \rightarrow C)$ ? And even vice versa?

Let’s try to show this. Say that $D = Clo(C,C \rightarrow c)$ . Now, consider $D^{'} = Clo(D,c \rightarrow C)$ ; we want to show that $D^{'} = C$ . Say that $c \in C$ ; we want to show that $c \in D^{'}$ . Say that a statement $\lambda$ is true about $c$ ; is it true about $D$ ? Well, $c \in C$ , and any statement true about $C$ is true about every member of $D$ , by definition of $D = Clo(C,C \rightarrow c)$ . But just because a statement is true about $c$ doesn’t mean it’s true about all of $C$ . So we can’t conclude this just yet. In fact, the singleton in the previous example seems to be especially important for the argument here.

But $D = Clo(C,C \rightarrow c)$ doesn’t just mean that every statement true of $C$ is true of $D$ ; it means that there is no model outside of $D$ for which every statement true of $C$ is true of that model. By definition, $D$ contains all such models. So maybe we can do a reverse implication here. Say that $c \notin D^{'}$ ; can we show that $c \notin C$ ?

So we have $c \notin D^{'}$ (different from $c \notin D$ , but we’ll get to that conjecture later.) We have that $D^{'}$ is the class of all $c$ such that any statement true of $c$ is true of $D$ . Hence, since $c \notin D^{'}$ , we must logically have either:

No statements are true of $c$ ; or
There exists a statement true of $c$ but not true of some member of $D$ .

It’s not possible for there to be no true statements for $c$ ; even for equational logic, $\forall a(a = a)$ always holds. So the second condition must be true: there must exist some $\lambda$ that is true of $c$ but not true of some member of $D$ .

Now, assume for the sake of contradiction that $c \in C$ . Then, because $\lambda$ is true of $c$ … but actually, it’s very possible for $\lambda$ not be true of some other member of $C$ , so it wouldn’t have to be true of $D$ . So this argument fails here.

What about at least a subclass relation? Our argument for $c \in C \rightarrow c \in D^{'}$ fails, but what about $c \in D^{'} \rightarrow c \in C$ ? In other words, this would show that $Clo\left( Clo(C,C \rightarrow c),c \rightarrow C \right) \subseteq C$ . Is this true?

Assume that $c \in D^{'}$ , so that if a statement is true of $c$ , then it is true of $D$ . But if a statement is true of $D$ , then it is true of $C$ . Conversely, if a statement is true of $C$ , then it is true of $D$ , by definition of the $C \rightarrow c$ closure. Then, by definition of the $c \rightarrow C$ closure, the statement must be true of $c$ … actually, that is not true, that looks like conversive logic.

So what have we shown here? That if a statement is true of $c$ , then it is true of $C$ . Thus, $c \in Clo(C,c \rightarrow C)$ . Thus, we have shown actually that $Clo\left( Clo(C,C \rightarrow c),c \rightarrow C \right) \subseteq Clo(C,c \rightarrow C)$ .

I actually think we can generalize this massively though: if $C \subseteq D$ , then $Clo(D,c \rightarrow C) \subseteq Clo(C,c \rightarrow C)$ .

Incidentally, using $c \in D$ with this notation seems confusing, so let’s rename our variables: if $C_{1} \subseteq C_{2}$ , then $Clo\left( C_{2},c \rightarrow C \right) \subseteq Clo\left( C_{1},c \rightarrow C \right)$ . Of course, this would imply a similar assertion with the opposite ordering: if $C_{1} \supseteq C_{2}$ , then since $C_{2} \subseteq C_{1}$ , we have $Clo\left( C_{1},c \rightarrow C \right) \subseteq Clo\left( C_{2},c \rightarrow C \right)$ , or $Clo\left( C_{2},c \rightarrow C \right) \supseteq Clo\left( C_{1},c \rightarrow C \right)$ . The intuition for this guess is that if $C_{1} \subseteq C_{2}$ , then there are “more statements to hold” for each $c$ in the downward closure for $C_{2}$ , so that the resulting class would be smaller.

Let’s try to prove this. Assume $c_{2} \in Clo\left( C_{2},c \rightarrow C \right)$ . Then, by definition, if a statement is true of $c_{2}$ , it is true of $C_{2}$ . But since $C_{1} \subseteq C_{2}$ , it must be true of $C_{1}$ too. Thus, $c_{2} \in Clo\left( C_{1},c \rightarrow C \right)$ .

OK, well, that was anti-climactic.

Is the converse true too? Assume $Clo\left( C_{2},c \rightarrow C \right) \subseteq Clo\left( C_{1},c \rightarrow C \right)$ . Let $c_{1} \in C_{1}$ ; we want to show that $c_{1} \in C_{2}$ . Well, for any $c_{2} \in Clo\left( C_{2},c \rightarrow C \right)$ , we have $c_{2} \in Clo\left( C_{1},c \rightarrow C \right)$ , so if a statement is true of $c_{2}$ , then it must be true of $C_{1}$ , and thus of $c_{1}$ . Thus, any statement true of any element of $Clo\left( C_{2},c \rightarrow C \right)$ is true of $c_{1}$ …

—

Actually, do we even have generally that $C \subseteq Clo(C,c \rightarrow C)$ ? It doesn’t seem obviously true. If this fails, then that would go pretty strongly against our natural intuition around the term “closure.” So if this fails, while the analogy to $Clo(C,C \rightarrow c)$ in notation is interesting, maybe it’s best to consider this concept outside of logical closure theory and under a separate, more meaningful name and notation. In that case, only the concepts $Clo(C,C \rightarrow c)$ and $Clo(C,C \leftrightarrow c)$ would remain for this particular exploration.

Let’s try to show the failure of $C \subseteq Clo(C,c \rightarrow C)$ with a counterexample, since I’m suspecting that. Specifically, it seems that if $C$ is not a singleton, then we have issues. Now, of course, for first-order logic we just have $Clo(C,c \rightarrow C) = Clo(C,c \leftrightarrow C)$ , so in that case we clearly have $C \subseteq Clo(C,c \rightarrow C)$ . So our counterexample should be from equational logic.

What’s our approach? We want to construct a set $C$ of two models which satisfy different equations. If that’s the case, then an equation being true in one doesn’t imply that it’s true for both, so neither model in $C$ would be part of the “closure.”

But this is obvious! Simply take say $\mathbb{Z}_{2}$ and $\mathbb{Z}_{3}$ with addition. Then, $\mathbb{Z}_{2}$ satisfies $x + x = 0$ , but $\mathbb{Z}_{3}$ doesn’t satisfy this (take $x = 1$ for example.) And furthermore, $\mathbb{Z}_{3}$ satisfies $x + x + x = 0$ , but $\mathbb{Z}_{2}$ doesn’t (take $x = 1$ for example.)

In fact, we can generate an infinite number of counterexamples with $\mathbb{Z}_{p}$ and $\mathbb{Z}_{q}$ for any pair of primes $(p,q)$ , in this same way. Thus, $C \subseteq Clo(C,c \rightarrow C)$ generally fails, and the name “closure” hence doesn’t really apply to this concept.

But wait … this seems to say something about $Clo(C,c \rightarrow C)$ for first-order. This logic would seem to work for first-order too. Indeed, $x + x = 0$ and $x + x + x = 0$ are first-order statements, thus neither $\mathbb{Z}_{2}$ nor $\mathbb{Z}_{3}$ would be part of $Clo\left( \left\{ \mathbb{Z}_{2},\mathbb{Z}_{3} \right\},c \rightarrow C \right)$ . But we also have that $Clo\left( \left\{ \mathbb{Z}_{2},\mathbb{Z}_{3} \right\},c \rightarrow C \right) = Clo\left( \left\{ \mathbb{Z}_{2},\mathbb{Z}_{3} \right\},c \leftrightarrow C \right)$ , so $\mathbb{Z}_{2},\mathbb{Z}_{3} \notin Clo\left( \left\{ \mathbb{Z}_{2},\mathbb{Z}_{3} \right\},c \leftrightarrow C \right)$ . And we can yield similar counterexamples where we have $Clo(C,c \leftrightarrow C)$ that contains no element of $C$ . So the term “closure” wouldn’t really apply to this either!

So actually, while they are interesting concepts, we shouldn’t use the term “closure” for $Clo(C,c \rightarrow C)$ or $Clo(C,c \leftrightarrow C)$ , since in general they only contain $C$ when $C$ is a singleton. Thus, we’d want to consider them separately, outside logical closure theory, and probably with a different notation.

We can try to replace the $Clo$ part of the notation to something else that is more evocative of the meaning. All these concepts deal with logical implication around classes of models, so maybe something like $Locl$ ? So we can write $Locl(C,c \rightarrow C),Locl(C,c \leftrightarrow C),Locl(C,C \rightarrow c)$ , where only the last of these would be the “logical closure.” (We can now say “the” without ambiguity, and alternatively just denote it as $Clo(C)$ .)

That anyway makes more sense given what we started this exploration with, from the example of abstract Boolean algebras: that only corresponds to $Clo(C)$ .

—

Actually, can we use this example to motivate the proof of an even stronger characterization? We know that if $C$ consists of models elementary equivalent to each other then $Locl(C,c \rightarrow C) = Locl(C,c \leftrightarrow C)$ would just be the class of models elementary equivalent to the elements of $C$ . Can we say more strongly that $Locl(C,c \rightarrow C) = Locl(C,c \leftrightarrow C)$ are non-empty exactly when the elements of $C$ are elementary equivalent to each other, and in that case this is just equal to the class of all models elementary equivalent to the elements of $C$ ? Is this true only for first-order or for equational logic too? (Here, we use “elementary equivalent” to refer to bound-statement truth equivalence regardless of logic, as first done in a previous exploration.)

First, say that $C$ consisted of models that are elementary equivalent to each other. Then, what is $Locl(C,c \rightarrow C)$ ? It’s the class of all models $c$ such that, if a statement is true for $c$ , then it is true for $C$ . But if a statement is true for any element of $C$ , then it is true for all of $C$ , and conversely. Thus, if a model $c$ is elementary equivalent to an element of $C$ , then if a statement is true of $c$ , it will be true of that element of $C$ , and hence of all of $C$ . Thus, $c \in Locl(C,c \rightarrow C)$ . Furthermore, if $c \in Locl(C,c \rightarrow C)$ , so that any statement true for $c$ is true for all of $C$ , then pick any element $d \in C$ ; any statement true in $c$ is true in all of $C$ , and therefore in $d$ . But if a statement is not true in $c$ , then we show that it is not true in $d$ , so that $c$ and $d$ are elementary equivalent. Assume for the sake of contradiction that the statement was true in $d$ , so that it was true in all of $C$ . Then, since $Locl(C,c \rightarrow C)$ is the class of all models such that statements in $c$ imply statements in $C$ … actually, I’m not sure how to finish up a proof from that. But we do have this clearly if we just talk about first-order logic, since if the statement isn’t true in $c$ then its negation is true in $c$ , thus its negation is true for all of $C$ , but that’s impossible since the statement is true for all of $C$ too.

Thus, we have that for first-order, $Locl(C,c \rightarrow C) = Locl(C,c \leftrightarrow C)$ is the class of models elementary equivalent to all elements of $C$ .

But can we go further, as conjectured earlier? If $C$ contains two models $d_{1},d_{2}$ that are not elementary equivalent, then can we show that $Locl(C,c \rightarrow C)$ is empty?

Assume that there existed $c \in Locl(C,c \rightarrow C)$ . Since $d_{1},d_{2}$ are not elementary equivalent, there must exist a statement $\lambda$ true in $d_{1}$ but with $\neg\lambda$ true in $d_{2}$ — for if this weren’t true, then for all statements $\lambda$ we’d have either $\lambda$ is true in both $d_{1}$ and $d_{2}$ , or $\neg\lambda$ is true in both $d_{1}$ and $d_{2}$ , but then that would imply that $d_{1},d_{2}$ are elementary equivalent. Now, consider whether $\lambda$ is true of $c$ . If it is true of $c$ , then it must be true of all of $C$ , and thus of $d_{2}$ , contradiction. Otherwise, if it is false for $c$ , then its negation must be true for $c$ , so its negation must be true for all of $C$ , and thus its negation must be true for $d_{1}$ , contradiction.

Thus, we have completely characterized first-order $Locl(C,c \rightarrow C)$ and $Locl(C,c \leftrightarrow C)$ entirely in terms of elementary equivalence of individual models. There is thus nothing further to consider for these concepts for first-order; their theory is entirely contained in the theory of elementary equivalence.

—

The constructs $Locl(C,c \rightarrow C)$ and $Locl(C,c \leftrightarrow C)$ may be interesting to consider for other logics like equational logic, but we can discuss them separately, as they don’t seem like they should topically belong to logical closure theory.

And while we’re at it, let’s remember that this whole discussion started not from logical closures (going from $C$ to $c$ ), but the other way around. In fact, the title of this series is “Non-Standard Axioms for Various Math Structures,” and that seems to align better with starting with a class $C$ and finding a “non-standard” axiomatization with a “representative” subclass. We argued that “representative” wasn’t a great term since it could be confused with other uses of the word “representation” in math, but now I have a better term that really strongly connotes the inherent meaning of what we are studying: logical basis.

So let’s go back to considering classes $C$ and logical bases of them — subclasses for which $C$ can be “generated” as the class of all models satisfying all statements true of the basis. For example, as noted earlier:

The Boolean algebra $\left\{ 0,1 \right\}$ is a singleton equational basis for the class of abstract Boolean algebras;
The class of permutation groups is an equational basis for the class of all groups.

Instead of calling this study “logical closure theory,” a better term now would be “logical basis theory.”

Thus, we can study logical basis theory, and we can note that another point of view on this concept leads naturally to the definition of $Clo(*)$ as given earlier, and that further leads naturally to the definitions of the $Locl$ constructs. I’m not sure what we should call the study of the $Locl$ constructs, especially for equational logic, where they might still be interesting — we can now consider that as a separate but possibly related question.

—

Let’s try to dive further into $Locl$ in the equational case. Can we adapt the elementary equivalence result to this logic? Say that two models $a$ and $b$ are elementary equivalent by equational logic: any equation true in $a$ is true in $b$ , and vice versa. This actually means that negations of equations are preserved too: if an equation were not true in $a$ , then it couldn’t be true in $b$ , for if it were true in $b$ , then it would have to be true in $a$ , producing a contradiction in $a$ . So elementary equivalence here preserves negation of equations. Let’s say then that we are looking at $Locl(C,c \leftrightarrow C)$ , where $C$ consists of models that are elementary equivalent to each other. What would $Locl$ have to be?

Well, we conjecture that $Locl$ would have to be the class of all models elementary equivalent to each element of $C$ . If a model $c$ is elementary equivalent to an element of $C$ , then if an equation is true of $c$ , it will be true of that element of $C$ , and hence of all of $C$ . Conversely, if an equation is true of all of $C$ , then it is true of that element of $C$ , and thus true of $c$ . Hence, $c \in Locl(C,c \leftrightarrow C)$ . Furthermore, if $c \in Locl(C,c \leftrightarrow C)$ , then any equation true for $c$ is true for all of $C$ , so pick any element $d \in C$ ; we have that any equation true in $c$ is true in $d$ . But assume an equation is true in $d$ ; then, it must be true in all of $C$ . But since $c \in Locl(C,c \leftrightarrow C)$ , the equation must be true in $c$ . Thus, $c$ and $d$ are elementary equivalent. It follows that $Locl$ is exactly the class of models elementary equivalent to the elements of $C$ .

Furthermore, say that $C$ contained elements not elementary equivalent to each other; then, we show that $Locl$ is empty. We have that there exist $d_{1},d_{2} \in C$ not elementary equivalent to each other, and thus there must exist an equation $E$ true in $d_{1}$ but not true in $d_{2}$ — for if this weren’t the case, then every equation true or not true in $d_{1}$ would have to be true or not true (respectively) in $d_{2}$ , so that $d_{1}$ and $d_{2}$ are elementary equivalent. Now, assume for the sake of contradiction that there existed $c \in Locl$ ; is $E$ true of $c$ ? If yes, then we have a contradiction with $d_{2}$ . If no, then $\neg E$ is true for $c$ ; if $E$ was true of some element of $C$ , then since the elements of $C$ are elementary equivalent to each other $E$ would be true of all of $C$ , and hence of $c$ , producing a contradiction in $c$ . Thus, $\neg E$ is true of every element of $C$ , but that yields a contradiction in $d_{1}$ .

It follows that for equational logic $Locl(C,c \leftrightarrow C)$ reduces to elementary equivalence of individual models. However, it seems hard to replicate these proofs for $Locl(C,c \rightarrow C)$ since in some parts we run into conversive logic.

—

We consider another idea for gaining insight into $Locl$ in the equational case. To mimic the point of view that we have been taking on $Clo$ , where we are first given $Clo(C)$ and then try to find suitable $C$ , let’s do a similar thing for $Locl(C,c \rightarrow C)$ . Specifically, say we are given $C^{'} = Locl(C,c \rightarrow C)$ and we are trying to find $C$ . What does knowledge of $C$ mean about $C^{'}$ ? What information can that yield?

Well, we are by hypothesis given $C^{'}$ , or the class of all $c$ such that if any equation is true in $c$ , then it is true in every member of $C$ . So $C^{'}$ is the class of all models that “contain” subsets of the equations true of all of $C$ — but not other equations that are not true of $C$ . In other words, $C$ is a sort of “union” of all equations over all elements of $C^{'}$ : $C$ “contains” (satisfies) the set of equations that are true for some element of $C^{'}$ . In some sense, then, $C$ is the “logical union” of equations across $C^{'}$ , containing all equations that would be encompassed by some element of $C^{'}$ .

It seems like this would be very hard to exist, especially if $C^{'}$ contains a diversity of equations, some of which may contradict each other. Can we show that for “most $C^{'}$ ” a suitable $C$ can’t exist? Hopefully that could even lead to our desired elementary equivalence reduction!

It remains to try this.

—

This discussion continues in the next post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply