Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Became Hot Network Question
Source Link

Distinguishing finite families of sets by algebras of bounded size

Say that an algebra of sets $K$ distinguishes set $B$ from set $C$ provided that for some $A\in K$, we have exactly one of $A\cap B$ and $A\cap C$ non-empty. Given families $F$ and $G$ of sets, say that $K$ distinguishes $F$ from $G$ provided that it distinguishes every member of $F$ from every member of $G$.

Question 1: Is there a fixed finite $N$ such that for any finite families $G$ and $H$ of finite sets with $G\cap H=\varnothing$, there is an algebra $K$ of sets with $|K|\le N$ that distinguishes $G$ from $H$?

Question 2: If the answer is negative, is it still negative if we constrain $G$ and $H$ by requiring that all the members of $G\cup H$ have the same cardinality?

I would guess the answer to both is negative, but don't know how to prove it or find a reference. (This came up as part of something in finite model theory.)