An Abstract Approach to Generating Sets 3

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

I now have a much better understanding of the free object, so I have more clarity on abstract generation theory and how it relates to the free object. Let’s dive in.

In general, given a set $U$ , an abstract generation on $U$ is any unary relation on $2^{U} \times U$ satisfying the two axioms of generation of self and generation by subset. Now, given an algebra $A$ , or a set with some operations on it, we can define generation to mean that $S \subseteq A$ generates $s \in A$ if $s$ can be written as an expression in finitely many elements of $S$ (where of course the expression will involve the operations.) This is immediately seen to be a special case of an abstract generation.

Now, given an algebra $A$ and an algebraic structure $\mathcal{A}$ , we can define $A$ to be free over a subset of $A$ , $S \subseteq A$ , if every new expression in finitely many elements of $S$ corresponds to a different element of $A$ , except for those expressions that can be proven equal from the axioms of $\mathcal{A}$ . In particular, the notion of free object is relative to an algebraic structure, not just a provided member of the class for that algebraic structure.

As an example, let $A$ be an abelian group. Then, $A$ satisfies additional statements beyond what groups satisfy, but we can’t talk about whether $A$ is free without mentioning whether this is with respect to the algebraic structure of a group or the algebraic structure of an abelian group. In fact, abelian groups can’t be free groups except in trivial cases, as the Wikipedia article mentions — if we have a subset $\left\{ a,b \right\} \subseteq A$ , then for $A$ to be a free group over $\left\{ a,b \right\}$ we would need $ab \neq ba$ since the equality of $ab$ and $ba$ doesn’t follow from the group axioms, but if $A$ is abelian then this is not possible. (In fact, the only abelian groups that are free groups are those that are over a subset of size less than 2, which correspond to the trivial group $\left\{ e \right\}$ and the infinite cyclic group $\mathbb{Z}$ .) As expected from this discussion, free groups are different from free abelian groups.

I misread the Wikipedia article on free objects; the subset that the object is free over is in fact standardly called a basis. Thus, free objects are the in-literature natural encapsulation of the concept of a basis. To better compare and contrast our theory with free objects, we can more specifically say that free objects are the natural encapsulation of unique generation, and abstract generation theory captures certain abstracted properties of generation. I had made this point before, but I will try to explain it better now.

When we say that the free object is the natural encapsulation of unique generation, this is what we mean: we typically in math discuss uniqueness “up to” a certain point. The condition for “up to” corresponds exactly to the equivalence relation that we use to construct the equivalence classes that make up the free object (when constructing the free object formally from just the basis); we are essentially asserting uniqueness up to what the equivalence relation would dictate to be equal. In some sense, each equivalence class is a “unit” of uniqueness, so that uniqueness means that all the possibilities belong to only one such class.

I was also confused about a point with free objects as they apply to vector spaces. My reasoning was as follows: the vector space axioms don’t imply something like $v + v = 0$ for a vector $v$ ; in fact, since there exist vector spaces over fields of characteristic 0, based on what the vector space axioms imply, the terms $v,v + v,v + v + v,\ldots$ would all be different for a free vector space. However, it is well-known that all vector spaces are free, but we certainly have vector spaces for which $v,v + v,v + v + v,\ldots$ are not all different; take for example any vector space over $\mathbb{Z}_{p}$ , which would satisfy an equation $v + \ldots + v = 0$ where there are $p$ copies of $v$ . What gives?

The resolution of this conundrum comes from the fact that a vector space treated as a pair of a field of scalars and a set of vectors isn’t actually an algebra. Rather, the set of vectors is an algebra, where the signature “keeps track of” the field of scalars. In the signature, there is one operation for each scalar. Thus, really, within the formulation of universal algebra, vector spaces aren’t an algebraic structure; instead, $K$ -vector spaces are an algebraic structure for any field $K$ . The axioms of a vector space over a field $K$ would then imply any relations like $v + \ldots + v = 0$ that “come from” the nature of $K$ . For example, any $\mathbb{Z}_{2}$ -vector space is free, where one of the implications of the axioms of that algebraic structure is $v + v = 0$ .

