Question about definition of Semi algebra

Solution 1:

Here is a counterexample showing that 1,2, and 3 do not prove 3'.

Let $X$ be the nodes of an infinite complete binary tree. Then for $x\in X$, let $L(x)$ denote all nodes in the left subtree from $x$, and similarly let $R(x)$ denote all nodes in the right subtree from $x$. Then let

$S = \{\{x\}| x\in X\} \cup \{\{x\}\cup L(x)| x\in X\} \cup \{\{x\}\cup R(x)| x\in X\} \cup \{\{\} \}$

In other words, S is comprised of all singletons, all singletons with their left subtrees, and all singletons with their right subtrees. One can check that this is a semi-algebra in the sense of 1,2,and 3. But we will never be able to write $X$ (the complement of the empty set) as a finite disjoint union of elements of $S$.

Solution 2:

My guess is that you cannot easily show this. Most good books I have seen, that use the concept of semi-algebra, take care to use your 1,2, and 3' - not 1,2, and 3 as its definition.

Answer 1 to your question is (as you have spotted yourself, I think) basically wrong: Alex has missed the fact that in his construction of the $B_i$ from the $A_i$, he is relying on complements being members of ${\cal S}$, which he is not entitled to do.

I don't know whether 3' can be deduced by 1,2, and 3. It's an interesting question. I suppose a disproof would be to exhibit a class of subsets of some set that satisfies 1, 2, and 3 but contains a member whose complement is not a disjoint union of members.

I would be interested if someone here could answer your conundrum one way or another.