You might think that, by contrast to the case of a graph, the definition of a group would be quite clear-cut.
Traditionally there are four axioms. A group is a set G with a binary operation • satisfying
- closure: for all a,b∈G, a•b∈G.
- associativity: for all a,b,c∈G, (a•b)•c = a•(b•c).
- identity: there exists e∈G such that, for all a∈G, a•e = e•a = a.
- inverses: for all a∈G, there exists a*∈G such that a•a* = a*•a = e, where e is the element from the preceding axiom.
There are some small comments that can be made. As stated the axioms are redundant, since if • is a binary operation on G then by definition the closure axiom holds. It is there for historical reasons (the definition used to be that a group was a set of transformations on a set closed under composition and inversion and containing the identity transformation) as well as pedagogical reasons (having defined a group, we go on to define a subgroup, where closure is a crucial condition to check).
Also, of course, the associative law is really a kind of commutative law: it says that, for any two elements a and c, left translation by a and right translation by c commute.
Then one can give axioms for an action of the group G on a set X; this is a map μ from X×G to X satisfying
- for all a,b∈G and x∈X, μ(x,a•b) = μ(μ(x,a),b).
- for all x∈X, μ(x,e) = x.
These axioms “correspond” in a sense to the closure and identity axioms for a group; the inverse axiom is not needed since it can be deduced from the others.
But my purpose here is to give a more radical re-definition of a group acting on a set.
An independence algebra is an algebra A (in the sense of universal algebra) with two properties:
- the minimal generating sets have the exchange property (that is, if X,Y are minimal generating sets and x∈X\Y, then there exists y∈Y\X such that X\{x}∪{y} is a minimal generating set.
- any map from a mimimal generating set of A into A extends (uniquely) to an endomorphism of A.
These axioms are clearly very different from the axioms for a group, since it doesn’t matter exactly what the operations in A actually are. I am going to assume that the algebra A is finitely generated; then the exchange property implies that all minimal generating sets have the same cardinality, and indeed they are the bases of a matroid. Then the second axiom has, in my view, a claim to be the “missing axiom” of matroid theory, since it holds in vector spaces (the motivating example of matroids), and lies at the foundation of linear algebra. (A map from a basis into the vector space is specified by a matrix; and, without further thought, we use the matrix to represent the linear transformation extending this map.)
The rank of a finitely generated independence algebra is the cardinality of a minimal generating set.
Now the theorem for today is:
An independence algebra of rank 1 is “the same thing” as a group acting on a (possibly empty) set.
To explain: let A be an independence algebra of rank 1. Let B be the set of elements which generate A, and C the remaining elements of A. Choose a fixed b∈B. Then for every a∈A, there is a unique endomorphism of A mapping b to a; it is an automorphism if a is in B. So we have matched the elements of B with the group G of automorphisms of A. Now we have an action of this group on the set of endomorphisms which are not automorphisms, by composition; this induces an action of G on C.
Conversely, if the group G acts on a set C, we define an algebra with a nullary operation (a constant) for each element of C, and a unary operation for each g∈G (right multiplication on G, and the given action on C); it is easy to check that we obtain a rank 1 independence algebra from this construction.
You can find a more detailed account in my paper with Csaba Szabó in J. London Math. Soc. 61 (2000). We went on to “determine” all the finite independence algebras. There are two types: a group acting on a set, “blown up” by an auxiliary set; and a very restricted type consisting, more-or-less, of vector spaces and affine spaces (with a few “exceptional” examples of small rank).
I’m not too sure about the missing axiom claim… in order to qualify, we must have
1) It holds if and only if M is representable
2) It is not of the form “there exists a collection of vectors whose dependencies are the dependencies of the matroid”
I wasn’t being entirely serious there.
Pingback: Definition and Determination : 10 | Inquiry Into Inquiry