Helpful context:

Propositional logic gives us a calculus for reasoning about compound statements built from atomic propositions - things that are simply true or false as fixed objects. But mathematics is filled with statements that are not atomic: “every even integer is divisible by two,” “there exists a prime larger than one million,” “for any triangle, the sum of its angles is 180 degrees.” These statements contain variables that range over some collection of objects, and their truth depends on the quantifiers binding those variables - not just on the truth values of component atoms. Predicate calculus, also called first-order logic, extends propositional logic by introducing variables, predicates, and quantifiers, giving us the language in which essentially all of ordinary mathematics is written.

Set theory, meanwhile, provides the objects that populate these logical statements. A set is a collection of distinct objects - finite or infinite, concrete or abstract - and virtually every mathematical structure (numbers, functions, relations, spaces) can be defined as a kind of set. The axioms of set theory, together with the inference rules of predicate logic, form the foundation on which modern mathematics rests. Understanding both together - the language and the objects - is what separates someone who can follow mathematical arguments from someone who can construct and critique them.

This post develops both subjects systematically. Predicate calculus comes first: predicates, quantifiers, free and bound variables, the universe of discourse, and the four rules of inference that govern quantified reasoning. Set theory follows: the basic operations, power sets and cardinality, binary relations with their key properties, functions and bijectivity, and the beautiful and counterintuitive theory of countability culminating in Cantor’s diagonal argument. The two subjects reinforce each other continuously - set operations are defined by logical formulas, and logical quantifiers range over sets.

Predicates and Atomic Formulas

In propositional logic, the atoms are complete propositions: “$P$” might stand for “it is raining,” a statement that is true or false without further context. In predicate logic, atoms are more fine-grained: they express properties of objects, or relations between objects, where the objects are not yet specified.

A predicate $P(x)$ is a property that an object $x$ may or may not have. It is not yet a proposition - it is an open expression that becomes a proposition only when the variable $x$ is assigned a specific value from some domain. If the domain is the integers and $P(x)$ is the predicate “$x$ is even,” then $P(4)$ is true and $P(7)$ is false. The predicate itself is neither true nor false; it is a function from objects to truth values.

More generally, an $n$-ary predicate $P(x_1, x_2, \ldots, x_n)$ expresses a relation among $n$ variables. The binary predicate “$x < y$” holds when the first argument is strictly less than the second; it requires two inputs before it becomes a proposition. “$x + y = z$” is a ternary predicate on integers. An atomic formula is a predicate applied to a specific list of terms (variables or constants) - it is the smallest unit of predicate-logic syntax that can be assigned a truth value once variables are interpreted. Compound formulas are then built from atomic formulas using the propositional connectives $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$ that carry over from propositional logic, plus the quantifier symbols introduced next.

Quantifiers

The two quantifiers of first-order logic express different ways of binding a variable to a domain of objects.

The universal quantifier $\forall x P(x)$ asserts that $P$ holds for every object in the domain: “for all $x$, $P(x)$.” If the domain is the natural numbers and $P(x)$ is “$x + 0 = x$,” then $\forall x P(x)$ is true - the additive identity law holds for every natural number. If $P(x)$ is “$x$ is prime,” then $\forall x P(x)$ is false, since $4$ is not prime.

The existential quantifier $\exists x P(x)$ asserts that $P$ holds for at least one object in the domain: “there exists an $x$ such that $P(x)$.” If the domain is the integers and $P(x)$ is “$x^2 = 2$,” then $\exists x P(x)$ is false (no integer squares to two). Over the reals, $\exists x P(x)$ is true ($x = \sqrt{2}$).

Quantifier duality connects $\forall$ and $\exists$ through negation, exactly as De Morgan’s laws connect $\land$ and $\lor$ in propositional logic:

$$\neg \forall x P(x) ;\equiv; \exists x \neg P(x)$$ $$\neg \exists x P(x) ;\equiv; \forall x \neg P(x)$$

The first says: “not every $x$ has property $P$” is the same as “some $x$ lacks $P$.” The second says: “no $x$ has $P$” is the same as “every $x$ lacks $P$.” These equivalences are used constantly in mathematics - to disprove a universal claim, exhibit a counterexample (existential witness); to disprove an existence claim, show that every candidate fails.

Multiple quantifiers can be nested, and the order matters. $\forall x \exists y (x < y)$ over the integers means “for every integer there is a larger one” - true. But $\exists y \forall x (x < y)$ means “there is an integer larger than every integer” - false. Swapping the order of unlike quantifiers changes meaning and truth value.

Free and Bound Variables

A variable in a formula is bound if it falls within the scope of a quantifier that binds it; it is free if it is not bound by any enclosing quantifier. This distinction controls how formulas behave.

Consider $\forall x P(x, y)$. The variable $x$ is bound - the $\forall x$ quantifier captures every occurrence of $x$ in $P(x, y)$. The variable $y$ is free - it floats without a quantifier binding it. Now consider the formula $\forall x P(x) \to Q(x)$: if the scope of $\forall x$ is only $P(x)$ (parsed as $(\forall x P(x)) \to Q(x)$), then the $x$ in $Q(x)$ is free; if the scope is the whole conditional (parsed as $\forall x (P(x) \to Q(x))$), both occurrences are bound. Parenthesization is therefore essential.

A formula with no free variables is a closed formula, also called a sentence. A sentence has a definite truth value relative to a given interpretation and domain - it asserts something specific. The formula $\forall x (x + 1 > x)$ over the integers is a sentence, and it is true. A formula with at least one free variable is an open formula. The expression $x + 1 > x$ is open: it is not true or false on its own, but becomes a proposition when $x$ is assigned a value. Open formulas function like predicates; sentences function like propositions.

The substitution principle says that wherever a free variable $x$ appears in a formula $\phi(x)$, it is legitimate to substitute a constant or term $t$ for $x$, producing $\phi(t)$ - provided the substitution does not accidentally bind a variable that was free in $t$ (a phenomenon called “capture,” avoided by renaming bound variables first if necessary).

Universe of Discourse

Quantifiers do not range over everything in existence simultaneously - they range over a fixed background collection called the universe of discourse (or domain), often denoted $D$. Writing $\forall x P(x)$ is shorthand for “for all $x$ in $D$, $P(x)$,” and $\exists x P(x)$ means “there is some $x$ in $D$ such that $P(x)$.” The choice of domain is part of the interpretation, and changing the domain can change truth values dramatically.

Over the domain of positive integers, $\forall x \exists y (y < x)$ is false - the integer $1$ has no positive predecessor. Over the domain of all integers, it is true. The statement $\exists x (x^2 = 2)$ is false over the rationals and true over the reals. This domain-dependence is not a defect; it is the system working as intended. A sentence like $\forall x \exists y (x = y^2)$ should be false over the integers but true over non-negative reals, and predicate logic correctly captures both cases by letting the domain vary.

Two special moves involve the domain explicitly. Universal instantiation (described in the next section) draws a conclusion about a specific element from a universal statement over the domain. Universal generalization concludes a universal statement about the entire domain from a proof that works for an arbitrary element. The constraint on generalization - that the element be genuinely arbitrary, with no special properties assumed - is precisely what forces the domain to be treated as fixed and unspecified during the generalization step.

Rules of Inference for Predicate Logic

Predicate logic inherits all the propositional inference rules (modus ponens, hypothetical syllogism, and so on) and adds four rules governing quantifiers. These are the tools that make formal proof in predicate logic mechanical.

Universal Instantiation (UI). From $\forall x P(x)$, conclude $P(c)$ for any constant $c$ in the domain. If a property holds universally, it holds for any particular element you name. This rule is always valid, with no restrictions, as long as $c$ is in the domain.

$$\forall x P(x) ;\vdash; P(c)$$

Existential Instantiation (EI). From $\exists x P(x)$, introduce a new constant $c$ and conclude $P(c)$, where $c$ has no other assumptions made about it. The idea: if something with property $P$ exists, give it a name so you can reason about it. The critical restriction is that $c$ must be fresh - it must not have appeared anywhere else in the proof or in the premises. If $c$ already appeared, you might be assuming the witness has properties it need not have.

$$\exists x P(x) ;\vdash; P(c) \quad (c \text{ fresh})$$

Universal Generalization (UG). If you have derived $P(c)$ for an arbitrary constant $c$ - one introduced without any special assumptions about it - then conclude $\forall x P(x)$. Arbitrariness is the key requirement: if $c$ was obtained by EI (so it has some property $P(c)$ by assumption), you may not generalize. If $c$ appears free in an undischarged hypothesis, you may not generalize. Only when $c$ truly stands for “any element” - nothing special was assumed - does the rule apply.

$$P(c) ;\vdash; \forall x P(x) \quad (c \text{ arbitrary})$$

Existential Generalization (EG). From $P(c)$ for a specific constant $c$, conclude $\exists x P(x)$. If you know some particular thing has a property, then certainly something has that property. This rule is always valid.

$$P(c) ;\vdash; \exists x P(x)$$

The most common mistakes: applying UG after an EI step (the constant from EI is not arbitrary - it was chosen because it satisfies $P$, so you cannot conclude the property holds for all); or reusing a constant in an EI step when that constant already carries other information.

Worked Examples in Predicate Logic

Example 1. Prove: $\forall x (P(x) \to Q(x)),; \forall x P(x) ;\vdash; \forall x Q(x)$.

Let $c$ be an arbitrary constant in the domain. By UI on the first premise: $P(c) \to Q(c)$. By UI on the second premise: $P(c)$. By modus ponens: $Q(c)$. Since $c$ was arbitrary (introduced with no special assumptions), apply UG: $\forall x Q(x)$. This is the predicate-logic analog of the syllogism “all humans are mortal, all Greeks are humans, therefore all Greeks are mortal.”

Example 2. Prove: $\exists x P(x) ;\vdash; \exists x (P(x) \lor Q(x))$.

By EI on the premise: let $c$ be a fresh constant with $P(c)$. By disjunction introduction: $P(c) \lor Q(c)$. By EG: $\exists x (P(x) \lor Q(x))$. The argument says: if something has property $P$, then that same thing has the property of either $P$ or $Q$ (since it already has $P$), so something with the disjunctive property exists.

Notice the asymmetry: $\exists x P(x)$ is used exactly once in the EI step. If the proof had required two separate existential instantiations from $\exists x P(x)$, we would have needed two fresh constants $c_1$ and $c_2$ - they might or might not be the same element, and we cannot assume they coincide.

Basic Sets and Notation

A set is a collection of distinct objects, called its elements or members. Sets have no notion of order among their elements, and each element either belongs or does not belong - multiplicity is irrelevant. The two standard notations are roster notation, listing elements explicitly: $\{1, 2, 3\}$, $\{a, e, i, o, u\}$; and set-builder notation, specifying elements by a predicate: $\{x \mid P(x)\}$ means the set of all $x$ (in some understood domain) satisfying $P(x)$. For example, $\{x \in \mathbb{Z} \mid x^2 < 10\} = \{-3, -2, -1, 0, 1, 2, 3\}$.

The empty set $\emptyset = \{\}$ contains no elements. It is unique - there is exactly one empty set - and it is a subset of every set.

The membership relation $\in$ is primitive: $a \in A$ means “$a$ is an element of $A$.” The negation is $a \notin A$.

Set $A$ is a subset of set $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$:

$$A \subseteq B ;\iff; \forall x (x \in A \to x \in B)$$

This is a universal statement - to prove $A \subseteq B$, take an arbitrary $x \in A$ and show $x \in B$. $A$ is a proper subset of $B$, written $A \subset B$, if $A \subseteq B$ and $A \neq B$ - something in $B$ is not in $A$.

Set equality is defined in terms of mutual containment: $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$. Equivalently:

$$A = B ;\iff; \forall x (x \in A \leftrightarrow x \in B)$$

This is the standard proof strategy: to show two sets are equal, show containment in both directions, each by the take-an-arbitrary-element method. The equivalence between $A = B$ and mutual subset inclusion reflects the axiom of extensionality - sets are determined entirely by their elements.

Set Operations

Given sets $A$ and $B$ (with both understood as subsets of some universal set $U$ in context), the standard operations are defined by logical formulas on membership.

Union: $A \cup B = \{x \mid x \in A \lor x \in B\}$. The union contains every element in $A$, every element in $B$, and nothing else. Venn diagram: the entire region covered by either circle.

Intersection: $A \cap B = \{x \mid x \in A \land x \in B\}$. Only elements belonging to both sets. Venn diagram: the overlapping region. $A$ and $B$ are disjoint if $A \cap B = \emptyset$.

Difference: $A \setminus B = \{x \mid x \in A \land x \notin B\}$. Elements of $A$ that are not in $B$. Also written $A - B$. Venn diagram: the part of $A$’s circle not covered by $B$.

Complement: $\bar{A} = U \setminus A = \{x \in U \mid x \notin A\}$, relative to a fixed universal set $U$. Venn diagram: everything outside $A$’s circle.

Symmetric difference: $A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$. Elements in exactly one of $A$ and $B$. The two definitions are equivalent, which itself is a good exercise in set algebra. Venn diagram: the two crescents, excluding the overlap.

Cartesian product: $A \times B = \{(a, b) \mid a \in A, b \in B\}$. The set of all ordered pairs with first coordinate from $A$ and second from $B$. Unlike union and intersection, the Cartesian product cares about order: $(a, b) \neq (b, a)$ in general, and $A \times B \neq B \times A$ unless $A = B$ or one is empty. $|A \times B| = |A| \cdot |B|$ for finite sets.

The algebraic laws governing these operations mirror the propositional laws, which is no coincidence - the set operations are defined directly in terms of the logical connectives. Commutativity: $A \cup B = B \cup A$; associativity: $(A \cup B) \cup C = A \cup (B \cup C)$; distributivity: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$; De Morgan: $\overline{A \cup B} = \bar{A} \cap \bar{B}$ and $\overline{A \cap B} = \bar{A} \cup \bar{B}$. Each identity follows directly from the corresponding propositional tautology by translating membership predicates into truth values.

Power Set and Cardinality

The power set of a set $A$, written $\mathcal{P}(A)$ or $2^A$, is the set of all subsets of $A$:

$$\mathcal{P}(A) = \{S \mid S \subseteq A\}$$

For example, $\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$ - four elements. Note that $\emptyset \in \mathcal{P}(A)$ always (since $\emptyset \subseteq A$) and $A \in \mathcal{P}(A)$ always ($A \subseteq A$).

Theorem. For any finite set $A$ with $|A| = n$, we have $|\mathcal{P}(A)| = 2^n$.

Proof. Each subset of $A$ corresponds to a binary string of length $n$: position $i$ is $1$ if element $i$ is included and $0$ if excluded. This is a bijection between $\mathcal{P}(A)$ and $\{0,1\}^n$, which has $2^n$ elements. Alternatively, argue inductively: $\mathcal{P}(\emptyset) = \{\emptyset\}$ has $2^0 = 1$ element. Adding one new element $a$ to a set $A$ of size $n$ doubles the count, because every subset of $A \cup \{a\}$ either contains $a$ or does not - yielding exactly twice as many subsets. $\square$

The cardinality $|A|$ of a set is the number of elements it contains (for finite sets). For infinite sets, cardinality is defined via bijections: two sets have the same cardinality if there is a bijection between them. This definition, due to Cantor, leads to the surprising result that some infinite sets are strictly “larger” than others - the subject of the countability section.

A brief but important warning: one might try to define a “set of all sets” $U$ that contains everything, so that $\mathcal{P}(U) \subseteq U$ and thus $2^{|U|} \leq |U|$. This is impossible by Cantor’s theorem ($|\mathcal{P}(A)| > |A|$ for every set $A$). More concretely, defining $R = \{x \mid x \notin x\}$ and asking whether $R \in R$ leads to a contradiction either way - this is Russell’s paradox. Modern set theory (ZFC) avoids this by restricting what collections count as sets and by not admitting a universal set.

Binary Relations

A binary relation $R$ from set $A$ to set $B$ is any subset $R \subseteq A \times B$. We write $aRb$ or $(a, b) \in R$ to indicate that $a$ and $b$ are related. Relations generalize functions (which are relations with a uniqueness condition, introduced below) and capture comparisons, connections, and structure between elements.

When $A = B$, we speak of a relation on $A$, meaning $R \subseteq A \times A$. Such relations can have structural properties that classify them into important families:

Reflexive: $\forall a \in A, aRa$. Every element is related to itself. The relation $\leq$ on integers is reflexive ($n \leq n$); the relation $<$ is not ($n \not< n$).

Symmetric: $\forall a, b \in A, aRb \to bRa$. If $a$ relates to $b$, then $b$ relates to $a$. The relation “is a sibling of” is symmetric; “is a parent of” is not.

Antisymmetric: $\forall a, b \in A, (aRb \land bRa) \to a = b$. If $a$ and $b$ are mutually related, they must be the same element. The relation $\leq$ on integers is antisymmetric: $m \leq n$ and $n \leq m$ implies $m = n$.

Transitive: $\forall a, b, c \in A, (aRb \land bRc) \to aRc$. Chains of relatedness propagate. The relation $<$ on integers is transitive; “is a parent of” is not (your parent’s parent is your grandparent, not parent).

Two combinations of these properties define the most important classes:

An equivalence relation is one that is reflexive, symmetric, and transitive. Equivalence relations capture sameness under some abstraction: equality, congruence modulo $n$, having the same cardinality. Given an equivalence relation $\sim$ on $A$, the equivalence class of an element $a$ is $[a] = \{b \in A \mid b \sim a\}$ - all elements equivalent to $a$. The equivalence classes are pairwise disjoint and their union is all of $A$; this is called a partition of $A$. Conversely, every partition of $A$ induces an equivalence relation (elements in the same part are equivalent). Equivalence relations and partitions are in exact correspondence.

A partial order is a relation that is reflexive, antisymmetric, and transitive. The integers under $\leq$, sets under $\subseteq$, natural numbers under divisibility - all partial orders. A total order (or linear order) additionally requires that for every $a, b$, either $aRb$ or $bRa$ (every pair is comparable). The integers under $\leq$ are totally ordered; subsets under $\subseteq$ are not (neither $\{1,2\}$ nor $\{2,3\}$ is a subset of the other).

Functions

A function $f: A \to B$ is a relation $f \subseteq A \times B$ in which every element of $A$ appears in exactly one pair: for every $a \in A$, there is exactly one $b \in B$ with $(a, b) \in f$, written $f(a) = b$. The set $A$ is the domain, $B$ is the codomain, and the image (or range) is $\{f(a) \mid a \in A\} \subseteq B$, which may be a proper subset of $B$.

The functional properties of interest concern how $f$ maps $A$ into $B$:

Injective (one-to-one): $\forall a_1, a_2 \in A, f(a_1) = f(a_2) \to a_1 = a_2$. Different inputs give different outputs; no two elements of $A$ map to the same element of $B$. Equivalently, $a_1 \neq a_2 \to f(a_1) \neq f(a_2)$.

Surjective (onto): $\forall b \in B, \exists a \in A, f(a) = b$. Every element of $B$ is hit by some element of $A$; the image equals the entire codomain.

Bijective: both injective and surjective simultaneously. Every element of $B$ is the image of exactly one element of $A$. A bijection is a perfect matching between $A$ and $B$, and it is the formal notion of “same size” for infinite sets.

The inverse function $f^{-1}: B \to A$ exists if and only if $f$ is bijective. If $f$ is injective but not surjective, $f^{-1}$ can be defined only on the image of $f$, not all of $B$. If $f$ is surjective but not injective, multiple elements of $A$ map to some $b$, so there is no unique “undoing.”

Composition: Given $f: A \to B$ and $g: B \to C$, the composition $(g \circ f): A \to C$ is defined by $(g \circ f)(x) = g(f(x))$. Composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$. If $f$ and $g$ are both injective, so is $g \circ f$; if both are surjective, so is $g \circ f$; if both are bijective, so is $g \circ f$, and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

The identity function $\text{id}_A: A \to A$ defined by $\text{id}_A(x) = x$ satisfies $f \circ \text{id}_A = f$ and $\text{id}_B \circ f = f$ for any $f: A \to B$. This makes functions-with-composition a category, though that language belongs to abstract algebra.

Countable and Uncountable Sets

Two sets $A$ and $B$ have the same cardinality, written $|A| = |B|$, if there exists a bijection $f: A \to B$. For finite sets this agrees with the ordinary count of elements. For infinite sets, it is the only coherent definition - and it leads to a rich hierarchy of infinite sizes.

A set is countably infinite if it has the same cardinality as $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ - that is, its elements can be listed in a sequence $a_0, a_1, a_2, \ldots$ that includes every element exactly once. A set is countable if it is either finite or countably infinite.

Example: $\mathbb{Z}$ is countable. The integers include both positive and negative values, which might suggest it is “twice as large” as $\mathbb{N}$. But bijections ignore intuitions about size. List the integers by interleaving: $0, 1, -1, 2, -2, 3, -3, \ldots$. Formally, define $f: \mathbb{N} \to \mathbb{Z}$ by $f(2k) = k$ and $f(2k+1) = -(k+1)$ for $k \geq 0$. This is a bijection, so $|\mathbb{Z}| = |\mathbb{N}|$.

Example: $\mathbb{Q}$ is countable. The rationals - fractions of integers - form a much denser set than the integers, yet they are still countable. Arrange the positive rationals in an infinite grid: row $p$, column $q$ contains $p/q$. Now traverse the grid by diagonals (the Cantor dovetailing method): $1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, \ldots$, skipping fractions already seen in reduced form. Every positive rational appears in the grid and is eventually reached; adding $0$ and the negatives (by interleaving as with $\mathbb{Z}$) gives a bijection $\mathbb{N} \to \mathbb{Q}$. This result is genuinely surprising: the rationals are dense in the reals (between any two rationals is another rational) yet there are only countably many of them.

