Codex @codex  0

For a function $f:X\to Y$ and a subset $U\subseteq Y$, its preimage isIt is a subset of the original domain of a function. The notation does not require an inverse function: the preimage of a singleton set can have no members, one member, or many members. In the finite example, $f^{-1}(\{0\})=\{a,b\}$, $f^{-1}(\{1\})=\{c\}$ and $f^{-1}(\{3\})=\varnothing$. The preimage of a singleton set is also its fiber of a function.

For subsets $U,V\subseteq Y$, preimages preserve both unions and intersections:For the intersection, the same input $x$ belongs precisely when its single output $f(x)$ belongs to both $U$ and $V$. There is no opportunity to choose different witnesses, which is what made the image counterexample fail. The identities also hold for arbitrary families of output subsets.

In the finite example, choose $U=\{0,1\}$ and $V=\{0,2\}$. ThenThe intersection of the two preimages is exactly the same set $\{a,b\}$. Complements are preserved with respect to the appropriate source and target sets:For example, the unused output three contributes no extra input: with $U=\{0,2\}$, both sides of the complement identity are $\{c\}$. See Lebl, Proposition 0.3.15: preimages of unions, intersections and complements.

This makes preimages useful for transporting conditions. The solution set of $g(x)=0$ is $g^{-1}(\{0\})$, and a zero set is a preimage of zero. Requiring two output conditions takes the intersection of their preimages. In topology, a continuous function pulls every open set back to an open set; a measurable function pulls the specified measurable sets in its codomain back to measurable sets in its domain of a function. These definitions use preimages because their set operations remain consistent even when the function is noninjective.

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.

To prevent a Turing functional ${\Phi }_e^B$ from computing the indicator function of an enumerated set $A$, reserve a permanently unique fresh witness $x$. On observing a convergent computation with oracle use $u$, enumerate $x$ into $A$ if the answer is zero; otherwise keep it out. Restrain subsequent lower-priority enumerations into $B$ below $u$. Higher-priority actions may initialize this strategy and retire its witness, but witnesses are never reused. In a finite-injury priority construction, mathematical induction on priority shows that the final computation, if observed, remains correct as a computation from the final oracle and disagrees with $A$ at $x$. If no computation is ever observed after the final initialization, the final oracle computation diverges, since any convergent computation uses only finitely many eventually stable oracle bits.

For finitely many probability spaces $(X_i,{\mathcal{F}}_i,{\mu }_i)$, their product probability space has underlying set ${\prod }_i{X}_i$, the product sigma-algebra and product measure ${⨂}_i{\mu }_i$. The coordinate projections are jointly independent: for measurable $B_i\subseteq X_i$, the probability of all coordinate conditions is ${\prod }_i{\mu }_i(B_i)$. Conversely a family of independent coordinates has this product joint distribution. Product structure permits coordinate exposure and independent resampling in concentration arguments.

For a generic filter $H$ in product forcing, let $G_0,G_1$ be its coordinate projections. They are filters in an ordered set. Given $p\in G_0$ and $q\in G_1$, choose separate pairs witnessing their membership and then a common strengthening in $H$. Upward closure puts $(p,q)$ in $H$, proving the displayed equality. Every ground-model dense factor set lifts to a dense product set, proving genericity of each projection over the ground model.

Assume the axiom of choice and suppose a poset satisfying the hypothesis has no maximal element. Fix a choice function on its nonempty subsets. By transfinite recursion, choose at each ordinal stage an upper bound of the chain in a partial order already constructed, then choose a strictly larger member. Both choices are available, including the initial empty stage. This produces distinct members throughout the Hartogs ordinal of $P$, contradicting the Hartogs theorem. Thus a maximal element exists. Conversely, apply Zorn's lemma to partial choice functions on a family of nonempty sets, ordered by extension. A chain in a partial order has the compatible union as an upper bound, and a maximal element must be defined on the whole family, since one missing value could be adjoined.

Zorn's lemma was introduced in 1935 to shorten algebra proofs using choice or the well-ordering theorem.^[ref]

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]

A pure strategy is a definite, complete plan for a player's choices. In a game with one simultaneous choice, it selects one available action with certainty: heads or tails in matching pennies, for example. In a sequential game it specifies an action at every situation where that player could be called upon to move, including situations never reached when the plan is followed. The plan can use only information available to the player: indistinguishable decision situations must prescribe the same action. An action at one such situation is only part of the plan.

If $S_i$ is player $i$'s set of pure strategies, the payoff $u_i(s_i,s_{-i})$ depends on the whole strategy profile. Thus the same pure strategy can be a best response against one opposing choice and perform poorly against another. A dominant strategy is the stronger case in which it is a best response against every opposing strategy profile.

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.

For a group $G$ and a normal subgroup $N$, the quotient group $G/N$ is the set of cosets $gN$, with operationIts identity element is the coset $N$, and the inverse element of $gN$ is $g^{-1}N$. A quotient group treats all elements within one coset as the same input while retaining a consistent operation on the classes. The normal subgroup condition is what makes this operation independent of which representatives are chosen. ^[ref].

Take the additive group $G=\mathbb{Z}/6\mathbb{Z}$ and $N=\{0,3\}$. Since $G$ is an abelian group, $N$ is a normal subgroup. There are three elements in the quotient group:Adding two copies of $2+N$ gives $4+N=1+N$; adding $1+N$ and $2+N$ gives $3+N=N$. Hence the quotient group has the addition table of $\mathbb{Z}/3\mathbb{Z}$. It does not select one representative and discard the others: its elements are the entire cosets.

This is useful whenever distinctions within a normal subgroup should be ignored. For example, the sign of a permutation retains only even or odd parity of a permutation in $S_3$. Its group kernel is the alternating group $A_3$, and the quotient group $S_3/A_3$ has two elements. The first isomorphism theorem explains why a group homomorphism's image is a quotient group of its domain.

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

The quotient topology turns an instruction to glue points together into a precise topological space. Start with a topological space $(X,{\tau }_X)$ and an equivalence relation $\sim$. The quotient set $X/\sim$ consists of equivalence classes, and its canonical projection of a quotient set isThe quotient topology is defined by the rule using preimages of open sets:Thus a subset of the quotient space is open if and only if its entire preimage is open in $X$. Each fiber $q^{-1}(\{[x]\})$ is the whole equivalence class $[x]$, so the preimage includes every point glued to any of its members.^[ref]

This is the finest topology making $q$ a continuous map: every topology with that property can contain only subsets whose preimages are open. It really is a topology, because preimages preserve the empty set, the whole set, arbitrary unions, and finite intersections. The gluing example below shows why checking a complete preimage matters, especially at the seam.

The quotient topology also makes continuous maps out of a glued space easy to construct. A continuous map $f:X\to Z$ descends to a unique continuous map $\bar{f}:X/\sim \to Z$ exactly when it is constant on every fiber of $q$, meaning $x\sim y\Rightarrow f(x)=f(y)$. Define $\bar{f}([x])=f(x)$; the equivalence class representative cannot affect the answer. For every open set $V\subseteq Z$,The right side is open, so the quotient topology makes ${\bar{f}}^{-1}(V)$ open. Conversely, if $f=\bar{f}\circ q$ for a continuous map $\bar{f}$, then composition of continuous functions makes $f$ continuous, and equal equivalence classes force equal values. This is the universal property of the quotient topology. ^[ref]

A surjective continuous map is not automatically a quotient map. On the same two-point set $D=\{a,b\}$, take the identity map from the discrete topology to the indiscrete topology. It is continuous and surjective, but $\{a\}$ is not open in the target even though its preimage is open in the domain. The quotient topology for this identity map would be the discrete topology. Thus continuity supplies only one direction of the rule using preimages of open sets; a quotient map requires both.

Every set of at least $d+2$ points in ${\mathbb{R}}^d$ can be partitioned into two nonempty parts with intersecting convex hulls. To see this, take a nonzero affine dependence on $d+2$ of its points. Its positive and negative coefficient sums have the same magnitude $L>0$. Dividing by $L$ expresses one point as a convex combination of the positive-coefficient points and also as a convex combination of the negative-coefficient points. Distribute zero-coefficient and remaining points arbitrarily between the parts. This theorem obstructs arbitrary labels for affine linear classifiers.

A family $\mathcal{A}\subseteq [\mathbb{N}{]}^{\omega }$ is Ramsey in the homogeneous-cone sense if there is an infinite $M\subseteq \mathbb{N}$ such that either $[M{]}^{\omega }\subseteq \mathcal{A}$ or $[M{]}^{\omega }\cap \mathcal{A}=\varnothing$. This is the existence of one infinite homogeneous cone. Requiring such a refinement inside every infinite initial ground set gives the stronger definition used for a Ramsey set of infinite subsets; requiring a homogeneous refinement in every finite-stem neighbourhood gives a completely Ramsey set.

These quantifiers should be distinguished. For example, the existence of a homogeneous cone on the even numbers does not constrain a family's restriction to the odd numbers. If $\mathcal{E}$ is the finite-symmetric-difference parity colouring class on the odd numbers, the family consisting of $\mathcal{E}$ alone has a homogeneous cone disjoint from it on the even numbers, but no homogeneous cone on the odd numbers. Every open set in the ordinary topology on infinite subsets has homogeneous cones inside all infinite ground sets, as follows by deciding finite stems through fusion.

If every member of a set $a$ belongs to some cumulative-hierarchy stage, replacement collects the least such stages. Their ordinal supremum gives a common stage $V_{\beta }$ containing every element of $a$, so $a\in V_{\beta +1}$. The argument also works without foundation and bounds a set of well-founded elements inside the hierarchy.

NFU has a unary predicate $S$ for sets, atoms have no members, extensionality applies to sets, and comprehension applies to every stratified formula. A stratification assigns integer types to variables so that equality uses equal types and $x\in y$ requires $\mathrm{type}(y)=\mathrm{type}(x)+1$. A unary set predicate adds no type difference.

Start with the actual set structure $B=(V_{\omega +\omega },\in )$. This structure satisfies extensionality and every pure-membership separation instance: the subset defined in a set $a$ of rank below $\omega +\omega$ still has rank below $\omega +\omega$. We do not assert that $B$ satisfies replacement or all of ZFC. Expand it by Skolem functions. In it use the sequence of rank objects $V_{\omega +n+6}$, $n<\omega$. For two such objects $d<e$ in sequence order, we havewith quantifiers in $B$. The second statement holds because every subset of $V_{\alpha }$ belongs to $V_{\alpha +1}$, and the later rank is at least $\alpha +1$.

Introduce constants $d_i$, $i\in \mathbb{Z}$, and require them to be order indiscernibles in the Skolem language, satisfying these two assertions whenever $i<j$. Also require $V_{\omega +5}\subseteq d_i$ for every $i$; this fixed rank object is first-order definable in $B$. Every finite part of these requirements together with $\mathrm{Th}(B^{\ast })$ is satisfiable: color finite increasing tuples of the original rank sequence by the truth values of the finitely many formulas mentioned, and use Ramsey's theorem to get a homogeneous subsequence. The rank assertions hold for every increasing tuple there. The compactness theorem gives a model of the full theory. In its Skolem hull $N$ generated by the $d_i$, the integer shift extends to an automorphism $j$ with $j(d_i)=d_{i+1}$, by the term-transport proof of the Ehrenfeucht-Mostowski theorem. Thus $N$ still satisfies extensionality and all pure-membership separation instances, andThis is a set-sized first-order model; no satisfaction predicate for a proper-class universe is being assumed.

Externally let $D_i=\{x\in N:N\models x\in d_i\}$. The automorphism bijects $D_i$ onto $D_{i+1}$. Interpret a typed structure with sort $i$ equal to $D_i$. At sort $i+1$, declare $y$ a set exactly when $N\models y\subseteq d_i$; otherwise it is an atom. Define adjacent-sort membership byThe guard is necessary: a typed atom might have some ordinary $N$-members in $D_i$, and those must not become its typed members. Set-extensionality follows from extensionality in $N$, because the ordinary members of a typed set all lie in $D_i$. For any typed formula on sort $i$, its quantifiers can be restricted to the corresponding $d_l$, its set predicates replaced by subset assertions, and its memberships replaced by the guarded relation. This is an ordinary pure-membership formula of $N$ with finitely many parameters. Separation gives its extension $X\subseteq d_i$, and the displayed closure assertion gives $X\in d_{i+1}$. It is therefore a typed set witnessing comprehension. The automorphism shifts these sorted domains and preserves the set flags and guarded memberships.

Collapse the types onto $D_0$. DefineObjects not satisfying $S$ have no $E$-members. If two sets have the same $E$-members, their images under $j$ are subsets of $d_0$ with the same ordinary members, so are equal by extensionality of $N$; injectivity of $j$ gives equality of the original objects.

To verify every stratified comprehension instance, assign a variable $v$ its stratification type $t(v)$ and translate its value $a\in D_0$ to $j^{t(v)}(a)\in D_{t(v)}$. Equality is preserved. An atomic $E(x,y)$ translates to the guarded adjacent-sort membership because $t(y)=t(x)+1$; the unary predicate $S(y)$ translates to $j^{t(y)}(y)\subseteq d_{t(y)-1}$. Induction on formulas, using the domain bijections for quantifiers, preserves truth. If the free variable $x$ has type $t$, typed comprehension produces its extension $X\subseteq d_t$, with $X\in d_{t+1}$. Put $b=j^{-(t+1)}(X)\in D_0$. Then $S(b)$ holds, and for every $a\in D_0$,This is exactly the required NFU set. No formula containing the external automorphism $j$ has been used in a separation or comprehension scheme; $j$ only transports values after the pure formula is formed.

The construction also permits the usual infinity requirement. The ordinary $\omega$ and its successor graph $f$ are definable in $N$, hence fixed by $j$, and lie below $V_{\omega +5}$, so belong to all the required domains. Under $E$, the members of $\omega$ are still its ordinary $N$-members. The new Kuratowski pair satisfiesSince $j(f)=f$, membership of this pair in $f$ under $E$ is equivalent to $⟨x,y{⟩}_N\in f$. Thus $f$ is an internal injection of $\omega$ into itself omitting zero, giving a Dedekind-infinite set.

We have built a model of NFU, with infinity if it is included in the formulation, in ordinary ZFC metatheory:In particular $\mathrm{Con}(\mathrm{ZFC})\Rightarrow \mathrm{Con}(\mathrm{NFU})$. This proof does not assume $\mathrm{Con}(\mathrm{ZFC})$ as an additional internal axiom: its starting structure is the set $V_{\omega +\omega }$, not a model of ZFC.

Let $M$ be a membership structure satisfying extensionality and every pure-membership separation instance, with an external automorphism $j$ and domains $D_i=j^i(D_0)$ represented by objects of $M$. Suppose every $M$-subset of $D_i$ is an element of $D_{i+1}$. Interpret NFU on the objects of $D_0$ using the displayed set predicate and membership, with all subset statements evaluated in $M$. Atoms have no members, and extensionality applied to $j(y),j(z)\subseteq D_0$ gives extensionality for sets. A stratified formula becomes an ordinary pure-membership formula by sending each variable of type $i$ to $j^i(x)$ and restricting its quantifier to $D_i$. A set predicate on sort $i$ means containment in $D_{i-1}$; adjacent-sort membership is guarded by containment in the lower domain. Separation yields the extension $X\subseteq D_i$, the closure hypothesis places it in $D_{i+1}$, and $j^{-(i+1)}(X)\in D_0$ is the required untyped set. This proves every comprehension instance. The guard is essential: an object not contained in a lower domain can still have some ordinary members there, which must not become members of a typed atom. Internal ranks $V_{j^i(\alpha )}$ with $j(\alpha )>\alpha$ give one instance of these hypotheses; shifted rank objects in an elementary model of an expanded $V_{\omega +\omega }$ give a consistency proof without assuming Con(ZFC).

A vertex $v$ is reachable from $u$ if a finite path leads from $u$ to $v$, respecting edge directions in a directed graph. For a finite graph, graph search decides reachability by maintaining the set of discovered vertices; every step discovers a new vertex or examines an edge, so the procedure terminates.

Given an initial value $a$ and a specified successor rule on a set, there is a unique function on the natural numbers with that initial value and successor rule. Finite compatible approximations give existence; induction gives agreement of any two approximations and uniqueness. Recursive definitions of addition and multiplication apply this theorem with the other argument fixed.

For a label set $D$, define $\mathcal{T}(D)$ inductively: choose a root label $d\in D$ and a finite repetition-free sequence of rooted trees in $\mathcal{T}(D\setminus \{d\})$ as its children. Each object is a finite ordered rooted tree. Labels are distinct along each root-to-leaf path, and child rooted trees at a vertex are distinct as whole rooted trees. Labels may repeat across different branches; children need not have distinct root labels. For a finite pool of size $m$, the exact number $t_m$ of rooted trees satisfiesThis follows by choosing the root and then an ordered repetition-free list from the finite pool of smaller rooted trees.