8
$\begingroup$

I am wondering if someone could help me with basic properties of semi algebra. We say that $S$ is a semi algebra of subsets of X if

  1. $\emptyset \in S$
  2. If $P_1$, $P_2 \in S$, then $P_1 \cap P_2 \in S$
  3. If $P \in S$, then $X \backslash P$ can be written as a finite union of sets from $S$.

But I am finding that sometimes it is defined using the following 3' instead of 3.

3'. If $P \in S$, then $X \backslash P$ can be written as a disjoint finite union of sets from $S$.

My question is are these definitions equivalent? If so can someone please show me how we can obtain 3' from the first three conditions?

Thank you.

  • 0
    This thread was confusing because a seemingly incorrect answer has been accepted. Other answers don't seem fully confident that their answers are correct. I would like a correct answer. I have therefore reposted this question here http://math.stackexchange.com/questions/1135203/question-about-the-definition-of-a-semialgebra Future readers or answers should look to this new thread if they find this one unhelpful. Hopefully this new thread can come to an accepted answer to this question that is correct this time.2015-02-06

2 Answers 2

6

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.

6

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$.