Now, it’s not possible for a free object’s algebraic structure axioms to imply something like $\forall a\forall b(a = b)$ . When we talk about whether an algebra $A$ is free over a subset $S$ , regardless of the algebraic structure we’d need different elements of $S$ to still be different — so the free object isn’t defined for algebraic structures whose axioms contain an implication like $\forall a\forall b(a = b)$ . With that in mind, it’s easy to show that all free object bases are in fact abstract generation bases. That a free object basis is a generating set is immediate from the relevant generation and the definition of a free object, but that it’s independent also follows from the definition of a free object, specifically the point that different expressions in the elements of the basis must be unequal (modulo the algebraic structure.) Let $S$ be a free object basis and assume for the sake of contradiction that $S$ was dependent, so that for some $s \in S$ we had that $S - \left\{ s \right\}$ generates $s$ . Then, $s$ would be equal to an expression in $S - \left\{ s \right\}$ . But $s$ itself is an expression (a one-term expression), and these shouldn’t be equal according to the definition of free object. We have a contradiction.

Note that this is true regardless of the algebraic structure — for any such structure $\mathcal{A}$ (that applies to $A$ ), free object bases with respect to $\mathcal{A}$ are abstract generation bases. Our logic shows that uniqueness modulo any algebraic structure implies independence.

—

Let’s continue investigating our questions.

We’ve shown that free object bases are abstract generation bases. What about the other direction? Are all abstract generation bases of an algebra in fact free object bases? Does this hold for any algebraic structure?

Since both abstract generation bases and free object bases are generating sets for $A$ , this reduces to whether independence implies uniqueness. Or equivalently, the contrapositive: non-uniqueness implies dependence. In other words, assume that there exist two expressions that are equal even though they are not implied to be equal by the algebraic structure; does this imply dependence?

Let’s write this out. Assume $B$ is a generating set such that there exist two expressions in the elements of $B$ that are equal even though they aren’t implied to be equal by the algebraic structure. Does this yield dependence — that an element of $B$ can be written as an expression in terms of the other elements of $B$ ?

This essentially seems to boil down to whether an element can be “isolated” — think the cancellation property or invertibility. For example, say that we had $\left\{ a,b,c,d \right\} \subseteq B \subseteq A$ and $ab = cd$ . An algebraic structure can’t imply that an expression in just $a$ and $b$ could possibly be equal to an expression in just $c$ and $d$ , so this is an example of non-uniqueness. But assuming say that $A$ satisfies invertibility, we can go from $ab = cd$ to $b = a^{- 1}cd$ , which is dependence (an expression for $b$ in terms of $a,c,d$ .) In cases that we can’t isolate an element in this manner, for example if $A$ doesn’t satisfy such invertibility, can we show that we don’t have dependence? Can we use an example where $A$ doesn’t have invertibility to show that abstract generation bases aren’t necessarily free object bases?

(If $A$ doesn’t satisfy a property, then $\mathcal{A}$ certainly can’t imply it, so for such an example, there could be abstract generation bases that aren’t free object bases with respect to any algebraic structure applicable to $A$ .)

Incidentally, the invertibility part could be connected to the fact that all vector spaces are free while not all modules are, since the underlying field for a vector space satisfies invertibility, implying invertibility for scalar multiplication (for a vector space, given vectors $v,w$ and a scalar $a \neq 0$ , in the equation $av = w$ we can divide by $a$ to get $v = a^{- 1}w$ , but a similar result doesn’t necessarily hold for a module where scalars may not be invertible.)

Let’s try a simple example: let $A$ be a monoid. Actually, to simplify the argument, let $A$ be a commutative monoid. Let $\left\{ a,b \right\} \subseteq A$ be an abstract generation basis. This implies that $A = \left\{ a^{i}b^{j}:i,j \geq 0 \right\}$ since $\left\{ a,b \right\}$ is a generating set and $A$ is commutative. This also implies that there is no relation of the form $a = b^{k}$ or $a^{l} = b$ , since $\left\{ a,b \right\}$ is independent. Can we show that $\left\{ a,b \right\}$ won’t be a free object basis? This is possible I think if we have a relation like $a^{2} = b^{3}$ . Relations can’t exist among members of a free object basis, so in that case $\left\{ a,b \right\}$ won’t be a free object basis. Would it still be an abstract generation basis? Equivalently, is $\left\{ a,b \right\}$ still independent even when $a^{2} = b^{3}$ ? Well, independence written out is the non-existence of $k,l$ such that $a = b^{k}$ and $a^{l} = b$ . So we just need to show that such $k,l$ don’t exist. Assume that such a $k$ existed, then $a = b^{k} \rightarrow a^{2} = b^{2k} = b^{3}$ . Similarly, if such an $l$ existed, then $b = a^{l} \rightarrow b^{3} = a^{3l} = a^{2}$ . But we can easily choose $A$ such that this isn’t possible: let $A$ be the set of equivalence classes of formal expressions of the form $a^{i}b^{j}$ , subject to commutative monoid axioms and $a^{2} = b^{3}$ . Then, all powers of $a$ would be different from each other, and all powers of $b$ would be different from each other.

Thus, free object bases are more restrictive than abstract generation bases; they are a subset of abstract generation bases. Note in particular that for the example above, $\left\{ a,b \right\}$ is an abstract generation basis but is not a free object basis with respect to any algebraic structure (since regardless of the algebraic structure, a free object basis can’t have relations among its members.)

—

We will now focus on abstract generation theory in its own right. Due to the overloading of the term “basis” in the context of free objects, for our theory we will instead use the term “independent generating set.”

I thought about adding a “generation by empty set” axiom, that the empty set doesn’t generate anything, but this would then conflict with the natural generation on an algebra with identity (since by convention an empty product is the identity) — see for example the Wikipedia article on free abelian groups where it is stated that the free group over the empty set is the trivial group $\left\{ e \right\}$ , so that $e$ is generated by the empty set. Thus, we won’t add this axiom, and we will instead stick with just the original two.

Let us summarize and generalize some of the discussion from previous posts now, in a more concisely readable form.

We define the concepts of generation, generating set, span, and independence as before. We note that as an example, there is a “natural” generation on any algebra.

We have:

Lemma. If $S \subseteq S^{'}$ and $S$ is dependent, then $S^{'}$ is dependent.

Lemma. If $S \subseteq S^{'}$ and $S^{'}$ is independent, then $S$ is independent.

These follow quickly from the generation by subset axiom.

We also have a number of conjectures:

Conjecture. Let the “overall” set that the generation is defined on be denoted $U$ . Then, $U$ must have an independent generating set.

(Note that this doesn’t contradict the fact that not all algebras are free, since that concerns free object bases. It is still possible that any set with a generation on it must have an independent generating set, which if true would imply that any algebra has an independent generating set.)

Other conjectures apply in the case that independent generating sets are guaranteed to have the same cardinality:

Definition. If all independent generating sets of $U$ have the same cardinality, then the dimension of $U$ is defined to be this cardinality.

Conjecture. If $U$ has dimension $n$ , then if $S \subseteq U$ has cardinality smaller than $n$ , $S$ cannot span $U$ .

Conjecture. If $U$ has dimension $n$ , then if $S \subseteq U$ has cardinality greater than $n$ , $S$ cannot be independent.

—

On second thought, these conjectures actually look pretty doable! Let’s pattern our approach off of the theory for vector spaces:

Conjecture. If $S$ is independent, then there exists a superset of $S$ that is an independent generating set.

This would allow us to enlarge any independent subset $S$ into an independent generating subset — similar to the analogous situation with the special case of vector spaces. Naturally, we’d have a corresponding conjecture for the other direction:

Conjecture. If $S$ is a generating set, then there exists a subset of $S$ that is an independent generating set.

This would allow us to remove “unnecessary” elements from any generating set $S$ to form an independent generating set.

How much of our desired theory (desired results analogous to those known for vector spaces) follows from these two conjectures?

Note that the second conjecture implies that $U$ has an independent generating set since $U$ is a generating set for itself. Thus, it implies existence of an independent generating set for any span.

Also, these two conjectures would allow very similar reasoning to what we do with vector spaces when comparing sizes of sets against the dimension:

Lemma. If $U$ has dimension $n$ , then if $S \subseteq U$ has cardinality greater than $n$ , $S$ cannot be independent.

Proof. Assume for the sake of contradiction this wasn’t true, so there exists $S$ with cardinality greater than $n$ that is independent. Is $S$ a generating set? If yes, then $S$ is an independent generating set, but this contradicts the fact that all bases must have cardinality $n$ . If not, then some superset of $S$ will be an independent generating set, but this superset again will have cardinality greater than $n$ , contradiction. $\blacksquare$

Lemma. If $U$ has dimension $n$ , then if $S \subseteq U$ has cardinality less than $n$ , $S$ cannot be a generating set.

Proof. Assume for the sake of contradiction this wasn’t true, so there exists $S$ with cardinality less than $n$ that is a generating set. Is $S$ independent? If yes, then $S$ is an independent generating set, but this contradicts the fact that all bases must have cardinality $n$ . If not, then some subset of $S$ will be an independent generating set, but this superset again will have cardinality less than $n$ , contradiction. $\blacksquare$

We have other results that are analogous to those for vector spaces (in finite dimension — the analogous result can’t hold in infinite dimension, take for example the set of all polynomials as a vector space and the $\aleph_{0}$ -cardinality set $\left\{ x^{2},x^{3},\ldots \right\}$ , which isn’t a basis):

Lemma. If $U$ has finite dimension $n$ , then any set of $n$ independent elements must be a generating set too (hence an independent generating set), and similarly any $n$ -element generating set must be independent too (hence again an independent generating set.)

Proof. Let $S$ be a set of $n$ independent elements, and assume for the sake of contradiction that $S$ wasn’t a generating set. Then, some superset of $S$ will be an independent generating set, and this must be a strict superset, but this implies the existence of an independent generating set with size greater than $n$ , contradiction. The other part of the lemma is similar. $\blacksquare$

Now, let’s try to prove our two conjectures, which we can call “going-up” and “going-down,” that would yield all these nice results:

Conjecture (Going Up). If $S$ is independent, then there exists a superset of $S$ that is an independent generating set.

Attempt. If $S$ is a generating set, we’re done. Otherwise, intuitively, we can add elements to $S$ to keep it independent while ultimately ensuring it is a generating set. To do this, note that since $S$ is not a generating set, there is a subset of $U$ of all the elements not generated by $S$ (i.e., this subset is nonempty.) Call this subset $T$ . We know that $S \cup T$ is a generating set: otherwise there must exist some element $u \in U$ not generated by $S \cup T$ , thus not generated by $S$ , but by definition such an element must be in $T$ , and thus generated by $S \cup T$ , contradiction. Now if $S \cup T$ is independent then we’re done, otherwise $S \cup T$ is dependent, so there exists $c \in S \cup T$ such that $(S \cup T) - \left\{ c \right\}$ generates $c$ . Let $T^{'}$ be the subset of $S \cup T$ consisting of all such $c$ . We claim that $(S \cup T) - T^{'}$ is the desired superset.

Actually, that wouldn’t work: take for example a vector space with $\left\{ v,w,2v \right\}$ where $v,w$ are linearly independent and the space is two-dimensional. This would remove both $v$ and $2v$ , which wouldn’t yield a generating set anymore.

Instead, a possible approach here could be to “choose” one of the elements in $T^{'}$ to remove, and then to keep going with the same procedure. This would involve the Axiom of Choice in general, which seems appropriate since this kind of result seems to me in general to follow only from the Axiom of Choice (or some axiom slightly weaker than AC) — I suspect it wouldn’t just follow from ZF. However, this leads to the question: would this procedure be guaranteed to terminate? Actually, if $S \cup T$ is infinite and there is say a finite dimension, then this definitely wouldn’t terminate.

Instead, we’d probably have to do a construction that makes infinitely many choices at once. That seems to be the only way that approach could work.

Let $S$ be given; we can then define $T$ . Presumably, not every element in $T$ would need to be added to $S$ . If we can partition $T$ into subsets and then make a choice from each subset where the result, added to $S$ , is guaranteed to still be independent but still generate all of $U$ , then we’d be done. How can we specify what this partition would be?

It remains to finish this. $\blacksquare$

Conjecture (Going Down). If $S$ is a generating set, then there exists a subset of $S$ that is an independent generating set.

Attempt. If $S$ is independent then we’re done, so assume $S$ is dependent. Let $S^{'}$ be the subset of $S$ consisting of all $c$ such that $S - \left\{ c \right\}$ generates $c$ ; since $S$ is dependent, $S^{'}$ is non-empty. Similar to the approach for going-up, if we can partition $S^{'}$ and make a choice from each subset in the partition, for a suitable specification of a partition, then we’d think that $S$ minus those choices would be the desired independent generating set.

It remains to finish this. $\blacksquare$

—

This discussion is continued in the next post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply