Set

Basically, a set is an unordered collection of different things called elements. Sets are defined only by what elements they contain. A capital letter is commonly used to symbolize a set.

Contents

Roster notation

To define a set in roster notation, list its elements between curly brackets, separated by commas. This is the clearest way to write a set.

$$S = \set{0, 1, 2, 3, 4}$$

The elements can be written in any order, and repeating an element will not change the set.

For a set with many elements, listing out all the elements can be exhausting. However, as long as the elements follow an obvious pattern, you can use ellipses to quickly write it in roster notation:

$$E = \set{2, 4, 6, 8, ... 100}$$

Here, the set $E$ can be assumed to contain all positive even integers up to $100.$

Set-builder notation

Alternatively, you can define a set in set-builder notation, in which elements are taken from some larger set and have to meet some specified membership condition.

$$A = \set{ x \in S : P(x) }$$

Here, $S$ is the larger set from which elements are obtained, and $P(x)$ is the proposition that must be true for an element $x$ to be a part of the set $A.$ This is read as "all $x$ in $S$ such that $P(x).$"

Cardinality

The cardinality of a finite set is the number of unique elements it contains. The empty set is the only set whose cardinality is $0.$

The cardinality of a set $S$ is represented by $|S|.$

Let $S = \set{0, 1, 2, 3, 4}.$ Then: $$|S| = 5$$

⚠ If one of the elements were a set, it would still only contribute $1$ to the cardinality.

Sign specification

Sometimes, you may encounter sets written as $T^{+}$ or $T^{-}.$ The superscript $+$ and $-$ are meant to indicate the positive and negative elements of a set, respectively. So, $T^{+}$ is the set containing only the positive elements of $T.$ Similarly, you may use a superscript $\geq 0$ or $\leq 0$ for non-negative and non-positive, such as in $T^{\geq 0}$ or $T^{\leq 0}.$

Venn diagrams

A Venn diagram is a popular way of visualizing sets and their relations. First, the universal set $U$ is drawn as a large rectangle, which will contain all the sets. Then, each set is drawn as an oval-like shape (although they could be any shape) that encloses all their elements. Sets can be seen to intersect when they have elements in common.

⚠ While Venn diagrams are a nice visualization tool, they cannot be used to prove anything about a set.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort