Non-Standard Axioms for Various Math Structures 8

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

After learning more about the free object, I suspect that we can construct models at least for algebraic theories (where there are only operations in the signature) that satisfy a given desired set of sentences. If this is the case, then this can provide immediate answers to our main questions of logical generation theory. Specifically, I conjecture:

For any equational theory, there exists a singleton generating set, which we can construct as a free object.
For any first-order theory, if not all models of the theory are elementarily equivalent to each other (in which case any model forms a singleton generating set), then there is a two-element generating set, comprised of two models where both satisfy all the sentences in the theory, but for sentences not in the theory (or not implied by the theory) the models satisfy opposite sentences (for every sentence $s$ not implied by the theory, one of the models satisfies $s$ and the other satisfies $\neg s$ .)

On second thought, part 2 seems harder to prove, given that the free object (at least, the free object construction I’ve learned just for algebras) won’t apply to general first-order theories.

Note for first-order logic that, if there is a first-order theory $T$ and a sentence $s$ not implied by $T$ such that $T \cup \left\{ s \right\}$ implies some sentence $t$ , then $T \cup \left\{ \neg s \right\}$ can’t also imply $t$ , since then $t$ would be an implication of $T$ regardless of the satisfaction of $s$ . It may be possible though (as far as my logic so far shows) that $T \cup \left\{ \neg s \right\}$ doesn’t imply $\neg t$ , so that $t$ is independent of $T \cup \left\{ \neg s \right\}$ but a consequence of $T \cup \left\{ s \right\}$ .

Regardless, let’s start by attempting to prove part 1. First, any equational theory must correspond to an algebra (only operations in the signature.) Thus, we can certainly construct free objects for the theory. To avoid cases like where the free object over a singleton basis may satisfy additional equations (for example, the free group over $\left\{ a \right\}$ is an abelian group), we’ll pick an infinite starting basis; assuming all operations are finitary, and furthermore that every expression is built of a finite number of applications of operations (which we’ll restrict to here), an infinite starting basis should hopefully be enough to rule out these additional equations.

Thus, say that we have an infinite set $X$ (for example, $X\mathbb{= Z}$ ), and construct the free object over $X$ with respect to the given equational theory $T$ . Call the free object $F$ . It is immediate that $F$ is a model of $T$ by construction. Is $\left\{ F \right\}$ a logical generating set for the class of models of $T$ ? In other words, is it true that an equation is satisfied by $F$ if and only if it is satisfied by all models of $T$ ? Well, if an equation is satisfied by all models of $T$ , it must certainly be satisfied by $F$ . But if an equation is satisfied by $F$ , then we show that it is satisfied by all models of $T$ .

It remains to continue this.

—

EDIT: we add some new thoughts. (These were first written on my phone, so they don’t have mathematical formatting.)

I have an idea to disprove the singleton conjecture for equational logic. If we have a set of equations S and the class M of all models of S, then every member of M would satisfy every statement implied by S. Now, say there is some equation t not implied by S; the singleton can’t satisfy t, since if it did, every member of M would satisfy t, so by Gödel’s Completeness Theorem S would need to imply t, contradiction. Say there are equations t and u such that t is equivalent to not u, given S, but neither t, u, nor their negations are implied by S. This would disprove the singleton conjecture, since if the singleton satisfied t it couldn’t satisfy u, but there would be a model of S satisfying u, which then would not satisfy t, contradiction. (Actually, is this strictly true: if t is independent of S then there exists a model of S satisfying t as well as a model of S not satisfying t? I think this boils down again to Gödel’s Completeness Theorem: if there didn’t exist any model of S satisfying t then every model of S couldn’t satisfy t, thus every model of S satisfies the negation of t, thus by Gödel’s Completeness Theorem S would imply the negation of t, so that t isn’t independent of S, and similarly if there didn’t exist any model of S that didn’t satisfy t then t couldn’t be independent of S. This is the contrapositive of the desired statement.) Otherwise, if the singleton didn’t satisfy t, it must satisfy u, but since t is independent of S there must exist a model of S satisfying t and not satisfying u, contradiction.

Thus, we can disprove the singleton conjecture if we can find a set of “defining” equations S and two independent equations t and u such that (not t) implies u, and u implies (not t), under S.

To see if this is possible, we need to see if a set of equations can imply an inequation. Is this possible?

We can do this I think via size control — if we can guarantee only two elements in the model, then an equation would imply a corresponding inequation, and vice versa. We have to watch out though for the Löwenheim-Skolem theorem: we need to prevent any infinite models. Can we, for any n, produce a set of equations that guarantees the model is size n?

Let’s try a simple case of n=2. The “easy” first thought, a=b, yields a size 1 model, which can’t satisfy inequations. Can we guarantee size 2?

What about something like ab=a? We can have a three element set of a,b,c, and this would still be a model.

It remains to investigate this approach.

—

EDIT: we really need to understand for which algebraic structures we can construct a free object over an infinite set.

