An Abstract Approach to Generating Sets 2

We continue the discussion from this post.

Let’s delve into the terminology further.

We have an abstracted definition of generation, which results in a concept that we call an “abstract generation.” Separately, a lot of the intuition behind the concept of generation goes hand-in-hand with the concept of basis, whose standard general formulation is essentially given by the free object. As expected, the “natural” concept of generation in the context of the free object indeed satisfies the axioms of an abstract generation.

However, in the abstract generation framework, we can also define independence and then bases. Thus, we now essentially have two different definitions of “basis.” One of them is from our concept of abstract generations, where a basis is a generating set that is independent (in the sense that no subset of that set can generate the other elements of that set.) The other one is the “standard definition,” which is in the context of the free object — specifically, in this definition, $B \subseteq S$ is a basis for $S$ if and only if $S$ is isomorphic to the free object over $B$ . Can we show these to be equivalent in the context of the free object under the standard definition of “generation” (via word expressions) in the framework of the free object?

Well, writing out the standard definition of generation in this scenario, $S$ generates $s$ if $s$ can be expressed as a word with the elements of $S$ as “characters.” Assume $B \subseteq S$ is a basis by the second (standard) definition, then we show it must be by the first. So we have that $S$ is isomorphic to the free object over $B$ , hence every element of $S$ can be expressed as words in the elements of $B$ , so $B$ generates $S$ . If we had $b \in B$ such that $B - \left\{ b \right\}$ generated $b$ , then $b$ could be expressed as a word in $B - \left\{ b \right\}$ . If $S$ is isomorphic to the free object over $B$ , then this means that $S$ is (or more precisely can be identified with) the equivalence classes of words in $B$ . But all of these words can be reduced to words in $B - \left\{ b \right\}$ . Can we use this to contradict that $S$ is isomorphic to the free object over $B$ ?

It actually seems that this depends on what the defining relations are. In a trivial case, if the defining relations include $a = b$ (either directly or as a consequence), then for any $B$ , the free object over $B$ would consist of one equivalence class. In fact, this generalizes massively: if the defining relations include (either directly or as a consequence) something of the form $b = f\left( a_{1},\ldots,a_{n} \right)$ , then by substituting $b$ for anything we can yield $a = b$ as a consequence, thus the free object over $B$ would consist of one equivalence class. This is unavoidable for general sets of defining relations, and by the free object definition it would very much be possible that $B$ would be a basis of this one-element free object, even if $B$ is not independent by our abstract generation framework definition. Thus, the two definitions actually aren’t equivalent, in general.

So let’s discuss some follow-up questions then. Is the converse at least true — that if a subset is a basis by our abstract framework definition, then it is a basis by the free object definition? Also, can we better characterize exactly for which sets of defining relations we have that all bases by the free object definition are also bases by the abstract framework definition?

It remains to figure this out.

EDIT: There actually seems to be no ambiguity here. In the Wikipedia article for free object, “basis” seems to be used informally, so that there isn’t an analogous formal definition of the word “basis” in the free object framework. This seems to be supported by this link too. Furthermore, I’d hold that the free object isn’t really a formal encapsulation of “basis” since “basis” could be intuitively interpreted differently too. Rather, the free object is the formal encapsulation of the concept of *unique* generation. The key there is unique — the idea is that any “condition of uniqueness” would go into the equivalence relation for the equivalence classes that the free object is constructed from. Actually, in the construction of the free object in universal algebra, really the equivalence relation is based on equivalence implied by a set of defining relations — can we extend this naturally to consider free objects for other notions of equivalence? How can we define this in general, and how would that relate to the free object of category theory? It remains for me to delve further into these questions. So really, the free object is best seen as just the set of equivalence classes of all expressions with equivalence brought about by certain defining relations — and this precisely captures the concept of unique generation for at least a subset of cases.

Is it true that a basis of an abstract generation must do unique generation, based on the independence assumption of the basis? Then, can I show possibly that an abstract generation basis would be a special case of the free object construction?

It remains to investigate these questions. We start now.

—

First, let’s talk about the free object and general unique generation. We want to formalize this concept of unique generation with arbitrary kinds of equivalence relations, and we want to see how this relates to the free object (whether this is more general than or actually equivalent to the free object.)

Let $V$ be a set whose elements we call characters, and let $L$ be a (first-order) language consisting of operation symbols. The set of words with operations from $L$ and characters in $V$ is denoted by $W$ . Now, let $E$ let be an equivalence relation on $W$ . We can define the generalized free object by $E$ over $V$ to be the set of equivalence classes by $E$ on $W$ .

But wait … right now this construction is specific to $V$ . Can we have a framework for as general a $E$ as possible but without knowing $V$ ? Earlier, this was done exactly by defining relations.

In other words, we want to define a general way to impose an equivalence relation on a set of words in some set of variables $V$ , independent of $V$ .

This really seems like an informal question; I’m not sure how to define this in a way we can work with precisely. It seems like defining relations might be the best bet for defining such an equivalence relation most generally, without any knowledge of $V$ ; it would then follow that (in an informal sense) the free object formally captures exactly the concept of unique generation.

Next, let’s talk about the whether the basis of an abstract generation must generate uniquely. Actually, here there is no conception in general of the idea of “unique” — that isn’t defined when we just have a generation relation. So it doesn’t even make sense to ask this question.

It really seems like what we’re doing here — which we can aptly name “abstract generation theory” — is just different from what the free object does. The free object captures unique generation; abstract generation captures general properties of generation. When it comes to generation, the free object does (as expected) satisfy the abstract axioms, with generation interpreted in the natural way as expression as a word in the variables that the free object is over. When it comes to bases, we’re just doing different things, although it doesn’t even seem like the term “basis” is formally defined in the framework of the free object (nevertheless, defining $B$ to be a basis of $S$ if $S$ is isomorphic to the free object over $B$ seems natural and seems to be the general terminology used in specific examples of the free object like say free modules, even if the term “basis” isn’t explicitly defined in general in the free object framework.)

—

Let’s switch gears and focus just on abstract generation theory. I suspect that with the Axiom of Choice we can show that for abstract generations every span must have a basis (an independent subset that spans it.)

Our conjectured result is:

Conjecture. If $T$ is the span of some subset, then $T$ must have a basis.

Attempt. First, note that we can just prove that the universal set in consideration has a basis, since any subset that is a span can just be “treated as its own universe.” In other words, say we have an abstract generation on $U$ ; we simply wish to prove that $U$ has a basis. Then, if $T \subseteq U$ is the span of some subset of $T$ , then the abstract generation on $U$ with domain restricted to $T$ is closed on $T$ , so we can just apply this result to $T$ while “ignoring the rest of $U$ outside of $T$ .”

So assume that $U$ has an abstract generation; we wish to prove that $U$ has a basis. Consider the set of all subsets of $U$ which generate (and hence span) $U$ , and call this set $S$ . We claim that the intersection of all sets in $S$ is in fact a basis of $U$ . Denote this intersection by $I$ . We show this by showing generation and independence in turn.

First, we consider generation. We have that every set in $S$ generates $U$ . Assume for the sake of contradiction that the intersection $I$ didn’t generate $U$ . Then, … (it remains to complete this — I think this is very doable, and something I will come back to soon.)

Next, we consider independence. Assume $I$ wasn’t independent, so there is $i \in I$ such that $I - \left\{ i \right\}$ generates $I$ . For each $T \in S$ , we have $I \subseteq T$ , so that $I - \left\{ i \right\} \subseteq T$ and $i \in T$ . Thus, $T$ is dependent. Hence, every element of $S$ is dependent. (It remains to complete this too — I think this is very doable, and something I will come back to soon as well.)

It remains to complete this. $\blacksquare$

—

As I mentioned in this post, I suspect that if we have an abstract generation where the cardinality of a basis is unique, then that implies further consequences analogous to familiar results from vector spaces. We try to show these here. We assume that a basis exists and the cardinality of a basis is unique, and we call this cardinality the dimension.

Conjecture. Assuming existence of dimension, no set of smaller cardinality than the dimension can span the set $U$ .

Attempt. Assume for the sake of contradiction that this was possible, that a set of smaller cardinality than the dimension could span the class.

It remains to continue this. $\blacksquare$

Conjecture. Assuming existence of dimension, any set of cardinality greater than the dimension must be dependent.

Attempt. It remains to do this. $\blacksquare$

(I also suspect that these results generalize appropriately if $U$ is a class and not just a set, as in the case of my logical generation theory in the linked-to post.)

—

This discussion is continued in the next post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply