Consider the following definition from section 2.2 of this research paper

We write $\mathcal{P}(𝑃)$ for the power set of the set $𝑃$. An $π‘Ÿ-$partition $Ξ©=\{𝑃_1,\cdots,𝑃_π‘Ÿ\}$ of a set $𝑃$ is a disjoint family of $π‘Ÿ$ nonempty subsets of $𝑃$ with $𝑃=𝑃_1βˆͺ \cdots βˆͺ 𝑃_π‘Ÿ$. Let $Ξ›βŠ†\mathcal{P}(𝑃)$ be a family of subsets of $𝑃$. For a permutation $𝜎$ on $𝑃$, we define $𝜎(Ξ›)=\{𝜎(𝐴):π΄βˆˆΞ›\}βŠ†\mathcal{P}(𝑃)$. A family of subsets $Ξ›βŠ†\mathcal{P}(𝑃)$ is said to be $Ξ©-$partite if $𝜎(Ξ›)=Ξ›$ for every permutation $𝜎$ such that $𝜎(𝑃_𝑖)=𝑃_𝑖$ for every $𝑃_π‘–βˆˆΞ©$. We say that $Ξ›$ is $π‘Ÿ-$partite if it is $Ξ©-$partite for some $π‘Ÿ-$partition $Ξ©$. These concepts can be applied to access structures, which are actually families of subsets.

My doubt lies in $𝜎(Ξ›)=\{𝜎(𝐴):π΄βˆˆΞ›\}βŠ†\mathcal{P}(𝑃)$ because the paper does not define the permutation function on a set, but used it. I didn't came through any standard defifnition of permutation function on set which gives another set which is different from the input set because the order of elements in a set is immaterial.

What I am clear from the context is

$$\sigma: P \rightarrow P$$ $$ \sigma(A \in \mathcal{P}(P)) = B \in \mathcal{P}(P)$$

but I don't know what exactly $B$ is.

What is the definition of a permutation function over a set?

In addition, can you give some example of the above $Ξ©-$partite ?


1 Answer 1


A permutation on a set is a bijection from the set to itself; thus $\sigma$ is a (bijective) map from $P$ to itself, not from $p(P)$ to itself (though it does induce a map from $p(P)$ to itself in a natural manner).

Also, if $f$ is a map from $A$ to $B$ and $X$ is a subset of $A$, then $f(X) = \{f(x), x \in X\}$. This is completely standard notation.

For a collection $\Lambda$ of subsets of $P$, $\sigma(\Lambda) = \{\sigma(A), A \in \Lambda\}$ is the collection of subsets of $P$ which is obtained by applying $\sigma$ to all the elements of $\Lambda$.

Example: $P = \{1,2,\dots,8\}$, $\Omega = \{\{1,2\},\dots,\{7,8\}\}$. Then $\Lambda = \{\{1,2,3,4\},\{5,6,7,8\}\}$ is $\Omega$-partite since clearly every permutation of $P$ that fixes each $P_i$ also fixes each element of $\Lambda$, so in fact we even have $\sigma(A) = A$ for all $A$. On the other hand, $\Lambda' = \{\{1,2,3\},\{4,5,6\},\{7,8\}\}$ is not; for instance $\sigma = (34)$ yields $\sigma(\Lambda') = \{\{1,2,4\},\{3,5,6\},\{7,8\}\} \ne \Lambda'$.

  • $\begingroup$ My observation is $\mathcal{P}(P)\longrightarrow \mathcal{P}(P)$ . Domain is $\mathcal{P}(P)$ and codomain is $\mathcal{P}(P)$. but you are telling $P\longrightarrow P$, How it is? Can you give an explanation $\endgroup$
    – Natwar
    Dec 21, 2019 at 7:46

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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