next up previous
Next: Proving Functions One-to-One Up: NOTES ON BASIC PROOFS Previous: Proving Set Inclusion

Proving Sets Equal

In order to prove two sets are equal, there are two methods commonly used. The first is to show that each set is a subset of the other. That is, if tex2html_wrap_inline154 and tex2html_wrap_inline156 then A=B. The methods of the previous section apply here.   The second method is to use an algebraic approach based on Boolean Algebra. If in doubt as to which method to use, the rule of thumb is to prove each set a subset of the other. The Boolean algebra method requires knowing the axioms and elementary results. To illustrate this method, consider how to prove one of De Morgan's laws tex2html_wrap_inline160 . It relies on the following result namely "If tex2html_wrap_inline162 and tex2html_wrap_inline164 where U is the universal set, then tex2html_wrap_inline168 ". You may wish to try and prove this result from the axioms of Boolean algebra. We also make use of the more obvious results " tex2html_wrap_inline170 " and " tex2html_wrap_inline172 ". Anyway, let's continue with establishing De Morgan's law.

tabular33

This establishes the first part of what we need to prove. To complete the proof we look at the intersection of the sets.

tabular36



Peter Williams
Wed Aug 21 23:10:39 PDT 1996