Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote -2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.