Set

A set is a collection of distinct objects regarded as its set elements. Membership, written $a\in A$, is the basic question: is $a$ one of the objects in $A$? For example, $\{1,2,2\}=\{1,2\}=\{2,1\}$: repeated entries and their written order do not change a set. A multiset retains multiplicities, while a tuple retains positions as well. Choosing the right object therefore determines which distinctions the mathematics remembers.

A set can collect possible outcomes of a probability space, vertices of a graph, or allowed inputs of a function. The empty set contains none; a subset selects members of a previously given set; the power set collects every such selection. These constructions are useful because they can be stated once and reused regardless of what the members represent. In an axiomatic account, rules such as the axiom schema of separation specify which collections exist as sets.

An equality between sets expressed in terms of arbitrary input sets that holds for every allowed choice of those inputs. A double inclusion proof proves a set identity by proving both set inclusions. Membership equivalences give another proof: the expressions are equal if and only if each element belongs to either both or neither.

The solution set of a mathematical condition $P$ in a specified domain $D$ collects every allowed value that satisfies it:It describes the answer without committing to the steps used to find it. For the equation $x^2=1$ over the real numbers, the solution set is $\{-1,1\}$; restricting to positive real numbers leaves $\{1\}$. For $2x=1$, the solution set is $\{1/2\}$ over the rational numbers and the empty set over the integers. The domain is part of the question.

An equation can have one solution, several solutions, no solutions, or an entire domain of solutions. Over the real numbers, $2x+3=9$ gives the singleton set $\{3\}$, $x^2+1=0$ gives the empty set, and the mathematical identity $(x+1{)}^2=x^2+2x+1$ gives the whole real line. Changing that second equation's domain to the complex numbers gives $\{-i,i\}$. The elementary definition by values that satisfy an equation and the classification by solution sets appear in College Algebra 2e, §2.2: Solving Linear Equations in One Variable.

Requiring several conditions simultaneously takes the intersection of their solution sets. The squared equation $x=(x-2{)}^2$ has solution set $\{1,4\}$. Adding the restriction $x\ge 2$ giveswhich is also the solution set of $\sqrt{x}=x-2$. The extraneous solution example explains why the sign restriction is needed. Requiring at least one of several conditions instead takes their union. This turns logical combinations of constraints into reusable operations on sets.

For several variables, a solution is an ordered assignment, usually represented by a tuple. The real equation $x+y=1$ has solution set $\{(t,1-t):t\in \mathbb{R}\}$, a straight line in the Euclidean plane with coordinates $(x,y)$. Adding $x-y=0$ intersects that straight line with another, leaving the single tuple $(1/2,1/2)$. A system of linear inequalities has no solution exactly when the intersection of its individual solution sets is the empty set. For optimization constraints, this common solution set is the feasible region.

Because a solution set is a set, the order in which its members are listed is irrelevant. The multiple root of $(x-1{)}^2=0$ is still the one solution $1$; its multiplicity of a root is additional polynomial information, rather than a second occurrence inside the solution set. Equivalent equations preserve the solution set on the stated domain, even if their algebraic forms differ.

A cover of a set $E$ is a family of sets whose union contains $E$. The members may overlap and may include points outside $E$; intersecting each member with $E$ gives a cover by its subsets. An open cover requires its members to be open sets. In Hausdorff measure, countable covers with a bound on each member's diameter determine geometric size. Constructing one inexpensive cover supplies an upper bound, while a lower bound must control all allowed covers.

A set element is an object belonging to a set. The statement $a\in A$ asserts membership; $a\notin A$ denies it. Membership differs from inclusion: $a\in A$ concerns one member, whereas $B\subseteq A$ asserts that every set element of $B$ belongs to $A$.

A partition of a set $X$ is a family of pairwise disjoint nonempty subsets whose union is $X$. Every equivalence relation defines a partition into equivalence classes, and conversely belonging to the same cell of a partition defines an equivalence relation. The nonempty colour classes of a finite colouring form a finite partition.

A colouring assigns to each member of a set $X$ a colour in another set $C$. Its nonempty fibres form a partition of a set. The colour set may be infinite; a finite colouring is the special case with finitely many colours. A homogeneous set for a colouring of finite subsets has all its subsets of the specified size assigned one colour.

A subset $A$ of a specified ambient set $X$ is coinfinite if its complement of a set $X\setminus A$ is infinite. In $\mathbb{N}$, the even numbers are both infinite and coinfinite, whereas a cofinite set is not coinfinite.

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.

In ZF, an injection $h:\omega \to X$ yields an injective nonsurjective self-map by shifting $h(n)$ to $h(n+1)$ and fixing the complement. Conversely, if an injection $g:X\to X$ omits $a$, the natural-number recursion theorem defines $h(n)=g^n(a)$. Any repetition would, after cancellation, put $a$ in the image of $g$. Thus $h$ is injective. The argument uses no axiom of choice, even when some infinite sets are Dedekind-finite sets.

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 set difference $A\setminus B$ keeps the set elements of $A$ that do not belong to $B$:Thus set difference combines logical conjunction (AND) with logical negation (NOT): pass the first condition and fail the second. The definition applies to any two sets; $B$ need not be a subset of $A$.

For $A=\{1,2,3\}$ and $B=\{3,4\}$, the two orders give different answers:The common member $3$ is removed in both directions. A database filter illustrates the usefulness: if $A$ is the set of records matching the first condition and $B$ the set matching the second, $A\setminus B$ selects records matching the first but not the second. The Venn diagram in set union shades both directions separately.

The name relative complement emphasizes that the ambient set is $A$: $A\setminus B$ is the complement of $A\cap B$ within $A$. If a larger universal set $U$ contains $A$ and $B$, then $A\setminus B=A\cap (U\setminus B)$. Changing that larger universal set does not change the set difference, because membership still requires belonging to $A$. In ZF the set difference exists by the axiom schema of separation. It also gives relative complements within a fixed tuple domain in finite relation closure for set-theoretic coding.

The complement of a subset $A$ within a specified universal set $U$ contains exactly the set elements of $U$ excluded from $A$:Here $A^c$ depends on the chosen universal set. Within $U$, taking a complement performs logical negation (NOT) on membership. Writing $U\setminus A$ keeps the ambient set visible when there could be ambiguity.

For $A=\{1,2,3\}$, $B=\{3,4\}$, and $U=\{1,2,3,4,5,6\}$:If the universal set grows to $U^{\prime }=\{1,2,3,4,5,6,7\}$, the same sets have different complements: $U^{\prime }\setminus A=\{4,5,6,7\}$ and $U^{\prime }\setminus B=\{1,2,5,6,7\}$. In a database illustration, “records that fail this condition” therefore requires deciding which records are eligible to begin with; those eligible records form $U$.

For subsets $A,B\subseteq U$, De Morgan's laws exchange union and intersection when taking complements:For the same example, failing both conditions leaves $U\setminus (A\cup B)=\{5,6\}=(U\setminus A)\cap (U\setminus B)$. Failing at least one condition leaves $U\setminus (A\cap B)=\{1,2,4,5,6\}=(U\setminus A)\cup (U\setminus B)$. This is useful for rewriting exclusion rules into separate membership tests. The symmetry is also pleasing: exchanging union with intersection turns one rule into its partner.

A brief membership proof works in classical propositional logic. For any $x\in U$, let $P$ mean $x\in A$ and $Q$ mean $x\in B$. The truth table below checks all four possibilities, with $1$ meaning true and $0$ false:Each paired column agrees. Translating logical disjunction (OR), logical conjunction (AND), and logical negation (NOT) back into membership proves the two set equalities. For the general method of reducing set equalities to equivalences in propositional logic, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), §4.1.5 and Problem 4.5.

A historical perspective appears in Augustus De Morgan's ^[ref]: he describes treating each name together with its contradictory name. In the membership viewpoint here, a set and its complement likewise pair a condition with its logical negation.

A universal set $U$ fixes the objects under consideration in a particular discussion; each set under consideration is a subset of $U$. For example, $U=\{1,2,3,4,5,6\}$ makes the complement of $\{1,2,3\}$ equal to $\{4,5,6\}$. This use of “universal” is local to the discussion: it does not assert the existence of a set containing every set. Stating $U$ makes exclusion rules precise.

A Venn diagram represents sets by closed curves, with each region recording a possible pattern of membership. For two sets, the regions mean “first only”, “both”, “second only”, and “neither”; the enclosing rectangle can represent the universal set. Shading regions displays union, intersection, set difference, or complement. In the numbered examples in set union and complement, positions encode membership, while curve shapes and region areas do not encode cardinalities.

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.

The operation adding multiset multiplicities pointwise. Its result retains all occurrences from both operands. Some sources use the name multiset union instead for pointwise maximum, so a contract should state which operation is meant.

The number of occurrences of $x$ in a multiset $M$, always a nonnegative integer for ordinary finite multisets.

The number of times a value occurs in observed data. Keeping 26 indexed counters for lowercase alphabet characters gives constant-time frequency queries independent of document length.

The function mapping each possible element to its multiset multiplicity. Finite multisets correspond to nonnegative functions with finite support of a multiset. A functional representation can answer queries without supporting enumeration of all elements.

A multiset of keys in a fixed finite integer range represented by one nonnegative count per key. The abstraction function extends the stored array counts by zero outside the range. Single-key additions, removals and queries use constant array work, provided overflow and operation preconditions are handled. Encapsulation of the count array is necessary to preserve its representation invariant.

Maintain a counter equal to the number of positive count-array entries. Increment it only when an addition changes zero to one; decrement it only when a removal changes one to zero. Other count changes leave the support unchanged. Initialization at zero and these cases prove the representation invariant by induction over completed operations, giving a constant-time distinct-size query.

The set of keys with positive multiplicity. Its cardinality counts distinct keys, whereas summing the multiplicities counts all occurrences. A count-array implementation can maintain the support cardinality by tracking only zero-to-positive and positive-to-zero transitions.

A finitely supported function $m:T\to \mathbb{Z}$, allowing negative as well as positive multiplicities. Missing keys denote zero. Addition, exact subtraction, pointwise maximum/minimum and pointwise order can be implemented over the union of operand supports. A nonnegative multiset is a refinement, but exact subtraction can leave that refinement while still producing a signed multiset. Fixed-width count implementations must also specify overflow behavior.

The common multiplicity of two multisets, summing the smaller multiplicity of each value. To return an order-preserving overlap of two finite lists, scan the first list and consume one equal item from the second whenever available. Each token can be consumed at most once, so the resulting subsequence has maximum possible length among those that occur in a permutation of the second list.

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$, including the empty set and $X$ itself. It is useful whenever an object is a selection rather than an individual member: a possible collection of active vertices in a graph, for example, belongs to the power set of the vertex set.

For $X=\{a,b,c\}$, the power set has eight members:Each of the three set elements is either included or excluded. More generally, if $|X|=n<\infty$, these $n$ independent binary choices give $|\mathcal{P}(X)|=2^n$. This is a bijection between subsets and binary strings of length $n$, not a probabilistic independence assumption.

Ordering the subsets by inclusion gives a Boolean lattice. In the picture an upward edge adds one member. Complementation reverses inclusion, and union and intersection combine selections. The empty-input case is worth checking: $\mathcal{P}(\varnothing )=\{\varnothing \}$ has one member, not zero, consistently with $2^0=1$.

For arbitrary sets $A,B$ each containing at least two elements, the displayed inequality follows by explicitly encoding two subsets in disjoint parts of a Cartesian product. Choose $a_0\ne a_1$ and $b_0\ne b_1$, put $S$ along the row $A\times \{b_0\}$, put $T\setminus \{b_0\}$ along the column $\{a_0\}\times (B\setminus \{b_0\})$, and add the extra point $(a_1,b_1)$ precisely when $b_0\in T$. These regions are disjoint, so the encoding recovers both $S$ and $T$ and is an injection from $\mathcal{P}(A)\times \mathcal{P}(B)$ into $\mathcal{P}(A\times B)$. This proves the cardinality inequality even for infinite sets. For finite sizes $a,b\ge 2$, the same result is $2^{ab}\ge 2^{a+b}$, since $ab-a-b=(a-1)(b-1)-1\ge 0$. Mapping $(S,T)$ to $S\times T$ is insufficient because all pairs with an empty factor collapse.

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$.

For any candidate function $f:X\to \mathcal{P}(X)$, form $D=\{x\in X:x\notin f(x)\}$. This is a subset of $X$ by set comprehension. If $f(d)=D$, then $d\in D$ holds exactly when $d\notin D$, a contradiction. Thus $D$ is missing from the image of $f$. On the other hand, $x\mapsto \{x\}$ is an injection from $X$ into its power set, establishing the strict comparison of cardinalities. For $X=\mathbb{N}$, the omitted selection is the subset version of Cantor's diagonal argument.

For each natural number $n$, the family $[A{]}^n$ of all $n$-element subsets is nonempty when $A$ is not finite. These families are pairwise distinct elements of $\mathcal{P}(\mathcal{P}(A))$, giving an explicit injection of the natural numbers. No representative from each family is selected. A power set cannot be countably infinite in ZF: if $\mathcal{P}(B)$ were countably infinite, singleton injection would make $B$ an infinite subset of a countable set and hence countably infinite; Cantor's theorem would then contradict countability of its power set. Apply this to $B=\mathcal{P}(A)$ to make the displayed lower bound strict.

A finite set is a set with finitely many elements.

The property of being a finite set. In a finite set, an injective self-map is surjective; this implication can fail for an infinite set.

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$.

A set $B$ is a superset of $A$ when $A$ is a subset of $B$, meaning that every element of $A$ belongs to $B$. Equality is permitted; a proper superset additionally differs from $A$.

Set inclusion $C\subseteq D$ means that every set element of the set $C$ also belongs to the set $D$. Strict set inclusion additionally requires $C\ne D$. A maximal clique cannot grow through strict set inclusion, while a maximum clique maximizes cardinality.

To prove equality of two sets, show each set inclusion separately. If both inclusions hold, every element belongs to one set exactly when it belongs to the other; the axiom of extensionality gives equality. Each direction may use different hypotheses. For example, when $x\in A$, the condition $x\notin A\setminus B$ implies $x\in B$; without $x\in A$, that inference would be invalid.

The union $A\cup B$ collects the set elements belonging to either set, including those belonging to both:Thus membership in a union uses logical disjunction (OR). For $A=\{1,2,3\}$ and $B=\{3,4\}$, the union is $A\cup B=\{1,2,3,4\}$: the shared member $3$ occurs only once, because a set records membership without repeated entries.

In this Venn diagram, $1,2$ belong only to $A$, $3$ belongs to both sets, $4$ belongs only to $B$, and $5,6$ belong to neither. The surrounding universal set is $U=\{1,2,3,4,5,6\}$. Numbers are placed by membership; circle areas do not represent cardinalities. Each panel shades the region selected by its operation.

For a database illustration, let $A$ collect records matching one condition and $B$ collect records matching another. Their union selects records matching at least one condition, with a record satisfying both still appearing once. This interpretation turns an abstract operation into a reusable rule for combining selections. For an authored treatment of union, intersection, set difference, and complement, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), Definition 4.1.1, pp. 82–83.

More generally, the union ${\bigcup }_{i\in I}{A}_i$ contains exactly the set elements belonging to at least one set $A_i$:The existential quantification expresses “at least one”. With no indexing members, the union is the empty set. Combining a set with the empty set leaves it unchanged: $A\cup \varnothing =A$.

The union of an empty family of sets is the empty set: membership would require a member of that family containing the proposed set element, and there are no members.

A finite union is a union of finitely many sets. The indexing set is finite; its member sets need not be finite sets. The union of an empty indexed family is the empty set.

The union of a sequence of sets: an element belongs to it exactly when it belongs to at least one $A_n$.

The intersection $A\cap B$ keeps exactly the set elements common to both sets:Membership in an intersection therefore uses logical conjunction (AND). For $A=\{1,2,3\}$ and $B=\{3,4\}$, the only shared member is $3$, so $A\cap B=\{3\}$. The Venn diagram in set union shades only the overlap for this operation.

An intersection is useful when every requirement must hold. If $A$ and $B$ are the sets of database records passing two separate conditions, their intersection gives the records passing both. Similarly, satisfying two equations requires belonging to the intersection of their solution sets. The same membership rule applies even when the objects have entirely different meanings.

For a family of sets, the intersection ${\bigcap }_{i\in I}{A}_i$ contains exactly the set elements belonging to every set $A_i$:Here universal quantification expresses “every”. If all the sets lie within a fixed universal set $U$, the intersection over no indexing members is defined to be $U$: there are no requirements to fail. This convention depends on specifying $U$. By contrast, intersecting with the empty set always gives $A\cap \varnothing =\varnothing$.

A finite intersection is an intersection of finitely many sets. The indexing set is finite, regardless of the size of the intersected sets. For an empty indexed family of subsets of a specified ambient set $X$, the convention is that the intersection equals $X$.

Two sets are disjoint when their intersection is the empty set: $A\cap B=\varnothing$.

The countable intersection of a sequence of sets contains exactly the elements belonging to every set. De Morgan's laws identify its relative complement with the union of their complements.

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

Two sets differ by finite symmetric difference when only finitely many points belong to exactly one of them. This is an equivalence relation, since $A△C\subseteq (A△B)\cup (B△C)$.

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

An ordered pair is a pair with distinguished first and second positions; an unordered pair does not record those positions.

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.

Reachability in a directed graph, allowing length-zero paths, is a preorder: zero steps give reflexivity and concatenation gives transitivity. Distinct mutually reachable vertices violate antisymmetry. Its equivalence classes under mutual reachability are the strongly connected components; the induced reachability relation on those classes is a partial order. Equivalently, contracting the classes gives the acyclic condensation graph.

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.

Every infinite sequence in a well-quasi-ordering has an infinite subsequence all of whose earlier terms precede its later terms. Some term must have infinitely many later terms above it: otherwise choose each new index outside the finitely many upper-cone index sets of the terms already chosen, producing a bad sequence. Apply the same observation successively inside the infinite upper-cone subsequence. Each restriction preserves all earlier inequalities, proving the assertion.

A finite Cartesian product of well-quasi-orderings is well-quasi-ordered in the componentwise order. Every infinite sequence in one well-quasi-order has an infinite nondecreasing subsequence: colour pairs by whether they are ordered, apply Ramsey's theorem, and exclude an all-bad subsequence. Restrict successively to such a subsequence in each coordinate. The same argument, or the infinite pigeonhole principle, proves closure under finite disjoint unions with no cross-component comparisons.

A quasi-order is better-quasi-ordered if every array into it from every barrier in better-quasi-order theory is good: some barrier members $s◃t$ satisfy $f(s)\le f(t)$. Singleton barriers recover the usual infinite-sequence condition for a well-quasi-ordering. The stronger condition is useful for infinitary closure operations for which well-quasi-ordering alone fails. Equivalently one may use continuous maps from infinite subsets of an infinite subset of the natural numbers, with the discrete topology on the range, and compare $X$ with $X\setminus \{\min X\}$.

If $Q$ is a better-quasi-ordering, its full power set is better-quasi-ordered by the Hoare domination preorder. A bad continuous array of subsets would allow a choice of $q_X\in A_X$ not below any member of $A_{X^{-}}$, where $X^{-}$ deletes the least element. Choose this witness as a fixed function of the two locally constant subsets. Then $X\mapsto q_X$ is a bad continuous array in better-quasi-order theory into $Q$, a contradiction. Empty source subsets cannot occur in a bad array because they precede every subset.

A continuous array takes infinite subsets of an infinite $A\subseteq \omega$, in the ordinary topology on infinite subsets, to a discrete preorder $Q$. It is bad if $F(X)\nleqq F(X\setminus \{\min X\})$ for every infinite $X$. A barrier in better-quasi-order theory array induces such a continuous array by evaluating its unique barrier initial segment. The continuous-array and barrier formulations of better-quasi-ordering are equivalent, using refinement of fronts to barriers in the reverse direction.

A barrier on an infinite $A\subseteq \mathbb{N}$ is a family of nonempty finite increasing sequences, viewed as finite subsets, no one contained properly in another, such that every infinite subset of $A$ has a member of the family as an initial segment. Write $s◃t$ if there is a finite increasing sequence $u$ of which $s$ is an initial segment and of which $t$ is an initial segment after its first term is deleted. This shift relation underlies the good-array definition of better-quasi-ordering.

Every finite coloring of a barrier in better-quasi-order theory has an infinite restriction on which all barrier members have the same color. It extends finite-dimensional Ramsey's theorem from fixed-length subsets to variable-length initial segments. A proof proceeds by well-founded induction on the initial-segment tree and a fusion construction selecting successively nested infinite tails. It implies that every finite set with the equality order is a better-quasi-ordering. The barrier/front partition proof is given in Section 3.2 of arxiv.org/pdf/1604.05866 .

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.

The barrier in better-quasi-order theory $[\omega {]}^2$ has shifts $\{m,n\}◃\{n,l\}$ for $m<n<l$. Map each pair to the corresponding element of the Rado order. Neither clause of $(m,n){\le }_R(n,l)$ holds: the first coordinates differ, and the second coordinate of the first pair equals, rather than precedes, the first coordinate of the second. Thus this array is bad, although the Rado order is a well-quasi-ordering. It separates better-quasi-ordering from 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.

Every subset having an upper bound has a least upper bound. If the empty subset is included, a nonempty such partially ordered set has a least element. This condition differs from a directed-complete partial order: a directed set need not have an upper bound.

A partially ordered set in which, for every $x$, the elements way-below $x$ form a directed set with least upper bound $x$. Directed least upper bounds other than these approximating ones need not exist.

A partially ordered set in which the compact elements below each element form a directed set with that element as their least upper bound.

Let $K_x$ be the directed set of compact elements below $x$, with least upper bound $x$, and put $A_x=\{y:y\ll x\}$. A compact element $k\le x$ belongs to $A_x$: a directed set whose least upper bound is at least $x$ also has least upper bound at least $k$, so the definition of $k\ll k$ supplies an element above $k$. Hence $K_x\subseteq A_x$.

If $y_1,y_2\in A_x$, apply the way-below relation to $K_x$ to find $k_1,k_2\in K_x$ above them. Since $K_x$ is directed, it contains a common upper bound $k$ for $k_1,k_2$. This $k$ belongs to $A_x$, proving that $A_x$ is directed. Every member of $A_x$ is below $x$, while $K_x\subseteq A_x$ has least upper bound $x$. Therefore $x$ is the least upper bound of $A_x$, which is the defining property of a continuous poset.

A continuous poset that is also a directed-complete partial order.

Give the real interval $[0,1]$ its usual total order. Every nonempty directed set has a least upper bound in the real interval, so it is a directed-complete partial order. If $x<y\le \sup D$, some $d\in D$ exceeds $x$; otherwise $x$ would be an upper bound for $D$. Also $0\ll 0$, since every member of a nonempty $D$ is at least zero. For $x>0$, the increasing sequence $x(1-1/n)$, $n\ge 1$, has least upper bound $x$ but never reaches it, so $x/\ll x$. Together with $x\ll y\Rightarrow x\le y$, this proves the displayed way-below relation.

For each $y>0$, the elements way-below $y$ form $[0,y)$, a directed set with least upper bound $y$; for $y=0$ they form $\{0\}$. Thus this is a continuous poset. Its only compact element is zero, so it is not an algebraic partially ordered set.

In a partially ordered set, $x\ll y$ means that every nonempty directed set $D$ whose least upper bound exists and satisfies $y\le \sup D$ contains some $d$ with $x\le d$. Taking $D=\{y\}$ shows that $x\ll y$ implies $x\le y$; the converse need not hold. Some formulations quantify over the empty directed set as well; this changes the behaviour at the least element and must be specified.

An element that is way-below itself.

The partial order on nonempty closed integer intervals given by subset inclusion. The least upper bound of two such intervals is their interval hull $[\min (l,l^{\prime }),\max (u,u^{\prime })]$. The hull can contain points absent from both original intervals, so it need not equal their union.

A subset $U$ of a partially ordered set is an upper set when $x\in U$ and $x\le y$ imply $y\in U$. The upward closure $\uparrow A=\{y:\exists a\in A,a\le y\}$ is the smallest upper set containing $A$. Both union and intersection preserve this property.

An upper set generated by a finite set $A$ is represented by the minimal elements of $A$. Removing a nonminimal generator preserves the upward closure. If each pair has a least upper bound, then $\uparrow A\cap \uparrow B=\uparrow \{a\vee b:a\in A,b\in B\}$, so finite generators support intersection without enumerating the potentially infinite represented sets.

An irreflexive transitive comparison whose induced incomparability relation is transitive. Incomparability is then an equivalence relation, and its classes are totally ordered by the comparison. A comparison-based sorting algorithm can treat incomparable elements as ties; a merge algorithm that takes from the left input on ties preserves stable sorting. Ordinary ordering on real numbers is an example; machine NaN values require separate handling.

Given a partially ordered set $B$ and a set $A$, the pointwise order on the function space of functions $A\to B$ compares their values at every argument. It is a partial order: reflexivity and transitivity hold at every argument, and antisymmetry follows because two functions equal at every argument are equal. Even if $B$ has a total order, this function space need not: the two functions on $\{0,1\}$ with values $(0,1)$ and $(1,0)$ are incomparable when $B=\mathbb{R}$.

Take disjoint antichains $P,C$ and place every element of $P$ below every element of $C$. Together with equality these comparisons define a partial order: a strict step always moves from $P$ to $C$, so there cannot be a strict two-step path or a reverse comparison.

If both levels have at least two elements, a subset $S$ has an upper bound exactly when it contains at most one element of $C$. When it contains one such element $c$, that element is its maximum and its only upper bound. A singleton $\{p\}\subseteq P$ has maximum and least upper bound $p$. A subset of $P$ with at least two elements has all of $C$ as upper bounds and has no least upper bound, because these elements are incomparable. The empty subset has all of $P\bigsqcup C$ as upper bounds and has no least upper bound. These cases prove the complete classification.

A Hasse diagram draws a finite partially ordered set using one point for each element and an upward line from $x$ to $y$ for each cover relation $x\prec y$. It omits reflexive loops and comparisons already implied by paths. Line crossings are not additional elements. In a finite partially ordered set, following upward paths recovers exactly the original comparisons. The diagram is named after Helmut Hasse.

In a partially ordered set, $y$ covers $x$ when $x<y$ and there is no $z$ with $x<z<y$. Thus a cover relation records an immediate increase, rather than every comparable pair. For a finite partially ordered set, every strict comparison can be obtained by chaining cover relations.

A subset $I$ of a partially ordered set such that $x\in I$ and $y\le x$ imply $y\in I$. Thus membership forces all smaller elements to belong as well. This definition concerns an order, rather than an ideal of a ring.

For an order ideal in a finite rectangular grid with coordinatewise partial order, occupied cells in each row form a left prefix. Their lengths form a nonincreasing sequence $r_y$. Conversely, any nonincreasing sequence of valid row lengths specifies exactly one such order ideal, giving an abstraction function with no redundant per-cell information.

Removing all occupied cells with $x\ge a$ and $y\ge b$ replaces $r_y$ by $\min (r_y,a)$ for $y\ge b$ and leaves earlier rows unchanged. The new lengths remain nonincreasing: affected rows preserve their mutual order, and the first affected row only decreases. For a legal removal, the boundary immediately below it was already at least $a$. A cached sum of row lengths can be updated by subtracting the decreases. This yields constant-time membership and count queries, linear storage, and an update linear in the number of affected rows.

A downward-closed subset of a finite product grid can be represented by nonincreasing column heights. Occupancy is $0\le y<h(x)$; the condition $h(0)\ge \cdots \ge h(N-1)$ is exactly closure toward smaller coordinates. Removing the northeast rectangle anchored at a legal $(x,y)$ truncates each height to its right to $\min (h(i),y)$, preserving closure. This represents a potentially quadratic number of occupied cells using a linear number of boundary values.

The zeta transform on a finite partially ordered set sends $f$ to $F(x)={\sum }_{y\le x}f(y)$. The subset zeta transform is the case where the order is inclusion of subsets.