For the Ehrenfeucht-Mostowski theorem, let be an infinite first-order structure and any linear order. Choose a full Skolem expansion : add witness functions for existential formulas, repeat in the expanded languages, and take their union. We will construct a model of its theory containing distinct generators , , forming an order-indiscernible sequence.
Adjoin the elementary diagram of , the inequalities for , and for every expanded-language formula and every two increasing -tuples of indices, the sentences
Every finite subcollection is satisfiable in . To prove this, choose a countably infinite sequence of distinct elements of , and for each of the finitely many relevant arities color its increasing index tuples by the finite vector of truth values of the formulas of that arity. Repeated applications of the Ramsey's theorem give an infinite subsequence homogeneous for all these finitely many finite colorings. Interpret the finitely many mentioned by its elements in their index order. All indiscernibility and distinctness constraints hold, and the finite diagram fragment holds because the ambient structure is still .
By compactness theorem, a model of the full enlarged theory exists. Its Skolem hull generated by the is elementary: whenever an existential formula with parameters in holds in , its chosen witness function returns a value in , so the Tarski-Vaught test applies. Its reduct is a model of . If the index order has size , the hull has size at most , and it contains distinct generators.
Every order automorphism of induces the automorphism
To check well-definedness, write any two terms being compared over the same increasing list of their generators. Their equality is an expanded-language formula; indiscernibility of the order-indiscernible sequence preserves its truth under . The same argument preserves each relation, and the term construction preserves the functions. Applying gives the inverse. The extension is unique in the specified Skolem language since every hull element is a term in the generators; no uniqueness among all automorphisms of the reduct is being asserted. This proves the Ehrenfeucht-Mostowski theorem, including its usual automorphism consequence.
For simple typed set theory with atoms, use sorts , predicates for sets, and typed membership from sort to sort . Atoms have no members, extensionality compares sets, and every well-typed formula defines a set of the next sort. Typical ambiguity is the schema for every closed typed sentence, where the superscript raises all types by one.
Here are concrete full typed models before imposing the ambiguity schema. Choose increasing natural numbers and set
The auxiliary merely interprets the set predicate at the lowest sort. Define typed membership by
Then the other objects of are atoms, regardless of their old membership. Every subset of has its representative in , giving comprehension even for formulas with higher-sort quantifiers and parameters. Extensionality holds for the set representatives and atoms have no typed members. The rank gaps leave infinitely many atoms at each sort, and all sorts are infinite.
Consider finitely many ambiguity instances with unraised sentences , and choose a fixed window length sufficient to include every sort used and its auxiliary predecessor. Color every increasing -tuple of natural numbers by the vector of truth values of these unraised sentences in its finite rank-window interpretation. There are only colors. The Ramsey's theorem gives an infinite homogeneous set. Choose successive points from it. The first points and last points have the same color, while the latter interpretation of is exactly the former model's interpretation of . The auxiliary predecessor shifts too, so this remains true for sentences mentioning the lowest set predicate. Extend the chosen rank sequence arbitrarily to interpret the remaining sorts. This yields a model of typed set theory satisfying all the specified ambiguity instances.
Thus every finite subset of the typed axioms together with all ambiguity instances has a model. Applying multisorted compactness theorem gives
The final model satisfies first-order typed comprehension, with quantification over its own sorts and sets as in Henkin semantics.
Work inside a model of ZF. Let be a definable class bijection, with definable inverse, so that its image and inverse image of every set are sets by Axiom schema of replacement. Define new membership by
This is the Rieger-Bernays permutation model convention used here. Its basic advantage is that every prescribed old set is the new extension of the object . We verify the axioms rather than treating a membership permutation as automatically harmless.
The new axiom of extensionality follows because equality of the new extensions means , hence . The new empty set and unordered pair are and . Union and power set are represented by
Indeed, the elements of the first object are exactly the new elements of new elements of ; the elements of the second are exactly the objects whose new extensions are subsets of .
Translate an arbitrary formula recursively by replacing each atomic by . This is an ordinary definable formula in the old model. Old axiom schema of separation forms any specified subclass of , and supplies the new separated set. Old Axiom schema of replacement similarly collects the uniquely specified images of all elements of , and applying supplies its new representative. This verifies the full schemas, including formulas with unbounded quantifiers.
For axiom of infinity, define and
Then . These objects are distinct by induction: equality of with an earlier would equate old sets of respectively and distinct members. Old replacement collects , and is a new inductive set. Thus the construction satisfies every axiom of ZF except possibly Axiom of foundation.
Now interchange the old objects and and fix everything else. For we have , so its new sole member is itself: . This Quine atom contradicts Axiom of foundation. The identity permutation preserves the original model and its foundation. Hence, relative to consistency of ZF, foundation is independent of the other ZF axioms.
For the further independence result, a full permutation of a model of choice is insufficient. If the old model satisfies axiom of choice, then for any new family of nonempty new sets, old choice selects for every . Encode its graph using the new ordered pairs, and represent that graph by . This is a new choice function. We therefore add a hereditary finite-support restriction to a universe with many Quine atoms.
Start now with a model of ZFC. Put , and let interchange and for every , fixing other objects. All these transpositions are disjoint: the infinite ordinals are distinct and none is a singleton. In the resulting membership structure, is an infinite family of Quine atoms.
Build its universe by the internal transfinite hierarchy
Write for the union over the old ordinals. Apart from the atomic self-loops, an object's new members have lower construction ranks. Every permutation of therefore extends recursively to : on atoms use the prescribed permutation, and on other objects put
This is well defined and preserves . A nonatom cannot be sent to an atom, since an extension consisting solely of one atom already represents that atom. Recursing with gives the inverse, so these maps are genuine automorphisms.
Say that has finite support if every such permutation fixing pointwise fixes . Let consist of the atoms and the objects with finite support all of whose new members, recursively away from atomic self-loops, belong to . This is the hereditarily finite-supported Quine-atom model. We check why it still has the required set-theoretic axioms.
It is closed under taking new members, so extensionality remains valid. The empty object and the pure finite ordinals have empty support. Their internally represented infinite collection also has empty support, giving infinity. Pairs and unions use the finite unions of their constituents' supports; all their members remain hereditary members of .
For a set , take all objects whose new extensions are subsets of . They form an old set, since the unrestricted new power set is an old set and membership in is definable. Its representative has support contained in a support of , because an automorphism fixing permutes precisely these hereditary subsets. All its members belong to . Hence this is the power set required inside , not a claim that unrestricted external subsets are retained.
For separation, relativize the formula to . A support for together with supports of the finitely many parameters fixes the resulting subclass; its members are hereditary, so its representative belongs to . For replacement, old replacement applied to this relativized definable functional relation collects the range. Its members have a common bound on their construction ranks, by taking the supremum of the set of ranks, so the range's representative lies in . The same finite union of parameter and domain supports fixes the range by uniqueness of each image. It is therefore hereditary and belongs to . These arguments verify the full schemas. Thus .
Finally and the family of its two-element subsets belong to with empty support. Suppose a choice function for this family belongs to , and let be a finite support for . Choose distinct atoms and transpose them. This permutation fixes and fixes the unordered pair , but interchanges its two possible selected members. Equivariance would require
which is impossible. Hence choice fails in . Together with a model of ZFC, or with its full permuted model satisfying choice and failing foundation, this proves independence of axiom of choice from ZF minus foundation, relative to consistency of ZFC. All hierarchy and support arguments are internal to the starting model; no transitive-model assumption is needed.
Here and throughout, a filter on a set is proper: it contains the whole underlying set, excludes the empty set, and is upward closed and closed under finite intersections. An improper filter cannot be extended to a proper ultrafilter.
Order the proper filter extensions of by inclusion. The union of a chain is again a proper filter on a set: any two members already occur in one member of the chain, where their intersection belongs; the empty set never appears. By Zorn lemma, take a maximal proper extension . If , adjoining must make the generated filter improper, so some has . Upward closure then gives . Exactly one of belongs to , proving the ultrafilter lemma.
Let be nonempty structures for a common first-order language, and let be an ultrafilter on the index set . In the ultraproduct , identify functions when ; interpret function symbols coordinatewise and relations by membership of their coordinate truth sets in . The Łoś theorem states, for every first-order formula ,
Changing representatives changes a coordinate truth set only outside a member of , so the definitions are well defined.
Prove the theorem by structural induction on formulas. An induction on terms gives , and therefore the required equivalence for atomic equality and relation formulas. For conjunction the truth set is an intersection, and a finite intersection belongs to a proper filter on a set exactly when each constituent does. For negation it is a complement, and the ultrafilter decides exactly one of a set and its complement. These prove the Boolean induction steps.
For the existential step, a witness in gives, by induction, a member of on which holds. It is contained in the coordinate existential truth set, so that set belongs to . Conversely, if
choose a coordinate witness for , and any element of the nonempty factor otherwise. Then the truth set of contains . Induction gives a witness in the ultraproduct. Universal quantification follows from negation and existence. This completes the actual proof of the Łoś theorem.
For the compactness theorem, take to be the set of finite subsets of , and choose a model of each such subset. The cones
are nonempty and satisfy . They generate a proper filter on a set, which extends to an ultrafilter by the proved lemma. For every , the coordinate truth set of contains . The Łoś theorem therefore gives
This proves the requested compactness theorem. In fact the same proof works without the countability restriction on the language.
Represent the arena by a pruned set-theoretic tree of legal finite positions. Players I and II alternate; every position has a legal continuation. The usual terminal-position convention can also be handled by adding terminal wins and losses at the initial stage. Give the branches the product topology generated by finite-position cylinders, and let be I's winning open set.
Define the winning-position attractor in an infinite game by transfinite recursion. Start with
At a successor stage retain and add I-positions with at least one child in , and II-positions with every child in . At a limit stage take the union. The increasing sequence stabilizes because the positions form a set: strict increases at arbitrarily many stages would select too many distinct positions. Write for the stable set. The rank of a position in is its first entry stage; any positive such rank is a successor ordinal.
If the initial position belongs to , at every I-position of positive rank choose a child that was present at the preceding stage. Every move by II also leads to a child of smaller rank, by the rule for II-positions. There is no infinite strictly decreasing sequence of ordinals, so every play following this strategy in an infinite game reaches after finitely many moves. Its complete branch then belongs to . Hence this is a winning strategy in an infinite game for I.
If the initial position is outside , every move of I stays outside . At a II-position outside at least one child is outside : otherwise the entry ranks of its set of children have a common ordinal bound, and that position would enter at the next stage. Choose such a child. This gives II a strategy in an infinite game that never enters . A resulting branch cannot belong to , because is an open set and would therefore have a finite prefix whose whole cylinder lies in , namely a member of . Thus II wins. This proves the Gale-Stewart theorem for an arbitrary set-sized arena, in the ordinary metatheory with choice. Countability of the move set was never used.
The restriction on the payoff is essential. Under the axiom of choice, already for binary moves there is an undetermined game. There are strategies for each player, since a strategy is a binary-valued map on a countable set of positions. List I's strategies and II's strategies for . Each strategy is compatible with different plays, obtained by varying all the opponent's binary moves.
At stage , choose a fresh play following and then a different fresh play following , avoiding every previously chosen play. Fewer than plays have been used at that stage, even when is singular, so these choices are possible. Let . No I-strategy wins , because its selected is outside ; no II-strategy wins, because its selected is inside . Future choices avoid all earlier , so they never spoil the first assertion. This is the choice diagonalization of an undetermined game. Consequently determinacy for all payoff sets is incompatible with the axiom of choice. The attractor still makes sense for a nonopen payoff, but an avoiding play may then enter the payoff without ever having a winning finite prefix.
The printed arrow is a partial-function arrow. Thus the central objects are partial computable functions , with total computable functions as the special case in which every input has an output. Here includes zero; changing this convention by a computable shift changes none of the results. A program computing must halt with output exactly on its domain, and run forever elsewhere. A finite program is a function in intension, whereas its possibly partial input-output map is a function in extension; many programs have the same extension.
A precise machine model is a register machine with finitely many instructions to increment a register, decrement it conditionally, jump, and halt. Registers hold natural numbers. A Turing machine instead uses a finite transition table, a finite alphabet and an unbounded tape. These models simulate one another: encode the finite nonblank tape, state and head position as numbers for the register simulation; conversely represent each register by a finite tape block and implement its increment and decrement by finite scans. Tuple inputs can be encoded by a primitive recursive pairing function. The equivalence of these formal models is a mathematical result. Their identification with every informal effective procedure is the Church–Turing thesis, rather than an additional mathematical theorem about an already formal notion.
There is also an algebraic description. Begin with zero, successor and projections, close under composition of partial functions and primitive recursion, and then under unbounded minimization. The primitive recursion scheme is
Applied within the primitive recursive class it produces only total functions, by mathematical induction on . Unbounded minimization searches for the first zero of ; its output is defined only if that search reaches such a zero with every preceding necessary computation defined. Composition is likewise strict about the intermediate values it requires. These schemes compile into machine programs using finite subroutines, loops and an unbounded search loop.
For the converse, encode a machine's finite configurations and finite computation histories using Gödel numbering. Testing that a history starts with the specified input, that every adjacent pair follows the transition table, and that its final configuration halts is primitive recursive: all the tests are bounded by the finite code. Extracting the final output is primitive recursive too. For a suitable checking predicate and output decoder this proves the Kleene normal form theorem:
The symbol means equality of values and of definedness. A halting computation has a passing history code and every passing history has its actual output; a nonhalting computation has none. This proves that the partial recursive and machine-computable functions coincide, including their domains of divergence.
Finite programs can be effectively listed. Simulating the program with index gives a universal partial computable function . Fixing some inputs is effective syntactically: prepend instructions writing those constants and then call the original program. This proves the S-m-n theorem in this machine presentation. In particular, reductions that construct a program from numerical parameters really do produce its index effectively.
The primitive recursive functions are a proper subclass of the total computable functions. Enumerate all valid unary primitive recursive descriptions, interpreting invalid descriptions as zero. Evaluating any fixed valid description terminates by structural induction. Thus the diagonal map is total and computable, but cannot be one of the enumerated primitive recursive maps, since . This is a total computable diagonal over primitive recursive syntax. The evaluator can terminate on every particular description without itself being primitive recursive.
In contrast, one cannot effectively enumerate exactly the programs for all total computable functions. If such an infinite enumeration were available, wait for its th program and run it on , then add one. Totality makes this another total computable function, while its diagonal disagrees with every listed function. Equivalently, there is no total computable universal evaluator listing precisely all total computable maps.
The halting problem is undecidable. If decided whether program halts on , construct a program which halts on input exactly when says that it does not halt. Taking to be 's own index gives a contradiction. The halting relation is nevertheless computably enumerable, since finite halting histories can be searched for.
More generally, a set is computably enumerable exactly when it is the domain of a partial computable function. From an enumeration, halt on when appears; in the other direction use dovetailing over all inputs of a partial program to enumerate its halting inputs. A set is a computable set exactly when both it and its complement are computably enumerable: dovetail the two searches and return the answer from the one that succeeds. Neither a semidecision procedure nor an unbounded search supplies a uniform negative answer.
Finally, the Rice theorem explains the scope of this obstruction. Let be a nontrivial property of the extension of a partial computable program. Choose a partial computable whose -status differs from that of the nowhere-defined function. Given a program and input , effectively form the program which, on , first waits for to halt and then computes . If never halts its extension is nowhere defined; otherwise its extension is . A decision procedure for would therefore decide the halting problem. Effective descriptions allow universal simulation and positive verification, but not a decision procedure for every semantic property or for termination.
We first prove the simple Artinian case of the Artin–Wedderburn theorem. This part does not need finite dimension over . Choose a minimal nonzero left ideal , using the descending chain condition. Simplicity gives . Also : otherwise would be zero, since each lies in . Choose for which right multiplication is nonzero. By simplicity of , it is an automorphism. Choose with . Then , and injectivity of gives . Thus .
Right multiplication by splits the left regular module as . Repeat within the remaining left ideal: if it contains a minimal left ideal generated by an idempotent, the map splits off . Each nonzero remaining complement is a strictly smaller left ideal, so the Artinian condition terminates the process. Therefore the regular module is a finite direct sum of minimal left ideals.
All these simple summands are isomorphic. For primitive idempotents , simplicity gives , so ; otherwise would be zero. A nonzero element of defines a nonzero homomorphism , which is an isomorphism between simple modules. Thus as a left module. Put , a division algebra by the Schur lemma. Right multiplication gives
Taking opposites, with matrix transposition reversing products, proves
The construction is -linear and embeds into the center of .
A central simple algebra is a finite-dimensional simple -algebra whose center is exactly . The Brauer group consists of such algebras modulo matrix stabilization: represent the same class if for some positive integers . Its operation and inverse are
The tensor product is central simple, and by , explaining the inverse. Both facts can be checked after a splitting field of a central simple algebra extension, where they are matrix-algebra identities, and descended by faithful scalar extension. Every class has a unique central division-algebra representative, by the regular-module description above.
To prove infinitude over explicitly, put and, for , let
This is a quaternion algebra. It is central simple: the center is , and after adjoining its generators have the faithful matrix model
These generate ; consequently a nonzero proper two-sided ideal over is impossible. The quaternion conjugation gives
A nonzero element has an inverse exactly when this norm is nonzero. Thus is a division algebra when is not an norm; if is a norm it has a nonzero zero divisor and is by the classification just proved.
For a prime , every nonzero rational sum has even -adic valuation. Divide out the minimum valuation of ; cancellation modulo is impossible because is not a square modulo . Therefore is not an norm, and is a nontrivial division-algebra Brauer class. This is the quaternion norm obstruction at primes congruent to three modulo four.
We also prove the product rule needed to distinguish classes. In , write the generators as . The commuting subalgebras generated respectively by
are and the split quaternion algebra . The latter has the matrix model and . Together the two subalgebras generate the whole tensor product, since they recover and . Dimensions are sixteen on both sides, giving
Quaternion conjugation identifies with its opposite, so these classes have order at most two. For distinct primes , the parameter has odd valuation at , so is a division algebra. Thus . There are infinitely many such primes: if their list were , the integer would have a prime factor congruent to three modulo four outside that list. We conclude
Indeed the same valuation argument for any nonempty finite product gives independent quaternion classes over rational numbers.
For , we prove the required division-algebra classification. Let be finite-dimensional and central over . If , choose a nonreal element; its irreducible real minimal polynomial is quadratic, so translating and rescaling it gives with . The centralizer of is a finite-dimensional division algebra over , with that field central. Every element has a split minimal polynomial over , hence belongs to , so .
Conjugation by is an involution, giving , where . If , then , contrary to its center being . Choose in . For any , commutes with , so . Also and commutes with , forcing . It cannot be positive, since , or zero, since is a division algebra. Rescale to . Consequently
Conversely the positive definite quaternion norm makes a division algebra. The two possible central division representatives are therefore and . They are not equivalent, and conjugation identifies with its opposite, so
This uses the finite-dimensional real division-algebra classification directly, not as an unexplained theorem citation.
Finally let be a separable closure and . The cohomological description is
Here has the discrete topology and its natural Galois action. For a finite Galois splitting field , identify with a matrix algebra. Its descent action is implemented by matrices , unique up to scalars, so
The inverse convention here agrees with the crossed-product convention below. The semilinear operators commute with the descended algebra ; their crossed product has class by the commuting-factor decomposition of the full endomorphism algebra. Inverting its scalar cocycle therefore gives the class . Associativity gives the two-cocycle identity, and changing the representatives changes by a coboundary. Conversely a two-cocycle defines the crossed-product algebra of a Galois extension, with and . It is central simple and split by . Galois descent identifies coboundaries with split matrix-algebra classes and gives . Every central simple algebra has a finite separable, hence finite Galois, splitting field, yielding the displayed limit.
For a left -module, group cohomology is
with the trivial module. Equivalently take a projective resolution and the cohomology of . This also describes the right-derived functors of the invariant-module functor .
For an explicit model, the homogeneous bar free resolution has , with diagonal -action and boundary the alternating sum of coordinate deletions. It is free over : each orbit has a unique representative with first coordinate . The augmented complex is exact because inserting as a first coordinate supplies a contracting homotopy of underlying abelian groups; its lack of -equivariance does not affect exactness. The associated inhomogeneous group cochains are functions , with
For group cochains of degree zero, . Adjacent deletions cancel in pairs, giving and hence .
In degree zero this gives
It is also , since a map is determined by the invariant image of .
In degree one the cocycle condition is , so
These are crossed homomorphisms modulo principal crossed homomorphisms. For trivial action they reduce to ordinary group homomorphisms, so .
There are two further useful descriptions. If is the augmentation ideal, a crossed homomorphism gives an equivariant map by , because . Applying to therefore gives
Also a section of has the form and is a group homomorphism exactly when is a crossed homomorphism. Conjugation of sections by an element of changes by a principal crossed homomorphism. Thus classifies the -conjugacy classes of such sections, or equivalently of complements to in the semidirect product.
In degree two, a normalized two-cocycle satisfies
Define multiplication on by
The displayed cocycle identity is precisely associativity; normalization gives the identity and inverses exist. This produces a group extension with the prescribed action on .
Conversely a set-theoretic section , , gives in the additive kernel of a group homomorphism. Associativity gives the cocycle condition. Replacing by changes by
The resulting extensions are equivalent through a change of coordinates in . Conversely any extension equivalence preserving both kernel of a group homomorphism and quotient yields such a change of section. Hence
The zero class corresponds exactly to a split extension. With trivial action these are central group extensions; addition of classes corresponds to the Baer sum. This proves the second group cohomology classifies group extensions interpretation.
For and trivial coefficients , put . The Koszul resolution for a rank-two free abelian group is
where and . To check exactness at , reduce modulo . Since is not a zero divisor in , write , and cancellation gives . Injectivity of follows because is a domain. The augmentation kernel is generated by , proving the other exactness statement.
Applying makes both differentials zero, since act trivially. Thus
Degree-one classes assign arbitrary integers to the two generators. Geometrically these are also the cohomology groups of the torus, a classifying space for ; its cohomology ring is the exterior algebra on the two degree-one classes.
The integer in degree two has an explicit extension representative. On triples , set
The bilinear term is a two-cocycle. With generators , and central ,
Every central extension of by has this form: choose lifts of the two generators and the fixed generator of the kernel of a group homomorphism, then their group commutator determines and every element has a unique form . Changing the lifts by central elements leaves that commutator unchanged. Thus distinct integers give inequivalent extensions, and the cocycles add with . The case is ; is the integer Heisenberg group. This realizes the integral central extensions of a rank-two free abelian group concretely.
For a finite-dimensional algebra over an algebraically closed field, basic algebra means , so its simple modules are one-dimensional and occur once in the semisimple quotient of the regular module. A hereditary ring has every submodule of a projective module projective; equivalently its global dimension is at most one.
Choose representatives of the simple modules. Our Ext quiver convention gives one vertex for and
With primitive orthogonal idempotents , put and . Applying to gives
The restriction map from is zero since every map to a simple kills , and is projective. Thus the arrow multiplicity is . This specifies the orientation rather than silently replacing the quiver by its opposite.
Because is hereditary, is projective. Its semisimple top has copies of , where is the arrow multiplicity. Its projective cover therefore supplies an epimorphism
This splits by projectivity of . Its kernel is a summand contained in the radical of the source; projection onto that summand and Nakayama lemma force the kernel to be zero. Hence
Every arrow forces , so has no directed cycles.
Choose lifts in of bases of the arrow spaces. Send the vertices and arrows of the path algebra to these idempotents and lifts, multiplying paths in the order for consecutive arrows , . This defines an algebra homomorphism . It is surjective: vertices span , arrows span , and products show that paths of length span . Nilpotence of then gives all of .
Let be the number of directed paths starting at , including the length-zero path. Acyclicity gives the same recursion , with value one at a sink. Induction from sinks gives . Therefore
The surjective homomorphism is an isomorphism. This proves the basic hereditary algebra path-algebra theorem:
For each connected component of the underlying unoriented graph, is a central idempotent. Paths never connect distinct components, so as a direct sum of two-sided ideals. To prove each is a block, let be any central idempotent. Modulo the arrow ideal it has coordinates . Commuting with an arrow and reducing modulo the square of that ideal gives . Thus these coordinates are constant on each component. If they are zero on a component, the restriction of there is a nilpotent idempotent, hence zero; if they are one, apply that argument to . Consequently
An idempotent gives a projective module , since . It is primitive when it cannot be written as a sum of two nonzero orthogonal idempotents. This is equivalent to indecomposability of : a projection onto a direct summand is an idempotent of , and conversely such an idempotent splits . Starting with , split any nonprimitive summand repeatedly. The process terminates because each splitting increases the number of nonzero vector-space summands in a finite-dimensional algebra. Thus
with orthogonal primitive idempotents and indecomposable projective modules. Each summand is generated by its idempotent.
Let . A Frobenius algebra is a finite-dimensional algebra with as left modules over , where . Equivalently there is a linear functional for which is nondegenerate. A symmetric algebra satisfies the stronger bimodule isomorphism , with ; equivalently the functional can be chosen with . This is the associative-algebra meaning of symmetric, rather than the symmetric algebra of a vector space.
For a finite-dimensional module,
The socle is its largest semisimple submodule, and the radical of a module gives its largest semisimple quotient. With one has and : is semisimple, and annihilates every simple module.
Now let for a primitive idempotent, allowing the field to be nonsplit. Symmetry identifies with through the pairing
It is nondegenerate on these corners. If , choose with ; then . The other variable is treated similarly. The pairing respects the left -action, so
The right-module quotient is simple. A primitive idempotent remains primitive modulo the nilpotent radical: idempotents lift through that radical, so a decomposition in the quotient would lift to one in . In the semisimple algebra , the left simple and the dual of the right simple belong to the same matrix block. There is exactly one left simple isomorphism class in that block, even over a nonalgebraically closed field. Hence the head-socle identity for a symmetric algebra is
This is an isomorphism of left modules, and need not be canonical.
For the modular examples put , , so and . The coefficient-of-identity functional on the group algebra is symmetric and nondegenerate, so the identity just proved applies.
In characteristic two, the central idempotents are and . The first block has basis and is . For the second, choose a primitive cube root and use
The two -eigenlines are interchanged by , proving irreducibility. Polynomial interpolation in gives diagonal matrix units, and multiplying by gives the off-diagonal units. Thus the four-dimensional block maps onto and is isomorphic to it:
There are two simple modules, the trivial one-dimensional module and the two-dimensional module ; the sign module equals . Their projective covers are , with layers , and . The regular module is , and the Cartan matrix of a group algebra is . Every module is a sum of : the first block is classified by Jordan chains for a nilpotent linear map of lengths one and two, while the matrix block is semisimple. Thus there are exactly three indecomposable isomorphism classes. This describes the 2-modular blocks of S3.
In characteristic three put . The ideal satisfies , and , so . The only simples are the trivial and sign modules . Put . The projectives have dimension three. A convenient radical generator is :
The basis gives the radical layers
Thus and its Cartan matrix of a group algebra is
The elements and give one arrow in each direction between the two simples. All paths of length three vanish, and the six paths of lengths zero, one and two are linearly independent. Hence is the path algebra of that two-vertex oriented cycle modulo the ideal of paths of length three. Its connected quiver also proves there is a single block of S3 in characteristic three.
Any module is a -graded vector space given by the -eigenspaces, with interchanging the grades and . Constructing Jordan chains with homogeneous bases in the kernel and image filtrations and homogeneous lifts decomposes it into graded chains. Each chain has length or and is determined by its top sign. It is a uniserial module and hence indecomposable. Consequently there are exactly six indecomposables, the length- quotients , .
Write and , its Jacobson radical. First suppose the characteristic is . We prove the counting statement through the cocenter of a finite-dimensional algebra
where is the linear span of commutators, not an ideal. In a group algebra, this span is exactly the span of differences of conjugate group elements: is such a difference, and . Consequently has one basis vector for each conjugacy class.
There is a well-defined Frobenius map on an algebra cocenter
Here is additive and . To prove additivity, expand into words of length . Cyclic rotations of a word are equal modulo commutators. Every nonconstant word has a rotation orbit of length , so its orbit contributes zero; only remain. Also
because the two products are cyclic rotations. Additivity then shows that the whole commutator subspace maps to zero, proving well-definedness on the quotient.
Let be the number of simple modules up to isomorphism. The semisimple algebra is : over an algebraically closed field, a finite-dimensional division algebra is the field itself, since the minimal polynomial of any element splits into linear factors and a division algebra has no zero divisors. In a matrix algebra, the commutator subspace is precisely the traceless matrices. Off-diagonal matrix units are commutators, and ; these span that subspace in every characteristic. Thus
The map induced by on each coordinate is , since . This is bijective because is a perfect field.
The natural surjection has kernel . Every kernel class has a representative in . Since is nilpotent, kills that kernel for sufficiently large . On the quotient it remains bijective, so its image has dimension exactly . On the conjugacy-class basis, however,
For large , every is a p-regular element; moreover the -power map permutes the p-regular conjugacy classes, because an inverse exponent can be chosen modulo the prime-to- part of the exponent of . The stable image therefore has precisely those conjugacy classes as its basis. Comparing dimensions proves
This argument uses dimensions of semilinear images: a bijective scalar Frobenius map preserves dimension, so the usual rank count applies.
In characteristic zero every group element is relevant. Averaging a linear projection onto a submodule over makes that projection -equivariant, proving Maschke's theorem and semisimplicity of . The same matrix-algebra cocenter calculation now gives , the total number of conjugacy classes.
For the second request, is a relative projective module for when every -equivariant epimorphism onto which splits after restriction to already splits over . Equivalently is a direct summand of , the induced representation of the restriction of a representation to . We can verify the defining splitting property directly: if has an -linear section , choose representatives of the left cosets and set
The sum is independent of representatives by -linearity. Reindexing proves -linearity, while . Hence every is relatively -projective when the index is invertible in .
For completeness the canonical induced-module epimorphism has the explicit -linear section
It exhibits the promised direct summand and is the projectivity detected on a subgroup of invertible index construction.
Here a nowhere locally homogeneous metric means a smooth Riemannian metric with no nonidentity local isometry: an isometry between open subsets must fix every point of its domain. This is the strong local-rigidity meaning of “bumpy” used in this question, not the different convention about nondegenerate closed geodesics. Sunada's local isometry lemma states that, on a closed smooth manifold of dimension at least two, such Riemannian metrics form a residual subset of the space of smooth Riemannian metrics and are dense in its topology. In dimension one this conclusion is false: arclength coordinates give local translations for every Riemannian metric.
For maps , the jet bundle of maps records the source point, the target value and all derivatives through order . There are monomials of total degree at most in variables. Hence
Over , the value is already fixed, so the fibre has dimension
In local coordinates it is the space of Taylor series coefficients of orders one through , represented by a direct sum of symmetric powers, . This direct sum identification is coordinate-dependent for : higher derivatives mix with lower ones under nonlinear coordinate changes. Intrinsically, the truncation to order is an affine bundle modeled on . For the fibre is canonically .
For the density assertion as printed, an isometry is a bijective Riemannian isometry. A localized volume perturbation suffices; it is not necessary to prove the stronger generic local-rigidity lemma afresh. We take the coordinate-ball basis without repetitions, and each as the interior of its smooth closed-ball closure. Distinct such domains have a nonempty open difference in at least one direction. Indeed, if both were contained in the other's closure, their regular-open property would make them equal.
Fix any Riemannian metric . If the two domains have unequal volumes, they cannot be isometric, so already lies in the desired complement. Otherwise, after interchanging the two indices if necessary, choose a nonnegative nonzero smooth bump function supported in , and set
These are positive-definite smooth Riemannian metrics tending to in the topology as . Their Riemannian volume forms satisfy . The Riemannian metric and volume on are unchanged, whereas
For every sufficiently small , the volumes differ. Thus no isometry of the two closed domains exists, proving
The volume difference is continuous in the smooth topology, so the unequal-volume Riemannian metrics even form an open dense subset of this complement. The regular-open assumption is also needed to justify this literal closed-domain assertion. As written, requiring only that each closure be a closed ball permits two distinct basis members with the same closure. For example in , adjoin and to a countable basis of a topology of coordinate balls. Both are open and both closures are the same closed ball. The identity is an isometry of those closures for every Riemannian metric, so the indicated complement is empty. Thus the conclusion needs distinct closures, as in the usual basis of genuine coordinate balls used above. The no-repetitions convention is necessary as well: if the indexed basis repeats a domain, its identity map is always an isometry and the asserted complement for those two indices is empty. This volume argument concerns isometries onto the specified whole domains; the stronger assertion excluding arbitrary local isometries is the separate Sunada lemma stated above.
Retain and define the heat operator by . A Riemannian heat kernel satisfies for and has the delta initial limit
On standard Euclidean space the kernel is
On the Riemannian manifold, the Gaussian function factor in the local construction uses in place of .
Choose an open neighbourhood of the diagonal such that every pair is joined by a unique short minimizing geodesic and with the inverse exponential map smooth in both variables. It can be obtained from normal coordinates tubes of radius smaller than the local injectivity radius, or from normal neighbourhoods with geodesic convexity. Then is smooth on . Write the Riemannian volume form in normal coordinates as , where is smooth and .
For fixed , radial divergence in normal coordinates gives
For , use away from the diagonal and the product rule to obtain
The identities extend smoothly in the expressions involving , even though itself is not smooth on the diagonal. The singular powers cancel if
The correct initial normalization is . These heat-kernel transport equations have the explicit solutions
and, recursively,
To derive the integral, multiply the radial equation by and integrate the derivative of from zero to . The zero integration constant is forced by smoothness when . Changing variables from radial distance to gives the displayed nonsingular expression. Its integrand is smooth in , so differentiation under the integral proves inductively that every is smooth across the diagonal. In particular .
Summing the product-rule identity makes adjacent terms telescope. For , the only term remaining is
This also fixes the sign convention: with the nonnegative Laplace-Beltrami operator , the right-hand side would instead be .
A heat parametrix is an approximate kernel with the same delta initial limit and an error under that is sufficiently regular, or flat, at to be corrected by time convolution. On a closed compact manifold choose a smooth cutoff equal to one near the diagonal and supported in . A finite-order explicit parametrix is
Near the diagonal its error is . Derivatives of produce errors supported a positive distance from the diagonal, where decays faster than every power of . Taking large makes the whole error as regular at time zero as any specified finite number of derivatives requires. Its initial delta limit follows from and the Euclidean Gaussian function change of variables .
One may obtain a smooth error flat at zero by summing all coefficients with time cutoffs. Let equal one near zero and zero for arguments at least one, and choose sufficiently fast. Set
For each the sum is locally finite. Choosing successively so that the th term and its derivatives through order have bounds on their cutoff transition regions gives the usual smooth asymptotic sum. For any fixed derivative order, its tail is then smaller than an arbitrarily high power of ; the transport identities cancel all earlier orders. Consequently extends smoothly and flatly to .
Here is the Volterra parametrix correction, with the order of the Volterra convolution of kernels factors specified. Define
Since acts in the second spatial variable and has the delta initial limit, . Thus
Indeed, by the geometric-series cancellation, whence . If on a bounded time interval and , then
This proves convergence; the smooth flat error permits the corresponding derivative estimates. The correction has zero initial limit, so retains the delta initial condition. Uniqueness of the heat equation on a closed compact manifold identifies this kernel with the global Riemannian heat kernel.
The local coefficient construction requires no compactness. The global uniformly bounded convolution argument just given uses a closed compact manifold, the usual spectral-geometry setting. For noncompact or incomplete Riemannian manifolds one must specify the heat realization and justify global convergence separately; a canonical choice is the minimal kernel obtained as the increasing limit of Dirichlet kernels on a smooth relatively compact exhaustion. This gives the minimal heat semigroup rather than asserting an unqualified uniqueness statement at infinity or at a missing boundary.
Fix a bounded tile in Euclidean space with labelled flat boundary faces. For each face label , encode an assembly of copies by an involutive real symmetric signed permutation matrix : a paired interface contributes a two-by-two swap, an unglued face with a Neumann boundary condition contributes on the diagonal, and an unglued face with a Dirichlet boundary condition contributes . Use the same face-identification convention on each copy. If a second assembly has matrices and there is an invertible constant matrix satisfying
then the map is an isomorphism between corresponding Laplace-Beltrami operator eigenspaces. This is the transplantation theorem.
To prove it, restrict an eigenfunction to the tile copies and identify each copy with . Along a face, let be its vector of boundary values and its vector of outward normal derivatives. At a glued interface the values agree and the outward derivatives are opposite. At an unglued face with a Neumann boundary condition the derivative vanishes, and at a face with a Dirichlet boundary condition the value vanishes. All three cases are encoded by
The intertwining identities give and , so the transplanted function satisfies the second assembly's interface and boundary conditions. On each tile its Laplace-Beltrami operator is the same constant linear combination of the original Laplacians, hence it has the same eigenvalue. Across an interface, matching values and opposite normal derivatives make it a weak solution; elliptic regularity, or the allowed reflection principle, makes it a genuine smooth solution there. At corners the operator is understood by its finite-energy, Friedrichs extension; the same matching argument applies to its quadratic form domain. Applying reverses the construction. Thus dimensions of all eigenspaces agree, including multiplicities, and the two specified boundary-value spectra coincide.
The requested pair exists with explicitly specified mixed boundary conditions and polygonal boundary. Take four copies of an octagonal regular polygon in Euclidean space. Label four alternate sides in cyclic order; the four intervening sides always have a Neumann boundary condition. The labelled sides are disjoint even at their endpoints. Parameterize every side in the positive boundary direction of the reference octagon. When pairing same-labelled sides, identify equal parameters. This produces a locally flat surface with boundary: a neighbourhood of an interior point of an interface consists of two half-disks glued along their diameters. All tile vertices remain boundary points, with boundary angles or ; there are no interior cone points.
Here are the complete gluing and boundary conditions. An entry pairs the corresponding sides of . The indicated unpaired sides have a Dirichlet boundary condition; every other unpaired side has a Neumann boundary condition.
Both assemblies are compact and connected. The Laplace-Beltrami operator is the nonnegative operator associated with the finite-energy quadratic form , with zero Sobolev trace on the specified Dirichlet arcs. Thus the mixed boundary condition is defined without requiring classical differentiability at a corner or at a Dirichlet–Neumann junction.
The four signed permutation matrices for are
For they are
Use the Hadamard matrix
The intertwining relations can be checked on all columns at once. Writing the columns of as , direct application of the displayed gives
For the four intervening faces both assemblies have the identity face matrix, so these intertwining relations hold as well. Also . This four-tile mixed-boundary transplantation between a disk and a nonorientable surface gives a bijection of every pair of eigenspaces, preserving eigenvalues and multiplicities.
There is also a direct argument on the quadratic form domains that handles all boundary corners. The orthogonal matrix acts on tile restrictions, preserves their L2 inner product and the sum of their Dirichlet energies, and commutes with taking a Sobolev trace. The condition on each face encodes equality of the two traces at a paired interface and vanishing trace at an unpaired Dirichlet face. Intertwining takes these conditions exactly to . Consequently maps the whole form domain onto the other form domain and preserves its quadratic form. The associated self-adjoint operators are unitarily equivalent, proving isospectrality for the stated mixed boundary conditions without any assumption of smoothness at a Dirichlet–Neumann junction.
We now verify the actual topology using the topology of disk tiles glued along disjoint boundary arcs. Because the gluing arcs in each tile are disjoint, the resulting surface with boundary is a thickening of its gluing graph, with one vertex for each closed disc tile and one edge for each paired arc. One can construct this homotopy equivalence by taking a small central closed disc in each tile and narrow strips to its paired arcs. What remains is a collar neighbourhood of the boundary, which retracts onto this connected system of closed discs and strips. Shrinking each central closed disc and each strip then gives the gluing graph. Equivalently, begin with a spanning tree of the gluing graph: its closed disc tiles joined along boundary arcs form one closed disc, and every remaining pair of boundary arcs adds one band. Thus for tiles and paired arcs the fundamental group is a free group of rank , and the Euler characteristic is .
For , the gluing graph is the path
Gluing a new closed disc to a closed disc along one boundary arc again gives a closed disc; applying this three times proves that is homeomorphic to a closed disc. In particular
For , the five paired arcs give the graph edges . It is connected, and hence
Here is the free group on two generators, so is not simply connected. To decide orientation of a surface, give every reference tile its counterclockwise orientation. Our same-parameter gluing preserves boundary directions, so a global orientation requires opposite orientation signs on paired tiles: the two induced boundary orientations at an interior interface must be opposite. Such signs exist exactly when the gluing graph is bipartite. In the cycle
has length three. Following it forces the sign to reverse three times and return to its starting tile with the opposite sign. This proves that is a nonorientable surface. It has nonempty boundary because every intervening octagon side remains unpaired. Thus is a simply-connected orientable surface with boundary, whereas its isospectral partner is neither simply connected nor orientable, exactly as required, for the specified mixed boundary problem.
The boundary qualification is essential. With smooth boundary and the same pure Dirichlet boundary condition or pure Neumann boundary condition on both surfaces, the following existing obstruction applies. Polygonal corners and the mixed boundary conditions in the construction above place it outside that obstruction.
With the interpretation of compact smooth Riemannian surfaces with the same pure Dirichlet boundary condition or pure Neumann boundary condition, the printed simply-connected/nonorientable pair cannot exist. The two-dimensional heat trace has the following expansion (the smooth-boundary coefficients are given in the heat-coefficient formulas, Theorems 5.1–5.2):
where the boundary sign is minus for Dirichlet and plus for Neumann. The Gauss-Bonnet theorem identifies the constant term with . Isospectrality therefore forces equal Euler characteristics. A compact connected simply-connected surface with boundary is a disk and has . A connected nonorientable surface with crosscaps and boundary components has . Thus no such smooth pure-Dirichlet or pure-Neumann pair exists. This is the Euler characteristic from the heat trace of a bordered surface.
Piecewise-smooth boundaries introduce corner terms, and mixed boundary conditions change the heat coefficients, as the explicit construction above demonstrates. Moreover, in the usual pure-Neumann polygonal reflection-transplantation setup, the pure Neumann reflection transplantation preserves Euler characteristic argument applies even with corners. The numbers of tiles agree. For each face label the number of edge classes is , so these agree too. For each tile-vertex label, vertex classes are orbits of the subgroup generated by incident-face involutions. Their number is the dimension of invariant vectors in that permutation representation, which is unchanged by the intertwiner. Hence the numbers of vertices agree, proving equal . Thus this standard tiled construction also cannot supply a disk on one side and a nonorientable surface on the other.
For comparison, the following existing construction gives an orientable and a nonorientable pair with the same spectrum for the pure Neumann boundary condition. Both have nontrivial fundamental groups; this is a separate example, not the construction used to meet the simply-connected requirement above. This eight-tile Neumann transplantation across orientability makes the comparison explicit. The finite seed is the affine modulo-eight example in the original orientability construction; the intertwiner and the topology checks are derived below. Take eight copies of a regular Euclidean hexagon and label three pairwise nonadjacent sides . Every remaining side is a side with a Neumann boundary condition. Index the copies by . For the first assembly pair same-labelled faces according to
for the second, use
with all arithmetic modulo eight. A fixed point means an unglued side with a Neumann boundary condition. Pair faces by the reflection convention, matching the same endpoint parameter in the reference tiles. The distinguished sides are disjoint, so no interior vertex singularities are created; the resulting surfaces have polygonal boundary corners.
Let on the eight-dimensional tile-index space and set
It commutes with the permutation matrices for and , because its coefficients are invariant under reversing cyclic order. For , write , where , , and all other vanish. The required relation is exactly , verified from these four nonzero entries. Thus all three intertwining relations hold.
The cyclic Fourier vectors diagonalize . Its eigenvalues are
namely . None is zero, so is invertible and the two assemblies are isospectral manifolds for the Neumann boundary condition.
We prove their topology as well. Their gluing graphs are connected: the first contains the spanning path , and the second contains the spanning cycle . Each has eight tile vertices and ten paired-face edges. Since tiles are disks and gluing arcs are disjoint, each surface retracts up to homotopy to this multigraph; thus its Euler characteristic is and its fundamental group is a free group of rank three.
An orientation assigns a sign to each reference tile, and a reflection gluing requires opposite signs at the ends of every graph edge. The second graph admits this assignment: take sign on and sign on . Every paired face joins opposite signs, proving orientability. In the first graph the cycle
has odd length. Transporting orientation around it reverses the initial sign, proving nonorientability. Hence the first surface is also not simply connected. The second surface is orientable but likewise not simply connected; the disk required in the question is supplied instead by the four-tile mixed-boundary construction above.
The four-tile construction resolves the printed simply-connected requirement under explicit mixed boundary conditions. The eight-tile comparison only concerns orientation of a surface under a pure Neumann boundary condition.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact