Full semantics for second-order logic Created 2026-10-06 Updated 2026-10-14
Under full semantics for second-order logic, a second-order relation variable of arity ranges over exactly , the external power set of the appropriate Cartesian product. Thus
and universal quantification over checks every such subset. Here the power set is taken in the ambient mathematical universe, not merely among relations definable by formulas or represented by objects inside .
For , a unary second-order relation variable has eight possible values, including the three singletons needed by the second-order encoding of three-colorability. The three unary witnesses can range independently over those eight subsets, giving candidate triples before the first-order sentence is checked; only six triples pass for the complete graph . For , there are candidate triples and none passes. Distinguishing the range of candidates from the constraints on valid witnesses clarifies both full semantics for second-order logic and the verifier view of NP.
The appeal of full semantics for second-order logic is its literal reading of assertions about every subset or every relation. A first-order structure fixes the second-order ranges automatically, in contrast to Henkin semantics. That expressive force comes with a limitation: there is no effective, sound deductive system complete for all valid second-order logic sentences under full semantics for second-order logic. This limitation and the change of intended models motivating Henkin semantics are described at the start of [ref].
For a domain , an external functional graph with all its individual ordered pairs in is therefore available, even if the whole graph does not belong to . More generally, a binary second-order relation variable can denote any external subset of ; its ordered pairs need not themselves be elements of the individual domain. Having endpoints in the domain is what matters. This distinction between internal objects and externally available relations is essential when applying second-order logic to the cumulative hierarchy.
Generating function Created 2026-10-07 Updated 2026-10-14
A generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series ; in counting problems, the coefficient records the number of objects of size . The variable initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as . One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.
Start with two contributions: choose from and from , with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials and . To count ordered pairs by total , multiply:
The coefficients count the ways to obtain totals zero through three. For total two, the possibilities are and ; the two corresponding monomials both contribute . There are six ordered pairs altogether, agreeing with .
Figure 1.
Polynomial multiplication groups six ordered choices by their total contribution
. Details.
If the first contribution has two distinguishable choices when , replace by . Its product with becomes . The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.
In general, the Cauchy product gives
For each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.
Now cover a board of length with tiles of lengths one and two, without gaps or overlaps. Let count these tilings. There is exactly one empty tiling, so , and . Removing the first tile leaves a board shorter by one or two, giving the recurrence relation
These are the Fibonacci numbers shifted by one index: under the convention , . Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.
Figure 2.
Length-one and length-two tiles give five coverings of a length-four board and the Fibonacci recurrence
. Details.
For , the empty board or a first tile followed by a remaining tiling gives
Equivalently, : each factor chooses one tile, and counts pieces while the exponent of records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories and differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. [ref]
These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is , the reciprocal of the golden ratio. At , the rational function equals , but the counting series diverges: that value cannot represent its sum.
Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses . A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.
Graph of a function Created 2026-10-05 Updated 2026-11-05
For a function , its graph of a function is the subset of the Cartesian product . Exactly one ordered pair has first coordinate for each . For example, the quadratic function on the real line has the parabola as its graph.
The graph determines the values and the domain of a function, but alone does not record a larger specified codomain: the same set of ordered pairs can be regarded as lying in or when both contain all its outputs. It also differs from a graph in graph theory, whose edges need not specify exactly one output per input.
Kuratowski ordered pair 2026-10-05
This representation of an ordered pair by sets satisfies exactly when and . Its intersection recovers , and its union recovers ; if the latter is a singleton then . Its rank of a set is , which bounds the ranks of function graphs in absoluteness of cardinalhood in limit ranks.
Life glider 2026-10-13
The Life glider is a five-cell pattern that recreates its shape after four generations, shifted one cell along each coordinate. Use increasing rightward and increasing downward, as in the figure, and start from the live set
Every cell outside starts dead. Applying the Conway's Game of Life rule, rather than moving the drawing by hand, gives:
Figure 1.
Four synchronous Conway's Game of Life steps translate the Life glider by (1,1)
. Original computed toy configuration, not measured data. All five panels use fixed coordinates. Orange dashed outlines in the last panel mark the original live cells; blue cells show the computed fourth generation. The displayed window is part of an infinite board, not a finite boundary. Details.
For an exact check of every frame, the intermediate live sets are
Here means add to each ordered pair in . In the first step, the live cells and have respectively one and one live neighbors, so die; the other three have respectively three, three and two and survive. Exactly and are born, with three live neighbors each. This derives and explains how motion can occur while individual cells merely switch states.
Because the rule uses the same relative neighbors at every position, applying the global update function and applying a translation commute. Thus for every generation ; the four-step calculation establishes continued motion on the infinite board. The average displacement is cells per generation, or Euclidean distance per generation. The live-cell count happens to stay five in these frames, but the rule does not conserve live-cell count in general: a single isolated live cell dies immediately. The Life glider persists indefinitely in an otherwise empty infinite board; encounters with other patterns or a finite implementation's edge can change that conclusion.
// Destination: computer-science.bigb
Orbit (group theory) 2026-10-14
For a group action of a group on a set , the orbit of a group action of is the subset of all positions reachable from :
Two points belong to the same group orbit exactly when one can be moved to the other by a group element. This is an equivalence relation: the identity element gives , the inverse element of a transformation reverses a move, and a product combines two moves. Hence the group orbits form a partition of a set of into equivalence classes. A transitive group action on a nonempty set has just one group orbit. See Ackerman's algebra notes, lemma 0.5.1.3, for the orbit partition.
For the square and the eight-element dihedral group defined under group action, direct enumeration gives the following separate group orbits:
These counts depend on the chosen group action, not just the group. An orbit of a group action describes all configurations equivalent under the permitted transformations. For ordered pairs under the symmetric group, equality of the two entries is preserved, separating the two group orbits in equality-pattern orbits of ordered pairs; the orbit-stabilizer theorem computes their sizes when the symmetric group is .
Orbit-stabilizer theorem Created 2026-09-24 Updated 2026-10-14
For a group action of any group on a set , the cardinality of the orbit of a group action through is the index of a subgroup of its stabilizer subgroup:
In particular, if is a finite group,
For a fixed finite group, a larger stabilizer subgroup means a smaller group orbit: more transformations repeat the same image of . The set itself need not be finite.
The underlying bijection uses left cosets, without requiring to be a normal subgroup:
To check it briefly, replacing by with preserves , so is well-defined. Every member of the group orbit has this form. Finally, implies , hence , proving the bijection. This is the construction in MIT's group-action notes, lemma 23.5. For infinite groups, the bijection and the cardinality statement still hold; division of infinite cardinalities does not supply the finite formula.
For the eight-element dihedral group acting on the square described under group action, moving a marked vertex of a polygon gives . Moving a marked side of a polygon also gives ; moving one unoriented diagonal of a polygon gives ; moving the centroid gives . These are four different group actions, each with one group orbit. In the first group action, the four left cosets of are
They correspond respectively to . Counting all eight transformations would count each position of the marked vertex of a polygon twice.
Figure 1. . The left panel matches four left cosets of a stabilizer subgroup to four images of a vertex of a polygon. The right panel compares the group orbits for separate group actions on vertices of a polygon, sides of a polygon, diagonals of a polygon, and the centroid; each group orbit size times the corresponding stabilizer subgroup group order equals eight. Details.
For a second computed example, let the symmetric group act on the Cartesian product by . There are two orbits of a group action:
and
The first stabilizer subgroup can exchange and while fixing ; the second must fix both and , so also fixes . The orbit-stabilizer theorem gives and , and the two group orbit sizes account for all nine ordered pairs. The general reason for exactly these two group orbits is equality-pattern orbits of ordered pairs.
Ordered pair Created 2026-09-24 Updated 2026-11-05
An ordered pair records two elements together with their positions. Its defining equality rule is exactly when and . Thus , and repeated entries such as are allowed.
The Cartesian product consists of the ordered pairs with first entry in and second entry in . A function can be represented by a set of such pairs with exactly one output for each input. In set theory, a Kuratowski ordered pair realizes the equality rule using ordinary sets.
Pair Created 2026-09-24 Updated 2026-11-05
A pair records two objects. An ordered pair has a distinguished first and second position, so and can differ; an unordered pair does not record their order. Repeated entries are permitted in an ordered pair, while is a singleton.
Pairing function Created 2026-10-03 Updated 2026-10-14
A pairing function is a computable function that gives a bijection from the Cartesian product to , with two computable functions recovering its coordinates. Here consists of the natural numbers, including zero. If is the pairing function and its decoding functions, the requirements are
Every ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.
The Cantor pairing function makes this concrete through triangular numbers:
On the diagonal , list . There are ordered pairs there, and ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from through . These intervals touch without overlapping and cover all natural numbers; within each interval the offset determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.[ref]
For example, the Cantor pairing function gives
The order of the coordinates matters: and are different ordered pairs with different codes.
Figure 1.
The Cantor pairing function on a finite window: labels are codes, and the first 21 ordered pairs fill diagonals zero through five
. Details.
To decode a natural number , find the unique diagonal index satisfying
The inequality gives , so both recovered coordinates are natural numbers. At , , hence , , and . At , and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expression
This is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large . Use an exact integer square root instead: with computed using integer arithmetic, . Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.
A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with binary digits has possible values, while two such words have possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product . Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.
Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes as
Decode the outer ordered pair first: gives . Decode its first coordinate to recover , giving the nested ordered pair and thus the original tuple .
Figure 2.
Decoding a known three-entry tuple: first unpair 257 into (18, 4), then unpair 18 into (2, 3)
. Details.
The tuple length and nesting convention must be known. The same code represents as a two-entry tuple and as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.
A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.[ref]
Use the Kuratowski ordered pair
The axiom of pairing first constructs and , then constructs the displayed pair of those sets, proving that it is a set.
For any , the intersection of the members of this pair is , and their union is . Thus equality of two ordered pairs first gives , hence , and then . If , this latter set is a singleton and forces . If , its unique member distinct from is , forcing . Hence equality of ordered pairs gives equality of both coordinates.
For a set of ordered pairs, both coordinates of every pair belong to
which is a set by two applications of the Axiom of union. Axiom of separation inside gives
These are sets, including when is empty.
The Axiom of foundation asserts that every nonempty set has an element with . If a descending membership sequence existed, replacement would give the nonempty range set . Foundation would give some disjoint from . But and , contradicting that disjointness. Thus foundation rules out every such sequence.
Conversely suppose there is no descending membership sequence, but foundation fails. There is then a nonempty set such that for every . The axiom of choice selects a function on with . Choose and use recursion to define
Every value remains in , and for every . This is the forbidden sequence. Therefore, with the stated choice assumption, foundation is equivalent to the absence of descending membership sequences. The selection step explains exactly where choice is used; dependent choice would suffice.
A logical formula. Both and are propositional variables, so and are logical formulas. Applying the binary logical implication formation rule to this ordered pair of logical formulas gives the displayed whole expression. This supplies a construction of its formula syntax tree rather than merely checking that its parentheses balance.
The unique readability theorem says that every propositional formula has exactly one of the following forms: a unique propositional variable; for a unique logical formula ; or for a unique ordered pair of logical formulas . These three alternatives are disjoint. Consequently each logical formula has a unique formula syntax tree and a uniquely determined principal logical connective whenever it is not a logical variable.
Use the Kuratowski ordered pair
The axiom of pairing first produces by pairing with itself, then , and then the pair of these two sets. The axiom of extensionality supplies the usual uniqueness of each specified set. In particular, no use of Axiom schema of replacement is needed to construct a single ordered pair from two given sets.
To recover the coordinates from , observe that
The first equality recovers . Once is known, the second recovers : if its union is the singleton then , and otherwise is its unique element different from . Hence equality of two encoded pairs forces equality of both coordinates, including the degenerate case .
The first ordered triple encoding works. If
injectivity of the ordered pair construction first gives and , and a second application gives and . The construction uses only two successive ordered pair constructions, so is a set as well.
This encoding works. Use three distinct tags and the ordered pair construction already proved injective. In the set
exactly one member has first coordinate , exactly one has first coordinate , and exactly one has first coordinate . Equality of two such sets therefore matches the members carrying each tag. Injectivity of the ordered pair construction then gives equality of , of and of , respectively.
This is a tagged encoding of a finite tuple. It remains valid when coordinates coincide with one another or with tags: the equality criterion for ordered pairs still distinguishes their first coordinates. Finite set formation using pairing and union makes the encoding a set.
This encoding works, interpreting the outer three-coordinate brackets by the nested ordered pair convention established in item 1. Equality of the outer ordered triples gives
For any fixed set , the map is injective. If , equality makes the right-hand side a singleton and forces . If , membership of in forces . Applying this argument with recovers the respective coordinates.
The outer brackets must encode an ordered triple, rather than an unordered set of three doubletons. The source uses three-coordinate angle brackets here; using the successful convention of item 1 makes their meaning explicit and supplies a genuine construction.
The independence statements are relative consistency statements. We construct models from an ambient model of ZFC; the construction is an interpretation and does not assume that the ambient model is transitive. Foundation is already true in the ordinary ambient membership structure, so its positive consistency direction is immediate.
For the negative direction, construct an extensional cumulative universe over Quine atoms. Let be a countably infinite set of formal symbols . Give each the extension . For a set of already constructed objects, let be its unique representative: set , and otherwise use a fresh tagged code . Atom codes have a different tag. Begin with and put
Set . The interpreted membership relation gives exactly the members , and gives exactly the member . This convention matters: creating a second representative for would violate extensionality. Every object is uniquely determined by its extension, so satisfies full extensionality. Every set-sized collection of objects has bounded construction rank, by ambient replacement, and hence has its representative in .
Here are the remaining axiom verifications. Empty set and pairing use and . If , its interpreted union is . Its interpreted power set is
since every subset extension has a unique representative. The pure, atom-free finite hierarchy supplies a copy of and an inductive set. For separation, translate an -formula into the ambient language, with quantifiers restricted to the definable class ; ambient separation gives the appropriate subset of , and represents it. For replacement, uniqueness in the interpreted functional relation gives an ambient definable functional image of the set . Ambient replacement makes that image set-sized, and again represents it. These arguments also establish that all the operations used have bounded construction rank.
Ambient choice gives choice in : choose a member from each nonempty extension in a set-sized family and represent the graph, using interpreted ordered pairs. But , and the nonempty set with extension has no -minimal member. Thus
Together with the ordinary model, this proves independence of foundation from the other ZF axioms, even when choice is retained.
To extend the construction to failure of choice, let the full permutation group of act on by
The singleton convention is equivariant, so this is an automorphism of . An object has finite support if some finite has the property that every permutation fixing pointwise fixes the object. Retain objects all of whose membership descendants have finite support, stopping the hereditary recursion at the atomic self-loops. This gives the hereditarily finite-supported Quine-atom model ; each belongs to it, with support .
Extensionality persists because every retained object's members are retained. Empty set, pairing, infinity and union preserve hereditary finite support. For separation on a retained set , the union of finite supports for and the formula's parameters supports the separated extension: permutations fixing those supports preserve satisfaction in . All its members are retained, so its representative is retained. For replacement, the same support fixes the functional range, because an automorphism must take the unique output at an input to the unique output at its transported input. Ambient replacement bounds that range; all its members are in , so its representative belongs to . Finally, the collection of all retained subset representatives of is an ambient set, contained in the full interpreted power set of . A support of permutes this collection onto itself, and its members are retained. Its representative is therefore the internal power set in . This verifies every ZF axiom except foundation; foundation still fails at each .
The atom set and the family of its two-element subsets have empty support and are retained. Suppose a choice function on were retained, with finite support . Choose distinct outside and transpose them. The transposition fixes and fixes the unordered pair , but moves whichever of its two members selects. Equivariance would require that selected member to be fixed, a contradiction. Hence
The full universe gives the corresponding positive-choice model. Choice is therefore independent of ZF without foundation. Unlike a permutation model with ordinary urelements, this model retains full pure-set extensionality: the atomic objects are self-membered sets, not empty objects exempted from extensionality.
The constructible-universe interpretation gives . Thus the consistency assumptions in both displayed conclusions can equivalently be taken to be ; no additional consistency strength is being used.
The axiom of infinity excludes and all smaller stages, so the cardinal is uncountable. Full semantics for second-order logic is decisive: every externally specified functional relation whose ordered pairs lie in is an allowed class parameter, even if the relation itself is not an element of .
If , choose an external cofinal function . Its graph is an allowed class parameter: each input, output and ordered pair has rank of a set below the infinite cardinal , which is a limit ordinal. The domain belongs to . The second-order form of Axiom schema of replacement would give its range as an element of . But a cofinal subset of has rank of a set and cannot belong to . Therefore .
If for a cardinal , choice supplies an external surjection . The domain belongs to and the ordered pairs of its graph have ranks below . Applying Axiom schema of replacement to this external functional class would put its range, the ordinal , in , again impossible. Hence for every .
Consequently
These are exactly the defining conditions for a strongly inaccessible cardinal. This full second-order replacement rank obstruction would not follow from Henkin semantics, where the available class relations may exclude the external functions just used.
Use the Lévy hierarchy, with bounded formulas in set theory as the quantifier-free level for this purpose. Let be the bounded ordinal predicate, and let be the bounded predicate saying that is a graph of a bijection from onto . Then cardinalhood is expressed by
All quantifiers in and are bounded by the displayed sets and the graph. Ordered-pair membership, graph functionality, injectivity and surjectivity have bounded expansions using the usual set coding of ordered pairs. The only unbounded quantifier shown is universal over . The formula is therefore and in particular a Pi-one formula modulo ZF.
In ZF, a cardinal number is an ordinal not in bijection with any smaller ordinal, so this formula has exactly the required meaning. Thus cardinalhood is Pi-one definable; the argument does not use the axiom of choice.
With the condition-first name convention used here, evaluation of a forcing name is
Since a generic filter is nonempty, there is a condition in . In the given paired forcing name, every condition is paired with both and , and there are no other lower-rank names. Therefore
This is the unordered pair of the two interpreted sets. If the interpretations coincide, it is a singleton. It is neither an ordered pair nor the set union of those interpretations. Reversing the two components in the name-pair convention changes only the syntax of the same recursive evaluation.