> See also: > - [[Fundamentals of Logic]] # Set Theory A **set** is simply a list of objects, known as **elements**, An **element** is that could be in a set A set is always a subset of itself ## Logical Quantifiers $\forall$ = "For All" $\exists$ = "There exists (at least one)" Rules of Inference for Quantified Statements ![[Pasted image 20230129210623.png|400]] ## Set Symbols | Symbol | Translation | |:---:| --- | | $\in$ | Is an element of/belongs to | | $\subseteq$ | Is a subset of | | $\subset$ | Is a proper subset of (subset but not equal) | | $\emptyset$ | Empty set | The elements ## Set Operators | Symbol | Name | Definition | Translation | |:---:| --- | --- | --- | | $\cap$ | Intersection | $x \in A \land x \in B$ | Is in both $A$ AND $B$ | | $\cup$ | Union | $x \in A \lor x \in B$ | Is in $A$ OR $B$ | | $\bar A$ | Complement | $x \notin A$ | Is not in $A$ | | $A - B$ | Difference | $x \in A \land x \notin B$ | Is in $A$ but not $B$ | - Set Difference = Relative Complement symmetric difference ($\oplus$): every element that belongs to exactly one of two given sets - $B - A = B \cap \neg A$ ## Set Equality 1. Table Method 2. Set Laws 0 = an arbitrary element not within the set 1 = an arbitrary element within the set ## Laws of Set Theory - **Law of Double Negation** - $\neg \neg A = A$ - **DeMorgan's Law** - $\overline{A \cup B} = \bar A \cap \bar B$ - $\overline{A \cap B} = \bar A \cup \bar B$ - **Commutative Laws** - $A \cup B = B \cup A$ - $A \cap B = B \cap A$ - **Associative Laws** - $A \cup (B \cup C) = (A \cup B) \cup C$ - $A \cap (B \cap C) = (A \cap B) \cap C$ - **Distributive Laws** - $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ - $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ - **Idempotent Law** - $A \cup A = A$ - $A \cap A = A$ - **Inverse Laws** - $A \cup \bar A = U$ - $A \cap \bar A = \emptyset$ - **Identity Laws** - $A \cup \emptyset = A$ - $A \cap U = A$ - **Domination Laws** - $A \cup U = U$ - $A \cap \emptyset = \emptyset$ - **Absorption Laws** - $A \cup (A \cap B) = A$ - $A \cap (A \cup B) = A$ ## Proofs Using the double-subset property, if you can prove that two different sides (LHS & RHS) of an equation are subsets of eachother,