Does this hierarchy of intersection and union collapse?

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

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.



Related Questions


Updated August 07, 2015 15:08 PM

Updated February 21, 2017 03:20 AM

Updated March 26, 2018 10:20 AM

Updated June 12, 2017 00:20 AM