Set Theory and Logic Notation — Mathematical Foundations

Introduction

Set theory and logic form the foundation of mathematics and computer science. From database queries to type systems, from algorithm correctness proofs to formal verification, these concepts appear throughout technical documentation.

This guide covers the essential notation for sets, set operations, propositional logic, predicate logic, and proof structures. You'll learn how to express these concepts clearly using KaTeX in your technical documentation.

Prerequisites

This guide assumes familiarity with basic KaTeX syntax. If you're new to KaTeX, start with our KaTeX Syntax Quick Reference first.

Set Notation Basics

Sets are collections of distinct objects. Understanding set notation is essential for documenting data structures, type systems, and mathematical specifications.

Defining Sets

Set Definition Notation

Different ways to define and describe sets

Roster notation (listing elements):

A = \{1, 2, 3, 4, 5\}

Set-builder notation (defining by property):

B = \{x \in \mathbb{Z} : x > 0\}

Alternative set-builder with vertical bar:

C = \{x \mid x^2 < 10\}

Interval notation:

[a, b] = \{x \in \mathbb{R} : a \leq x \leq b\}

(a, b) = \{x \in \mathbb{R} : a < x < b\}

Special Sets

Standard Number Sets

Common mathematical sets with blackboard bold notation

Number sets:

Natural numbers: $\mathbb{N} = \{1, 2, 3, \ldots\}$
Integers: $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$
Rationals: $\mathbb{Q} = \{\frac{p}{q} : p, q \in \mathbb{Z}, q \neq 0\}$
Real numbers: $\mathbb{R}$
Complex numbers: $\mathbb{C}$

Special sets:

Empty set: $\emptyset$ or $\{\}$
Universal set: $U$ or $\mathcal{U}$
Power set: $\mathcal{P}(A)$ or $2^A$

Positive/negative variants:

\mathbb{Z}^+ = \{1, 2, 3, \ldots\}, \quad \mathbb{R}^- = \{x \in \mathbb{R} : x < 0\}

Set Membership and Relations

Membership and Subset Relations

Expressing element membership and set relationships

Element membership:

$x \in A$ — $x$ is an element of $A$
$x \notin A$ — $x$ is not an element of $A$

Subset relations:

$A \subset B$ — $A$ is a proper subset of $B$
$A \subseteq B$ — $A$ is a subset of $B$ (possibly equal)
$A \supset B$ — $A$ is a proper superset of $B$
$A \supseteq B$ — $A$ is a superset of $B$
$A \not\subset B$ — $A$ is not a subset of $B$

Set equality:

A = B \iff (A \subseteq B) \land (B \subseteq A)

Set Operations

Set operations are fundamental to database queries, type systems, and algorithm design. These operations combine or modify sets to create new sets.

Basic Operations

Union, Intersection, and Difference

Core set operations

Union (elements in either set):

A \cup B = \{x : x \in A \lor x \in B\}

Intersection (elements in both sets):

A \cap B = \{x : x \in A \land x \in B\}

Set difference (elements in $A$ but not $B$ ):

A \setminus B = \{x : x \in A \land x \notin B\}

Alternative notation: $A - B$

Symmetric difference (elements in exactly one set):

A \triangle B = (A \setminus B) \cup (B \setminus A)

Alternative: $A \oplus B$

Complement and Power Set

Complement relative to universal set and power sets

Complement (elements not in $A$ ):

A^c = \overline{A} = U \setminus A = \{x \in U : x \notin A\}

Power set (set of all subsets):

\mathcal{P}(A) = \{S : S \subseteq A\}

Example:

\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}

Cardinality of power set:

|\mathcal{P}(A)| = 2^{|A|}

Cartesian Product

Ordered pairs from two sets

Cartesian product:

A \times B = \{(a, b) : a \in A \land b \in B\}

Example:

\{1, 2\} \times \{a, b\} = \{(1, a), (1, b), (2, a), (2, b)\}

n-fold Cartesian product:

A^n = A \times A \times \cdots \times A \quad (n \text{ times})

Cardinality:

|A \times B| = |A| \cdot |B|

Indexed Operations

Indexed Unions and Intersections

Operations over families of sets

Indexed union:

\bigcup_{i=1}^{n} A_i = A_1 \cup A_2 \cup \cdots \cup A_n

\bigcup_{i \in I} A_i = \{x : \exists i \in I, x \in A_i\}

Indexed intersection:

\bigcap_{i=1}^{n} A_i = A_1 \cap A_2 \cap \cdots \cap A_n

\bigcap_{i \in I} A_i = \{x : \forall i \in I, x \in A_i\}

Disjoint union:

\bigsqcup_{i \in I} A_i

Propositional Logic

Propositional logic deals with statements that are either true or false. It's the foundation for boolean algebra, circuit design, and programming conditionals.

Logical Connectives

Basic Logical Operators

Connectives for combining propositions

Negation (NOT):

\neg P, \quad \lnot P, \quad \sim P, \quad \overline{P}

Conjunction (AND):

P \land Q, \quad P \cdot Q, \quad P \& Q

Disjunction (OR):

P \lor Q, \quad P + Q

Exclusive OR (XOR):

P \oplus Q, \quad P \veebar Q

Implication (IF...THEN):

P \implies Q, \quad P \to Q, \quad P \Rightarrow Q

Biconditional (IF AND ONLY IF):

P \iff Q, \quad P \leftrightarrow Q, \quad P \Leftrightarrow Q

Truth Tables

Truth Table Notation

Documenting logical operations with truth tables

Implication truth table:

$P$	$Q$	$P \implies Q$
T	T	T
T	F	F
F	T	T
F	F	T

De Morgan's Laws:

\neg(P \land Q) \equiv \neg P \lor \neg Q

\neg(P \lor Q) \equiv \neg P \land \neg Q

Logical Equivalences

Important Logical Equivalences

Common tautologies and equivalences

Contrapositive:

(P \implies Q) \equiv (\neg Q \implies \neg P)

Material implication:

(P \implies Q) \equiv (\neg P \lor Q)

Distributive laws:

P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)

P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)

Double negation:

\neg(\neg P) \equiv P

Absorption:

P \lor (P \land Q) \equiv P

Predicate Logic

Predicate logic extends propositional logic with quantifiers and predicates, allowing us to make statements about objects and their properties. It's essential for formal specifications and mathematical proofs.

Quantifiers

Universal and Existential Quantifiers

Expressing 'for all' and 'there exists'

Universal quantifier (for all):

\forall x \in A, P(x)

"For all $x$ in $A$ , property $P(x)$ holds"

Existential quantifier (there exists):

\exists x \in A, P(x)

"There exists an $x$ in $A$ such that $P(x)$ holds"

Unique existence:

\exists! x, P(x)

"There exists exactly one $x$ such that $P(x)$ "

Negation of quantifiers:

\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)

\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)

Nested Quantifiers

Multiple Quantifiers

Combining quantifiers for complex statements

Order matters:

"For every $x$ , there exists a $y$ ":

\forall x, \exists y, P(x, y)

"There exists a $y$ for every $x$ ":

\exists y, \forall x, P(x, y)

Example - Continuity:

\forall \epsilon > 0, \exists \delta > 0, \forall x, (|x - a| < \delta \implies |f(x) - f(a)| < \epsilon)

Example - Limit definition:

\lim_{x \to a} f(x) = L \iff \forall \epsilon > 0, \exists \delta > 0, (0 < |x - a| < \delta \implies |f(x) - L| < \epsilon)

Predicates and Relations

Predicate Notation

Expressing properties and relations

Unary predicate (property):

P(x) \text{ — "$x$ has property $P$"}

Binary predicate (relation):

R(x, y) \text{ — "$x$ is related to $y$ by $R$"}

Alternative notation: $xRy$

Examples:

$\text{Prime}(n)$ — " $n$ is prime"
$x < y$ — " $x$ is less than $y$ "
$x \equiv y \pmod{n}$ — " $x$ is congruent to $y$ modulo $n$ "

Relation properties:

Reflexive: $\forall x, xRx$
Symmetric: $\forall x, y, (xRy \implies yRx)$
Transitive: $\forall x, y, z, (xRy \land yRz \implies xRz)$

Proof Notation

Mathematical proofs require specific notation to express logical structure clearly. This notation is essential for formal verification, algorithm correctness, and mathematical documentation.

Proof Structure Symbols

Proof Notation

Symbols used in mathematical proofs

Therefore / Hence:

\therefore \quad \text{(therefore)}

Because / Since:

\because \quad \text{(because)}

QED / End of proof:

\square \quad \blacksquare \quad \text{Q.E.D.}

Contradiction:

\bot \quad \text{(contradiction/false)}

Tautology:

\top \quad \text{(tautology/true)}

Turnstile (proves/entails):

\vdash \quad \text{(syntactic entailment)}

\models \quad \text{(semantic entailment)}

Proof by Contradiction

Proof by Contradiction Structure

Documenting indirect proofs

Proof by contradiction:

To prove $P$ :

Assume $\neg P$
Derive a contradiction: $Q \land \neg Q$
Conclude $P$ must be true

Example - $\sqrt{2}$ is irrational:

Assume $\sqrt{2} = \frac{p}{q}$ where $\gcd(p, q) = 1$ .

Then $2 = \frac{p^2}{q^2}$ , so $p^2 = 2q^2$ .

$\therefore p^2$ is even, so $p$ is even.

Let $p = 2k$ . Then $4k^2 = 2q^2$ , so $q^2 = 2k^2$ .

$\therefore q$ is even. But $\gcd(p, q) = 1$ . $\bot$

$\therefore \sqrt{2}$ is irrational. $\square$

Mathematical Induction

Induction Proof Structure

Documenting proofs by induction

Principle of Mathematical Induction:

To prove $\forall n \in \mathbb{N}, P(n)$ :

Base case: Prove $P(1)$
Inductive step: Prove $P(k) \implies P(k+1)$

Example - Sum formula:

Claim: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

Base case ( $n = 1$ ):

\sum_{i=1}^{1} i = 1 = \frac{1 \cdot 2}{2} \checkmark

Inductive step: Assume true for $k$ . Then:

\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k+1) = \frac{k(k+1)}{2} + (k+1)

= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} \checkmark

$\therefore$ By induction, the formula holds $\forall n \in \mathbb{N}$ . $\square$

Applications in Technical Documentation

Here are practical examples of set theory and logic notation in common technical documentation scenarios.

Type Systems

Type Theory Notation

Set theory in programming type systems

Type as a set:

\text{Int} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}

Union types:

\text{String} \cup \text{Number}

Intersection types:

\text{Serializable} \cap \text{Comparable}

Subtyping:

\text{Integer} \subseteq \text{Number} \subseteq \text{Object}

Generic types:

\text{List}\langle T \rangle = \{[x_1, x_2, \ldots] : x_i \in T\}

Function types:

f: A \to B \quad \text{means} \quad f \in B^A

Database Queries

Relational Algebra

Set operations in database theory

Selection (filter rows):

\sigma_{\text{age} > 21}(\text{Users})

Projection (select columns):

\pi_{\text{name, email}}(\text{Users})

Join:

\text{Users} \bowtie_{\text{Users.id} = \text{Orders.user\_id}} \text{Orders}

Set operations on tables:

\text{ActiveUsers} \cup \text{PremiumUsers}

\text{AllUsers} \setminus \text{BannedUsers}

Query composition:

\pi_{\text{name}}(\sigma_{\text{status} = \text{'active'}}(\text{Users}))

Algorithm Specifications

Formal Specifications

Logic in algorithm correctness

Precondition:

\text{Pre}: \forall i \in [0, n), A[i] \in \mathbb{Z}

Postcondition:

\text{Post}: \forall i \in [0, n-1), A[i] \leq A[i+1]

Loop invariant:

\text{Inv}: \forall j \in [0, i), A[j] \leq A[j+1]

Termination:

\text{Variant}: n - i \geq 0 \land \text{decreasing}

Hoare triple:

\{P\} \, S \, \{Q\}

"If precondition $P$ holds before executing $S$ , then postcondition $Q$ holds after."

Boolean Algebra in Circuits

Digital Logic

Boolean algebra for circuit design

Basic gates:

AND: $Y = A \cdot B$
OR: $Y = A + B$
NOT: $Y = \overline{A}$
XOR: $Y = A \oplus B$
NAND: $Y = \overline{A \cdot B}$

Boolean simplification:

\overline{A \cdot B} + A = \overline{A} + \overline{B} + A = 1

Sum of products:

F = \overline{A}BC + A\overline{B}C + AB\overline{C}

Product of sums:

F = (A + B)(\overline{A} + C)(B + \overline{C})

Best Practices

Use Standard Notation

Stick to widely recognized symbols. Use ∈ for membership, ⊆ for subsets, and ∀/∃ for quantifiers. Avoid inventing new notation unless absolutely necessary.

Define Your Universe

Always specify the domain of discourse. Write "∀x ∈ ℝ" rather than just "∀x" to avoid ambiguity about what values x can take.

Use Set-Builder Notation for Complex Sets

When a set cannot be easily listed, use set-builder notation like "{x ∈ A : P(x)}" to clearly express "all elements of A satisfying property P".

Break Down Complex Formulas

For nested quantifiers or complex logical expressions, introduce intermediate definitions or break the formula across multiple lines with explanations.

Use Aligned Environments for Proofs

When showing step-by-step derivations, use the aligned environment to align equals signs and implications for clarity.

Common Mistakes

Confusing ∈ and ⊆

Use ∈ for element membership (x ∈ A) and ⊆ for subset relations (B ⊆ A). An element is not a subset, and a set is not an element (usually).

Wrong Quantifier Order

"∀x, ∃y, P(x,y)" and "∃y, ∀x, P(x,y)" mean different things. The first says "for each x, there is some y" (possibly different for each x). The second says "there is one y that works for all x".

Forgetting Negation Rules

When negating quantified statements, flip the quantifier and negate the predicate: ¬(∀x, P(x)) ≡ ∃x, ¬P(x).

Misusing Implication

Remember that P ⟹ Q is true when P is false, regardless of Q. This "vacuous truth" often confuses readers unfamiliar with formal logic.

Inconsistent Set Notation

Do not mix "{1,2,3}" with "(1,2,3)" for sets. Curly braces denote sets; parentheses denote ordered tuples or intervals.

Quick Reference

Concept	KaTeX Syntax	Result
Element of	x \in A	$x \in A$
Subset	A \subseteq B	$A \subseteq B$
Union	A \cup B	$A \cup B$
Intersection	A \cap B	$A \cap B$
Empty set	\emptyset	$\emptyset$
For all	\forall x	$\forall x$
There exists	\exists x	$\exists x$
Negation	\neg P	$\neg P$
AND	P \land Q	$P \land Q$
OR	P \lor Q	$P \lor Q$
Implies	P \implies Q	$P \implies Q$
If and only if	P \iff Q	$P \iff Q$
Therefore	\therefore	$\therefore$

Set Theory and Logic Notation — Mathematical Foundations

Introduction

Set Notation Basics

Defining Sets

Set Definition Notation

Special Sets

Standard Number Sets

Set Membership and Relations

Membership and Subset Relations

Set Operations

Basic Operations

Union, Intersection, and Difference

Complement and Power Set

Complement and Power Set

Cartesian Product

Cartesian Product

Indexed Operations

Indexed Unions and Intersections

Propositional Logic

Logical Connectives

Basic Logical Operators

Truth Tables

Truth Table Notation

Logical Equivalences

Important Logical Equivalences

Predicate Logic

Quantifiers

Universal and Existential Quantifiers

Nested Quantifiers

Multiple Quantifiers

Predicates and Relations

Predicate Notation

Proof Notation

Proof Structure Symbols

Proof Notation

Proof by Contradiction

Proof by Contradiction Structure

Mathematical Induction

Induction Proof Structure

Applications in Technical Documentation

Type Systems

Type Theory Notation

Database Queries

Relational Algebra

Algorithm Specifications

Formal Specifications

Boolean Algebra in Circuits

Digital Logic

Best Practices

Common Mistakes

Quick Reference

Related Content

KaTeX Syntax Quick Reference — Math Equations in Markdown

Calculus in Technical Documentation — Derivatives and Integrals

Using KaTeX in AutEng

Ready to Start?