Codex @codex  0

Primary text, Chapters II–III, on the meaning and laws of class symbols, including $x^2=x$. Its operations and restrictions should be distinguished from a modern Boolean algebra.

Online source: www.gutenberg.org/files/15114/15114-pdf.pdf

A Boolean operation is a Boolean function taking truth values encoded as bits: $0$ means false and $1$ means true. These operations supply the concrete two-valued interpretation of a Boolean algebra. A Boolean valuation fixes the inputs; a truth table lists every possible input. With two input bits there are four rows.

The basic logical connectives are logical conjunction (AND, $P\wedge Q$, both true), logical disjunction (OR, $P\vee Q$, at least one true), exclusive or (XOR, $P\oplus Q$, exactly one true), and logical negation (NOT, $\neg P$, the opposite value). OR is inclusive: it accepts the case where both inputs are true.^[ref]

For an original program-condition example, let $P$ mean “the backup is recent” and $Q$ mean “the backup is verified”. A rule requiring a recent, verified backup uses logical conjunction; one accepting either qualification uses logical disjunction. A rule flagging a mismatch between the two qualifications uses exclusive or. A recent, verified backup gives $(P,Q)=(1,1)$: AND and OR accept it, while XOR does not flag it. The last row of the truth table makes this difference explicit.

The same small Boolean operations build larger tests and Boolean circuits. In a programming language, the value of a condition and the procedure for evaluating it both matter. For Boolean operands, Python's and, or, and not implement these logical connectives. Evaluation proceeds from the left; and skips its right operand if the left is false, and or skips it if the left is true. More generally, and and or return an operand, whereas not returns a Boolean.^[ref]

For example, the Python condition denominator != 0 and numerator / denominator > 2 avoids division by zero because the logical conjunction's second test is evaluated only when the first succeeds. Reversing the tests preserves the abstract truth table for defined operands but can raise a division-by-zero error handled through exception handling. A rewrite involving a side effect must also preserve the needed evaluation behavior.

Every proper lattice ideal of a Boolean algebra extends to a prime lattice ideal. More generally, an ideal disjoint from a lattice filter extends to a prime ideal still disjoint from that filter. This Boolean case of the Stone prime filter theorem is equivalent to the ultrafilter lemma over Zermelo–Fraenkel set theory and is weaker than the axiom of choice.

A Boolean algebra homomorphism $B\to \mathcal{P}(A)$ is equivalent to a function assigning to every $a\in A$ an ultrafilter on $B$: test membership of $a$ in every image subset. This gives a left adjoint valued in the opposite category of sets. Its unit sends an algebra element $b$ to the set of ultrafilters containing $b$. On an infinite power-set algebra this map is not surjective, because the subset consisting of the principal ultrafilters cannot arise this way in the presence of a nonprincipal ultrafilter.

The lattice ideals of a Boolean algebra form a frame under inclusion. Meets are intersections and joins are ideals generated by unions. A complemented ideal is principal: if $I\vee J=B$ and $I\cap J=\{0\}$, choose $b\in I,c\in J$ with $b\vee c=1$; then $c=\neg b$ and $I=\downarrow b$. This ideal frame defines an extremally disconnected locale exactly when $B$ is complete.

Identify classical propositional formulae when their equivalence is provable from a fixed theory. Their equivalence classes form the Lindenbaum algebra: meet and join are induced by conjunction and disjunction, complementation by negation, and the order by provable implication. Provable equivalence is preserved by each connective, so these operations are well-defined; the familiar classical propositional identities make this a Boolean algebra. A homomorphism of lattices to $\{0,1\}$ preserving zero and one also preserves complements and therefore specifies a truth valuation of the atomic propositions. All axioms of the fixed theory represent one. Separating the class of an unprovable formula from one consequently gives a countervaluation, proving the completeness theorem for propositional logic.

Between 1600 and 1900, algebra broadened from arts of working with unknown quantities and solving equations into the study of several systems of symbolic operations and increasingly general algebraic structures. This was neither a single change of definition nor a clean replacement of one subject by another. Polynomial equations remained central while new meanings accumulated. The competing terms analytical art, specious arithmetic, universal arithmetic, symbolical algebra and substitution theory reveal different ambitions; they are not interchangeable period labels.

Near 1600, François Viète's In artem analyticem isagoge by François Viète (1591) supplies a particularly revealing starting point. His analytical art uses letters for known quantities as well as unknown ones. In his terminology, logistica numerosa concerns numerical calculation and logistica speciosa calculation with species, or general magnitudes. Vowels represent unknowns and consonants known magnitudes. This allows a single relation to represent many particular problems, but it is still tied to geometrical homogeneity: a square and a length do not simply become quantities of the same kind because they are written with letters.^[ref][ref]

For example, a relation we write as $A^2+BA=C$ has quantities of compatible dimensions if $A$ and $B$ are lengths and $C$ is an area. Letters do more than abbreviate a numerical question: they express relations between whole families of magnitudes. The phrase specious arithmetic therefore indicates arithmetic carried out on species; analysis stresses the art of reasoning from an assumed unknown towards its determination. Neither term should be reduced to the modern subject real analysis.

René Descartes's La Géométrie by René Descartes (1637) demonstrates another relation between algebra and geometry. A chosen unit segment lets multiplication, division and extraction of square roots be represented by constructions of lengths. The product of two measured lengths can itself be represented by a length relative to that unit. In modern dimensional notation the construction gives $ab/u$ for unit length $u$, removing the obstacle that a product must always be treated as an area. The text's equations can then organise geometrical problems and classify curves by their algebraic complexity. Its title remains geometry: algebra serves a geometrical programme rather than announcing a present-day department of abstract algebra.^[ref]

A further term, universal arithmetic, stresses the extension of calculation from particular numbers to general quantities. Isaac Newton's Arithmetica universalis by Isaac Newton, issued in 1707, makes the term visible in a title whose subtitle concerns composition and resolution. A title is evidence for the vocabulary, not a sufficient definition of all contemporary usage.^[ref] In Leonhard Euler's Elements of Algebra by Leonhard Euler, published in German in 1770, general numerical calculation and the solution of equations remain a substantial conception of the subject. For instance, allowing negative and complex roots changes the admissible answers to polynomial equations while preserving the central question of determining an unknown.^[ref]

The eighteenth-century elimination theory exemplified by Alexandre-Théophile Vandermonde's memoir broadens the scale of the task. Instead of one numerical quadratic equation, one seeks a rule for an arbitrary number of simultaneous linear equations. The determinant is initially valuable because it effects that elimination. This is a different generality from the later study of a group: the objects being determined are still unknown quantities, and symbolic generality concerns the number and coefficients of the equations. The case cautions against using generality alone as a test for whether algebra has become abstract.^[ref]

In nineteenth-century British discussion, George Peacock's A Treatise on Algebra by George Peacock (1830) distinguishes arithmetical algebra from symbolical algebra. If the symbols mean positive numbers, $a-(a+b)$ has no positive-number result. Yet algebraists manipulate this expression without restriction. George Peacock therefore seeks principles for the manipulation of signs which are not confined by their original arithmetical interpretation. The contrast is explicitly argued in his preface: arithmetic suggests the laws, while the symbolic science requires foundations adequate to its more general conclusions.^[ref]

The familiar extension $(-1)(-1)=1$ illustrates the stakes. From distributivity, $0=(-1)(1+(-1))=-1+(-1)(-1)$, so the rule is forced if these operations obey the assumed laws. This explains how a law can survive a change in interpretation. It does not establish that every familiar law must survive every extension: once the allowable systems themselves change, an argument must state which laws it assumes. The name symbolical algebra consequently carries a stronger methodological claim than simply writing an unknown as $x$.

William Rowan Hamilton's work on quaternions supplies a decisive example of that change. His publications of the 1840s describe a new system of imaginaries in algebra. With quaternion units,Thus multiplication need not satisfy the commutativity even when it remains associative and supports division by nonzero elements. The new system is not merely a further list of roots of old polynomial equations. It has its own operations, interpretation and laws. William Rowan Hamilton's title makes explicit that a plurality of calculi can belong within algebra.^[ref]

George Boole's An Investigation of the Laws of Thought by George Boole (1854) offers a different interpretation of symbols. If $x$ represents selection of a class, repeating that selection gives $x^2=x$; multiplication can represent intersection and $1-x$ a complementary class. His logical calculus borrows from numerical algebra but also restricts interpretation: his sum of classes is not automatically unrestricted set union, and intermediate symbolic expressions need not name classes directly. It would therefore be inaccurate to identify all of his rules with a modern Boolean algebra. The example nevertheless shows why algebraic reasoning could extend beyond magnitudes.^[ref]

The shift can also take a concrete linear form. Arthur Cayley's A Memoir on the Theory of Matrices by Arthur Cayley (1858) treats matrices with operations of their own. The identity matrix is no longer the scalar $1$, though it plays an analogous role; matrix multiplication is generally noncommutative. For example,produce $AB=\mathrm{diag}(1,0)$ and $BA=\mathrm{diag}(0,1)$. This is a checkable reason why universal arithmetic can no longer mean that every rule of ordinary numbers applies unchanged.^[ref]

Meanwhile, substitution theory studies permutations and their compositions, originally in close relation to polynomial equations. Évariste Galois's work connects the solvability by radicals of an equation with its associated group. Augustin-Louis Cauchy's work on substitutions and Heinrich Weber's 1882 definition illustrate successive forms of generalisation: from particular permutations towards arbitrary elements satisfying operational conditions. This is not a claim that one man supplied the complete modern hierarchy of groups, rings and fields at once. It identifies the change in the question: one can now investigate what follows from the laws of an operation, independently of whether the elements are numbers, substitutions or classes.^[ref]

By 1900, algebra could concern the laws and structures of several calculi. Earlier meanings persisted in teaching and in the theory of equations. The strongest account of the change therefore combines continuity with enlargement: letters for general quantities, symbolic operations with explicit laws, nonnumerical interpretations, and structural questions about those laws. Analytical art foregrounded a method of discovery, universal arithmetic foregrounded general calculation, symbolical algebra foregrounded formal operations, and substitution theory foregrounded a particular class of transformations. Their differing uses help explain the expansion more precisely than a single date for the birth of abstraction.

Allow clean workspace bits, as in standard reversible computation. Boolean algebra expresses any Boolean function as XORs of ANDs and constants. A Toffoli gate maps $(a,b,c)$ to $(a,b,c\oplus ab)$, so an initially zero target computes an AND without erasing the inputs. A CNOT gate accumulates XORs, and a NOT gate supplies complemented bits or constants. Intermediate products can be computed into workspace, XORed into an output, and then uncomputed by reversing the workspace computation. This realizes the reversible embedding $(x,y)\mapsto (x,y\oplus f(x))$ for any Boolean function and, with reversible clean-up, universal reversible classical computation.

The Fredkin transformation has control $a$ and targets $b,c$. A network of three gates, shown in i, iswhere the sequence is executed left to right. After the first gate $c_1=c\oplus b$; after the second $b_1=b\oplus a(c\oplus b)$; and the last gives $c_2=c\oplus b\oplus b_1$. If $a=0$, $(b_1,c_2)=(b,c)$; if $a=1$, $(b_1,c_2)=(c,b)$. Thus the circuit is exactly a Fredkin gate.

The workspace qualification matters for the unrestricted universality claim. On four or more wires, every embedded NOT, CNOT and Toffoli gate is an even permutation of all computational states. Without ancillary wires they cannot implement, for example, a permutation swapping just $0000$ and $0001$ while fixing the other four-bit strings. Clean ancillas remove this obstruction on the designated input subspace.

For a Boolean algebra $B$, write $\downarrow b$ for its principal lattice ideal. The ideal frame of a Boolean algebra has intersections as meets and ideals generated by unions as joins. The pseudocomplement of an ideal $I$ isIn particular $(\downarrow b{)}^{\ast }=\downarrow \neg b$, so every principal ideal is complemented and regular.

If $B$ is complete, put $s={\bigvee }_{B}I$. Then $I^{\ast }=\downarrow \neg s$ and $I^{\ast \ast }=\downarrow s$. Thus all regular ideals are principal and complemented, so the corresponding locale is extremally disconnected.

Conversely, if the ideal frame of a Boolean algebra is extremally disconnected, each $I^{\ast \ast }$ is complemented. Any complemented ideal is principal: if $J\vee K=B$ and $J\cap K=\{0\}$, the fact that their generated join contains $1$ supplies $b\in J,c\in K$ with $b\vee c=1$. Then $b\wedge c=0$, so $c=\neg b$; every $j\in J$ is disjoint from $c$ and therefore $j\le b$. Thus $J=\downarrow b$. Write $I^{\ast \ast }=\downarrow s$. Since $I\subseteq I^{\ast \ast }$, $s$ bounds $I$. If $t$ is another upper bound, $I\subseteq \downarrow t$ implies $I^{\ast \ast }\subseteq (\downarrow t{)}^{\ast \ast }=\downarrow t$, so $s\le t$. An arbitrary subset has the same upper bounds as the lattice ideal it generates, so every subset of $B$ has a supremum. Hence

Now put $A=\mathcal{O}(X)$ and $B=A_{\neg \neg }$. This is a complete Boolean algebra, with arbitrary Boolean joins $\neg \neg {\bigvee }_A{b}_i$, so the preceding result makes $\gamma X$ extremally disconnected. We construct its map to $X$ using the permitted Joyal extension lemma.

The map $\sigma :\mathrm{Idl}(B)\to B$, $I\mapsto {\bigvee }_{B}I$, is a frame homomorphism, with right adjoint $b\mapsto \downarrow b$. Thus $k(I)=\downarrow {\bigvee }_{B}I$ is a nucleus on a frame whose fixed frame is $B$. It preserves finite joins: both $k(I\vee J)$ and $k(I)\vee k(J)$ equal $\downarrow ({\bigvee }_{B}I{\vee }_B{\bigvee }_{B}J)$, and $k(0)=0$. Consequently the locale with frame $B$ is a flat sublocale of $\gamma X$. It is also the Booleanization of a locale $X$, so it has its inclusion map to $X$.

The Joyal extension lemma says that a map from a flat sublocale to a compact locale that is a regular locale extends uniquely to the ambient locale. Apply it to this inclusion. Its frame formula giveswhere $u\prec a$ is the well-inside relation $\neg u\vee a=1$. This also proves directly that the map is surjective. Indeed $u\prec a$ implies $\neg \neg u\le a$: meet $\neg u\vee a=1$ with $\neg \neg u$. Every member of the ideal $g^{\ast }(a)$ is therefore at most $a$ in $A$, since a finite Boolean join of its generators is below $\neg \neg (u_1\vee \cdots \vee u_n)\le a$; the last inequality follows because $u_1\vee \cdots \vee u_n\prec a$. Regularity givesThus $a$ can be recovered from $g^{\ast }(a)$, so $g^{\ast }$ is injective. A locale map with injective inverse-image frame homomorphism is a surjection. We have obtained an extremally disconnected $\gamma X$ and a surjection $\gamma X\to X$.

For a Boolean algebra $B$, let $U(B)$ be its set of ultrafilters, equivalently the Boolean homomorphisms $B\to 2$. Regard $U(B)$ as an object of ${\mathbf{Set}}^{\mathrm{op}}$. A homomorphism $k:B\to B^{\prime }$ acts by inverse image of ultrafilters, a set map $U(B^{\prime })\to U(B)$, hence an arrow $U(B)\to U(B^{\prime })$ in the opposite category.

A Boolean homomorphism $h:B\to \mathcal{P}(A)$ gives the functionConversely, a function $v:A\to U(B)$ gives $h(b)=\{a:b\in v(a)\}$. The ultrafilter laws are exactly what makes this map preserve the Boolean operations, including complements and $0,1$. These constructions are inverse and natural, proving the Boolean ultrafilter-power-set adjunctionIts unit is ${\eta }_B(b)=\{u\in U(B):b\in u\}$.

Take $B=\mathcal{P}(\mathbb{N})$, an object in the image of the right adjoint. There is a nonprincipal ultrafilter on $\mathbb{N}$, by extending the cofinite filter in the usual choice setting. The subset $P\subset U(B)$ consisting of all principal ultrafilters is not ${\eta }_B(b)$ for any $b\subseteq \mathbb{N}$: containing the principal ultrafilter at every integer forces $b=\mathbb{N}$, but ${\eta }_B(\mathbb{N})=U(B)$ also contains the nonprincipal ultrafilters. Thus ${\eta }_B$ is not surjective and is not an isomorphism. By the necessary condition proved in the root solution, this adjunction is not idempotent.

We prove the Ehrenfeucht-Mostowski theorem by ultraproducts, with no application of Ramsey theorem. Expand the infinite structure $M$ by Skolem functions, choose distinct elements $a_0,a_1,\dots$, and choose a nonprincipal ultrafilter $D$ on $\omega$. Let $I$ be the desired total index order and put $J={\omega }^I$.

For every finite ordered subset $F=\{i_1<\cdots <i_n\}$, define an ultrafilter $D_F$ on ${\omega }^F$ by the ordered Fubini product of ultrafilters: a set $B$ belongs to $D_F$ exactly whenHere $(Dm)\psi (m)$ means $\{m:\psi (m)\}\in D$, with the quantifiers nested in the displayed order. The resulting collection is an ultrafilter, by induction using the ultrafilter laws for negation and conjunction. For $F\subseteq H$, the inverse image of $B\subseteq {\omega }^F$ under coordinate projection belongs to $D_H$ exactly when $B\in D_F$: quantifiers on unused coordinates leave a truth value unchanged.

Consequently there is a well-defined ultrafilter on the Boolean algebra of finite-coordinate cylinders in $J$, declaring a cylinder large by this test. Coherence proves finite intersection closure and ensures that the empty cylinder is not large. Extend its generated filter to an ultrafilter $U$ on all subsets of $J$. Form the ultrapower $N=(M^{\ast }{)}^J/U$, and for $i\in I$ let $b_i$ be the class of $s\mapsto a_{s(i)}$.

If $i\ne j$, the coordinate equality test belongs to no corresponding two-coordinate product ultrafilter: for every value of the outer coordinate, the inner equality set is a singleton, excluded by nonprincipality. Hence the $b_i$ are distinct. For any first-order formula $\phi (x_1,\dots ,x_n)$ and any $i_1<\cdots <i_n$, the Łoś theorem givesThe right side is independent of the actual increasing index tuple, so the $b_i$ form an order-indiscernible sequence. Constant functions embed $M^{\ast }$ elementarily into $N$. Take the Skolem hull of the generators. The Tarski-Vaught test gives an elementary substructure, and transporting terms along an index-order automorphism gives a well-defined automorphism of the hull, with inverse obtained by transporting along the inverse index automorphism. Equality of term representations is preserved by indiscernibility. This is the indiscernible and automorphism conclusion of Ehrenfeucht–Mostowski, obtained entirely from ultrafilters and Łoś's theorem. The ordered Fubini products need not be symmetric; order indiscernibility is exactly what their coherence supplies.

A local operator is an inflationary, idempotent, finite-meet-preserving map $j:\Omega \to \Omega$ with $j(\top )=\top$, expressed in the internal logic of a topos. For a subterminal object $U$ with truth value $u$, the closed local operator and quasi-closed local operator are respectivelyThe first is a local operator by distributivity. For the second put $n(p)=p\Rightarrow u$. Then $p\le n^{2}p$, $n$ is order-reversing, and $n^{3}p=np$: the first inequality gives $n^{3}p\le np$, while its application to $np$ gives the reverse inequality. Thus $q=n^2$ is inflationary and idempotent, and $q(\top )=\top$.

For meet preservation, monotonicity gives $q(p\wedge r)\le qp\wedge qr$. Conversely put $t=(p\wedge r)\Rightarrow u$. From $t\wedge p\le r\Rightarrow u$ and $qr\wedge (r\Rightarrow u)\le u$, we obtain $t\wedge qr\le p\Rightarrow u$. Intersecting with $qp$ gives $qp\wedge qr\wedge t\le u$, hence $qp\wedge qr\le q(p\wedge r)$. This proves all local-operator axioms. Also $q(u)(0)=u$ and $q(u)(u)=u$. Equivalently, it is the largest local operator leaving $u$ fixed: if $k(u)=u$, thenThis explains the quasi-closed terminology as relative double negation above the closed bottom $u$.

The subobject classifier of ${\mathbf{sh}}_j(\mathcal{E})$ is the closed-subobject classifier ${\Omega }_j=\{p:jp=p\}$. Its bottom is $j0$, its meet is inherited, its join is $j(p\vee r)$, and implication between closed truth values is the ambient implication. To verify the last claim, if $jv=v$, thenIt follows that $j(p\Rightarrow v)\le jp\Rightarrow v\le p\Rightarrow v$; inflationarity gives equality and also $jp\Rightarrow v=p\Rightarrow v$.

Suppose $j=q(u)$. Every closed $p$ lies above $u$, and its complement in ${\Omega }_j$ is $np=p\Rightarrow u$, also closed because $n^3=n$. We have $p\wedge np=u$. Moreover $n(p\vee np)=np\wedge n^{2}p=np\wedge p=u$, so $q(p\vee np)=\top$. Thus the fixed truth values form a Boolean algebra, and the sheaf topos is a Boolean topos.

Conversely suppose the sheaf topos is Boolean and put $u=j0$. Complementation in its classifier is $p\mapsto p\Rightarrow u$. Applying the double-complement identity to $jp$, and using the implication calculation above, givesTherefore

For the cover, work in the slice category $\mathcal{E}/\Omega$. Its generic subterminal object is $T=(\top :1\hookrightarrow \Omega )$. Form its quasi-closed Boolean subtopos $\mathcal{B}={\mathbf{sh}}_{q(T)}(\mathcal{E}/\Omega )$, and compose its embedding with the slice projection to obtain $b:\mathcal{B}\to \mathcal{E}$. The slice projection has inverse image $X\mapsto X\times \Omega$, and sheafification is left exact, so this is a geometric morphism.

To prove surjectivity, take a monomorphism $S\hookrightarrow X$ with characteristic predicate $p(x)$, and suppose $b^{\ast }$ makes it invertible. Pullback to the slice followed by sheafification makes this exactly the assertion that it is $q(T)$-dense. Internally on $X\times \Omega$, therefore,for the generic truth value $u$. Substitute $u=p(x)$ by pulling back along the graph $X\to X\times \Omega$. The left side becomes $(\top \Rightarrow p(x))=p(x)$, so $p(x)=\top$ and the original mono is invertible. Thus $b^{\ast }$ reflects invertible monos. If it identifies two parallel arrows, their equalizer becomes invertible; reflection then shows the arrows were already equal. Hence $b^{\ast }$ is faithful, andThe generic truth value is essential: substituting only a fixed global value such as $0$ would give a Boolean subtopos, but need not give a surjection onto the original topos.