Question about definition of Semi algebra

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.

-
I am used to seeing semi-algebra defined with 2,3', without the first condition. – Braindead Jun 29 '13 at 0:51

Certainly $3'$ implies $3$ so we just need to show $3$ implies $3'$. You can write $X\backslash P$ as

$$X\backslash P=\cup_i^n A_i$$

Define $B_1=A_1$, $B_2=A_2\backslash A_1$, $B_3=A_3\backslash A_2\backslash A_1$... Note that for example, $B_2=A_2\cap(X\backslash A_1)$. Ive written it in this form to show its in your semi algebra, in particular complements of sets are defined through taking them away from the whole space and writing them as a union of finite sets. Then

$$X\backslash P=\cup_i^n B_i,$$

where the $B_i$ are disjoint. This a common trick to get disjoint unions from nondisjoint unions.

-
Are you saying that, since the $A_i$'s are in $S$, so are the $B_i$'s? That seems to be needed to complete this argument, but I don't immediately see why it should be true. – Andreas Blass Dec 12 '12 at 0:20
@AndreasBlass: I've added some clarification. Thanks for your point. – Alex R. Dec 12 '12 at 1:14
Hi, I am just having trouble understanding why $B_2$ has to be in the semi algebra... Could you possibly explain it a bit more? – J Kasahara Dec 12 '12 at 17:30
@JKasahara: Take a look here for further detail: books.google.com/… – Alex R. Dec 12 '12 at 21:24
@Alex: I did the "accept the answer" because I'm sure your answer is correct. Thank you for the reference. I looked but I am still confused about one thing.. As you say we can write $X \backslash A_1$ as a finite union of sets in the semialgebra $S$, but $S$ is not closed under finite unions so I just can't see how intersecting it with $A_2 \in S$ gets us a set in $S$. Are we assuming extra condition here by any chance? I would greatly appreciate if you could possibly explain this minor detail. Thank you very much. – J Kasahara Dec 13 '12 at 16:14

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.

-

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

-