# How to express the set of intersections between two ordered sets by selecting exactly one element per index?

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\}$$

where

$$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.

• 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. – Gus Kenny Jul 1 '18 at 6:55
• 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.. – Gus Kenny Jul 1 '18 at 7:10
• that should have been $x=\displaystyle\bigcap_{q \in Q}q$, sorry – Gus Kenny Jul 1 '18 at 7:43
• You could say $I_f = \bigcap_{i \in I} S_i^{f(i)}$ with $f : I \to \{+,-\}$ instead, if that notation is so important. – Henno Brandsma Jul 1 '18 at 8:13
• Thanks a lot for your help! – Gus Kenny Jul 1 '18 at 13:15