Given a set $\mathcal{S} = \{S_1, S_2, S_3\}$, two ordered sets can be produced:

$\mathcal{S}^+$, where $S^+_i \in (S_1,S_2,S_3)$, and

$\mathcal{S}^-$, where $S^-_i \in (U\setminus S_1, U\setminus S_2, U\setminus S_3)$, where $U$ is the universal set, i.e., $S^-_i$ is the complement of $S_i$.

How can I succinctly define a function $P(S_1,S_2,S_3)$ that produces a set of intersections for all combinations between the sets $\mathcal{S}^+$ and $\mathcal{S}^-$, while selecting exactly 1 element for each index?

In the above example, $P(S_1,S_2,S_3)$ would give:

$\{S^-_1 \cap S^-_2 \cap S^-_3, \\ S^-_1 \cap S^-_2 \cap S^+_3, \\ S^-_1 \cap S^+_2 \cap S^-_3, \\ S^-_1 \cap S^+_2 \cap S^+_3, \\ S^+_1 \cap S^-_2 \cap S^-_3, \\ S^+_1 \cap S^-_2 \cap S^+_3, \\ S^+_1 \cap S^+_2 \cap S^-_3, \\ S^+_1 \cap S^+_2 \cap S^+_3\}$

So clearly, $|P(\mathcal{S})| = 2^{|\mathcal{S}|}$.

The best I could come up with was:

$P(S_1, S_2, ..., S_n) = \displaystyle\bigcap_{S_i \in \mathcal{S}^+ \text{ or } \mathcal{S}^-} S_i$

but that seems pretty clunky and also, I am not sure it stops both $S^+_i$ and $S^-_i$ being selected anyway.

Is there an easy and concise way of writing this function?


The order of element sets in the set $\{S_1,S_2,S_3\}$ seems to be important to you, so it's better to use an indexed family $(S_i)_{i \in \{1,2,3\}}$ instead.

You could index the intersections using functions $f: \{1,2,3\} \to \{0,1\}$, this set of functions is denoted by $2^I$ if $I$ is your index set $\{1,2,3\}$. I could denote the set of intersections as follows:

$$I(({S_i})_{i \in I}) = \{I_f((S_i)_{i \in I}: f \in 2^I\}$$


$$I_f((S_i)_{i \in I}) = \{x \in U: \forall i \in I: (f(x) = 1) \iff (x \in S_i)\}$$ for any fixed $f \in 2^I$.

I think this is reasonably concise (you could omit the $(S_i)_{i \in I}$ argument if they're fixed in some context, and just write $\{I_f: f \in 2^I\}$ etc.), it generalises to any size of indexed family, and it's also clear that the sets $I_f, f \in 2^I$ indeed form a partition of $U$ (important, if the choice of tags means anything): If $f \neq g$, they must differ on some index $i$, say WLOG $f(i)= 0$ and $g(i) = 1$, and then $I_f \subseteq U\setminus S_i$ and $I_g \subseteq S_i$ so $I_f \cap I_g =\emptyset$. And if $x \in U$, define $f_x: I \to \{0,1\}$ by $f_x(i) = 0$ if $x \notin S_i$, $f_x(i) = 1$ otherwise. Then clearly $x \in I_{f_x}$.

If, as you say in the comments, you want to keep $S^+$ and $S^-$ why not use functions $f: I \to \{+,-\}$ instead? And then you can say

$$I_f = \bigcap S_i^{f(i)}$$ to stay in the spirit of your proposal. As the codomain has $2$ elements (symbols), we still have $2^{|I|}$ many such functions.

  • $\begingroup$ Thanks for your answer. The initial order of elements in the set $\mathcal{S}$ is not important, nor is it important for the final set. Order only mattered because I created the two sets $\mathcal{S}^+$ and $\mathcal{S}^-$ a choice needed to be made between $S^+_i$ or $S^-_i$, so the indices had to be the same between the two sets. $\endgroup$ – Gus Kenny Jul 1 '18 at 6:55
  • $\begingroup$ Actually, on second thought, because $S^+_i \cap S^-_i = \emptyset$, does that mean that i can just say that $P(S_1, S_2, ..., S_n) = \{x : \displaystyle\bigcap_{q \in Q} q, \quad \forall Q \in \mathscr{P}^{\mathcal{S}^+ \cup \mathcal{S}^-}, x \neq \emptyset\}$? $\mathscr{P}$ being the power set, and sets $\mathcal{S}^+$ and $\mathcal{S}^-$ no longer having to be ordered because if $S^+_i, S^-_i \in x$ then $p = \emptyset$. If possible i would like to keep the sets $\mathcal{S}^+, \mathcal{S}^-$ because they are used elsewhere.. $\endgroup$ – Gus Kenny Jul 1 '18 at 7:10
  • $\begingroup$ that should have been $x=\displaystyle\bigcap_{q \in Q}q$, sorry $\endgroup$ – Gus Kenny Jul 1 '18 at 7:43
  • $\begingroup$ You could say $I_f = \bigcap_{i \in I} S_i^{f(i)} $ with $f : I \to \{+,-\}$ instead, if that notation is so important. $\endgroup$ – Henno Brandsma Jul 1 '18 at 8:13
  • $\begingroup$ Thanks a lot for your help! $\endgroup$ – Gus Kenny Jul 1 '18 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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