Power set
The power set of a set is the set of all subsets of that set, including the empty set \(\emptyset\) and the set itself. The power set of some set \(A\) is denoted \(\mathcal{P}(A).\) Intuitively, \(\mathcal{P}(A)\) is the set of all combinations of elements that are possible given only the elements of \(A.\)
The cardinality of the power set of a set \(A\) is always \(2^{|A|}\), where \(|A|\) is the cardinality of \(A.\)
Consider the set \(S = \set{7, 8, 9}.\) Its power set is written as:
$$\mathcal{P}(S) = \set{\emptyset, \set{7}, \set{8}, \set{9}, \set{7, 8}, \set{7, 9}, \set{8, 9},
\set{7, 8, 9}}$$
Notice that \(|\mathcal{P}(S)| = 8\) because \(2^{|S|} = 2^3 = 8.\)
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
Algorithms
Relations
Number Theory
Induction
Combinatorics
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