Set Theory & Mathematical Logic: Symbols, Truth Tables, and Venn Relations
Explore formal mathematical logic and set theory notation. Detailed explanations of quantifiers, set relations, logical connectives, and truth tables with examples.
Mathematical logic and set theory form the bedrock of modern mathematics, theoretical computer science, database query architecture, and software verification. Every algorithm, SQL query, digital logic gate, and mathematical proof relies on the strict semantic rules formalized by George Boole, Georg Cantor, Gottlob Frege, and Bertrand Russell.
Whether you are taking an introductory discrete mathematics course, learning formal software engineering methods, or preparing mathematical proofs, this guide provides a complete, structured overview of all logical connectives, truth tables, quantifiers, and set-theoretic operations.
1. Foundations of Propositional Logic
A proposition is a declarative mathematical statement that is unequivocally either True ($T$ or 1) or False ($F$ or 0), but never both simultaneously. For example:
- "7 is a prime number." → Proposition (True)
- "$\pi$ is an integer." → Proposition (False)
- "$x + 2 = 5$." → Not a proposition (its truth depends on the value of $x$; this is a predicate).
In propositional logic, simple atomic propositions (represented by letters like $P, Q, R$) are combined using logical connectives to build complex truth expressions.
2. Core Connectives & Operators
| Operator | Name | Symbol | LaTeX Code | English Meaning |
|---|---|---|---|---|
| Negation | NOT | $\neg$ or $\sim$ | \neg | "It is not the case that $P$" |
| Conjunction | AND | $\wedge$ | \wedge or \land | "Both $P$ and $Q$ are true" |
| Disjunction | OR (Inclusive) | $\vee$ | \vee or \lor | "At least one of $P$ or $Q$ is true" |
| Exclusive OR | XOR | $\oplus$ | \oplus | "Either $P$ or $Q$ is true, but NOT both" |
| Conditional | IMPLIES | $\implies$ or $\to$ | \implies or \to | "If $P$, then $Q$" |
| Biconditional | IFF | $\iff$ or $\leftrightarrow$ | \iff | "$P$ if and only if $Q$" (equivalent truth values) |
3. Master Truth Tables for Composite Statements
A truth table enumerates all possible combinations of truth values for input propositions alongside the resulting truth value of the compound statement. Below is the master truth table for two propositions $P$ and $Q$:
| $P$ | $Q$ | $\neg P$ | $P \wedge Q$ (AND) | $P \vee Q$ (OR) | $P \oplus Q$ (XOR) | $P \implies Q$ (Conditional) | $P \iff Q$ (Biconditional) |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T |
| T | F | F | F | T | T | F | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | F | T | T |
4. Quantifiers: Universal (∀) vs Existential (∃)
When working with variables over a domain (universe of discourse), quantifiers specify for how many elements in the domain a predicate $P(x)$ holds true:
- Universal Quantifier ($\forall$): "For all", "for every", or "for each".
\forall x \in \mathbb{R}, \; x^2 \ge 0— For every real number $x$, $x^2$ is greater than or equal to 0 (True). - Existential Quantifier ($\exists$): "There exists", "there is at least one", or "for some".
\exists x \in \mathbb{Z}, \; x^2 = 25— There exists an integer $x$ whose square is 25 (True, e.g., $x = 5$ or $x = -5$). - Uniqueness Quantifier ($\exists!$): "There exists a unique" or "there is exactly one".
\exists! x \in \mathbb{R}, \; 2x + 4 = 10— Exactly one real number satisfies the linear equation (True, $x = 3$).
5. Set Relations: Membership, Subsets & the Empty Set
A set is an unordered collection of distinct mathematical objects.
| Symbol | Name | LaTeX Code | Formal Definition / Example |
|---|---|---|---|
| $\in$ / $\notin$ | Element of / Not element of | \in / \notin | $3 \in \mathbb{N}$ (3 is an element of the natural numbers) |
| $\subseteq$ | Subset of | \subseteq | $A \subseteq B \iff \forall x (x \in A \implies x \in B)$ |
| $\subset$ or $\subsetneq$ | Proper subset | \subset or \subsetneq | $A \subseteq B$ and $A \neq B$ |
| $\emptyset$ or $\varnothing$ | Empty set | \emptyset or \varnothing | $\{\}$, the unique set containing zero elements; $\emptyset \subseteq A$ for all sets $A$ |
| $|A|$ or $\#A$ | Cardinality | |A| | Number of distinct elements in set $A$ |
| $\mathcal{P}(A)$ | Power Set | \mathcal{P}(A) | Set of all subsets of $A$. If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$. |
6. Set Operations: Union, Intersection, Difference & Complement
Just as arithmetic has addition and multiplication, set theory has fundamental binary operations that correspond directly to logical connectives:
- Union ($A \cup B$): The set of elements belonging to $A$, $B$, or both.
Formal: $A \cup B = \{ x \mid x \in A \vee x \in B \}$. - Intersection ($A \cap B$): The set of elements belonging to both $A$ and $B$. If $A \cap B = \emptyset$, $A$ and $B$ are disjoint.
Formal: $A \cap B = \{ x \mid x \in A \wedge x \in B \}$. - Set Difference ($A \setminus B$ or $A - B$): The relative complement of $B$ in $A$. Contains elements in $A$ that are not in $B$.
Formal: $A \setminus B = \{ x \mid x \in A \wedge x \notin B \}$. - Absolute Complement ($A^c$ or $\bar{A}$): All elements in universal set $\mathcal{U}$ not in $A$.
Formal: $A^c = \mathcal{U} \setminus A = \{ x \in \mathcal{U} \mid x \notin A \}$. - Cartesian Product ($A \times B$): Set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$.
7. De Morgan's Laws & Duality Principles
Formulated by British mathematician Augustus De Morgan, these laws describe how negation distributes across conjunctions and disjunctions, and how complements distribute across unions and intersections:
De Morgan's Laws in Propositional Logic
\neg (P \wedge Q) \iff (\neg P \vee \neg Q)
\neg (P \vee Q) \iff (\neg P \wedge \neg Q)De Morgan's Laws in Set Theory
(A \cap B)^c = A^c \cup B^c
(A \cup B)^c = A^c \cap B^c8. Master Discrete Math & Set Theory Symbol Table
| Glyph | Unicode | LaTeX Code | Meaning / Usage |
|---|---|---|---|
| $\forall$ | U+2200 | \forall | Universal quantifier ("for all") |
| $\exists$ | U+2203 | \exists | Existential quantifier ("there exists") |
| $\nexists$ | U+2204 | \nexists | There does not exist |
| $\in$ | U+2208 | \in | Element of |
| $\notin$ | U+2209 | \notin | Not an element of |
| $\subseteq$ | U+2286 | \subseteq | Subset of or equal to |
| $\subsetneq$ | U+228A | \subsetneq | Strict proper subset |
| $\cup$ | U+222A | \cup | Set union |
| $\cap$ | U+2229 | \cap | Set intersection |
| $\emptyset$ | U+2205 | \emptyset | Empty set |
| $\implies$ | U+21D2 | \implies | Logical material implication |
| $\iff$ | U+21D4 | \iff | Logical equivalence / biconditional |
| $\therefore$ | U+2234 | \therefore | Therefore (proof conclusion) |
| $\because$ | U+2235 | \because | Because / since |
| $\blacksquare$ | U+220E | \blacksquare or \qed | Halmos tombstone / Q.E.D. (End of proof) |
Copy Discrete Math Symbols Instantly
Drafting assignments in logic, graph theory, or automata? Use our online Symbols Keyboard to copy quantifiers, arrows, and set brackets directly into Overleaf, Notion, Google Docs, or your code editor without hassle.
Frequently Asked Questions
What is the difference between subset (⊆) and proper subset (⊂)?
If set A is a subset of set B (A ⊆ B), every element in A belongs to B, but A and B may be identical. If A is a proper subset of B (A ⊂ B or A ⊊ B), every element in A belongs to B, AND B contains at least one element that is not in A (meaning A cannot equal B).
Why is an implication (P ⟹ Q) considered True when P is False?
In formal classical logic, an implication represents a promise or conditional guarantee: 'If P happens, then Q must happen.' If P does not occur, the promise has not been broken, regardless of whether Q happens or not. This is known in logic as 'vacuous truth'.
What is the difference between ∈ and ⊆?
The symbol ∈ (element of) relates an individual member or object to a set (e.g., 3 ∈ {1, 2, 3}). The symbol ⊆ (subset of) relates two sets together (e.g., {3} ⊆ {1, 2, 3}). Putting a raw element on the left side of ⊆ or a set on the left of ∈ (unless dealing with sets of sets) is a fundamental type error.
How do you negate a statement with quantifiers like ∀x P(x)?
By the duality of quantifiers, negating 'For all x, P(x) is true' gives 'There exists at least one x such that P(x) is false': ¬(∀x P(x)) ⟺ ∃x (¬P(x)). Similarly, ¬(∃x P(x)) ⟺ ∀x (¬P(x)).