0
$\begingroup$

Suppose we have a set of sets

$$S = \{S_1, S_2, ..., S_n \}$$

and for ease of notation, let

$$\Omega = \bigcup_{i=1}^n{S_i}$$

that is, the set of all elements that occur in any $S_i$.

And we want to find

$$T_k = \{x \in \Omega \mid x \text{ occurs in at least $k$ of the $S_i$} \}$$

For example, if we had:

$$ \begin{align} S_1 &= \{1, 2, 3\} \\ S_2 &= \{2, 3, 4\} \\ S_3 &= \{1, 5\} \\ S_4 &= \{1, 2\} \\ S_5 &= \{4, 5\} \end{align} $$

then

$$T_3 = \{1, 2\}$$

For the special cases of $k=1$ and $k=n$, we have

$$ T_1 = \bigcup_{i=1}^n{S_i} \\ T_n = \bigcap_{i=1}^n{S_i} $$

so it's kind of a stricter version of a union or a looser version of an intersection.

My question is:

Is there a mathematical term for this operation/function?


A kind of auxiliary question:

I realise you could break this process down a bit by defining

$$C(x) = |\{S_i \mid x \in S_i\}|$$

as a sort of "counter" function.

Then we can re-express $T_k$ in terms of this

$$T_k = \{x \mid C(x) \ge k\}$$

Is there a mathematical term for this function $C(x)$?


I'm not asking for a more concise way to write $T_k$ - this question has arisen in a programming context, so how to do the calculation isn't a concern. What I'm curious about is whether this is a pre-existed mathematical notion and whether it has a name.

I'd be happy to know if there's something defined using $=$ not $\geq$, i.e.

$$T_k = \{x \mid C(x) = k\}$$

so $x$ occurs in exactly $k$ of the $S_i$. The specifics of the comparison aren't so important.


These questions touch on similar ideas but neither really gets close to calculation in my question:

How to write a counter in proper notation?

How to write down formally number of occurrences?

Answers to both of these mention the Iverson bracket, which I'm sure I could use to write $T_k$ more concisely, but as I've said, that is not the question I'm asking.

$\endgroup$
1
  • 1
    $\begingroup$ What you did is perfectly fine. Math isn't about symbols, it is important to use the English language to express mathematics as clearly as possible. $\endgroup$
    – Qi Zhu
    Commented Jan 17, 2020 at 12:11

1 Answer 1

1
$\begingroup$

You should go for $$C(x)=|\{i\mid x\in S_i\}|$$ Observe e.g. that $|\{S_i\mid x\in S_i\}|=1$ and $|\{i\mid x\in S_i\}|=n$ if all $S_i$ are equal.

Also you can practicize indicator sets: $$C(x)=\sum_{i=1}^n1_{S_i}(x)$$

I cannot help you with specific terminology on this.

$\endgroup$

You must log in to answer this question.

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