## Exercise statement

Prove Proposition 3.1.28.

**Proposition 3.1.28** (Sets form a boolean algebra)**.** Let be sets, and let be a set containing as subsets.

(a) (Minimal element) We have and .

(b) (Maximal element) We have and .

(c) (Identity) We have and .

(d) (Commutativity) We have and .

(e) (Associativity) We have and .

(f) (Distributivity) We have and .

(g) (Partition) We have and .

(h) (De Morgan laws) We have and .

## Hints

- One can use some of these claims to prove others.
- Some of the claims have also appeared previously in Lemma 3.1.13.

## How to think about the exercise

The strategy for most of the parts of this exercise is to show that both and , from which we can conclude . (Just to be clear, the here are not the same as the in the exercise itself.) To show that , we suppose that , and then show that . You might be nervous about this maneuver, since we didn’t check that is non-empty. By single choice (Lemma 3.1.6) we can only say that when is non-empty, right? What is going on, and does this make all of our proofs invalid? Might we need to redo all of our proofs to split into cases depending on whether each set is empty or non-empty? It turns out that all of the proofs we do here are correct as stated, without having to consider empty sets separately. But we do need to be careful; indeed, I believe Exercise 3.5.6 is designed to demonstrate why we must be careful.

So why are all of the proofs here fine as stated? To show that , we must show that for all objects , if then . So we let be an arbitrary object, and we *suppose* that , in order to show . We aren’t claiming that an arbitrary object is contained in , and we aren’t even claiming that is non-empty. We are just saying to assume this as a hypothesis, in order to demonstrate an implication. This is the same as trying to show an implication and supposing that is true. If is empty, the proof is still valid since the implication is vacuous in this case.

If you are suspicious of some of the proofs here (e.g. the De Morgan laws) because they seem to rely on verbal trickery, you are right. We can’t do any better without going into the details of first-order logic, and even then it won’t be completely satisfying because a mind must already contain certain rules in order to do any mathematics at all; see here for a longer explanation.

I’m not entirely sure what Tao meant by “One can use some of these claims to prove others”; I can’t see a way to apply any of the parts to some other part in a way that saves a lot of time.

This exercise is pretty long and tedious, and it can become pretty tempting to quickly rush through it. If you don’t want to do the whole thing, and instead want to pick a couple of parts and do those carefully, then I would recommend doing parts (f) and/or (h).

The distributivity law, part (f), is probably the most interesting one to prove. My recommendation is to *not* appeal to the fact that logical “or” and logical “and” distribute over each other, as that fact has not been covered in the text. If you prefer, you could first show that logical “or” and logical “and” distribute over each other, after which proving distributivity for set operations becomes easy. The important point is that you show distributivity in one way or another “from first principles” rather than just assuming it.

## Model solution

(a) We have by Lemma 3.1.13. Thus we only have to show . There cannot be any object , because if there were such an object, we would have and , which contradicts the fact that contains no elements. Thus is empty, which means by the uniqueness of the empty set. (See the text following Axiom 3.2 for the uniqueness of the empty set.)

(One can also use Exercise 3.1.5 and the commutativity of the intersection operation for this part; part (d) can be proved without using part (a), so there is no circularity.)

(b) We first show . If , then or . If , then since is subset of we have as required. If , then we are already done. In either case we have , so this shows that . Now suppose conversely that . We must show that or ; but the latter statement is true, so , which means that .

Next we show that . Suppose first that . Then and , so in particular . Conversely, suppose . Then since is a subset of , we have . Thus we have both and , which means as required.

(One can also use Exercise 3.1.5 for this part, but I am doing the exercises out of order and I still haven’t done that one.)

(c) We have by Lemma 3.1.13. Thus we only have to show that . Suppose . Then and , so in particular . This shows that . Now suppose . Then and , so . This shows that . Combining these two parts, we have as required.

(One can also use Exercise 3.1.5 for this part, but I am doing the exercises out of order and I still haven’t done that one.)

(Since , we can also take and apply part (b).)

(d) We showed that the union operation is commutative in Lemma 3.1.13, so we only have to show that . Suppose . Then and . We can reorder logical “and” statements, so we have and , which means as required. The converse is proved in the same way, just switching the roles of and . Thus as required.

(e) The union operation is associative by Lemma 3.1.13, so we only have to show that . Suppose . This means that and . To say that means to say that and . Since and , this means . Since we also know that , we thus have . The converse is proved in the same way. Thus as required.

(f) We first show that . Suppose . This means that and . Since , this means that or , so now we have two cases. If , then since we already know that , we have . Thus we have or (since the first statement is true), so . Alternatively if , then we already know so . Thus we have or (since the second statement is true), which means that . In either case we have shown that , so this proves that . Conversely suppose that . This means that either or . In the former case, we have and . Since , we have or , which means . Thus we have both and , which means . Similarly in the latter case where , we can show that . In either case we have , so as required.

Next we show that . Suppose that . Thus we have or . If , then or (since the first statement is true), so . We also have or (since again the first statement is true), so . Thus we have and , so . On the other hand, if , then we have both and . Thus we have or (since the second statement is true), so . Similarly, we have or (since again the second statement is true), so . We thus have both and , so as required. In both cases, we have , so this shows that . Conversely suppose . Then we have both and . Now we have two cases, or . If , then or (since the first statement is true), so . On the other hand, if , then since we have or , and since the first option is impossible we conclude that . Similarly we have since and . Thus in this case , so we have or (since the second statement is true), which means . In either case we have shown that , so this shows that .

(g) We first show that . Suppose . Then or , so we have two cases. If , then since is a subset of . On the other hand, if , then we have and , so in particular . In either case we have , so . Conversely suppose that . We have two cases, either or . If then or (since the first statement is true), so as required. If , then since this means . Thus or (since the second statement is true), so . In either case we have , so .

Next we show that . To do this, we shall show that is empty; since the empty set is unique this will be sufficient. We want to show that there is no object such that . Suppose for sake of contradiction that such an object exists. Then we have and . The latter statement means and . Thus we have both and , a contradiction.

(h) First we show that . Suppose . This means and . The latter statement means that it is *not* the case that or ; thus and . But now we have and , which means , and we also have both and , so . Thus we have as required. Conversely, suppose . Thus we have both and . The first of these decomposes to and , and the second decomposes to and . To say that and is to say that is not in either of these sets, so . Since we also know , this means .

Next we show that . Suppose first that . This means and . The latter statement means that is not in both of the sets and , so it is either not in or not in , i.e. or . We now have two cases. If then since we already know , we have . Thus or (since the first statement is true), which means . On the other hand, if then we similarly have . Thus . Conversely suppose . Then we have either or . In the first case, we have both and . If then we would have , a contradiction, so we must have . Thus we have and , which means . In the second case, we can similarly show that . In either case we have so .