Set

A set is a collection of distinct objects regarded as its elements.

A set $X$ is Dedekind-finite when no injective function $\mathbb{N}\to X$ exists. In classical Zermelo–Fraenkel set theory this is equivalent to $X$ not being in bijection with a proper subset: an injective non-surjective self-map generates distinct iterates from an element outside its image, and a countably infinite subset permits a shift fixing its complement. A finite set is Dedekind-finite. Without the axiom of choice, some infinite sets can also be Dedekind-finite.

If $X$ is a Dedekind-finite set, its set of finite repetition-free sequences is also Dedekind-finite. An injective sequence of distinct finite lists would, by countable union of explicitly ordered finite lists without choice, either produce an injection $\mathbb{N}\to X$ or use only finitely many entries. The latter possibility is impossible because a fixed finite pool supports only finitely many repetition-free lists. If $X$ is infinite, the one-entry lists also show that the resulting set is infinite.

An infinite Dedekind-finite set is an infinite set with no subset that is a countably infinite set. The name Dedekind set is sometimes used for this combination of properties. Under the axiom of choice no such set exists; results about these sets must avoid obtaining arbitrary enumerations of finite subsets by unstated choices.

The difference consists of the elements of $A$ not belonging to $B$. In ZF it exists by axiom schema of separation. It gives complements relative to a fixed tuple domain in finite relation closure for set-theoretic coding.

A pointed set is a set $X$ with a distinguished element $x_0\in X$. A morphism of pointed sets is a function carrying the distinguished element to the distinguished element. The resulting category of pointed sets has every singleton as a zero object.

A multiset records a nonnegative integer multiplicity for each element of a set. A finite multiset has finite support and finite total multiplicity. Its cardinality is the sum of its multiplicities; its disjoint union with another multiset adds multiplicities. The hook lengths of a Young diagram form a multiset, since different cells can have equal lengths.

A family of sets $(A_t)$ indexed by an partially ordered set is nondecreasing when

The power set $\mathcal{P}(X)$ is the set of all subsets of $X$.

There is no surjection from a set $X$ onto its power set $\mathcal{P}(X)$. Consequently $\mathcal{P}(X)$ has strictly greater cardinality than $X$.

A finite set is a set with finitely many elements.

An infinite set is a set with infinitely many elements. Equivalently, assuming the axiom of choice, it contains a countably infinite set.

The empty set has no elements.

A singleton set has exactly one element.

Elements are distinct when they are unequal.

A generating set is a subset from which every element of a structure can be obtained using the structure's operations.

A set $A$ is a subset of $B$ when every element of $A$ belongs to $B$.

The union ${\bigcup }_{i\in I}{A}_i$ contains exactly the elements that belong to at least one set $A_i$.

The intersection ${\bigcap }_{i\in I}{A}_i$ contains exactly the elements that belong to every set $A_i$.

The symmetric difference $A△B=(A\setminus B)\cup (B\setminus A)$ contains the elements belonging to exactly one of the two sets.

A pair is a collection of two objects. An ordered pair records which object is first, whereas an unordered pair does not.

This representation of an ordered pair by sets satisfies $⟨a,b⟩=⟨c,d⟩$ exactly when $a=c$ and $b=d$. Its intersection recovers $\{a\}$, and its union recovers $\{a,b\}$; if the latter is a singleton then $b=a$. Its rank of a set is $\max (\mathrm{rank}(a),\mathrm{rank}(b))+2$, which bounds the ranks of function graphs in absoluteness of cardinalhood in limit ranks.

A preorder is a set equipped with a reflexive and transitive relation; unlike a partial order, distinct elements may be mutually comparable in both directions.

For subsets of a preorder, Hoare domination means every source element has some greater or equal target element: $S{\le }_{H}T⟺\forall s\in S\exists t\in T(s\le t)$. It is reflexive and transitive. If the base is a well-quasi-ordering, its finite subsets are well-quasi-ordered by this relation; arbitrary subsets need not be, as the Rado order shows.

Finite subsets of a well-quasi-ordering, compared by Hoare domination preorder, form a well-quasi-ordering. Enumerate each finite subset as a word and apply Higman lemma: a subsequence embedding with increased letters supplies a domination witness for every source element. This does not assert the same result for the full power set.

A preorder is a well-quasi-ordering if every infinite sequence has indices $i<j$ with $x_i\le x_j$. An infinite sequence with no such pair is a bad sequence. This formulation handles combinatorial embedding relations that need not be antisymmetric on syntactic codes.

The Rado order has domain $R=\{(m,n)\in {\mathbb{N}}^2:m<n\}$ and $(m,n){\le }_R(k,l)$ iff either $m=k$ and $n\le l$, or $n<k$. It is a well-quasi-ordering: either one row recurs infinitely in a sequence, or the first coordinates are unbounded and yield a cross-row comparison. Its infinite rows form an infinite antichain under Hoare domination preorder, showing that arbitrary-subset lifting need not preserve well-quasi-ordering.

If $Q$ is a well-quasi-ordering, its finite words form a well-quasi-ordering under subsequence embedding with coordinatewise increase of letters. A minimal bad sequence proof removes the last letter of selected words whose last letters form a nondecreasing subsequence, then contradicts minimality. The result implies finite-subset lifting of a well-quasi-order under Hoare domination preorder.

A bad sequence in a preorder is an infinite sequence with no indices $i<j$ satisfying $x_i\le x_j$. A preorder is a well-quasi-ordering precisely when no such sequence exists.

A minimal bad sequence chooses each successive object of least possible natural-number size among choices that admit an infinite bad continuation of the already fixed prefix. Replacing its next object by a strictly smaller one cannot leave a bad sequence. This contradiction principle proves Higman lemma and the labelled version of Kruskal's tree theorem.

Given a size bound with finitely many possible objects at each position, put finite bad sequences in a tree ordered by extension. The tree is finitely branching. Arbitrarily long bad sequences would give an infinite bad sequence by König infinity lemma. This compactness argument converts an infinite well-quasi-ordering theorem into a uniform finite length bound.

Finite rooted trees are well-quasi-ordered by rooted-tree homeomorphic embedding. Consequently every infinite sequence contains an earlier tree embedding into a later one. Size-controlled finite forms follow by applying König infinity lemma to the finitely branching tree of bad prefixes.

Finite rooted trees labelled in a well-quasi-ordering are a well-quasi-ordering under label-monotone tree embedding. A minimal bad sequence argument makes the collection of proper rooted subtrees a well-quasi-ordering; Higman lemma then compares their child lists while the root labels are compared in the label order.

For every natural parameter $k$, there is a finite length $N$ such that every sequence of $N$ finite rooted trees satisfying $|T_i|\le k+i$ has an earlier tree homeomorphically embedding into a later tree. It is a true finite-combinatorial principle unprovable in Peano arithmetic and in arithmetical transfinite recursion theory. Each fixed-parameter instance can still be verified by a sufficiently large finite search.

A partially ordered set, or poset, is a set equipped with a reflexive, antisymmetric and transitive binary relation.

A partial order in which the strict predecessors of each node form a well-order. The height of a node is the order type of its predecessors; nodes of a common height form a level. This order-theoretic meaning is distinct from a graph-theoretic tree.

A tree is splitting if every node has two incompatible extensions. This property is additional to height and level-size bounds in a kappa-tree. A cofinal branch through a splitting tree of regular uncountable height produces an equally large antichain by taking off-branch extensions and proceeding beyond their divergence heights. Thus a splitting ${\omega }_1$-tree with countable antichains has no uncountable chains; the nonsplitting chain ${\omega }_1$ itself is a counterexample to omitting splitting.

At a limit level, two nodes with the same predecessor at every smaller level must be equal. This is a uniqueness condition; it need not provide an upper node for every cofinal branch through the lower levels.

Every node has an extension at every higher level below the height of the set-theoretic tree. Equivalently, its extension heights are unbounded in the set-theoretic tree height. Having no terminal nodes alone is weaker.

For a kappa-tree, retain nodes whose extension heights are unbounded in $\kappa$. The retained nodes are predecessor-closed. Each level remains nonempty: otherwise regularity would bound the union of fewer than $\kappa$ bounded extension sets. The same argument above a retained node ensures retained extensions at every later level. Singular height invalidates this proof and the unrestricted conclusion.

For a regular uncountable cardinal number $\kappa$, a set-theoretic tree of height $\kappa$ with nonempty levels of cardinality less than $\kappa$. The regular-height convention is important for the unbounded-extension kernel of a regular tree.

For infinite regular cardinals $\kappa <\lambda$, a $\lambda$-tree whose levels all have size less than $\kappa$ has a cofinal branch. At levels of cofinality $\kappa$, bound all heights distinguishing distinct predecessor chains. The Fodor lemma makes this bound constant on a stationary set; one predecessor at that height occurs stationarily often. The resulting predecessor chains agree below their common heights and unite into a branch through every level. Distinct limit-level nodes with identical predecessor chains do not affect this argument.

A set-theoretic tree of height ${\omega }_1$ with countable levels and at least ${\aleph }_2$ distinct cofinal branches.

Let $\kappa$ be strongly inaccessible cardinal in the ground model and perform the finite Lévy collapse to omega-one. The ground full binary set-theoretic tree of height $\kappa$ has all levels of size less than $\kappa$, so these levels become countable. Its at least $({\kappa }^{+}{)}^M$ ground branches remain distinct. The chain in a partial order condition preserves $({\kappa }^{+}{)}^M$, which is the extension ${\aleph }_2$. The unchanged ground set-theoretic tree therefore witnesses the Kurepa hypothesis.

There exists an ${\omega }_1$-tree with countable levels and at least ${\aleph }_2$ distinct cofinal branches.

There is $\mathcal{F}\subseteq \mathcal{P}({\omega }_1)$ of size ${\aleph }_2$ such that $\{X\cap \alpha :X\in \mathcal{F}\}$ is countable for every $\alpha <{\omega }_1$. Its initial-segment tree, pruned and leveled to be normal, is a Kurepa tree.

A set-theoretic tree of height ${\omega }_1$ with countable levels and no cofinal branch. More generally, a $\kappa$-Aronszajn tree has height a regular uncountable $\kappa$, levels of size less than $\kappa$, and no cofinal branch.

Given coherent coinfinite injections into omega, use all restrictions $e_{\alpha }\upharpoonright \beta$, where $\beta \le \alpha <{\omega }_1$, ordered by proper extension. Every level is countable because its nodes differ finitely from a fixed function on a countable domain. An uncountable chain in a partial order would have unbounded domain heights, and its union would inject ${\omega }_1$ into $\omega$, which is impossible.

An Aronszajn tree with no uncountable tree antichain. A normal splitting Suslin tree yields a Suslin line by a lexicographic ordering followed by Dedekind completion.

A well-pruned set-theoretic tree that is an Aronszajn tree and a Suslin tree gives a forcing with the countable chain condition for forcing: stronger nodes extend weaker ones. The ${\omega }_1$ dense subsets of a forcing order of nodes at or above each level cannot all be met by a filter in an ordered set, since that would produce a cofinal branch. Thus ${\mathrm{MA}}_{{\aleph }_1}$ fails. When the continuum exceeds ${\aleph }_1$, full Martin axiom includes this instance.

An Aronszajn tree that is a union of countably many tree antichains. Equivalently, it admits a map into a countable set that is injective on each chain.

A set-theoretic tree of height ${\omega }_2$, levels of size at most ${\aleph }_1$, and no cofinal branch. The Continuum hypothesis supplies one through the minimal-walk tree.

A set-theoretic tree with one root, extensions of every node at every higher level, at least two immediate successors for every node, and distinct limit-level nodes distinguished by their predecessor chains. If splitting occurs only at later levels, a continuous cofinal selection of levels can enforce immediate splitting.

A maximal chain with nodes at unbounded heights in a set-theoretic tree. Taking predecessor closure gives one node at each level below the tree height.

A set of pairwise incomparable nodes in a set-theoretic tree. A maximal tree antichain has a comparable member for every node of the tree.

A subset of a partially ordered set on which the inherited order is total. The upper-bound hypothesis in Zorn lemma concerns all such subsets, not just countable increasing sequences.

A differential poset is a locally finite graded partially ordered set with a unique minimum, finite ranks, and up and down cover operators satisfying $DU-UD=rI$ for a fixed positive integer $r$. The Young lattice has $r=1$: distinct equal-rank diagrams have equally many common upper and lower covers, and each diagram has one more upper cover than lower cover.

If $DU-UD=I$, commuting every $D$ past every $U$ gives $(D+U{)}^{\ell }={\sum }_{i+j+2m=\ell }\ell !U^i{D}^j/(2^{m}i!j!m!)$. The recurrence follows from $D{U}^i=U^{i}D+i{U}^{i-1}$. Applied to the empty diagram in the Young lattice, it counts oscillating tableaux.

A filter is a nonempty upward-closed subset $G$ of a partial order such that every two members have a common lower bound in $G$. With standard notation for forcing, lower means stronger, so these are exactly the directed filters used to define a generic filter. The projection of a product-generic filter uses these properties before genericity of its factor filters is proved.

The principal filter in an ordered set generated by $p$ contains exactly the elements above $p$. It is upward closed, and $p$ is a common lower bound in the filter for any two of its members. With standard notation for forcing, these are the conditions weaker than $p$. The principal filter need not be a generic filter: a dense set can require a strict strengthening. The compatible-condition filter in a forcing atom determines a ground-model generic filter includes strengthenings as well as weakenings and can therefore be strictly larger.

A linear extension is a total ordering of the elements of a partially ordered set that preserves all its comparisons. For a finite set it can be recorded as a list. If two adjacent elements in that list are incomparable, their interchange is again a linear extension.

Two linear extensions of a finite partially ordered set can be joined using as many admissible adjacent swaps as the inversion count of their relative permutation. Label the current list by the desired positions in the target. An adjacent descent consists of incomparable elements, since comparable elements have the same order in both lists. Swap that descent; its inversion count decreases by one. Iteration sorts the list and gives a path of minimal Coxeter length.

An order-preserving function $f:P\to Q$ between partially ordered sets satisfies $x\le y\Rightarrow f(x)\le f(y)$.

The order dimension of a partially ordered set $(X,<)$ is the least cardinality of a family of total orders on $X$ whose intersection is $<$. Such a family is called a realizer of the partial order.

A partially ordered set is two-dimensional when there are two total orders ${<}_1$ and ${<}_2$ on its ground set such that

A partially ordered set is two-dimensional if every one of its finite induced suborders is two-dimensional. Encode two candidate total orders by propositional variables; every finite collection of the order, extension, and intersection clauses concerns a finite induced suborder, so the propositional compactness theorem supplies two global realizing orders.

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

An upper bound of a subset $A$ of a partially ordered set is an element $u$ satisfying $a\le u$ for every $a\in A$.

A directed set is a nonempty preorder in which every finite subset has an upper bound. It provides an index set in which any finite collection of stages has a common later stage.

An element $m$ of a partially ordered set is maximal when $m\le x$ implies $x=m$. A poset can have several maximal elements and need not have a greatest element.

An element $m$ of a partially ordered set is minimal when $x\le m$ implies $x=m$.

A total order is a reflexive, antisymmetric, transitive relation in which every two elements are comparable.

The topology generated by open intervals and open initial and final rays in a total order. For a dense order without endpoints, a subset is dense in this topology exactly when it meets every nonempty open interval.

Every pairwise disjoint collection of nonempty open intervals is countable. This is one of the defining properties of a Suslin line.

A subset of a total order meeting every nonempty open interval between two distinct points. A countable order-dense subset witnesses separability in the order topology of a dense order.

Every nonempty bounded-above subset of a total order has a least upper bound. In the real line this is the supremum property used to extend maps defined on an order-dense subset.

The completion of a total order by its nonprincipal proper cuts, supplying least upper bounds. For a dense order it contains the original order densely, and preserves the interval countable chain condition and separability or nonseparability.

An order isomorphism is a bijection preserving and reflecting the order relation. It transfers well-foundedness and order type between a coded order and its ordinal interpretation.

The order sum $A+B$ is the disjoint union of two total orders, preserving each order and placing every element of $A$ before every element of $B$. For example $\mathbb{N}+\mathbb{Z}$ has a least element but also has elements with infinitely many predecessors.

An order automorphism of a total order $(I,<)$ is a bijection $\pi :I\to I$ such that $i<j$ if and only if $\pi (i)<\pi (j)$. Composition and inverses are again order automorphisms. Transporting the indices of an order-indiscernible sequence by such a map preserves every first-order formula on increasing finite tuples.

An order-dense subset with no nonidentity order automorphism. A transfinite diagonal construction marks an included point and an excluded image for every nonidentity real-line order automorphism, yielding such a subset of size $2^{{\aleph }_0}$.

An order automorphism of an order-dense subset $D$ of the real line extends uniquely by $\tilde{\phi }(x)=\sup \{\phi (d):d\in D,d<x\}$. Order completeness supplies the extension, and the lower cuts in $D$ give uniqueness.

A strict total order is an irreflexive and transitive relation $<$ for which exactly one of $x<y$ and $y<x$ holds whenever $x\ne y$. It corresponds to a total order through $x\le y$ if and only if $x<y$ or $x=y$.

A well-order is a total order in which every nonempty subset has a least element.

A decidable well-order on the natural numbers is a well-order whose comparison relation is computable. Comparing two codes is an effective finite task; the proof that the relation has no infinite descending chain is a separate mathematical assertion. Computable Cantor normal form notation gives such an order of type epsilon zero.

The empty order is the unique total order on the empty set.

An element is greatest when every element of the ordered set is less than or equal to it.

An initial segment contains every element below each of its elements.