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

93 Views Asked by At

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?

1

There are 1 best solutions below

5
On BEST ANSWER

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.