is created by David Witten, a mathematics and computer science student at Vanderbilt University. For more information, see the "About" page.

Set Identities


In this article, we’ll be going through some identities involving sets

Basic Properties

$$A \cup A^C = U$$ $$A \cap A^C = \emptyset$$ $$A \cap U = A$$ $$A \cup \emptyset = A$$

Distributive Property

$$A \cup (B \cap C) = (A\cup B) \cap (A \cup C)$$ $$A \cap (B \cup C) = (A\cap B) \cup (A \cap C)$$ $$A \cap (A \cup B) = (A\cap A) \cup (A \cap B) = A \cup (A \cap B) = A$$ $$A \cup (A \cap B) = (A\cup A) \cap (A \cup B) = A \cap (A \cup B) = A \text{ (by the latest property)}$$

Example Proof

Prove this: $|A| = |A \cap B| + |A \cap B^c|$ $$A = A \cap U$$ $$ = A \cap (B \cup B^c)$$ $$ = (A \cap B) \cup (A \cap B^c)$$ $$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$ $$|A| = |A \cap B| + |A \cap B^c| - (A \cap B) \cap (A \cap B^c)$$ $$|A| = |A \cap B| + |A \cap B^c| - |(A \cap A) \cap (B \cap B^c)|$$ $$|A| = |A \cap B| + |A \cap B^c|$$

Probability Rules with Sets

Here are the basic definitions: $$p(\text{A or B}) = p(A \cup B)$$ $$p(\text{A and B}) = p(A \cap B)$$ What this ends up being is $$p(A \cup B) = p(A) + p(B) - p(A \cap B)$$ If you do just $p(A) + p(B)$ then you overcount the areas they intersect. In fact, we can expand this to an arbitrary number of unions. $$p(A \cup B \cup C) = p(A) + p(B) + p(C) \\ - P(A \cap B) - p(A \cap C) - p(B \cap C)\\ + p(A \cap B \cap C)$$ This presents another problem. If we just added up the singular probabilities and subtracted all of the two-set intersections, we would subtract the overall intersection one too many times.

This is something called the principle of inclusion-exclusion. If you extend it to n-unions. You just add the single, subtract the 2's, add the 3's, subtract the 4's, ...

$$p(\text{A and B}) = P(A \cap B) = p(A)p(B|A) = p(B)p(A|B)$$


Complements initially seem annoying to work with, but given these three properties, we can solve every problem. $$p(A^c) = 1 - p(A)$$ $$(A \cup B)^c = A^c \cap B^c$$ $$(A \cap B)^c = A^c \cup B^c$$

Example Problem

If A and B are independent, prove A and $B^c$ are independent. Also prove these are independent: $\\$ $A^c$ and $B^c$ $\\$ $A^c$ and B
This is what independent means: $P(A \cap B) = P(A)P(B)$ $$P(A^c \cap B^c) = 1 - P(A \cup B)$$ $$ = 1 - (P(A) + P(B) - P(A \cap B))$$ $$ = 1 - (P(A) + P(B) - P(A)P(B))$$ $$ = 1 - P(A) - P(B) + P(A)P(B)$$ $$ = (1 - P(A))(1- P(B))$$ $$ = P(A^c)P(B^c)$$

Moment Generating Function

Is a coin fair?