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

Set Identities

Introduction

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

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?