Back to Course
Sets and Logic
Set Fundamentals and Notation
A set is a well-defined collection of distinct objects, called Elements, typically denoted by capital letters like $A$ or $B$.
$$x \in A, \quad x \notin A$$
Notation describing the membership status of an object relative to a set.
$\in$=Element of / Belongs to(none)
$\notin$=Not an element of(none)
$A$=Target set(none)
Distinctness: Elements within a set must be unique; repetitions do not change the set.
Well-Defined: There must be a clear criterion to determine if any object belongs to the set.
Cardinality: Represented as $|A|$, it denotes the number of unique elements in set $A$.
Set Operations and Venn Diagrams
Sets can be manipulated through Union, Intersection, and Relative Complement to form new collections. A Venn Diagram uses overlapping circles inside a rectangle to visualise these operations.
$$|A \cup B| = |A| + |B| - |A \cap B|$$
The Inclusion-Exclusion Principle calculates the size of the union by subtracting the double-counted intersection.
$|A \cup B|$=Cardinality of the union(count)
$|A \cap B|$=Cardinality of the intersection(count)
$|A|$=Size of set A(count)
Union (∪): Contains all elements present in either set A, set B, or both. Symbolically: $A \cup B = \{x \mid x \in A \lor x \in B\}$.
Intersection (∩): Contains only elements present in both set A and set B simultaneously. Symbolically: $A \cap B = \{x \mid x \in A \land x \in B\}$.
Disjoint Sets: Sets with an empty intersection ($A \cap B = \emptyset$). For disjoint sets, $|A \cup B| = |A| + |B|$ since there is no overlap to subtract.
Overlapping Sets: Sets whose intersection is non-empty but neither is a subset of the other.
The Complement of set $A$ (written $A'$ or $A^c$) is everything in the Universal Set $U$ that is not in $A$. The set difference $A - B$ removes elements of $B$ from $A$.
$$A' = U - A = \{x \mid x \in U \land x \notin A\}$$
The complement contains every element of the universal set that does not belong to A.
$A'$=Complement of A(none)
$U$=Universal set(none)
$A - B$=Elements in A but not in B (set difference)(none)
Complement Notation: $A'$, $A^c$, and $U - A$ all mean the same thing.
Set Difference: $A - B = \{x \mid x \in A \land x \notin B\}$. Note: $A - B \neq B - A$ in general.
Difference via Intersection: $A - B = A \cap B'$, which is equivalent by definition.
Properties of Union and Intersection
Set operations obey algebraic properties analogous to arithmetic, including commutative, associative, and distributive laws.
$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$
Union distributes over intersection, just as multiplication distributes over addition in algebra.
$\cup$=Union (analogous to addition)(none)
$\cap$=Intersection (analogous to multiplication)(none)
$B = \emptyset$
→Both sides reduce to $A$, since $A \cup \emptyset = A$ and $A \cap A = A$.
$A \subseteq B \subseteq C$
→LHS = $A \cup B = B$. RHS = $B \cap C = B$. Both give $B$.
Commutative: $A \cup B = B \cup A$ and $A \cap B = B \cap A$.
Associative: $A \cup (B \cup C) = (A \cup B) \cup C$ and $A \cap (B \cap C) = (A \cap B) \cap C$.
Distributive: Union distributes over intersection AND intersection distributes over union — both directions work for sets (unlike numbers where only × distributes over +).
Identity Elements: $A \cup \emptyset = A$ (empty set is identity for ∪) and $A \cap U = A$ (universal set is identity for ∩).
Idempotent Laws: $A \cup A = A$ and $A \cap A = A$.
Complement Laws: $A \cup A' = U$ and $A \cap A' = \emptyset$.
Absorption Laws: $A \cap (A \cup B) = A$ and $A \cup (A \cap B) = A$.
De Morgan's Laws connect complement with union and intersection, allowing you to 'break apart' complements of compound sets.
$$(A \cup B)' = A' \cap B', \quad (A \cap B)' = A' \cup B'$$
Complementing a union turns it into an intersection of complements, and vice versa. The complement 'flips' the operation.
$(A \cup B)'$=Everything NOT in A or B(none)
$A' \cap B'$=Elements outside A AND outside B(none)
Proof Strategy: Show each side is a subset of the other. If $x \in (A \cup B)'$, then $x \notin A \cup B$, so $x \notin A$ AND $x \notin B$, meaning $x \in A' \cap B'$.
Verification Shortcut: Pick concrete sets and compute both sides. If $U = \{1,...,10\}$, $A = \{1,2,3\}$, $B = \{2,3,4,5\}$: LHS $(A \cup B)' = \{6,7,8,9,10\}$, RHS $A' \cap B' = \{4,5,...,10\} \cap \{1,6,...,10\} = \{6,7,8,9,10\}$.
Mnemonic: 'Break the bar, change the sign' — the complement bar distributes but the operation flips.
Propositions and Logical Operators
Logic uses Conjunction (AND), Disjunction (OR), and Negation (NOT) to evaluate the truth of complex statements.
$$p \lor q, \quad p \land q, \quad \neg p$$
Standard symbolic representations for logical disjunction, conjunction, and negation.
$\land$=Conjunction (AND)(logic)
$\lor$=Disjunction (OR)(logic)
$\neg$=Negation (NOT)(logic)
Conjunction (∧): True ONLY when both components are True. With $n$ propositions, the conjunction has $2^n$ rows in its truth table.
Disjunction (∨): False ONLY when both components are False. This is inclusive OR (both true is still true).
Negation (¬): Flips the truth value. Double negation cancels: $\neg(\neg p) \equiv p$.
Truth Table: A systematic table listing all $2^n$ combinations of truth values for $n$ variables, used to evaluate compound propositions.
Tautology vs Contradiction: A tautology is always True (e.g., $p \lor \neg p$). A contradiction is always False (e.g., $p \land \neg p$). Every other formula is a contingency.
Conditional Logic and Quantifiers
A Conditional statement $p \to q$ asserts that if $p$ is true, then $q$ must also be true.
$$p \to q \equiv \neg q \to \neg p$$
The contrapositive of a conditional statement is logically equivalent to the original statement.
$\to$=Implication (If...then)(logic)
$\equiv$=Logical Equivalence(logic)
$\neg$=Negation(logic)
Only False Case: $p \to q$ is False ONLY when $p$ is True and $q$ is False. A false hypothesis makes the conditional automatically True (vacuous truth).
Contrapositive: $\neg q \to \neg p$ — logically equivalent to $p \to q$. Always valid for proofs.
Converse: $q \to p$ — NOT equivalent to $p \to q$.
Inverse: $\neg p \to \neg q$ — NOT equivalent to $p \to q$. The inverse is the contrapositive of the converse.
Material Equivalence: $p \to q \equiv \neg p \lor q$. This lets you convert any conditional into a disjunction.
A Biconditional $p \leftrightarrow q$ asserts that $p$ and $q$ have the same truth value — both true or both false.
$$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$$
The biconditional is true exactly when both the conditional and its converse hold simultaneously.
$\leftrightarrow$=If and only if (iff)(logic)
$p \to q$=Forward direction(logic)
$q \to p$=Backward direction (converse)(logic)
Truth Values: True when both are T or both are F. False when they differ — exactly 2 True rows out of 4.
Read As: 'p if and only if q', abbreviated 'p iff q'.
Inductive and Deductive Reasoning
Mathematical reasoning falls into two categories: induction (specific → general) and deduction (general → specific).
Inductive Reasoning: Drawing general conclusions from specific observations or patterns. Example: observing 2, 4, 6, 8, ... and concluding the pattern is $2n$.
Deductive Reasoning: Drawing specific conclusions from accepted general premises. Example: 'All men are mortal; Socrates is a man; therefore Socrates is mortal.'
Key Difference: Inductive conclusions are probable but not certain; deductive conclusions are guaranteed if the premises are true.
Aristotelian Logic: Every Proposition is either True or False with no third option — the foundation of all deductive reasoning in mathematics.
Truth Sets: Linking Sets and Logic
Every logical proposition $p(x)$ has a truth set — the set of all values making $p$ true — creating a direct bridge between set theory and logic.
Truth Set of $\neg p$: The complement $P'$, since $\neg p$ is true exactly where $p$ is false.
Truth Set of $p \lor q$: The union $P \cup Q$, since the disjunction is true when either is true.
Truth Set of $p \land q$: The intersection $P \cap Q$, since both must be true simultaneously.
Truth Set of $p \to q$: The set $P' \cup Q$, using the equivalence $p \to q \equiv \neg p \lor q$.
Power of the Link: Any set identity (like De Morgan's Law) can be proved via truth tables, and any logical equivalence can be expressed in set notation.