Here's a list of some simple theorems of set theory. Mainly they are here for easy proof practice - try some! Some might also be HW proofs or examples from the text or lectures. Also, I may quote a few of them while working thru Ch 3, but we won't use them much after that. You don't have to memorize them.
Suppose A, B and C are sets and U is the universal set. Let A' be the complement, U \ A. Then - -
| Theorem | Remarks |
| Æ Í A | Prove "p is false". |
| A Í U | Prove "q is true". |
| A Ç U = A | Prove "Í both ways" (or...) |
| (A Í B Ù B Í C) ® A Í C | Use a tautology with p,q,r |
| A Í B ® B' Í A' | Use a tautology (contrapostive) |
| (A Ç B)' = A' È B' | Use a tautology (DeMorgan) |
| (A È B)' = A' Ç B' | Use a tautology (DeMorgan) |
| A Ç B = A « A Í B | Prove "Í both ways" |
| A Ç B Í A | Easy p®q proof |
| A Í A È B | Easy p®q proof |
| A \ B = A Ç B' | Use definitions |
Most of these are too easy to make good exam questions, but they are good for getting started. You are welcome to bring your answers to me for feedback, ideally during office hours so that we can discuss them. You might see one of these or something a little harder on Exam 1.
Written by S.Hudson, 9/03