Non-Standard Axioms for Various Math Structures 6

We continue the discussion from this post.

Let’s consolidate notation and different points of view by summarizing our insights thus far. We have:

For a class of models $C$ , we can define $Locl(C,C \rightarrow c),Locl(C,c \rightarrow C),Locl(C,C \leftrightarrow c)$ , in the manner given previously. In particular, $Locl(C,C \rightarrow c)$ can be viewed as providing a “logical basis”: given $C^{'}$ , a logical basis may be defined to be a subclass $C$ such that $C^{'} = Locl(C,C \rightarrow c)$ .
As examples, an equational logical basis for the class of all abstract Boolean algebras is the singleton consisting of $\left\{ 0,1 \right\}$ , and an equational logical basis for the class of all groups is the class of all permutation groups.
For first-order logic, $Locl(C,c \rightarrow C) = Locl(C,C \leftrightarrow c)$ , and these two reduce to elementary equivalence (for nonempty $C$ ) in the following sense: if $C$ consists of models that are not elementary equivalent to each other then these are empty, otherwise these are the classes of models elementary equivalent to each element of $C$ .
A similar result holds for equational logic but restricted to $Locl(C,C \leftrightarrow c)$ : if $C$ consists of models that are not elementary equivalent to each other then it is empty, otherwise it is the class of models elementary equivalent to each element of $C$ .

—

Can we establish a classification similar to point (3) of the other $Locl$ , namely $Locl(C,C \rightarrow c)$ , using similar arguments hinging on the fact that first-order logic includes negation?

Our intuition is that such a result would “go the other way” compared to $c \rightarrow C$ . Specifically, we conjecture the following: if $C^{'} = Locl(C,C \rightarrow c)$ , then if $C^{'}$ consists of all models elementary equivalent to a given model $m$ , any subclass of $C^{'}$ suffices for $C$ ; otherwise, no such $C$ exists. In fact, such a result could be stated cleanly using the language of a logical basis: if $C^{'}$ is a class of models, then if $C^{'}$ consists of all models elementary equivalent to a given model $m$ then any subclass of $C^{'}$ is a logical basis, otherwise no logical basis exists. (EDIT, 04/27/2023: this is not actually “the other way” compared to $c\rightarrow C$ — it in fact predicts the same classification for $C\rightarrow c$ as we yielded earlier for $c\rightarrow C$ .)

This is clearly different from the situation with equational logic, as we can see with the equational logical basis examples we’ve mentioned earlier. This is not surprising, since we weren’t able to achieve a similar reduction for $Locl(C,c \rightarrow C)$ in equational logic to elementary equivalence; it seems instead that $Locl(C,C \rightarrow c)$ and $Locl(C,c \rightarrow C)$ in equational logic are the two nontrivial concepts.

Let’s try to prove the first-order logical basis classification conjectured here. First, assume that $C^{'}$ consists of all models elementary equivalent to $m$ , and let $C$ be any subclass. If $c \in C^{'}$ , then $c$ must be elementary equivalent to $m$ , but $m$ is elementary equivalent to each member of $C$ , thus $c$ is elementary equivalent to each member of $C$ . Thus, every first-order statement true about each member of $C$ will be true of $c$ , and $c \in Locl(C,C \rightarrow c)$ . Conversely, if $c \in Locl(C,C \rightarrow c)$ , then every first-order statement true of some member of $C$ will be true of all members of $C$ (since they are elementary equivalent to each other), hence for each member of $C$ , every statement true about that member of $C$ is true about $c$ . The converse is true too, which we can see with the inverse statement and the negation of a first-order statement. Hence, $c$ is elementary equivalent to each member of $C$ , and thus to $m$ , so that $c \in C^{'}$ . Thus, we have classified logical bases of $C^{'}$ completely when it is of this form.

Now, assume $C^{'}$ has a logical basis $C$ ; we show that $C^{'}$ must consist of all models elementary equivalent to some $m \in C^{'}$ . (Of course, we assume $C^{'}$ is nonempty.) Assume for the sake of contradiction that for all $m \in C^{'}$ , $C^{'}$ is not equal to the class of models elementary equivalent to $m$ .

For any $m \in C^{'}$ , define $E(m)$ to be the class of models elementary equivalent to $m$ . We have $E(m) \neq C^{'}$ . First, we can “remove elementary equivalent models” from $C$ , in the following way: define $D$ to be a subclass of $C$ such that $D$ contains no pairwise equivalent models, and every model in $C$ is equivalent to a model in $D$ . (We’ll henceforth drop the “elementary” since it’s clear from context when applied to pairs of models.) (The existence of $D$ is guaranteed from NBG by the Axiom of Choice: form the class of equivalence classes of $C$ by elementary equivalence, then pick an element out of each equivalence class using the Axiom of Choice.) Then, we have that $D \subseteq C$ , $D$ contains only non-equivalent models, and $D$ is a logical basis for $C^{'}$ . We can see that $D$ is a logical basis for $C^{'}$ by showing that if a statement is true for $D$ then it is true for $C$ , and vice versa. Indeed, this is true: if a statement is true for $D$ , then since every model in $C$ is equivalent to a model in $D$ , the statement is true for $C$ . The converse is obvious since $D \subseteq C$ . The upshot of this is that we can “remove equivalent models” from $C$ so that $C$ only contains non-equivalent models (we basically rename $D$ to $C$ here, and discard the notation for the original $C$ .) Thus, assume without loss of generality that $C$ has non-pairwise-equivalent models.

Now, let $c \in C$ , and consider $E(c)$ . For any $m \in E(c)$ , if a statement is true about $C$ then it is true about $c$ , and thus about $m$ ; hence, $E(c) \subseteq C^{'}$ . Since $E(c) \neq C^{'}$ , $E(c)$ is a proper subclass of $C^{'}$ . Also, since elements of $C$ are pairwise non-equivalent, if $c \neq d$ are different elements of $C$ then $E(c),E(d)$ are disjoint. Now, consider $\cup_{c \in C}E(c)$ ; is this a proper subclass of $C^{'}$ ? (It’s clearly a subclass.)

If $C^{'} = \cup_{c \in C}E(c)$ , then we derive a contradiction. If a statement is true for all of $C$ … actually, the issue seems to be that a statement could be true of some elements of $C$ but not others, so that the first-order negation method doesn’t work here. So I’m not sure about this first-order elementary reduction conjecture anymore; we just have that in the case that $C^{'}$ is the class of all models elementary equivalent to some $m$ , any subclass is a logical basis.

Actually, we should change the definition of basis here, inspired by our construction to remove equivalent models within — a basis should be “as minimal as possible” (similar to the intuition for linear independence for vector spaces, or uniqueness relations for the general free object of universal algebra.) A logical basis for $C^{'}$ should not just “generate” $C^{'}$ , but also not have equivalent models within it.

