An Abstract Approach to Generating Sets

In this exploration, we generalize the theory of bases in vector spaces to other settings involving “generation” by subsets, inspired by our work with “logical bases” of classes of models (see my previous exploration for context on that.) We can even try to see how this relates to concepts like the free object.

All our work is done in a “universal” set $U$ — so basically a set $U$ that we designate as “the universe.” Given any subset $S \subseteq U$ and $c \in U$ , there is a generation relation, where either $S$ generates $c$ or $S$ doesn’t. (In the case of vector spaces, generation corresponds to linear expansion.) Of course, if $T \subseteq U$ and $S$ generates each element of $T$ , then we say that $S$ generates $T$ . Generation is required to satisfy the following axioms:

Generation of Self: $S$ always generates itself.
Generation by Subset: if $S \subseteq S^{'}$ and $S$ generates $c$ , then $S^{'}$ generates $c$ .

These two axioms are pretty intuitive, but would we want any more? As we go through with this theory, we can see if additional assumptions could help yield our desired results.

Let’s develop this theory now, inspired by and patterned off of that for vector spaces.

Definition. A subset $S$ is independent if for any $c \in S$ , $S - \left\{ c \right\}$ doesn’t generate $c$ . If $S$ is not independent, then $S$ is dependent.

Remark. An equivalent definition of independence is: for any $c \in S$ , no subset of $S - \left\{ c \right\}$ can generate $c$ . (The equivalence follows immediately from the “generation by subset” axiom.)

Definition. If $S \subseteq U$ , then the span of $S$ is the subset of all elements that are generated by $S$ . (Thus, saying that $S$ generates $c$ is equivalent to saying that $c$ is in the span of $S$ .)

Definition. A basis of $S$ is a subset $B$ such that $B$ is independent and the span of $B$ is $S$ .

Lemma. If:

$S$ is a proper subset of $S^{'}$ , and
$S$ and $S^{'}$ are subsets of $T$ , and
$S$ is a basis of $T$ ,

then $S^{'}$ is dependent.

(We write the conditions this way to avoid grammatical comma-based ambiguity that was present when written out as a single line.)

Proof. Since $S$ is a basis of $T$ and $S^{'} \subseteq T$ , $S$ generates $S^{'}$ . Then, it immediately follows that $S^{'}$ is dependent by definition. $\blacksquare$

Lemma. If $S$ is a proper subset of $S^{'}$ and $S^{'}$ is independent, then $S$ is independent.

Proof. Assume for the sake of contradiction that $S$ was dependent. So there would exist $c \in S$ such that $S - \left\{ c \right\}$ generates $c$ . But then $S^{'}$ would be dependent too, contradiction. $\blacksquare$

Can we show that any two bases must have the same cardinality? I highly doubt it from this, since we have free objects with different-cardinality bases (e.g., free modules whose underlying rings don’t have the Invariant Basis Number or IBN property; an example of such is discussed in linear algebra – A ring without the Invariant Basis Number property – Mathematics Stack Exchange.) And I highly suspect that this abstract framework encompasses free objects.

This could shed some light on why I was struggling to show the existence of a “logical dimension” in my previous exploration, and why the proofs of these statements for vector spaces seem to require more than what we assume here — we might need to involve other assumptions for that.

Upon further thought, it seems that we might even be able to prove this framework equivalent to the free object, in the sense that the free object satisfies it, and any generation that satisfies the abstract axiomatization can be expressed as a generation according to a free object.

Let’s try this now. More precisely, we want to show the following: generations that satisfy the axioms above (which here we call “abstract” generations) are equivalent to generations by expressions/words as would be done in the construction of the free object.

Well, the fact that generations a la free objects are also abstract generations is obvious: clearly $S$ generates itself trivially, and if $S^{'}$ generates $T$ (each element of $T$ can be expressed as expressions in $S^{'}$ ) then clearly $S \supseteq S^{'}$ generates $T$ . Thus, that direction is immediate.

But what about the other? Actually, I’m not so sure about this without additional assumptions above. But let’s try this anyway.

Let $G$ be a generation: in other words, $G$ is a relation of the form $G(S,c)$ where $S$ is a subset of $U$ and $c$ is an element of $U$ . (In other words, $G$ is a relation on $2^{U} \times U$ , specifically a unary relation.) Given $G$ , we want to find an algebraic structure on $U$ such that $G$ is exactly the generation on $U$ by that structure. Or we at least want to understand better for which $G$ this is possible.

Can we use cardinality to say something here? Like we can count the cardinality of possible (different) abstract generations, and then show that this is greater than the cardinality of possible algebraic generations, thus showing that not all abstract generations can be equal to algebraic generations? (This would follow because any map from the set of different abstract generations to different first-order generations then couldn’t be injective, so that two different abstract generations must map to the same algebraic structure, which would be impossible. In some sense, this is like a kind of “Pigeonhole Principle,” but for infinite cardinalities.)

So let’s try this. What is the cardinality of the set of different abstract generations? Well, for a unary relation on $S$ , there are $2^{S}$ such relations (we’re being sloppy with notation and confusing sets for cardinalities, but that’s OK for our purposes.) Thus, there are $2^{2^{U}U}$ abstract generations. How about algebraic generations? How many possible algebraic theories on $U$ are there? Well, if the size of the set of axioms is unlimited then a simple analysis would yield an unlimited upper bound, and we’d need more mathematical logic to talk about whether two theories are equivalent. So I’m not sure if this approach is the best to yield low-hanging fruit.

It remains to figure this out.

—

We continue this discussion in the next post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply