My knowledge of Sets is not be best so bare with me and I will appreciate corrections to any mistakes noticed :).

I was thinking through an algorithm to check the validity of a kind of set.


Given the sets $A_1$, $A_2$, $A_3$, $A_4$, $A_5$,

And a $Set A$ such that $A = \{A_1, A_2, A_3, A_4, A_5\}$

I consider an arbitrarily provided set $S_{input}$ (input to the algorithm) to be valid if for every set that is an element of $A$ (call it $A_i$), the intersection of $S_{input}$ and $A_i$ is not empty. That is: $A_i \cap S_{input} \neq \emptyset$ .

In other words:

In my algorithm an arbitrarily provided set $S_{input}$ is considered to be a valid set ($S_{valid}$), if and only if $S_{input}$ is a set such that $\forall A_i \in A; A_i \cap S_{input} \neq \emptyset$ where $A$ is a previously known set of sets.

Some examples:

If $A = \{ \ \{1,2,3,4\},\ \{1,2\},\ \{3\}, \ \{1, 4\}, \ \{1,2,3,4,5,6\} \ \}$

  1. $S_{input} = \{1,2,3\}$ is Considered a valid set $S_{valid}$ because for every set $A_i$ in $A$, you get the following results:

    • $\{1,2,3,4\} \cap \{1,2,3\} = \{1,2,3\} \neq \emptyset$
    • $\{1,2 \} \cap \{1,2,3\} = \{1,2\} \neq \emptyset$
    • $\{3\} \cap \{1,2,3\} = \{3\} \neq \emptyset$
    • $\{1,4\} \cap \{1,2,3\} = \{1\} \neq \emptyset$
    • $\{1,2,3,4,5,6\} \cap \{1,2,3\} = \{1,2,3\} \neq \emptyset$
  2. $S_{input} = \{1,2,4\}$ is Considered an invalid set because for every set $A_i$ in $A$, you get the following results:

    • $\{1,2,3,4\} \cap \{1,2,4\} = \{1,2,4\} \neq \emptyset$
    • $\{1,2 \} \cap \{1,2,4\} = \{1,2\} \neq \emptyset$
    • $\{3\} \cap \{1,2,4\} = \{\} = \emptyset$
    • $\{1,4\} \cap \{1,2,4\} = \{1, 4\} \neq \emptyset$
    • $\{1,2,3,4,5,6\} \cap \{1,2,4\} = \{1,2,4\} \neq \emptyset$

    Since the third set ($\{3\}$) results in an empty set when intersected with $S_{input}$, $S_{input}$ is not valid.

My questions:

  1. Is this a known type of set operation? Basically is there a name for such a set $S_{valid}$ (based on my definition above) that I don't know of? (by this definition there should be may such sets $S_{valid}$ for any given $A$)

  2. Will there exist a set (call it $A_u$) such that for a given set $S_{input}$, if all the elements of $S_{input}$ are also members of $A_u$ then $S_{input}$ can be considered to be a valid set ($S_{valid}$) based on my above conditions? In other words, does there exist $A_u$ such that if $\forall e \in S_{input}, e \in A_u$ then $S_{input}$ is considered a valid set $S_{valid}$ ?

  3. Any efficient suggestions (preferable pseudocode) on a routine to check if a given set $S_{input}$ is a valid set $S_{valid}$?

  4. Any suggestions on (preferably pseudocode) on a routine to generate a set $A_u$ described in question 2?


1 Answer 1

  1. The closest term might be "pairwise non-disjoint", but that's a stretch. This problem reminds me a bit of the sunflower lemma, but almost reversed: a set $W$ is called a sunflower if no matter which $w,v\in W$ we choose, $w\cap v$ is always the same set, called the "kernel" of $W$. For the sunflower problem, it doesn't matter if the sets $w\cap v$ are empty, as long as they are equal for any choice of $w,v$. In your problem, it doesn't matter if the sets $w\cap S_{input}$ are unequal, as long as they aren't empty for any choice of $w$.
  2. No. Assume there was such a set $A_u$. Then if we set $A=\{A_u,\{A_u\}\}$, $S_{input}=\{A_u,\{A_u\}\}$ is a counterexample, in particular $A_u\cap\{A_u\}$ is empty by the axiom of regularity.
  3. It's not really possible to compute because if $A$ is infinite, there will be infinitely many intersections to check. You can think of it as a "foreach" instruction, where "$S_{input}$ is valid" is the Boolean and applied to all statements "$A_i\cap S_{input}\neq\varnothing$" for $A_i\in A$
  4. By #2 there is no such set.

You must log in to answer this question.

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