Even if it seems that a first-order logical basis isn’t necessarily reducible to elementary equivalence, can we at least offer a classification as suggested here? Namely, can we show that if $C$ is a logical basis of $C^{'}$ , then $\left\{ E(c):c \in C \right\}$ is a partition of $C^{'}$ ? We already have that the $E(c)$ are pairwise disjoint; it just remains to show that $\cup_{c \in C}E(c) = C^{'}$ .

Let’s try to show this. Assume for the sake of contradiction that there exists $m \in C^{'}$ with $m \notin \cup_{c \in C}E(c)$ . Thus, $m \notin E(c)$ for any $c \in C$ ; in particular, $m$ isn’t equivalent to any $c \in C$ .

Now, “a statement true for $C$ is true for $m$ ” is equivalent by contrapositive to “if a statement is not true for $m$ , then it must fail for some $c \in C$ .” If a statement is not true for $m$ , then its negation is. But alas, this doesn’t imply much about $C$ , since this runs into the same issue from before: unlike for $c \rightarrow C$ where a statement’s truth (or falsity) implied something for all of $C$ , now it only implies something about some element of $C$ . That seems harder to derive a contradiction from. So I’m not sure about the truth of this conjecture earlier.

Note that the classification we showed in the case that $C^{'}$ is the class of all models equivalent to some $m$ works in any logic, not just first-order.

—

Let’s summarize again all our insights so far, now with our new thoughts:

For a class of models $C$ , we can define $Locl(C,C \rightarrow c)$ to be the class of all models $c$ such that, if a statement is true of every member of $C$ , then it is true of $c$ . We can define $Locl(C,c \rightarrow C)$ and $Locl(C,C \leftrightarrow c)$ analogously.
In particular, $Locl(C,C \rightarrow c)$ can be viewed as providing a “logical basis”: given $C^{'}$ , a logical basis is defined to be a subclass $C$ such that $C^{'} = Locl(C,C \rightarrow c)$ and $C$ contains no pairwise equivalent models. If there exists $C$ such that $C^{'} = Locl(C,C \rightarrow c)$ , then there always exists a subclass of $C$ that is a logical basis for $C^{'}$ .
As examples, an equational logical basis for the class of all abstract Boolean algebras is the singleton consisting of $\left\{ 0,1 \right\}$ , and if $C$ is the class of all models equivalent to some model $m$ , then the logical bases of $C$ are exactly the singletons (one-element subsets) of $C$ . (This holds in any logic.) If $G$ is the class of all groups and $P$ is the class of all permutation groups, then $G = Locl(P,C \rightarrow c)$ in equational logic.
We always have $C \subseteq Locl(C,C \rightarrow c)$ , but there exist examples where $C \cap Locl(C,c \rightarrow C) = \varnothing$ , and there exist examples where $C \cap Locl(C,c \leftrightarrow C) = \varnothing$ .
For first-order logic, $Locl(C,c \rightarrow C) = Locl(C,C \leftrightarrow c)$ , and these two reduce to equivalence (for nonempty $C$ ) in the following sense: if $C$ consists of models that are not equivalent to each other then these are empty, otherwise these are the classes of models equivalent to each element of $C$ .
A similar result holds for equational logic but restricted to $Locl(C,C \leftrightarrow c)$ : if $C$ consists of models that are not equivalent to each other then it is empty, otherwise it is the class of models equivalent to each element of $C$ .

—

Let’s now write a presentation of this material as I would communicate it to someone who is totally new to it — from the top, without the dead-ends and other steps taken in the process of getting to the current/final state of things.

Let’s start now. We are motivated by the fact that abstract Boolean algebras can be defined to be the models of the equational theory of the Boolean algebra $\left\{ 0,1 \right\}$ . For what other structures is this kind of result possible?

As another example, Cayley’s Theorem tells us that every group is isomorphic to the subgroup of a permutation group. This implies that groups can be equivalently defined to be the models of the equational theory satisfied by all permutation groups (for multiplication, identity, and inverse.)

This motivates a definition: let $C$ be a class of models. (The language and logic are implicit when we say “model” here.) Then, $Locl(C,C \rightarrow c)$ is defined to be the class of all models of the theory satisfied by all members of $C$ ; equivalently, $Locl(C,C \rightarrow c)$ is the class of all models $c$ such that any statement true about all members of $C$ is true about $c$ .

Of course, the statements in question here are all “bound-variable statements”: all occurrences of variables must be bound. Otherwise, truth cannot be judged without additional parameters corresponding to elements of the model. Consequently, all our concepts here will pertain to bound-variable statements; for example, we consider two models to be equivalent if any bound-variable statement is satisfied by one if and only if it is also satisfied by the other. (This corresponds to elementary equivalence in first-order logic, but we reuse this concept for any logic.)

This definition encompasses the examples we just discussed: we have that the class of abstract Boolean algebras is $Locl\left( \left\{ \left\{ 0,1 \right\} \right\},C \rightarrow c \right)$ (in equational logic), and if $P$ is the class of all permutation groups and $G$ is the class of all groups then $G = Locl(P,C \rightarrow c)$ (again in equational logic.)

The notation motivates other similar definitions: $Locl(C,c \rightarrow C)$ is defined to be the class of all models $c$ such that any statement true about $c$ is true about all members of $C$ , and $Locl(C,c \leftrightarrow C)$ is defined to be the class of all models $c$ such that any statement is true about $c$ if and only if it is true about all members of $C$ . With this notation, it immediately follows that $Locl(C,c \leftrightarrow C) = Locl(C,c \rightarrow C) \cap Locl(C,C \rightarrow c)$ .

Unlike the motivation introduced earlier for $Locl(C,C \rightarrow c)$ , it may be harder to find similar “meaning” for $Locl(C,c \rightarrow C)$ and $Locl(C,c \leftrightarrow C)$ . For example, $Locl(C,C \rightarrow c)$ could be viewed as some kind of “logical closure” of $C$ , consisting of all the models which satisfy all statements “from all of $C$ .” However, that idea of “closure” doesn’t apply as well to the other two notions: we always have $C \subseteq Locl(C,C \rightarrow c)$ (as expected from the motivation and for the term “closure”), but there exist $C$ such that $C \cap Locl(C,c \rightarrow C) = \varnothing$ , and similarly there exist $C$ such that $C \cap Locl(C,c \leftrightarrow C) = \varnothing$ .

There is in fact another way to find “meaning” for $Locl(C,c \leftrightarrow C)$ . For example, we have that $Locl\left( \left\{ \mathbb{R} \right\},c \leftrightarrow C \right)$ is the class of real-closed fields (where the implicit language is that of fields and the implicit logic is first-order.) In general, $Locl\left( \left\{ m \right\},c \leftrightarrow C \right)$ is the class of models equivalent to $m$ . It turns out that this is the only possibility: we have that (for nonempty $C$ ) if $C$ contains two models that are not equivalent to each other then $Locl(C,c \leftrightarrow C)$ is empty, otherwise $Locl(C,c \leftrightarrow C)$ is the class of models equivalent to each element of $C$ .

In first-order logic, the fact that first-order logic contains negation yields that $Locl(C,c \rightarrow C) = Locl(C,c \leftrightarrow C)$ . Hence, we’ve completely characterized $Locl(C,c \rightarrow C)$ in first-order logic as well.

—

With our new idea of a logical basis not containing equivalent models, can we show that bases must have the same cardinality? (In analogy with say bases of vector spaces.) This could even lead to a concept of a “logical dimension” if it turns out to be true.

Let $C,D$ be logical bases for a class $M$ . This means that $M = Locl(C,C \rightarrow c) = Locl(D,C \rightarrow c)$ , and $C$ and $D$ contain no equivalent models within. Can we form a bijection from $C$ to $D$ ?

Without loss of generality we may assume we can form an injection from $C$ to $D$ .

We are inspired by https://en.wikipedia.org/wiki/Dimension_theorem_for_vector_spaces to split into cases depending on finitude.

First, say $C$ and $D$ are both finite. Let’s try to establish some vector space-like lemmas:

Conjecture. If $C^{'}$ is a proper subclass of $C$ and $C^{'}$ is a basis, then $C$ is not a basis.

Actually, we can try to generalize this further and pattern off of the vector space theory more closely: we can define a subclass to be independent if it contains no two equivalent models, and dependent otherwise. Then, we have:

Conjecture. If $C^{'}$ is a proper subclass of $C$ and $C^{'}$ is a basis, then $C$ is dependent.

Proof Attempt. Assume for the sake of contradiction that $C$ was independent. There exists $m \in C$ with $m \notin C^{'}$ , and since $C$ is independent, $E(m)$ is disjoint from $\cup_{c \in C^{'}}E(c)$ . We are also given that $C^{'}$ is a basis, so that every element $n \in E(m)$ , for every statement true of $C^{'}$ , it is true of $n$ .

Actually, I’m not sure if this conjecture holds — in fact, let’s try to find a counterexample. A simple counterexample could be that $\left\{ \left\{ 0,1 \right\} \right\}$ is a basis for the class of abstract Boolean algebras, yet $\left\{ \left\{ 0,1 \right\},A \right\}$ for some abstract Boolean algebra $A$ could be independent. In fact, this is clear: there definitely exist abstract Boolean algebras not equivalent to $\left\{ 0,1 \right\}$ , so just picking one such example will disprove the conjecture. $\blacksquare$

Actually, on second thought, I’m not sure that dependence should be defined just by non-equivalence of individual elements; in the analogy to vector spaces, this is just two elements being pairwise linear independent. But it is very possible for a set in a vector space to have every pair of elements be linearly independent (aka not scalar multiples of each other) but there to still be a linear equation satisfied in all of them, making them linearly dependent. So really, we can try to define dependence instead by not just non-equivalence of each pair, but for any element in the class $C$ , no subclass of $C$ outside of it can “generate” it. In fact, maybe that could work: we define a class $C$ to be independent if for every $c \in C$ , no subclass of $C - \left\{ c \right\}$ can generate $c$ . (Here, for a class $D$ to generate an element $c$ means that every statement true about $D$ is true about $c$ .)

Actually, that is equivalent to: a class $C$ is independent if for every $c \in C$ , $C - \left\{ c \right\}$ doesn’t generate $c$ .

OK, so that definition would automatically encompass non-pairwise equivalence (since no individual model can generate another), but is it strong enough for our desired results? It definitely seems stronger and closer to the vector space analogy, although then I’m not sure how intuitively to interpret the meaning of independence (beyond the analogy to vector spaces.)

Let’s try this again.

Conjecture. If $D$ is a proper subclass of $C$ and $D$ generates $C$ , then $C$ is dependent. (In particular, this holds if $D$ is a basis.)

Proof. Assume for the sake of contradiction that $C$ is independent. Since $D$ is a proper subclass of $C$ , there exists $m \in C$ not in $D$ . Since $D$ is a basis, $D$ generates $m$ . But then that contradicts $C$ being independent. $\blacksquare$

Actually, the terminology works perfectly now in analogy to vector spaces: if $C^{'} = Locl(C,C \rightarrow c)$ , then $C$ generates $C^{'}$ . We can go further: we define the span of $C$ to be the class of all models generated by $C$ . Then, $Locl(C,C \rightarrow c)$ is exactly the span of $C$ . We can similarly define generating class (in analogy with generating set) and other terms analogous to those for vector spaces.

Then, a basis for $C$ is just an independent subclass that spans $C$ .

Conjecture. If $D$ is a proper subclass of $C$ and $C$ is independent, then $D$ is independent but doesn’t generate the span of $C$ .

Proof. First, we show that $D$ is independent. Assume for the sake of contradiction that $D$ was dependent, so that there exists $d \in D$ such that $D - \left\{ d \right\}$ generates $d$ . But then we have that $C - \left\{ d \right\}$ generates $d$ , since any statement true about $C - \left\{ d \right\}$ must be true about $D - \left\{ d \right\}$ , so that $C$ is dependent, contradiction. Thus, $D$ is independent.

Next, we show that $D$ doesn’t generate the span of $C$ . Assume for the sake of contradiction that it did. Since $D$ is a proper subclass of $C$ , there exists $c \in C$ not in $D$ . Now, $D$ must generate $c$ . But that contradicts that $C$ is independent. $\blacksquare$

Conjecture. If $D$ is a proper subclass of $C$ , then $C$ generates the span of $D$ .

Proof. This is immediately clear, since if we denote the span of $D$ by $S(D)$ , if a statement is true about $C$ then it must be true about $D$ , thus it must be true about $S(D)$ . $\blacksquare$

All these results seem very easily provable with the definitions we’ve formulated — it seems even plausible that we could define more abstractly and formalize the generalization of similar vector space-like arguments to other cases besides logical bases. But that would be for another exploration.

Conjecture. Any two bases must have the same cardinality.

Proof. I’m pretty sure we can use these lemmas and something exactly analogous to https://en.wikipedia.org/wiki/Dimension_theorem_for_vector_spaces. Let’s do this now.

Assume we have two bases $A,B$ , and WLOG assume there is an injection from $A$ to $B$ . We have that $A$ generates $B$ and $B$ generates $A$ ; we want to use this to show that there is an injection from $B$ to $A$ or that there is a surjection from $A$ to $B$ . (Maybe this only applies if $A$ and $B$ are sets; I’d have to look into that more. Actually, the concept of cardinality anyway seems to require $A$ and $B$ to be sets, so let’s just require that $A$ and $B$ must be sets for this result to possibly hold or even make sense.)

First, assume we have two bases $A,B$ . In the case that these are finite, this is easy to show with the lemmas above, in a way similar to the Steinitz exchange lemma:

Lemma. Let $C,D$ be finite subsets of a class $E$ . If $C$ is independent and $D$ spans $E$ , then $|C| \leq |D|$ and there is a set $D^{'} \subseteq D$ with $\left| D^{'} \right| = |D| - |C|$ such that $C \cup D^{'}$ spans $E$ .

Proof. Let $|C| = m,|D| = n$ . We proceed by induction on $m$ .

If $m = 0$ , then this is trivially true (since $D$ must be nonempty to span $E$ ); however, we anyway typically assume all sets/classes in question are nonempty — regardless, this case is moot.

If $m = 1$ , then since $|D| \geq 1$ of course $|D| \geq |C|$ . We have that $D$ spans $E$ and so generates $C$ . If $C \subseteq D$ then we simply pick $D^{'} = D - C$ , otherwise $C$ is a singleton of an element outside $D$ , call this element $c$ . We have that $D$ generates $c$ . Pick any element of $D$ , call it $d$ , and define $D^{'} = D - \left\{ d \right\}$ . Then, $C \cup D^{'} = D \cup \left\{ c \right\} - \left\{ d \right\}$ ; we want to show that this spans $E$ . Well, if we show that this generates $d$ , then we’re done, for then if a statement is true about $D \cup \left\{ c \right\} - \left\{ d \right\}$ then it must be true about $d$ , hence about $\left( D \cup \left\{ c \right\} - \left\{ d \right\} \right) \cup \left\{ d \right\} \supseteq D$ , hence about $E$ . Assume for the sake of contradiction there is some statement true about $D \cup \left\{ c \right\} - \left\{ d \right\}$ but not true about $d$ . We want somehow to contradict that $D$ generates $c$ ; maybe the same statement would have to be true about $d$ but not about $c$ .

Specifically, assume WLOG for the sake of contradiction that $|A| < |B|$ . Since $A,B$ are both bases, $A$ must generate $B$ . But where do we go from here?

It remains to continue this. $\blacksquare$

We’ll take a more abstract approach to this concept of “a subset generating an element” (in its own exploration) to illuminate this problem better. $\blacksquare$

My hope is that we can show at least a statement like: the class of all models of some theory has a basis. If we can even show the equal cardinality of bases and the existence of a “logical dimension,” that would be swell. Although given that we have free modules whose underlying rings don’t have IBN (Invariant Basis Number), I’m now not sure of the probability of this result.

—

Is it possible for the set of rings of real matrices to be a basis? Can we show that this set is independent? Maybe a first step: can we show that for $m \neq n$ , the rings of $m \times m$ and $n \times n$ matrices aren’t equivalent? (Here, we are working in equational logic, and consequently the language includes 0, 1, and additive inverse.)

We’d want to find an equation that one of these satisfies but not the other; then we’re done. Probably something that involves $m$ number of terms or a number of terms that is dependent on $m$ or $n$ — similar to how in the additive group $\mathbb{Z}_{n}$ the $n$ -term equation $x^{n} = e$ is satisfied.

Well clearly we can take $m < n$ without loss of generality, and if $m = 1$ then we can obviously take the commutative property $ab = ba$ for our desired. Can we try a similar approach in general? Could there be some “modified commutativity law” in $n$ terms that the $n \times n$ matrices satisfy, such that no similar law below $n$ terms is satisfied?

It remains to look more into this.

—

We continue this discussion in the next post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply