Set Theory: A First Course

A comprehensive vocabulary list covering logic, foundations, relations, functions, transfinite arithmetic, and set combinatorics based on Daniel W. Cunningham's Set Theory: A First Course.

Set

A collection of objects where the objects are called elements of the collection.

Subset ($A \subseteq B$)

A set $A$ is a subset of set $B$ if every element of $A$ is also an element of $B$.

Proper Subset ($A \subset B$)

A set $A$ is a proper subset of set $B$ when $A \subseteq B$ and $A \neq B$, meaning there is at least one element in $B$ that is not in $A$.

Disjoint Sets

Two sets $A$ and $B$ that have no elements in common.

Power Set ($P(A)$)

The set whose elements are all of the subsets of $A$, denoted by $P(A) = \{X : X \subseteq A\}$.

Conjunction ($P \wedge Q$)

A logical connective meaning '$P$ and $Q$', which is true only if both components are true.

Disjunction ($P \vee Q$)

A logical connective meaning '$P$ or $Q$', which is true if either $P$ or $Q$ (or both) are true.

Tautology

A compound sentence that is true regardless of the truth values assigned to its components.

Contradiction

A compound sentence that is false regardless of the truth values assigned to its components.

Logical Equivalence ($\psi \Leftrightarrow \phi$)

When two propositional sentences result in identical truth values for every possible truth assignment applied to their components.

Bound Variable

A variable in a statement that is immediately used or restricted by a quantifier like $\forall$ or $\exists$.

Free Variable

A variable in a mathematical statement that is not bound by a quantifier and for which a specific value may be substituted.

Atomic Formula

The simplest type of formula in set theory, having the form $x \in y$ or $x = z$.

Proper Class

A collection of objects that share a property but is too large to be considered a set, such as the collection of all sets.

Singleton

A set that contains exactly one element, such as $\{u\}$.

Intersection of $F$ ($\bigcap F$)

For a nonempty set $F$, the unique set containing all elements $x$ that belong to every member of $F$.

Ordered Pair ($\langle x, y \rangle$)

A set defined as $\{\{x\},\{x, y\}\}$ that possesses a unique first component $x$ and a unique second component $y$.

Relation

A set composed entirely of ordered pairs.

Domain ($\text{dom}(R)$)

The set of all first components of the ordered pairs in a relation $R$, defined as $\{x : \exists y(\langle x, y \rangle \in R)\}$.

Range ($\text{ran}(R)$)

The set of all second components of the ordered pairs in a relation $R$, defined as $\{y : \exists x(\langle x, y \rangle \in R)\}$.

Field ($\text{fld}(R)$)

The union of the domain and the range of a relation $R$, defined as $\text{dom}(R) \cup \text{ran}(R)$.

Single-rooted Relation

A relation $R$ where for each $y \in \text{ran}(R)$ there is exactly one $x$ such that $\langle x, y \rangle \in R$.

Reflexive Relation

A relation $\sim$ on set $A$ where $( \forall x \in A )(x \sim x)$; every element is related to itself.

Symmetric Relation

A relation $\sim$ where if $x \sim y$, then $y \sim x$ for all elements in the set.

Transitive Relation

A relation $\sim$ where if $x \sim y$ and $y \sim z$, then $x \sim z$ for all elements in the set.

Equivalence Relation

A relation on a set that is simultaneously reflexive, symmetric, and transitive.

Partition

A set of nonempty, pairwise disjoint subsets of a set $A$ whose union equals set $A$.

Equivalence Class ($[a]_\sim$)

The set of all elements in a set $A$ that are related to a given element $a$ under an equivalence relation $\sim$, defined as $\{x \in A : x \sim a\}$.

Quotient Set ($A/\sim$)

The set of all equivalence classes of elements of $A$ induced by the equivalence relation $\sim$.

Function

Any single-valued relation such that for each $x$ in the domain, there is only one $y$ such that $\langle x, y \rangle \in F$.

Injection (One-to-One Function)

A function where any two distinct elements in the domain are mapped to distinct elements in the codomain.

Surjection (Onto Function)

A function where the range is equal to the codomain, meaning every element in the codomain is mapped to by at least one element in the domain.

Bijection

A function that is simultaneously one-to-one (injective) and onto (surjective).

Partial Order

A relation that is reflexive, antisymmetric, and transitive.

Total Order (Linear Order)

A partial order $\preceq$ on set $A$ satisfying $( \forall x \in A )( \forall y \in A )(x \preceq y \vee y \preceq x)$; every two elements are comparable.

Chain

A subset of a partially ordered set in which every two elements are comparable.

Maximal Element

An element $b$ in a partially ordered set such that there is no element in the set larger than $b$.

Least Upper Bound

An upper bound $u$ for set $S$ such that $u \preceq b$ for every other upper bound $b$ of $S$.

Isomorphism

A bijection between two structures that preserves the defining relation (e.g., ordering).

Preorder

A relation that is reflexive and transitive, often called a proset.

Successor ($x^+$)

The set obtained by adjoining $x$ to its elements: $x^+ = x \cup \{x\}$.

Inductive Set

A set $I$ that contains the empty set (0) and is closed under the successor operation ($\forall a \in I, a^+ \in I$).

$$\omega$$

The set consisting of all natural numbers; it is the smallest inductive set.

Transitive Set

A set $A$ where every element of $A$ is also a subset of $A$ ($\forall a \in A, a \subseteq A$).

Peano System

An ordered triple $(N, S, e)$ where $e \notin \text{ran}(S)$, $S$ is one-to-one, and the induction postulate holds.

Well-Ordering

A total ordering on a set $A$ for which every nonempty subset of $A$ has a smallest (least) element.

Countable Set

A set $X$ for which there exists a one-to-one function $f : X \rightarrow \omega$.

Uncountable Set

A set that is not countable, such as the set of real numbers $\mathbb{R}$.

Cardinality

A measure of the size of a set; sets $A$ and $B$ have the same cardinality if there is a bijection between them.

Continuum Hypothesis ($CH$)

The conjecture that there is no set $A \subseteq \mathbb{R}$ such that $| \omega | <_c | A | <_c | \mathbb{R} |$.

Ordinal Number

A transitive set that is well-ordered by the membership relation $\in$.

Successor Ordinal

A nonzero ordinal $\alpha$ such that $\alpha = \eta^+$ for some ordinal $\eta$.

Limit Ordinal

A nonzero ordinal that is not the successor of any ordinal.

Rank

The least ordinal $\gamma$ such that a set $A$ is a subset of the stage $V_\gamma$ in the cumulative hierarchy.

Cardinal Number

An ordinal $\kappa$ such that for every $\beta \in \kappa$ there is no one-to-one function from $\kappa$ to $\beta$.

Regular Cardinal

An infinite cardinal $\kappa$ where the cofinality $\text{cf}(\kappa) = \kappa$.

Singular Cardinal

An infinite cardinal $\kappa$ where the cofinality $\text{cf}(\kappa) \in \kappa$.

Club Set

A set that is both closed and unbounded in a limit ordinal $\kappa$.

Stationary Set

A subset $S$ of a regular uncountable cardinal $\kappa$ that has a nonempty intersection with every club set in $\kappa$.

Regressive Function

A function $f : \kappa \rightarrow \kappa$ such that $f(\alpha) \in \alpha$ for all $\alpha \in S \setminus \{0\}$.