For example, a first order theory that is able to constrain to finite cardinalities (constriction to a particular set of cardinalities including infinite ones is not possible by the Löwenheim-Skolem theorem) could fall under the possible counterexample to the singleton conjecture that I mentioned earlier — this is why that attempt doesn’t conflict with the idea that a structure supporting a free object over an infinite set would necessarily satisfy the singleton conjecture.

An example of a structure that won’t have a free object is one whose axioms imply a=b. Another example is one whose axioms imply finite cardinality. Can we show these are the only possibilities for structures that don’t support free objects over infinite sets?

In fact, if a structure implies a=b then that implies cardinality 1, which implies finite cardinality. So these are both subsumed under implication of finite cardinality. Can we show that if a structure doesn’t imply finite cardinality, then it must support a free object over an infinite set? (In other words, that this is the complete answer?)

What about the contrapositive? This says that a structure that doesn’t support a free object over an infinite set must imply finite cardinality. In other words, if every model of that structure is not free over an infinite set, then that structure implies finite cardinality. In other words, given a structure S, that every model of S is not free over an infinite set implies that every model of S is finite.

It’s very possible that a model is infinite but not free, so we can’t show this via a per-individual-model argument.

If a structure doesn’t imply finite cardinality, then it must have an infinite model — can we show this via Gödel’s Completeness Theorem? Or do we even care that the “proof must take a particular form” (which is what Gödel’s Completeness Theorem is really saying)? Here, we don’t necessarily take “implies” to mean via a particular proof system, but rather any sort of proof — in the case of Gödel’s Completeness Theorem for example, if we proved that every model of a structure satisfies a property, we could take that itself as a proof that that structure implies the property, even in say a logic higher than first-order. So when we say “implies” here, we mean by any kind of proof. By this, if a structure doesn’t imply finite cardinality, then must it have an infinite model? The contrapositive states that if a structure doesn’t have an infinite model (so that all its models are finite), then it implies finite cardinality. For our meaning of “implies,” this is inherently true.

Thus, if the structure doesn’t imply finite cardinality, it must have an infinite model. Can we show that if it has an infinite model, then it supports a free object over an infinite set?

Let the infinite model be M, and consider the free object over M for this structure — is that well-defined? Every “individual character” expression is different as required, and after that everything seems to work as desired — the result is a free object over an infinite set. Thus, this works perfectly.

Actually, let’s dive into this a little more: why does this logic work only when the structure has an infinite model? It doesn’t look like we’ve actually used the fact that M is a model here.

If we can form the free object over an infinite set, then clearly the structure has an infinite model (since all “individual character expressions” must be different, so this free object will be infinite.) But that’s the converse of what we’re trying to show. If we can’t form the free object over an infinite set, then in trying to form the free object over an infinite set (call it T), the structure’s axioms must imply some of the individual character expressions to be equal to each other — that is what we need for general failure of constructability of the free object. Can we show that such axioms must imply finitude?

Or go back to the idea of taking an infinite model and forming the free object over that. It doesn’t matter that M is a model, so we can just take any infinite set T and attempt to form the free object over that. Ultimately, failure to form a free object is equivalent to saying that the axioms imply some of the elements in the basis to be equal to each other. So we’re really trying to show that, if the structure has an infinite model (and thus by Löwenheim-Skolem theorem it has models of all infinite cardinalities), then the axioms won’t imply some elements of an infinite basis to be equal to each other.

Let’s try the contrapositive of this statement. If the axioms do imply some elements of an infinite basis to be equal to each other, then does that imply finitude?

As far as the axioms “know,” they can’t “distinguish” between the basis elements. Thus, it can’t assert equality of any two of them without asserting equality of all of them. Since no basis element “starts off as” an expression in terms of any others, this is only possible if the axioms imply a=b. But then that implies that the cardinality is 1, and thus finite, as desired.

So with this logic, we yield that the following are equivalent:

A structure implies finite cardinality
A structure implies a=b
A free object can’t be formed for that structure over an infinite set

—

Based on this logic, assuming the infinite-free-object approach works, we’ve resolved the singleton conjecture fully. If the structure implies a=b, then all models have cardinality 1 and are trivially isomorphic to each other, hence the singleton conjecture is true for that structure; otherwise, the free object over an infinite set can be formed, which also implies the singleton conjecture for those structures.

This shows that the singleton conjecture is true for all of equational logic, and even beyond for algebraic structures satisfying first-order theories.

Actually, how can that work? Clearly if we do first-order logic then a singleton basis would imply elementary equivalence. But that’s clearly not true for many first-order theories, even without relations (first-order axioms for the algebraic structure.) So what gives?

So our logic above about free objects and algebraic structures doesn’t seem to be in jeopardy. Rather, the issue seems to be with going from the free object over an infinite set to “picking out” relations that are satisfied. It might be that the resulting free object is only guaranteed to satisfy a specific set of equations rather than first-order statements, so that this discussion would imply the singleton conjecture for equational logic but it wouldn’t say anything for first-order.

If that works out, then I’m curious to see how much this can extend to first-order and what we can say about the first-order two-model conjecture. Is it possible to “pick out” satisfied first-order statements in that manner?

Note at least that the attempted counterexample we were trying to achieve earlier, with an algebraic structure implying cardinality of 2, can’t exist.

—

Let’s try to show the following. Let S be an algebraic structure, and let F be the free object over \{x\_i: i positive integer\}. Is it true that an equation is implied by S if and only if is it true for F?

Clearly, any equation implied by S must be true of F, since F is a model of S — this is the “only if” direction. For the “if” direction, assume there was an equation E true of F but not implied by S. So assume E is true of F but not of some model M of S. E has to be of the form t1 = t2 where t1 and t2 are terms, and say the total number of different variables among t1 and t2 (within E) is n. Since E isn’t true of M, there must exist some m1, m2, \ldots, m\_n in M for which E isn’t true. But if we can form a homomorphism f from F to M (which we should be able to since F is the free object over an infinite set), then using f we can imply that any equation that holds for F must hold for M, contradiction. But we can definitely form this homomorphism, as implied by the Wikipedia article on free objects.

Thus, we have our desired result: for any equational class there exists a singleton logical generating subset.

—

Beyond equations, what else can we preserve using this homomorphism? We know from previous results on logical generation theory for first-order logic that we can’t preserve general first-order logic statements, but what else?

We can preserve logical-and, at least for binary logical-and, but even for infinitary logical-and: if a statement asserts that for all equations e in a set of equations E that e holds, then we can yield that if each e holds in F then it must hold in M, so that the overall statement must hold in M too given it holds in F.

Given the role of logical negation in our previous work on first-order logical generation theory, we suspect that negation can’t be preserved. In fact, can we go further, and say that negation is the only thing that can’t be preserved?

What about relations? Yes, relations certainly can be preserved by homomorphisms.

OK, what about logical-or? Or existence (as opposed to for-all?)

We can actually show that both are preserved. Indeed, if we have that for all $i \in I$ that if statement $S_{i}$ is true for $F$ then it is true for $M$ , then if $\vee_{i \in I}S_{i}$ is true for $F$ , $S_{i}$ must be true for $F$ for some $i$ , so $S_{i}$ must be true for $M$ , so $\vee_{i \in I}S_{i}$ must be true for $M$ . (This in fact takes care of arbitrary-arity logical-or’s.) Existence is similar (in fact, we might be able to think of existence as akin to “logical-or over a set,” and of for-all as akin to “logical-and over a set.”) If we have that, for any $x$ , if $P(x)$ is true for $F$ then it is true for $M$ , then if $\exists x P(x)$ is true for $F$ , we must have that $P(x)$ is true for $F$ for some $x$ , but then $P(x)$ is true for $M$ for that $x$ , hence $\exists x P(x)$ is true for $M$ .

Thus, singleton logical generating subsets exist for any theory in the logic consisting of existence, for-all, land, lor, operations, equations, and relations — essentially, the subset of first-order logic without negation. Are there any other aspects of first-order logic besides negation that we haven’t addressed?

The conditional is possibly one. We can clearly represent the conditional in terms of negation: $P \rightarrow Q$ is equivalent to $(\neg P) \vee Q$ . But can we go the other way? If we can, then that would show that supporting conditionals would be equivalent to supporting negation, as an addition to the subset of first-order logic already delineated (call that logic $L$ .)

In other words, can we represent $\neg P$ as a conditional? Yes, I think we can if we have access to a “false” constant $F$ ! Then, $\neg P$ is equivalent to $P \rightarrow F$ . (Here $F$ is not to be confused with the free object used earlier.) We can see this as follows: if $\neg P$ is true then $P \rightarrow F$ is certainly true, and if $P \rightarrow F$ is true then the contrapositive yields $T \rightarrow (\neg P)$ (where $T$ is the constant for “true”), and since $T$ is always true we have that $\neg P$ follows. But what if we don’t have access to the constants $T$ and $F$ ? Can we represent $F$ in the logic $L$ ? We can express $F$ as $\forall a\forall b(a = b)$ in the case that we limit to models that don’t collapse to one element. Does this allow us to express negation in terms of conditionals and $L$ ? (Of course, we can always express $T$ as $\forall a(a = a)$ .)

Actually, $T$ and $F$ are typically considered part of first-order logic too. Thus, to be precise, we can say that the singleton result holds for $L$ but not for general first-order logic. We also conjecture that two models are enough to comprise a logical generating subset for any first-order theory, although that would be best for another post.

Incidentally, this discussion shows that negation can’t be expressed in $L$ — there exist statements in $L$ whose negations aren’t in $L$ . This comes from the fact that the singleton logical generating subset result holds for any theory in $L$ but not in general for theories in $L$ plus negation.

(Presumably, we can also prove this “directly” by exhibiting statements in $L$ whose negations can’t be expressed by $L$ .)

—

We continue this discussion in the next post of the series.

Share and like (need WordPress account to like):

Leave a comment Cancel reply