# Does this hierarchy of intersection and union collapse?

by Agnishom Chattopadhyay   Last Updated October 20, 2019 05:20 AM - source

Suppose that $$F_0$$ is the collection of all the finite sets of $$\mathbb{N}$$ and $$G_0$$ is the collection of all the co-finite sets of $$\mathbb{N}$$.

Define $$F_{i+1}$$ to be $$\{f \cup g \mid f \in F_i, g \in G_i\}$$ and $$G_{i+1}$$ to be $$\{f \cap g \mid f \in F_i, g \in G_i\}$$ for all $$i \in \mathbb{N}$$.

Does there exist $$i$$ such that $$F_i = G_i = F_{i+1} = G_{i+1} = \cdots$$?

With some elementary calculations, the answer appears to be not. However, the calculations seem to get messy very soon.

My interest in this problem is to find an efficient data structure for subsets of an infinite domain (possibly $$\mathbb{N}$$) expresssed in terms of boolean combinations of finite sets.

Tags :