Algebraic Structures Applicable to All Sets 2

In this post, we attempt to better understand the questions posed in this post and its follow-up by formalizing them generally in the language of universal algebra.

Since finite and infinite seem to feel different, let’s restrict this formulation to infinite sets.

Problem. For which universal algebraic signatures $\Sigma$ and sets of $\Sigma$ -axioms $A$ is it the case that for any infinite set $S$ there is a collection of operations of type $\Sigma$ on $S$ satisfying $A$ ?

Clearly, if $A$ is empty then this is always possible. So this seems to be conditioned on the axioms in $A$ . But actually, why would it? I think this would be doable for any $(\Sigma,A)$ .

Upon further thought, this seems to be particularly amenable to Godel’s Completeness Theorem. Assume the axioms in $A$ are all first-order, except no relations, only operations. (This can still involve existence, negation/inequations, conditional implication, etc.) Then, Godel’s Completeness Theorem states that, if $s$ is a first-order sentence (in the language of $\Sigma$ ) such that any model of $A$ satisfies $s$ , then there is a proof of $s$ from $A$ . Can we choose $s$ in a clever way?

Actually, how would existence of proof help us? We want existence of model. So maybe we’d like to go the opposite direction (which would then be obvious though, no need for Godel’s theorem.) We cleverly produce $s$ as a consequence of $A$ , then we are given that $s$ must be satisfied in any model of $A$ . If we can show that there is a model of $s$ , then can we show that there is a model of $A$ ? What we’d further like to show is: given $A$ (which we assume to be consistent), there is a model of $A$ of any infinite cardinality.

So this is the question, then. Given a set of consistent axioms $A$ , there is a model of $A$ of any infinite cardinality. This seems to boil down to some fundamental mathematical logic arguments. In fact, in some sense, it would be intuitively suggestive for the consistency of a set of axioms to be equivalent to the existence of a model for them; clearly, if they are inconsistent, then there is no model for them. Is this true?

If a set of axioms $A$ is consistent, then must there be a model $M$ for them? Must there be a model $M$ for them of any infinite cardinality?

I suspect we can do something similar to the free object construction to construct a model for $A$ of any cardinality. Let’s review how we’d do this with a motivating example.

Let our axiom be cancellation: one operation and $ab = ac \rightarrow b = c$ . How do we construct a model $M$ of this axiom for any cardinality?

Well, we can basically consider “words” of variables, with words being equivalent if and only if they can be proven to be equal under the axioms. The set of equivalence classes of these words is then our free object, if I understand correctly.

So let’s be general again, with a set of axioms $A$ (that are consistent.) let $V$ be a set of variables, of any infinite cardinality. We define a set $M$ such that, for any $v_{1},\ldots,v_{n} \in V$ , we have

$\displaystyle v_{1}\ldots v_{n} \in M.$

Then, we define an equivalence relation on $M$ by: two words are equal if and only if they can be proven equal under the axioms $A$ . Is this guaranteed an equivalence relation?

Every word is automatically $A$ -provably equal to itself, assuming $A$ is consistent.
If a word $w_{1}$ is $A$ -provably equal to a word $w_{2}$ , then by basic property of equality (nothing else needed from $A$ ) this also yields that $w_{2}$ is $A$ -provably equal to $w_{1}$ .
Transitivity follows similarly to point 2, based on the fact that proofs from $A$ can involve basic logical steps like transitivity of equality.

Thus, we can form the set of equivalence classes, which we call $Eq(M)$ . This set is what we want; can we guarantee that it is in bijection with $V$ ? If we can, then we’re done.

As an aside, it seems like we haven’t really used the consistency of $A$ here in a fundamental way — what happens if $A$ is inconsistent? If $A$ is inconsistent, then anything can be proven from it (Principle of Explosion.) Thus, then any two words can be proven equal, but also any two words can be proven unequal … so none of this logic works then. So we do need $A$ consistent, in a fundamental way, to produce $Eq(M)$ .

Can we now show that $Eq(M)$ is in bijection with $V$ ? Would this depend somehow on the axioms in $A$ ? (Would reduction by axioms show that $Eq(M)$ would have to be smaller?)

Actually, let’s look at Free object – Wikipedia. I implicitly assumed associativity, but my idea was valid in comparison to how the free object is typically constructed. The main thing we’d want to prove then is: for any infinite set $V$ and any set of axioms $A$ (what the article refers to as “defining relations”), the free object for $A$ over $V$ is in bijection with $V$ . If we can show that, then we’re done.

Let’s have a trivial example: what if $A$ consisted of the one axiom $\forall a\forall b(a = b)$ ? Then $Eq(M)$ would just be $\left\{ M \right\}$ . So it’s very possible to have $A$ such that $Eq(M)$ is small.

OK, can we at least develop general equivalent conditions on $A$ for $Eq(M) \equiv V$ ? And is this equivalent to $A$ being imposable on any infinite set?

Let’s try some more examples. Let $A$ have the two axioms $a^{2} = a$ and $(ab)c = a(bc)$ . Then, $Eq(M)$ would consist of arbitrary-length words with no two same variables next to each other. Since each element of $V$ is a word on its own, we have that $\left| Eq(M) \right| \geq |V|$ . If we can show $\left| Eq(M) \right| \leq |V|$ , we’re done. But we actually already know that this $A$ is satisfiable for any cardinality, since these are part of the Boolean ring axioms and we know that any infinite set can be turned into a Boolean ring.

Do we know that: if the free object for $A$ over $V$ doesn’t biject with $V$ , then there exist infinite sets that can’t be turned into models of $A$ ? Can we prove this?

So assume that there exists infinite $V$ such that the free object for $A$ over $V$ doesn’t biject with $V$ . We conjecture that there exists an infinite set that can’t be turned into a model of $A$ . To prove this, assume for the sake of contradiction that every infinite set can be turned into a model of $A$ . In particular, $V$ can be turned into a model of $A$ . Since $V$ is a model of $A$ , we have …

Let’s try some special cases to see if this conjecture holds up. For the axiom $\forall a\forall b(a = b)$ above, can any infinite set be turned into a model of it? No, it can’t, because it implies that the max number of elements is 1.

OK, how about the axiom $ab = a$ ? Let’s denote the free object over a set $V$ by $F(V)$ ; we can include the $A$ as a subscript to be explicit if needed, as in $F_{A}(V)$ . So with this axiom, what does $F(V)$ look like? Well, everything disappears except the first character in the word, so this really is just $V$ . Certainly, then, $F(V) \equiv V$ . Can we impose this axiom on any infinite set? (This is actually clear, what we’re trying to build evidence for is the converse, but just a quick sanity check.) Let $S$ be an infinite set, and define the operation $f:S^{2} \rightarrow S$ by $f(a,b) = a$ . Then, we always have $ab = a$ with this operation. So this is trivially satisfiable.

From these examples, I have an even stronger conjecture: given a set of axioms $A$ and a set $S$ , $S$ can be turned into a model of $A$ if and only if $F_{A}(S) \equiv S$ . This would pinpoint exact cardinalities of sets that can be turned into models of $A$ , not just whether or not $A$ can be imposed on everything infinite.

We can establish one direction clearly: assume we have $A$ and $S$ , and $F_{A}(S) \equiv S$ , then we know that $F_{A}(S)$ is a model of $A$ by construction and so we can use the bijection to turn $S$ into a model of $A$ .

Let’s actually try the other direction: assume we have $A$ and $S$ , and $S$ can be turned into a model of $A$ . We also have that $F_{A}(S)$ is a model of $A$ , by construction. Can we show that $F_{A}(S) \equiv S$ ?

Would this work for finite sets $S$ ? Let’s try a toy example: $S = \left\{ a,b \right\}$ and $A$ is the set of group axioms. Clearly $S$ can be turned into a model of $A$ (via $\mathbb{Z}_{2}$ ), but what is $F_{A}(S)$ ? If we can show it contains more than two elements then we’d disprove this direction for finite $S$ . But of course it does: since no relations are imposed on $a,b$ we have $a,b,ab,ba$ at least as elements of the free object. Thus, this direction can’t be true in general for finite $S$ . But we could still believe in this direction for infinite $S$ , since bijection is different for finite versus infinite sets.

Let’s try to prove this direction for infinite $S$ .

We split into cases. In the first case, assume that $A$ does not contain the statement $\forall a\forall b(a = b)$ as a provable implication (whether as an axiom in $A$ or as a consequence.) Then, from how first-order logic is constructed, we know that each element of $S$ would be a separate “character” in $F_{A}(S)$ , so we have $S \subseteq F_{A}(S)$ . (It remains to continue this part.)

In the second case, assume that $A$ does contain as a provable implication $\forall a\forall b(a = b)$ . Then, any model of $A$ must have at most one element, so by the assumption that $S$ can be turned into a model of $A$ we must have $|S| \leq 1$ . But we assumed $S$ was infinite, contradiction, so this case is invalid. (Incidentally, in this case the direction is trivially true for any $S$ including finite: we also have $\left| F_{A}(S) \right| \leq 1$ , so if $S$ is empty, then $F_{A}(S)$ is empty (by definition of free object), and if $S$ has one element then $F_{A}(S)$ has one element, so $|S| = \left| F_{A}(S) \right|$ .)

—

Let’s go back to the infinite field conjecture. To show that, we just need to show that $F_{A}(S) \equiv S$ for infinite $S$ and $A$ the set of field axioms. (This doesn’t depend on whether the converse direction turns out to be true above.) So let $S$ be any infinite set, and consider $F_{A}(S)$ with $A$ the set of field axioms. What is $\left| F_{A}(S) \right|$ ?

At the very least, $F_{A}(S)$ must contain each element of $S$ as a “separate character,” which would each be a one-character word. Thus, $|S| \leq \left| F_{A}(S) \right|$ . If we can show that $\left| F_{A}(S) \right| \leq |S|$ , we’d be done. So we want to exhibit an injection $F_{A}(S) \rightarrow S$ .

Since this doesn’t work for finite $S$ we’d need to use the infinitude of $S$ somewhere. But that just seems to get us back in the same place as before with considering infinite cardinalities …

It remains to continue this.

Written February 22, 2023.

—

EDIT (03/27/2023): I’ve just read about the Löwenheim-Skolem Theorem. This basically achieved everything I was hoping was possible. This completely resolves my question about fields, as well as many other such analogous questions, in what I consider to be the best way possible. “Incredible” doesn’t begin to describe this theorem.

Sidenote: I’ve just heard that there is such a thing as a “real-closed ring,” which may not be a field. I’m confused about this. Aren’t the field axioms first-order? Meaning that any real-closed ring would have to satisfy them, and thus be a field? I went through the field axioms just to check that they are first-order; it is well-known that fields aren’t an equational class, but certainly all the axioms seem at least first-order to me? What am I missing here?

Actually, I got it. Fields are in fact a first-order theory. The Wikipedia article on real-closed rings states that the name is given by an extension of a certain characterization of real-closed fields; elementary equivalence to the real numbers is only one such characterization, and that one isn’t extendable beyond fields.

Share and like (need WordPress account to like):

Leave a comment Cancel reply