2
$\begingroup$

I have two finite sets: $S$and $S'$. I know $\mathrm{card}(S) = \mathrm{card}(S')$

I have a function $colour()$ that produces some colour for each element of $S$and $S'$.

I know that there is at least one "complete" bijection from $S$ to $S'$ that preserves colour, but there are as many as $\mathrm{card}(S)!$

I need some succinct notation to enumerate all such bijections that:

  • are from $S$ to $S'$
  • preserve colour
  • cover all elements of $S$ and $S'$

The more succinct and intuitive and widely understandable the notation, the more preferable (I'm aiming for one line in an algorithm).

What I'm current looking at is something like this:

$M := \{ \mu : S \xrightarrow{1:1} S' \mid s \mapsto s' : colour(s) = colour(s') \}$

... but I'm not sure this is "standard" / well-understood / complete on $S,S'$ / etc., so I'm looking for alternatives or feedback.


EDIT I really need to construct the set on one line without prose and I really don't think it needs to be so complicated as some (not all) of the answers suggest. :)

For the moment, very much inspired by Brian's answer, I'm going with simply:

$M := \{ \mu : S \xrightarrow{1:1} S' \mid colour(\mu(s)) = colour(s)\text{ for all }s\in S\}$

I hope this is clear and intuitive: $M$ is the set of all 1:1 mappings $\mu$ between $S$ and $S'$ where $\mu$ preserves colour.

$\endgroup$
3
  • $\begingroup$ What do you mean by "cover"? If you just mean that every element of $S$ is in the domain and every element of $S'$ is in the range, then that is already implied by "bijection". In fact, bijection is actually stronger than that, because it means that you can't have two different elements of $S$ mapping to the same element of $S'$. $\endgroup$
    – user14972
    Aug 19, 2013 at 18:42
  • $\begingroup$ Are you sure there is at least one color-preserving bijection? Let $S$ be the positive integers and $S'$ be the negative integers, and set $$\text{color}(n) = \begin{cases} \text{blue} & n = 1 \text{ or } n < -1 \\ \text{red} & n = -1 \text{ or } n > 1 \end{cases} $$ I'm pretty sure there is no color-preserving bijection between $S$ and $S'$. $\endgroup$
    – user14972
    Aug 19, 2013 at 18:45
  • $\begingroup$ @Hurkyl, wrt. "cover", of course. I was looking for a non-prose notation that might not actually mention the word "bijection", hence the pleonasm. The existence of at least one colour-preserving bijection is a pre-existing condition on $S$ and $S'$. This is assumed to be true for those sets. $\endgroup$
    – badroit
    Aug 19, 2013 at 18:54

3 Answers 3

3
$\begingroup$

I’d prefer to do it in two stages, and with a few more words:

Let $M^+$ be the set of bijections from $S$ to $S'$, and let $$M=\left\{\mu\in M^+:\operatorname{colour}(s)=\operatorname{colour}\big(\mu(s)\big)\text{ for all }s\in S\right\}\;.$$

$\endgroup$
7
  • $\begingroup$ I would suggest to use names that are a tad more descriptive. For example, instead of $M^+$, use $\mathrm{Bij}(S,S')$. I would also suggest using something else instead of $M$. The point is that it will be easier for the reader to recall what the set is if you call it, say, $\mathrm{Same}(S,S')$, than if you simply call it $M$. $\endgroup$ Aug 19, 2013 at 18:17
  • $\begingroup$ @Andres: I agree with the mnemonic principle, but my fairly strong dislike of long names like $\operatorname{Bij}$ overrides it in this case. (In any case, I was trying to retain as much as possible of the OP’s notation.) $\endgroup$ Aug 19, 2013 at 18:22
  • $\begingroup$ Hi Brian. Sure; this was a suggestion for the OP to consider not just in this case but also in the future. $\endgroup$ Aug 19, 2013 at 18:24
  • $\begingroup$ @Andres: And in principle I certainly second the advice! $\endgroup$ Aug 19, 2013 at 18:30
  • 1
    $\begingroup$ @badroit: It’s a reasonable choice, given your constraints, and I think it definitely preferable to the original version. $\endgroup$ Aug 19, 2013 at 19:18
1
$\begingroup$

If $C$ is the set of colors, then we can introduce the notion of a $C$-colored set. A $C$-colored set is hereby defined to be a pair $(S,c)$ where $S$ is a set and $c:S \to C$ (this is the function you called color).

A homomorphism of colored sets from $(S,c)$ to $(S',c')$ is a function $f:S \to S'$ with the additional property that $c(x) = c'(f(x))$.

An isomorphism is an invertible homomorphism. If $f$ is a homomorphism of $C$-colored sets, then it is a bijection of sets if and only if it is an isomorphism of $C$-colored sets.

If $X$ and $Y$ are colored sets -- that is, we have $X = (X', c)$ and $Y = (Y',d)$ where $c:X' \to C$ and $d : Y' \to C$, then the set of all isomorphisms of colored sets would be called

$$ \text{Iso}(X, Y) $$

$\endgroup$
1
$\begingroup$

Let $S_c = \{s \in S: colour(s) = c\}$.

We can express the number of such bijections as $\vert M \vert = \prod_c{(\vert S_c \vert !)}$.

The same notation can be abused to say $M = F(\prod_c{S_c!})$ where $F:S \rightarrow S'$ is the color-preserving bijection we are guaranteed to have. Or if $S = S'$, simply $M = \prod_c{( S_c !)}$

EDIT: One way to make it less ambiguous, is to first define the factorial of a set as the set of all bijections between $S$ and itself. Now for the $S = S'$ case we can write instead:

$M = \bigcup_c{(S_c!)}$.

And there is no longer any ambiguity, since the union of two functions with disjoint domains is a function defined on the union of those domains specializing to whichever corresponding function. Now if it also understood that a function composed with a set of functions denotes the set comprised of that function composed with each element of that set, then for the general case $S \ne S'$ we can write without ambiguity:

$M = F(\bigcup_c{(S_c!)})$

$\endgroup$
5
  • $\begingroup$ The notation $\{G\in \prod_c(S_c!): F\circ G\}$ does not mean anything. Literally, you read this as "the sets of $G$ in $\prod_c (S_c!)$ such that $F\circ G$". Perhaps you meant $\{F\circ G: G\in\prod_c (S_c!)\}$. $\endgroup$ Aug 19, 2013 at 18:35
  • $\begingroup$ I fixed it to something simpler. $\endgroup$ Aug 19, 2013 at 18:37
  • $\begingroup$ Thanks! I had tried something similar before in terms of using products to produce the pairs in the bijection. The number of bijections makes sense to me, but I'm not sure I follow the notation $S_c!$, this is the set of all permutations of the set? I fear that clarity is missing in this notation. $\endgroup$
    – badroit
    Aug 19, 2013 at 18:48
  • 1
    $\begingroup$ Yeah, it is certainly not widely understandable, although perhaps it is the best that can be done in terms of being succinct. The idea is that the factorial of a set can be defined as the set of its permutations. There is also some ambiguity about what $\prod$ means and how functions and permutations are identified with each other. $\endgroup$ Aug 19, 2013 at 18:55
  • $\begingroup$ It seems like by replacing $\prod$ with $\bigcup$ and specifically defining the factorial of a set as producing a function we can get rid of most of the ambiguity, I updated the question. $\endgroup$ Aug 19, 2013 at 19:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .