A commutative lattice-ordered group, usually written additively. Examples include real-valued function groups with pointwise addition, maximum and minimum. Such a group need not have a total order.
Archimedean linearly ordered groups are Abelian Created 2026-10-14 Updated 2026-11-05
An Archimedean ordered group with a two-sided invariant total order is commutative. If there is a least positive element, its cofinal powers exhaust the group. Otherwise each has with . To see this, choose and use if its square is below ; if not, the inequality gives . If positive satisfied , put and choose such a . Cofinality gives and . Two-sided order invariance then gives both and , a contradiction. Replacing negative elements by their inverses reduces arbitrary commutativity to the positive case.
Binary search tree Created 2026-10-13 Updated 2026-10-14
A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. [ref]
Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. [ref]
In the seven-key example, search for . At , the comparison selects the right subtree; at , selects the left subtree; at , equality ends the search. The visited keys are , three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of visits , five comparisons. Searching for absent key visits in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.
Figure 1.
Lookup of key in two binary search trees containing the same seven keys
. Orange highlights visited keys and edges; green marks the match. The balanced shape has height of a binary tree and requires three visits, while the chain has height of a binary tree and requires five visits for this target. Details.
For a nonempty binary search tree of height of a binary tree , lookup inspects at most vertices. Under constant-cost key comparisons and child-reference access, its time complexity is in Big O notation, usually written for . With entries, , giving worst-case lookup. If the shape is kept balanced so that , lookup takes for . The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. [ref]
In a shape with every level full, there are vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is , so it inspects six keys before finding , and an absent target requires all seven. Directed lookup uses the total order to choose one branch.
The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key , left child , right child , and right child under . Key must satisfy both , from its immediate parent in a rooted tree, and , from its position in the root's left subtree. Replacing by preserves all immediate parent-child comparisons, including , but violates . Lookup for would incorrectly go from to and then to an empty left subtree, overlooking the stored key.
Figure 2.
The binary search tree ordering rule constrains an entire subtree
. The valid example has . The invalid example passes immediate parent-child comparisons, but key lies in the left subtree of key and violates its inherited upper bound. Details.
An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is ; on the invalid example it is , exposing the descent from to . Both seven-key binary search trees yield . The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. [ref]
This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs time complexity for entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.
// Destination: computer-science.bigb
Binary tree Created 2026-10-13 Updated 2026-10-14
A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. [ref]
For example, give the root of a tree label , its left child label and its right child label . Attach as the left and right children in a rooted tree of , and as those of . This binary tree has seven vertices, six edges, and height of a binary tree : a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children , whose height of a binary tree is .
Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels and in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.
For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.[ref]
Figure 1.
Left and right binary tree child slots distinguish shapes even with just one child
. Solid circles are vertices; outlined squares mark empty binary tree child slots. The first two binary trees differ only in the occupied slot at . The last two have the same four labels but different height of a binary tree. Details.
In the four-vertex mixed example, has left child and right child , while has only a right child . Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus contributes , and contributes . The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.
Ignoring values, let count finite binary tree shapes with vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relation
For each left subtree size , choose its shape and the right subtree shape independently. This yields the Catalan numbers: , , and . The two shapes at are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.
There are at most continuum many binary relations on a countable set. For the matching lower bound, order the blocks by their index and independently choose the internal comparison in each block. A binary sequence determines those choices and distinct sequences give distinct labelled total orders. The resulting order types can all coincide; the count concerns relations, not isomorphism classes.
Ceiling function Created 2026-10-14 Updated 2026-10-20
The ceiling function gives the least integer large enough to meet a real lower bound. For a real number ,
Thus , , and . The operation rounds upward in the total order on the real numbers, which can move a negative input towards zero. Its difference from the input obeys . Python's math.ceil implements this least-integer definition. [ref].
The ceiling count for fixed-size batches is a direct application. Suppose each box holds at most items, with positive integer , and there are items. The smallest number of boxes with enough capacity is : a candidate count must satisfy . For , , six boxes are needed, leaving unused places. Exactly 100 items need only five boxes, and zero items need zero boxes. Adding one to the floor function result unconditionally would therefore overcount at exact multiples of .
Figure 1.
The ceiling function retains the endpoint on the left and counts enough whole containers
. Left: open and filled endpoints distinguish the half-open intervals where , including negative inputs. Right: the original capacity example uses 20 items per box; 101 items need six boxes, while an exact multiple of 20 needs no extra box. The right-hand inputs are integer item counts. Details.
For nonnegative integer and positive integer , Euclidean division gives the exact identity
Write , . The count is when the remainder is zero and otherwise, and the right-hand side encodes these two cases. This argument specifies the domain of the identity; arbitrary negative denominators require their own sign conventions.
The ceiling function is a nondecreasing function, constant on each of the half-open intervals , and has a discontinuity of a function at every integer. It is tied to the floor function by . Adding an integer shifts its output by the same amount: . At an integer the floor and ceiling agree; at every other input they differ by one. These statements refer to exact real numbers; an input already perturbed by floating-point arithmetic can land on the other side of a threshold.
Chain in a partially ordered set Created 2026-09-29 Updated 2026-10-14
A chain in a partially ordered set is a subset in which every two elements are comparable.
The order induced on this subset is a total order.
Give the real interval 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 , some exceeds ; otherwise would be an upper bound for . Also , since every member of a nonempty is at least zero. For , the increasing sequence , , has least upper bound but never reaches it, so . Together with , this proves the displayed way-below relation.
For each , the elements way-below form , a directed set with least upper bound ; for they form . Thus this is a continuous poset. Its only compact element is zero, so it is not an algebraic partially ordered set.
Dedekind completion 2026-10-06
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.
Dense order 2026-10-14
A total order is dense when between every two distinct ordered points lies a third. Endpoints are allowed; “without endpoints” is an additional condition. A dense order with two points cannot be a well-order, since is nonempty and has no least member. Its first-order axioms are the total-order axioms plus . Countability and uncountability are not first-order axiomatizable restrictions, by the upward and downward witness constructions of the Löwenheim-Skolem theorem.
Ehrenfeucht-Mostowski theorem Created 2026-09-28 Updated 2026-10-05
Let be an infinite first-order structure and a total order. After choosing a Skolem expansion of , an elementary extension contains distinct elements forming an order-indiscernible sequence in that expanded language. Their Skolem hull is an elementary substructure in the expanded language, and its reduct is a first-order model of . Every order automorphism of extends uniquely to a structure automorphism of the hull preserving the chosen Skolem expansion, by transporting terms in the generators.
Uniqueness need not hold among all structure automorphisms of the reduct. For an infinite structure in the pure logical equality language, take two distinct nullary Skolem function values in the hull. For an infinite order-indiscernible sequence, neither can equal a generator: the expanded formula would otherwise hold at every generator, contradicting their distinctness. Swapping fixes every generator and preserves the pure logical equality reduct, while failing to preserve the Skolem expansion. Thus the identity order automorphism already has two extensions in that reduct.
In the comparison model exposing only an equality test between otherwise opaque values, partitioning values into equivalence classes takes tests in the worst case. Run the algorithm on pairwise distinct values. If any pair remains untested, changing just those two values to equal is consistent with every answer observed so far but changes the required output partition. Every pair must therefore be tested. With a compatible total order, comparison sort can instead group equal values in time.
Extended real number line Created 2026-10-14 Updated 2026-11-05
The extended real numbers adjoin and to . They preserve the total order but leave some arithmetic expressions, such as , undefined.
Fagin's theorem 2026-10-14
Fix a finite relational first-order signature , and let be a class of finite nonempty -first-order structures closed under isomorphism. Fagin's theorem states that is definable by one existential second-order logic sentence under full semantics for second-order logic if and only if its language of standard finite encodings belongs to NP. A standard encoding numbers the domain and lists membership bits for each input relation, together with ; take an explicit encoding whose length is at least . The encoding language contains all numbered copies of members of , with malformed encodings rejected. The isomorphism condition makes membership a property of the structure rather than an arbitrary choice of labels. Changing between the usual explicit encodings preserves the NP characterization by polynomial time translations.
The forward direction is the witness-and-verifier calculation in existential second-order logic. For the reverse direction, the guiding idea is to encode an accepting nondeterministic computation using second-order relation variables: fixed-length tuples of domain elements index enough time steps and storage positions for a polynomial time computation. A first-order sentence checks the initial input, legal transitions, and acceptance. The number of tuples grows with the input, although the checking sentence stays fixed. No total order must be supplied as part of the input first-order signature: an auxiliary total order can itself be existentially guessed and constrained by a first-order sentence. Isomorphism invariance ensures that a change of this auxiliary numbering does not change membership in .
The second-order encoding of three-colorability is a small instance of the forward direction. The beauty of Fagin's theorem is the complete correspondence: the computational class NP can be characterized by the shape of a logical description, without mentioning a particular machine in the statement. The scope is finite relational first-order structures and fixed sentences; it is not a claim about deciding arbitrary second-order logic sentences or about arbitrary infinite domains.
Ronald Fagin published the result in Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, SIAM-AMS Proceedings 7 (1974), pp. 43–73, Section 4. The original paper frames the correspondence using classes of finite expansions and their encodings. Fagin's author-maintained publication list explains that the abstract in the available copy was added in 2019; its modern summary should therefore not be mistaken for part of the 1974 printing.
First-order logic Created 2026-09-24 Updated 2026-11-05
First-order logic builds assertions using variables, logical connectives, and quantifiers over elements of a structure. A chosen first-order language supplies constants, function symbols, and relation symbols. The quantifiers range over elements, rather than arbitrary subsets or predicates.
For example, says that an ordered domain has no greatest element. It is true in the integers but false in a nonempty finite total order. A formal proof manipulates formulas syntactically, while a model of a first-order theory supplies their meanings. Gödel's completeness theorem links these viewpoints: semantic consequence from a theory agrees with formal derivability.
Haskell type class 2026-10-24
A class specifies overloaded methods and a constraint supplies the applicable instance operations for a type. This programming-language concept is distinct from an information-theoretic type class. A method signature does not enforce algebraic laws such as a lawful total order.
Inorder traversal 2026-10-13
An inorder traversal of a binary tree uses recursion to visit the left subtree, output the current vertex, and visit the right subtree; an empty subtree outputs nothing. This is a depth-first traversal of a tree with output between the two recursive calls. It produces sorted keys for a binary search tree, but arbitrary labels in a binary tree need not appear in total order.
// Target: computer-science.bigb
Lexicographically ordered group Created 2026-10-14 Updated 2026-11-05
For ordered Abelian groups, compare tuples at their first differing coordinate. This gives a two-sided invariant total order on their direct product. The additive group with its first coordinate dominant is not an Archimedean ordered group, since for every positive integer .
Lexicographic order Created 2026-09-24 Updated 2026-10-18
For equal-size subsets and of an ordered ground set, precedes in lexicographic order when the smallest element of their symmetric difference belongs to .
For finite sequences over a total order, lexicographic order compares the first differing sequence terms; the smaller term determines the smaller sequence. If one sequence is a proper prefix of the other, the shorter precedes its extension. For fixed-length tuples, this is the first-difference rule used by radix sort key encoding.
Linearly ordered group 2026-10-14
A group with a two-sided invariant total order. Thus it is a lattice-ordered group whose join and meet choose the larger and smaller element. An order on only one side is not sufficient here. Every linearly ordered group is torsion-free: a positive element has strictly increasing positive powers, and a negative element has a positive inverse.