(Terminology) Name for a subset that has non-empty intersection with every block of a partition?

26 Views Asked by At

Consider the following data: a set $X$, a partition $\mathcal{P} := \{B_i\}_{i \in I}$ of $X$ whose elements $B_i \subseteq X$ are called "blocks", and another subset $Y \subseteq X$.

Question: Is there a name for $Y$ when it satisfies the following property with respect to $\mathcal{P}$: $Y \cap B_i \not= \emptyset$ for all $i \in I$? I.e. the intersection of $Y$ with every block of the partition is non-empty?

Examples: Let $p: X \to X$ be an idempotent function, $p \circ p = p$, then the preimages under $p$ induce a partition of $X$, and the set of fixed points (= the image in this case) of $p$ has this property with respect to that partition.

Let $f: X \to Y$ and $g: Y \to X$ be such that $f \circ g \circ f = f$. Then the preimages of $f$ induce a partition of $X$, and the image of $g \circ f$ satisfies this property with respect to the partition (if it didn't, then $f ( Im (g \circ f))$ would be a strict subset of $Im(f)$ and $f \circ g \circ f$ would not equal $f$).

Comment: Thinking of the blocks of the partition as being "horizontal", what is being asked for is a name for a "vertical" set that crosses each "horizontal" set at least once.

1

There are 1 best solutions below

1
On BEST ANSWER

Seemingly it is "hitting set"

Hitting set: Let C be a collection of sets. H is a hitting set of C if the intersection of H and any set in C is non-empty.

Ref: https://cs.nyu.edu/~shasha/papers/glife/algorithm.html