This is a continuation of Geometric Ruzsa triangle inequalities and metric spaces with dilations . Proposition 1 from that post may be applied to groupoids. Let’s see what we get.
Definition 1. A groupoid is a set , whose elements are called arrows, together with a partially defined composition operation
and a unary “inverse” operation:
which satisfy the following:
- (associativity of arrow composition) if
and
then
and
and moreover we have
,
- (inverses and objects)
and
; for any
we define the origin of the arrow
to be
and the target of
to be
; origins and targets of arrows form the set of objects of the groupoid
,
- (inverses again) if
then
.
____________________
The definition is a bit unnecessary restrictive in the sense that I take groupoids to have sets of arrows and sets of objects. Of course there exist larger groupoids, but for the purpose of this post we don’t need them.
The most familiar examples of groupoids are:
- the trivial groupoid associated to a non-empty set
is
, with composition
and inverse
. It is straightforward to notice that
and
, which is a way to say that the set of objects can be identified with
and the origin of the arrow
is
and the target of
is
.
- any group
is a groupoid, with the arrow operation being the group multiplication and the inverse being the group inverse. Let
be the neutral element of the group
. Then for any “arrow$
we have
, therefore this groupoid has only one object,
. The converse is true, namely groupoids with only one object are groups.
- take a group
which acts at left on the set
, with the action
such that
and
. Then
is a groupoid with operation
and inverse
. We have
, which can be identified with
, and
, which can be identified with
. This groupoid has therefore
as the set of objects.
For the relations between groupoids and dilation structures see arXiv:1107.2823 . The case of the trivial groupoid, which will be relevant soon, has been discussed in the post The origin of emergent algebras (part III).
____________________
The following operation is well defined for any pair of arrows with
:
Let be three subsets of a groupoid
with the property that there exists an object
such that for any arrow
we have
. We can define the sets
,
and
.
Let us define now the hard functions and
with the property: for any
we have
(1)
(The name “hard functions” comes from the fact that should be seen as an easy operation, while the decomposition (1) of an arrow into a “product” of another two arrows should be seen as hard.)
The following is a corollary of Proposition 1 from the post Geometric Ruzsa triangle inequalities and metric spaces with dilations:
Corollary 1. The function defined by
is injective. In particular, if the sets are finite then
.
____________________
Proof. With the hypothesis that all arrows from the three sets have the same origin, we notice that satisfies the conditions 1, 2 from Proposition 1, that is
- the function
is injective.
As a consequence, the proof of Proposition 1 may be applied verbatim. For the convenience of the readers, I rewrite the proof as a recipe about how to recover from
. The following figure is useful.
We have and
and we want to recover
and
. We use (1) and property 1 of
in order to recover
. With
comes
. From
and
we recover
, via the property 2 of the operation
. That’s it.
____________________
There are now some interesting things to mention.
Fact 1. The proof of Proposition 2 from the Geometric Ruzsa post is related to this. Indeed, in order to properly understand what is happening, please read again The origin of emergent algebras (part III) . There you’ll see that a metric space with dilations can be seen as a family of defirmations of the trivial groupoid. In the following I took one of the figures from the “origin III” post and modified it a bit.
Under the deformation of arrows given by the operation
becomes the red arrow
The operation acting on points (not arrows of the trivial groupoid) which appears in Proposition 2 is , but Proposition 2 does not come straightforward from Corollary 1 from this post. That is because in Proposition 2 we use only targets of arrows, so the information at our disposal is less than the one from Corrolary 1. This is supplemented by the separation hypothesis of Proposition 2. This works like this. If we deform the operation
on the trivial groupoid by using dilations, then we mess the first image of this post, because the deformation keeps the origins of arrows but it does not keep the targets. So we could apply the Corollary 1 proof directly to the deformed groupoid, but the information available to us consists only in targets of the relevant arrow and not the origins. That is why we use the separation hypotheses in order to “move” all unknown arrow to others which have the same target, but origin now in
. The proof then proceeds as previously.
In this way, we obtain a statement about algebraic operations (like additions, see Fact 2.) from the trivial groupoid operation.
Fact 2. It is not mentioned in the “geometric Ruzsa” post, but the geometric Ruzsa inequality contains the classical inequality, as well as it’s extension to Carnot groups. Indeed, it is enough to apply it for particular dilation structures, like the one of a real vectorspace, or the one of a Carnot group.
Fact 3. Let’s see what Corollary 1 says in the particular case of a trivial groupoid. In this case the operation is trivial
and the “hard functions$ are trivial as well
and
The conclusion of the Corollary 1 is trivial as well, because (and so on …) therefore the conclusion is
However, by the magic of deformations provided by dilations structures, from this uninteresting “trivial groupoid Ruzsa inequality” we get the more interesting original one!