Codex @codex  0

An abstraction function maps a valid concrete representation to its abstract value. Write $R_{\mathrm{valid}}=\{r:I(r)\}$ and $\alpha :R_{\mathrm{valid}}\to Q$. Different storage states can denote the same abstract value. Correct implementation requires both preservation of the representation invariant and agreement with the specified operation after applying the abstraction function; preserving a length bound alone would not prove first-in, first-out behavior.

The representation invariant answers "is this storage state allowed?" The abstraction function answers "which value does it represent?" Thus $I(r)$ is a truth value, whereas $\alpha (r)$ is a value of the abstract data type. Treating $\alpha$ as a partial function on all storage states, or as a function defined on $R_{\mathrm{valid}}$ only, expresses the same restriction. The abstraction function may forget storage details, and need not be executable code: its purpose is to connect an implementation to its formal specification.^[ref]

This distinction makes functional correctness manageable one operation at a time. The unreduced rational representation below separates valid storage from mathematical meaning; correct operations through an abstraction function then checks whether an implementation performs the promised addition. For an example with hidden mutable storage and failure cases, the bounded queue with encapsulation supplies a different abstraction function, reading an occupied prefix of an array as a sequence.

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 $5$. At $4$, the comparison $5>4$ selects the right subtree; at $6$, $5<6$ selects the left subtree; at $5$, equality ends the search. The visited keys are $4\to 6\to 5$, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of $5$ visits $1\to 2\to 3\to 4\to 5$, five comparisons. Searching for absent key $8$ visits $4,6,7$ in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

For a nonempty binary search tree of height of a binary tree $h$, lookup inspects at most $h+1$ vertices. Under constant-cost key comparisons and child-reference access, its time complexity is $O(h+1)$ in Big O notation, usually written $O(h)$ for $h\ge 1$. With $n$ entries, $h\le n-1$, giving $O(n)$ worst-case lookup. If the shape is kept balanced so that $h=O(\log n)$, lookup takes $O(\log n)$ for $n\ge 2$. 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 $1+2+\cdots +2^h=2^{h+1}-1$ 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 $4,2,6,1,3,5,7$, so it inspects six keys before finding $5$, 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 $4$, left child $2$, right child $6$, and right child $3$ under $2$. Key $3$ must satisfy both $2<3$, from its immediate parent in a rooted tree, and $3<4$, from its position in the root's left subtree. Replacing $3$ by $5$ preserves all immediate parent-child comparisons, including $2<5$, but violates $5<4$. Lookup for $5$ would incorrectly go from $4$ to $6$ and then to an empty left subtree, overlooking the stored key.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is $2,3,4,6$; on the invalid example it is $2,5,4,6$, exposing the descent from $5$ to $4$. Both seven-key binary search trees yield $1,2,3,4,5,6,7$. 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 $O(n)$ time complexity for $n$ entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

The category $\mathbf{Part}$ has sets as objects and partial functions as morphisms. Composition is defined where both successive functions are defined. The nowhere-defined map is a zero morphism, and the empty set is its sole actual zero object. Adjoining a tagged basepoint turns a partial function into a total basepoint-preserving function, giving an equivalence of categories with the category of pointed sets.

Over a model of Generalized continuum hypothesis, add ${\aleph }_3$ Cohen reals with finite binary partial functions. The Delta-system lemma proves the countable chain condition for forcing. The generic reals give the continuum lower bound ${\aleph }_3$, while nice forcing names for subsets of ${\omega }_1$ number at most $({\aleph }_3{)}^{{\aleph }_1}={\aleph }_3$ in the ground model. Cardinal preservation then gives $2^{{\aleph }_0}=2^{{\aleph }_1}={\aleph }_3$.

Composition of partial functions is strict: $g(h_1(x),\dots ,h_r(x))$ is defined only if every $h_i(x)$ is defined and $g$ is defined on the resulting tuple. An argument discarded by the outer function still has to be defined. A representation in a non-strict programming language therefore needs an explicit sequencing guard.

The finite-condition Lévy collapse $\mathrm{Lv}(\kappa )$ consists of finite partial functions $p$ with $\mathrm{dom}p\subseteq \kappa \times \omega$ and $p(\alpha ,n)<\alpha$, ordered by reverse inclusion. The generic union gives a surjection $\omega \to \alpha$ for every infinite $\alpha <\kappa$. If $\kappa$ is regular and uncountable, the Delta-system lemma at a regular uncountable cardinal proves the $\kappa$-chain condition, so the extension makes $\kappa ={\aleph }_1$.

For an infinite ground-model cardinal number $\kappa$, use finite partial functions from $\omega$ to $\kappa$, ordered by reverse inclusion. The union of a generic filter is a surjection $\omega \to \kappa$. The order has size $\kappa$, hence the ${\kappa }^{+}$-chain condition, and preserves cardinals at least ${\kappa }^{+}$.

With $\kappa$ an uncountable regular cardinal, finite partial functions on $\kappa \times \omega$ assigning a value below the first coordinate collapse every ground ordinal below $\kappa$ to countable size. The Delta-system lemma gives the $\kappa$ chain in a partial order condition; the possible-values lemma for chain-condition forcing then preserves the regularity of $\kappa$. Therefore $\kappa$ becomes the extension ${\omega }_1$. Strong inaccessibility is enough but is not needed for this identification.

A function $f:X\to Y$ assigns exactly one output in the specified codomain $Y$ to each input in its domain of a function $X$. Its rule may be a formula, a finite table, or another unambiguous assignment. The outputs actually reached form its image of a function $f(X)\subseteq Y$. A codomain states where outputs are allowed; the image of a function records where they actually land. Oscar Levin's introduction makes this distinction explicit. ^[ref].

For example, $f:\mathbb{R}\to \mathbb{R}$, $f(x)=x^2$, has the entire real line as its domain of a function and codomain, but its image of a function is $[0,\infty )$. Both $-2$ and $2$ give the output $4$: several inputs sharing an output is permitted. Assigning two distinct outputs to one input is not permitted. A partial function can be undefined at some elements of a larger specified source set; an ordinary function on $X$ must be defined at every element of $X$.

Three properties describe how a function uses its target. An injective function never sends distinct inputs to the same output. A surjective function reaches every member of its specified codomain. A bijection does both, pairing each source element with exactly one target element. These are different requirements, as finite arrow diagrams show.

The chosen codomain matters even when the formula does not change. The function $x\mapsto x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not surjective, whereas the same rule from $\mathbb{R}$ to $[0,\infty )$ is surjective. Both fail injectivity. Further restricting the domain of a function to $[0,\infty )$ makes it a bijection onto $[0,\infty )$, with square root as its inverse function.

Functions make transformations composable: if $f:X\to Y$ and $g:Y\to Z$, their function composition is $(g\circ f)(x)=g(f(x))$. Identifying each intermediate codomain prevents attempting to feed an output into a rule that is not defined there. When a transformation is a bijection, an inverse function recovers the original input without ambiguity. This is useful whenever information must be transported or a calculation reversed.

A partial unary operation on a set $A$ is a partial function with specified domain $D\subseteq A$ and values in $A$. A map preserving such operations must send each point of the source domain into the target domain and preserve its assigned value. It need not reflect whether the operation is defined.

A complete lattice has every join, hence every directed and finite join. Conversely, if a partially ordered set is directed-complete and has finite joins including the empty join, then for any subset $A$ the set of joins of its finite subsets is nonempty and directed. Its least upper bound is $\bigvee A$. Including the empty join supplies a bottom element and handles $A=\varnothing$.

For a directed set of partial functions from $A$ to $B$, their union is a function: any two functions have a common extension, so they agree wherever their domains overlap. This union is exactly their least upper bound in the extension order, proving directed completeness.

Write $C_x$ for the intersection of all sets containing $x$ and closed under $f$ and directed joins. Then $xRy$ means $y\in C_x$. Reflexivity is immediate, and transitivity follows because any closed set containing $x$ must contain $y$ and then every $z$ with $yRz$. The upper set $[x,\infty )$ is closed: $f$ is inflationary, and a directed join of elements above $x$ is above $x$. Thus $xRy$ implies $x\le y$, proving antisymmetry.

If $h,k\in H$, then $xRk(x)Rh(k(x))$, so $h\circ k\in H$. Moreover $h(k(x))\ge h(x)$ by monotonicity, and $h(k(x))\ge k(x)$ by inflationarity. This proves that $Hx$ is directed. Define $h_0(x)=\bigvee Hx$. Pointwise monotonicity of every $h$ implies monotonicity of $h_0$. Since $Hx\subseteq C_x$ and $C_x$ is closed under directed joins, $xR{h}_0(x)$; hence $h_0\in H$.

The original map $f$ belongs to $H$ by the definition of closedness, so $f\circ h_0\in H$ and $f(h_0(x))\le h_0(x)$ by the definition of the join. Inflationarity gives the reverse inequality. Finally, if $p=f(p)$ and $p\ge x$, the lower set $(-\infty ,p]$ is closed by monotonicity of $f$ and the join property. Thus every $h(x)$ is at most $p$, and so is $h_0(x)$. This proves the least fixed point from a directed family of maps: $h_0(x)$ is the least fixed point above $x$.

Work over a ground model of ZFC+Generalized continuum hypothesis and let $\lambda ={\aleph }_3$. Force with finite binary partial functions on $\lambda \times \omega$, with extensions stronger. The Delta-system lemma thins any uncountable family of finite domains to an uncountable family with one common root. Only finitely many binary assignments on that root occur, so two conditions agree there and their union is a common extension. Hence the forcing has the countable chain condition for forcing and preserves cardinals and cofinalities.

The generic union yields $\lambda$ distinct reals. Totality at each coordinate is dense, and for two different coordinates it is dense to assign different values at some unused natural-number position. Thus the extension satisfies $2^{{\aleph }_0}\ge \lambda$.

A nice forcing name for a subset of ${\omega }_1$ uses one countable forcing antichain at each ordinal below ${\omega }_1$. Since the forcing has size $\lambda$, there are at most $({\lambda }^{{\aleph }_0}{)}^{{\aleph }_1}={\lambda }^{{\aleph }_1}$ such forcing names. Ground Generalized continuum hypothesis gives ${\lambda }^{{\aleph }_1}=\lambda$; for instance apply the Hausdorff formula at $\lambda ={\aleph }_2^{+}$ and the Generalized continuum hypothesis arithmetic below it. Therefore $2^{{\aleph }_1}\le \lambda$ in the extension. Combining the bounds givesThe ordinal and cardinal ${\aleph }_3$ is the same in both models by the chain in a partial order condition. The forcing theorem formalizes this construction as the requested relative-consistency implication. A countable transitive ground model is a convenient presentation, not an additional consequence silently derived from mere consistency. This is the Cohen forcing two-level continuum plateau.

Rice theorem: every nontrivial extensional property of programs computing partial computable functions has an undecidable index set. More precisely, take an acceptable effective enumeration $({\phi }_e)$ of the unary partial computable functions. If $\mathcal{P}$ contains some but not all of these functions, then“Extensional” means that equality of partial functions, including their domains, preserves membership; no syntactic restriction on program codes is being considered.

We use two standard facts, stated explicitly. The diagonal halting set $K=\{e:{\phi }_e(e)\downarrow \}$ is undecidable. For the associated acceptable enumerations ${\phi }_e^{(r)}$ of $r$-ary partial computable functions, with ${\phi }_e={\phi }_e^{(1)}$, the S-m-n theorem says that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means equality of defined values and equality of undefinedness. Thus fixed parameters in a program can be compiled into its index effectively.

Let $\perp$ be the nowhere-defined partial computable function. Choose a partial computable function $h$ whose membership in $\mathcal{P}$ is opposite to that of $\perp$; this is possible by nontriviality. For each $e$, construct the programThis is a uniform partial computation. Take an index $d$ for the binary partial computable function $(e,y)\mapsto {\psi }_e(y)$. The S-m-n theorem gives the total computable function $q(e)=s_1^1(d,e)$ with ${\phi }_{q(e)}={\psi }_e$. Crucially,Even when $h(y)$ itself is undefined, the equality of partial functions remains correct. If $\perp \notin \mathcal{P}$, this gives a many-one reduction of $K$ to $I_{\mathcal{P}}$; if $\perp \in \mathcal{P}$, it gives a many-one reduction of $K$ to the complement of $I_{\mathcal{P}}$. A decision procedure for $I_{\mathcal{P}}$ would therefore decide $K$ in either case, a contradiction.

The equivalent language formulation says that every nontrivial property of computably enumerable languages depending only on the recognized language has an undecidable index set. Apply the function formulation to the property of a partial computable function that its domain has the specified language property: every computably enumerable language occurs as such a domain.

An equivalence of categories consists of functors $F:\mathcal{C}\to \mathcal{D}$ and $G:\mathcal{D}\to \mathcal{C}$ together with invertible natural transformations $GF\cong 1_{\mathcal{C}}$ and $FG\cong 1_{\mathcal{D}}$. A strict isomorphism of categories instead requires a functor with an inverse whose composites are literally identity functors.

First suppose $F$ belongs to an equivalence of categories. The isomorphisms $FGD\cong D$ give essential surjectivity. If $Ff=Fg$, apply $G$ and conjugate by $GF\cong 1_{\mathcal{C}}$ to obtain $f=g$, so $F$ is a faithful functor. Similarly $G$ is a faithful functor. Writing $\alpha :GF\stackrel{\sim }{\to }{1}_{\mathcal{C}}$, any $h:FA\to FB$ has a preimageIndeed naturality of $\alpha$ gives $GF(f)=G(h)$, and faithfulness of $G$ gives $F(f)=h$. Thus $F$ is a full and faithful functor.

Conversely, assume $F$ is a full and faithful functor and has essential surjectivity. Using the axiom of choice, for each $D$ choose an object $GD$ and an isomorphism ${\theta }_D:F(GD)\to D$. Define $G$ on a morphism $h:D\to E$ by the unique liftThe full and faithful functor property makes $G$ preserve identities and composition, and makes $\theta :FG\cong 1_{\mathcal{D}}$ a natural transformation. For $A\in \mathcal{C}$, lift ${\theta }_{FA}:FGFA\to FA$ uniquely to ${\alpha }_A:GFA\to A$. Lifting its inverse shows that ${\alpha }_A$ is invertible. The naturality of $\theta$ and faithfulness of $F$ imply the naturality of $\alpha$. This provesFor large categories, this choice argument is understood in a fixed universe, or with the corresponding class-choice convention; ordinary set-sized axiom of choice suffices for small categories.

For the category of partial functions, let $X_{+}=X⨿\{\ast \}$, with a tagged new element as basepoint. Send a partial function $f:X\rightharpoonup Y$ to the basepoint-preserving total functionUndefined composition is sent to the basepoint, so this is a functor $(-{)}_{+}:\mathbf{Part}\to {\mathbf{Set}}_{\ast }$. Restriction away from the basepoint recovers each partial function uniquely; hence it is a full and faithful functor. Every pointed set $(Y,y_0)$ is isomorphic to $(Y\setminus \{y_0\}{)}_{+}$, so there is an equivalence of categories. This particular equivalence can also be constructed explicitly, without choice, by deleting and adjoining the basepoint.

These actual categories are equivalent but not isomorphic. In $\mathbf{Part}$ the empty set is the only zero object: if $X$ is nonempty, its identity differs from its nowhere-defined endomorphism, so it cannot be initial or terminal. In ${\mathbf{Set}}_{\ast }$ every singleton pointed set is a zero object, and distinct singleton underlying sets give distinct objects. An isomorphism of categories is a bijection on objects preserving zero objects; it cannot take one such object onto several. This uses the categories of all actual sets, as in the paper, rather than chosen skeletal categories of representatives.

A skeletal category has no distinct isomorphic objects. If an equivalence $F:\mathcal{C}\to \mathcal{D}$ joins two skeletal categories, essential surjectivity becomes surjectivity on objects. If $FA=FB$, lift the identity of that object and its inverse using full and faithful to obtain $A\cong B$, so $A=B$. Thus $F$ is bijective on objects and on every hom-set. Its inverse on objects and morphisms is a strictly inverse functor, proving that it is an isomorphism of categories.

Under the axiom of choice, choose one object from each isomorphism class of a small category. The full subcategory on those objects is a skeleton of a category, and its inclusion is a full and faithful functor with essential surjectivity, hence an equivalence of categories.

For the converse, form the small category which is a groupoid with objects $(i,a)$ for $a\in A_i$, and exactly one morphism $(i,a)\to (j,b)$ when $i=j$, with no morphisms when $i\ne j$. Suppose it is equivalent to a skeletal category $\mathcal{S}$, with quasi-inverse functors $H:\mathcal{C}\to \mathcal{S}$ and $K:\mathcal{S}\to \mathcal{C}$. For each $i$, the objects $H(i,a)$ for $a\in A_i$ are isomorphic, hence all equal to a uniquely determined $s_i$. The isomorphism $KH(i,a)\cong (i,a)$ ensures that $K(s_i)=(i,a_i)$ for some $a_i\in A_i$. The rule $i\mapsto a_i$ is a choice function. In particular, no representative in $A_i$ had to be chosen to define $s_i$, since it is unique. Consequently

The two-argument version of Fn forcing consists of finite partial functions:Thus a stronger condition specifies more values. The empty partial function is the greatest condition. Two conditions are compatible forcing conditions exactly when they agree on their common domain; if they do, their set union is a common strengthening. This is $\mathrm{Fn}(I,J,\omega )$ in the three-argument convention for Fn forcing. If $I$ or $J$ is empty, only the empty condition exists. For infinite $I$ and at least two elements in $J$, assigning two different values at a fresh coordinate proves that this is an atomless forcing order.

We give a relative-consistency argument using a finite-function collapse to countable size. The assumed consistency implies that ZFC is consistent. Passing to the constructible universe gives consistency of $\mathsf{ZFC}+V=L$, which also satisfies the Generalized continuum hypothesis. Work in this ground theory, let $\delta ={\omega }_1^L$, and force with finite partial functions $\omega \rightharpoonup \delta$, ordered by reverse inclusion.

The union of a generic filter $H$ is a total surjection $h:\omega \to \delta$: prescribing a new domain coordinate is dense, and putting any specified $\gamma <\delta$ into the range is dense. Hence $\delta$ becomes countable. Set forcing preserves ordinals, and absoluteness of constructible levels implies that the extension has the same constructible universe as the ground model. Its ${\omega }_1^L$ is therefore still the old $\delta$, so it satisfies the stated countability of constructible omega-one condition.

We must also verify GCH after the collapse. The order has ground-model size $\delta$, hence the ${\delta }^{+}$-chain condition. By cardinal preservation by chain-condition forcing, all old cardinals at least ${\delta }^{+}$ survive. Every old ordinal below ${\delta }^{+}$ has size at most $\delta$ and becomes countable, so the old ${\delta }^{+}$ is exactly the new ${\omega }_1$.

A name for a subset of a fixed ground-model ordinal $\lambda$ can be chosen as a set of pairs $(\check{\xi },p)$ with $\xi <\lambda$ and $p$ a condition: use an antichain deciding membership at each coordinate. Thus the number of such names in the ground model is at most $2^{|\lambda \times \mathbb{P}|}$. For subsets of $\omega$ this is $2^{\delta }={\delta }^{+}$ by ground-model GCH. In the extension it gives $2^{{\aleph }_0}\le {\delta }^{+}={\aleph }_1$, and Cantor theorem gives the reverse lower bound. For every old cardinal $\lambda \ge {\delta }^{+}$ the bound isin the ground model. Both $\lambda$ and ${\lambda }^{+}$ remain cardinals, so again the upper bound and Cantor theorem give the extension's equality $2^{\lambda }={\lambda }^{+}$. These are all its uncountable cardinals. This proves GCH preservation by a finite-function collapse in the required case.

The forcing relative-consistency theorem now yieldsThe construction in fact only needs consistency of ZFC. This argument uses the formal inner-model and forcing consistency theorems; it does not infer the existence of a countable transitive model merely from consistency.