My Discrete Math book (Epp, 5th edition) has a list of properties of the union and intersection operations for sets. The first five properties listed are the commutative laws for union and intersection, the associative laws for union and intersection, the distributive laws for union and intersection, the identity laws (A union Empty = A and A intersect Universal = A), and the complement laws (the union of a set and its complement is the universal set, and the intersection of a set and its complement is empty). Later in the list, it also has the two De Morgan laws.
It then goes on to say that any set identity involving only unions, intersections, and complements can be proven algebraically using only those first five properties. Well, the De Morgan laws are both identities involving only unions, intersections, and complements, so that claim should include them. And of course, I can prove the De Morgan laws using an element argument. But I can’t seem to see how to do it algebraically, and all of the example algebraic proofs in the textbook just use the De Morgan laws without proving them.
Can it actually be done (and if so, how), or is the textbook mistaken on this claim?
Ok, I think this works. Let V be the universal set.
(A \cup B) \cup (\bar{A} \cap \bar{B}) = B \cup (A \cup (\bar{A} \cap \bar{B})) (comm.) = B \cup ((A \cup \bar{A}) \cap (A \cup \bar{B})) (dist.) = B \cup (V \cap (A \cup \bar{B}) (compl.) = B \cup (A \cup \bar{B}) (ident.) =(B \cup \bar{B}) \cup A (comm.) =V \cup A (compl.) =V (ident.)
By compl., since the union of the two sets in the first line is V, the second is the complement of the first, so \bar{(A \cup B)} = (\bar{A} \cap \bar{B})
That’s not enough, because you have to also prove that their intersection is empty. Though that proof would probably parallel the one you gave.
It also depends on using the definition of complement, which isn’t strictly speaking included in the book’s list of properties (they have that the union of a set and its complement is the universal set and their intersection is empty, but not that those two properties imply complementarity).
This appears to be the same argument, though a lot of the TeX seems to be broken.
Oh, sure, it’s just that sets are the context we’re working in right now (and the only Boolean algebra the students have seen so far-- this is only high school).
How can you have an axiom that refers to complementarity (and you list two) if the complement of a set is not previously defined. Either it is previously defined, or those two axioms would have to be taken as its definition I guess.
…And now that I’ve read the next section (on more general Boolean algebras, and the properties thereof), that is indeed the technique the book is using. So the author was just a little bit sloppy in the way she phrased the properties and what could be derived from them.