Theorem (Cantor): $\mathbb{R}$ is uncountable. Suppose, for contradiction, that the real numbers in $[0,1)$ are countable, enumerated as $r_0, r_1, r_2, \ldots$. Write each $r_i$ in its decimal expansion $r_i = 0.d_{i0} d_{i1} d_{i2} \ldots$. Construct a new number $x = 0.x_0 x_1 x_2\ldots$ by setting $x_i = 5$ if $d_{ii} \neq 5$ and $x_i = 6$ if $d_{ii} = 5$. Then $x$ differs from $r_0$ in the first decimal place, from $r_1$ in the second, from $r_2$ in the third, and so on - $x$ differs from every $r_i$ in the $i$-th decimal place. So $x \in [0,1)$ but $x$ is not in the enumeration. Contradiction. $\square$ (The choice of $5$ and $6$ avoids the $0.999\ldots = 1.000\ldots$ ambiguity in decimal representations.)

Theorem: $\mathcal{P}(\mathbb{N})$ is uncountable. Identify each subset $S \subseteq \mathbb{N}$ with its characteristic sequence $(\mathbf{1}[0 \in S], \mathbf{1}[1 \in S], \mathbf{1}[2 \in S], \ldots)$ - a binary sequence. The function sending subsets to binary sequences is a bijection between $\mathcal{P}(\mathbb{N})$ and $\{0,1\}^\mathbb{N}$. Apply the diagonal argument to $\{0,1\}^\mathbb{N}$: if $s_0, s_1, s_2, \ldots$ is any enumeration of binary sequences, the sequence $t$ with $t_i = 1 - s_{i,i}$ (flip the diagonal) differs from every $s_i$. So no enumeration covers all binary sequences, and $\mathcal{P}(\mathbb{N})$ is uncountable.

Cantor’s theorem in full generality: for any set $A$, $|\mathcal{P}(A)| > |A|$. The proof is the same diagonal: any function $f: A \to \mathcal{P}(A)$ fails to be surjective, since the set $D = \{a \in A \mid a \notin f(a)\}$ is not in the image of $f$ (if $D = f(c)$ for some $c$, then $c \in D \iff c \notin f(c) = D$, a contradiction). This generates an infinite hierarchy: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$. The cardinality of $\mathbb{R}$ equals $|\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}$, denoted $\mathfrak{c}$ (the continuum). The continuum hypothesis conjectures that there is no cardinality strictly between $|\mathbb{N}|$ and $|\mathbb{R}|$ - no infinite set of real numbers that is neither countable nor in bijection with all of $\mathbb{R}$. This hypothesis is independent of the standard axioms of set theory (ZFC): both it and its negation are consistent, a profound result due to Gödel and Cohen.

Summary

Concept Key Definition or Result
Predicate $P(x)$ Open expression; becomes a proposition when $x$ is assigned a value
$\forall x P(x)$ $P$ holds for all $x$ in the domain $D$
$\exists x P(x)$ $P$ holds for at least one $x$ in $D$
Quantifier duality $\neg\forall x P(x) \equiv \exists x \neg P(x)$; $\neg\exists x P(x) \equiv \forall x \neg P(x)$
Bound / Free variable Bound: falls within scope of its quantifier; free: does not
Sentence Closed formula (no free variables); has a definite truth value
UI $\forall x P(x) \vdash P(c)$ for any constant $c$ in domain
EI $\exists x P(x) \vdash P(c)$ for a fresh constant $c$
UG $P(c)$ for arbitrary $c ;\vdash; \forall x P(x)$
EG $P(c) ;\vdash; \exists x P(x)$
Set equality $A = B \iff A \subseteq B$ and $B \subseteq A$
Set operations $\cup$: $\lor$; $\cap$: $\land$; $\setminus$: $\land \neg$; $\bar{A}$: $\neg$; $\triangle$: exclusive-or
Power set $\mathcal{P}(A)$: all subsets; $
Equivalence relation Reflexive + symmetric + transitive; classes partition the set
Partial order Reflexive + antisymmetric + transitive
Bijection Injective + surjective; $f^{-1}$ exists iff $f$ is bijective
Countable Finite, or in bijection with $\mathbb{N}$; $\mathbb{Z}$ and $\mathbb{Q}$ are countable
Uncountable $\mathbb{R}$ and $\mathcal{P}(\mathbb{N})$ uncountable by diagonal argument
Cantor’s theorem $

Read next: