Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across a problem where I don't know what field to consult. The problem is simple to explain:

I have a geometric object $S$, and a finite set of maps $V$ from the points in this object to $V$.

Intuitively, any $v \in V$ partitions $S$, and chosing one of these partitions yields a new such partitioning.

What kind of thing is this and/or what could I google to get more information on it or similar structures? (I am particularly interested in iterated applications, given an initial element of $V$ (partitioning), to a given sequence of points.)

Thank you in advance.

share|improve this question
where did you come across this problem? –  bgins Feb 2 '12 at 8:59
I'm working in logic and this seemed a succinct way of describing an aspect of the semantics I'm investigating (tentatively). –  tap Feb 2 '12 at 9:05
add comment

1 Answer 1

This seems like a fairly general concept. For one, it seems to be a particular generalization of finite symmetry groups. Below is some food for thought.

Note that $V^{(k)}=\{v^k|v\in V\}\subset V$ for $k\in\mathbb{Z}^+$.

Note that we could also view each $s\in S$ as defining an action $\sigma(s)$ on $V$ by $v\rightarrow v(s)$. In other words, $(\sigma(s))(v)=v(s)$. For each $s$, let us call $\sigma(s):V\rightarrow V$ the induced action of $s$ on $V$ and let us call $\sigma:S\rightarrow V^V$ the "complementary" map.

Since composition of maps is associative, $V$ is a semigroup under map composition. If there is a unique element $e \in V$ so that $e(S)=\{e\}$ (i.e., a unique simultaneous fixed point of each "complementary" map $s:V\rightarrow V$), then $V$ is a monoid. Note, however, that composition of maps is not commutative. For example, we have no guarantee that right-inverses and left-inverses of each $v \in V$ exist (in $V$) or that they are the same. Of course, if this is the case, then $V$ is a group as well. But in general, $V$ will be a semigroup and we need to be aware of concepts like pseudoinverse, idempotents, Green's relations and absorbing elements before we try to think of $V$ as the more familiar group. Each $V^{(k)}$ above will be a sub-object of the respective type. In case $V$ is in fact a group (which is not true in general), it would help to have some background on the symmetric group of permutations.

If there exists an $n>1$ so that $v^n=v$ for all $v$ or, more generally, so that $V^n=V$ these would be interesting cases to study. The latter case (when the map $v\rightarrow v^n$ is onto or surjective) might imply that $V$ is a group with unique identity, particularly for $n=|V|$, but you might also need to assume a limit on the number of idempotents. Whether left or right inverses are always well-defined seems to also hinge on the number of distinct idempotents.

If left or right inverses are well-defined and there is at most one idempotent, I think we can extend $V$ to include an identity and left or right inverses of each element. Each stepwise extension would still be finite. Whether the recursive extension (like a closure) is finite is another question.

$V=S$ would be another interesting case to study, but might reduce or specialize to the study of symmetry groups, the symmetric group, and group actions. If $V$ were allowed to be infinite, elliptic curves would be another interesting example.

Intuitively, I'm thinking of the (finite sets) $V$ as "views" or perspectives or projections of the (possibly infinite sets) $S$, and as the "complementary" map $\sigma$ as an important key to decomposing $V$. If $S$ is itself already a group, then this "complementary" map could define a group action of $S$ on $V$, providing a rich source of examples.

Perhaps there are also fruitful connections with category theory.

share|improve this answer
Thank you for your elaborate answer. I will certainly look into the relfections you've offered. –  tap Feb 2 '12 at 13:28
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.