Theory and Applications of Categories, Vol. 16, No. 19, 2006, pp. 522–528.

NUMEROLOGY IN TOPOI

PETER FREYD

Abstract. This paper studies numerals (see definition that immediately follows), natural numbers objects and, more generally, free actions, in a topos.

A pre-numeral is a poset with a constant, 0, and a unary operation, s, such that: PN1) x ≤ y ⇒ sx ≤ sy PN2) x ≤ sx

A numeral is a “minimal” pre-numeral, that is, one such that any s-invariant subobject containing 0 is entire.

1. Lemma. A pre-numeral is a numeral iff:

1) 0 ≤ x;

2) (0 = x) ∨ ∃_{y} (x = sy);

3) (x ≤ y) ∨ (y ≤ x);

4) (x ≤ y) ∧ (y ≤ sx) ⇒ (x = y) ∨ (y = sx);

5) The coequalizer of 1 and s is the terminator.

2. Corollary. Exact functors preserve numerals.

Because of the exact plenitude of well-pointed topoi, this provides easy proofs of all sorts of things.^{1}

If n and m are numerals, I’ll write n ≤ m if there is a map of pre-numerals m → n. There is at most one such map for given m and n, hence the category of numerals is a pre-ordered set. The associated poset is a lattice: one may construct n∨m as the numeral

This paper has been circulating in manuscript form since June 1981. It was finally TEXed in 2004 with a few stylistic changes and the addition of few footnotes.

Received by the editors 2003-02-02 and, in revised form, 2005-03-15.

Transmitted by M. Barr. Published on 2006-08-30. 2000 Mathematics Subject Classification: 18B25. Key words and phrases: numerals, topoi. \begin{matrix}c \\ ◯ \end{matrix} Peter Freyd, 1981. Permission to copy for private use granted. 1A well-pointed topos is one that mimics the category of sets in that the terminator is a generator

(which forces—among other things—booleaness). The collective faithfulness of a topos’s exact representations into well-pointed topoi was first advertised in Aspect of Topoi [Freyd, Peter Bull. Austral. Math. Soc. 7 (1972), 1–76]. More accessible is Categories, Allegories [Freyd, Peter J.; Scedrov, Andre North-Holland Mathematical Library, 39. North-Holland Publishing Co., Amsterdam, 1990] which says [2.542]: For any topos 𝔸 there exists a boolean topos 𝔹 and a faithful representation 𝔸 → 𝔹. One then applies the capitalization lemma to obtain faithful 𝔹 → \underline{\underline{𝔹}} to land in a boolean topos in which the subterminators form a projective generating set. Then \underline{\underline{𝔹}}/F is well-pointed for each ultrafilter F ⊆ Val(\underline{\underline{𝔹}}).

inside the pre-numeral n×m and n ∧ m via the pushout:

\xymatrix{ & n ∨ m \ar[dl] \ar[dr] \\ n \ar[dr] &  & m \ar[dl] \\  & n ∧ m}

Using the exact plenitude of well-pointed topoi one may easily verify that this lattice is distributive. There is a largest numeral iff there is an NNO, a Natural Numbers Object.

Given an arbitrary object and subobject A′ ⊆ A and a reflexive relation, R from A to A, let PA be the power-object of A and s : PA → PA the unique map such that

\xymatrix{PA \ar[r]^{s} \ar[d]_{∋} & PA \ar[d]^{∋} \\ PA \ar[r]_{R} & A}

Let 1 ^{\underline{0}} →P A be the name of A′. Then ⟨PA, s, 0⟩ is a pre-numeral. Let n ⊆ P A denote the resulting numeral. I will use n ^{\underline{∋}} →A to denote the restriction of the universal relation PA ^{\underline{∋}} → A to n. For x ∈ A and i ∈ n, I will write x ∈ A′_{i} to mean that ∋ relates i and x. Define A′_{n} as the image of n ^{\underline{∋}} →A. Besides the pre-numeral axioms we have:

x ∈ A′_{0} ⟺ x ∈ A′

x ∈ A′_{si} ⟺ ∃_{y} [(y ∈ A′_{i}) ∧ (yRx)].

A′_{n} is easily seen to be the R-closure of A′, that is, the minimal R-invariant subobject containing A′.

3. Corollary. Exact functors preserve R-closures.

Let 1×R be the induced relation on A×A. The (1×R)-closure of the diagonal A ^{\underline{⟨1,1⟩}} →A×A is R^{∗}, the transitive closure of R, that is, the smallest transitive reflexive relation containing R. Note that if R is not reflexive then its transitive closure is R(1 ∪ R)^{∗}.

4. Corollary. Exact functors preserve transitive closures of relations.

For a near-exact functor (one that preserves finite limits, coproducts and images) the preservation of transitive closures clearly implies the preservation of co-equalizers, hence exactness. From near-exact to exact, therefore, is equivalent to the preservation of transitive closures (and then to the preservation of numerals) which yields:

5. Thesis. Weak second-order coherent logic is the syntax of exact functors.

By an A-action is meant an object B together with a map A×B ^{\underline{a}} → B. Let R be a relation from B to B defined by xRy iff x = y or ∃_{a} ax = y. For any B_{0} ⊆ B we can now easily obtain that exact functors preserve the construction of the sub-A-action generated by B_{0}. Let A^{∗} denote the free A-action generated by a single point 1 ^{\underline{0}} →A^{∗}.

6. Lemma. A^{∗} is characterized by:

1) ( \begin{matrix}0 \\ a \end{matrix} ) : 1 + A×A^{∗} → A^{∗} is monic,

2) A^{∗} is minimal, that is, the only sub-A-action containing 0 is entire.

In the proof I use the remarkable fact that exact faithful functors reflect (but need not preserve) freeness. (In the case at hand, given any A-action A×B → B and 1 ^{\underline{x}} → B let R ⊆ A^{∗}×B be the minimal A-action generated by 1 ^{\underline{⟨0,x⟩}} → A^{∗}×B. It suffices to show that R is the graph of a map.)

7. Corollary. Exact functors preserve A^{∗}.

8. Corollary. If 1^{∗} exists then so does A^{∗}.

For a proof of the latter note that 1^{∗} = N. It suffices to find an A-action A×B → B and 1 → B such that 1+B×B → B is monic because we can then minimize. Let B = (1+A)^{N}. Define the action as A × (1 + A)^{N} ^{\underline{⊆}} →(1 + A) × (1 + A)^{N} ^{\underline{≃}} →(1 + A)^{1+N} ^{\underline{≃}} →(1 + A)^{N}. Define 1 → (1 + A)^{N} as the curry of N → 1 ^{\underline{⊆}} →(1 + A).

The free A-action generated by B is easily seen to be A^{∗}×B. Thus A^{∗}×A^{∗} is the free A-action generated by A^{∗} and there is a canonical map A^{∗}×A^{∗} → A^{∗}. The fact that this gives a monoid structure which can then be shown to yield the free monoid generated by A is a nice fact, but not one that should be used to define A^{∗}.

For any A, PA is an A-action via A×PA ^{\underline{\{\}×1}} →PA×PA ^{\underline{∪}} →PA. Define KA as the minimal A-action generated by the name of the empty subobject 0 ⊆ A. KA is a commutative idempotent A-action, that is a(bx) = b(ax) and a(ax) = ax.

9. Lemma. KA is characterized among commutative idempotent A-actions by: 1) a(bx) = bx ⇒ (a = b) ∨ (ax = x)

2) KA is generated by 1 ^{\underline{0}} →KA

3) a0 ≠ 0. ^{2}

10. Corollary. Exact functors preserve KA.

11. Corollary. KA is the free commutative idempotent A-action.

Precisely as for A^{∗}, KA is easily shown to be the free commutative idempotent monoid generated by A. Such monoids, of course, are usually called semi-lattices. A is said to be K-finite if KA has a top element (necessarily the name of the entire subobject). This notion of finiteness is often credited to Kuratowski but apparently the notation is due to Sierpinski and the first to formulate it was Cesare Burali-Forti.

Define K_{A} ⊆ 1, the “K-finiteness of A”, via the pullback:

\xymatrix{K_{A} \ar[r]^{⊆} \ar[d] & 1 \ar[d]^{⌈A⌉} \\ KA \ar[r]_{⊆} & PA}

2Note that when A is the initial object this condition is vacuous.

K-finite objects are closed under the formation of finite products and quotient objects, but not subobjects (subobjects of 1 are K-finite only if they are complemented). So I’ll weaken this notion of finiteness to obtain one that is closed under the formation of subobjects. Given an object A, let Ã be its partial-map classifier (the down-deal in PA generated by the image of A ^{\underline{\{ \}}} → PA). Let P Ã → PA be the inverse-image map induced by the inclusion A ^{\underline{⊆}} →Ã and let

\xymatrix{B \ar[rr] \ar[d] &  & 1 \ar[d]^{⌈A⌉} \\ KÃ \ar[r] & P Ã \ar[r] & PA}

be a pullback. Define K̃_{A} as the image of B → 1.

For a numeral, n, the equalizer of 1_{n} and s is isomorphic to K_{n}, that is, the K-finiteness of n is the extent to which s has a fixed point.

For an arbitrary object, A, define num_{A} as the numeral arising in the construction of KA. A is R-finite if num_{A} is K-finite. R_{A} will denote the R-finiteness.

These three measurements of finiteness are related by K_{A} ⊆ K̃_{A} ⊆ R_{A}.

In an exacting topos, that is, one in which the global-section functor, Γ = (1, −) is exact (e.g. various free topoi), we may easily verify that A is K-finite iff it is covered by a finite (in the naive sense) copower of 1, that it is K̃-finite iff it is a subquotient of a finite copower of 1, that it is R-finite iff it satisfies ⋁_{0≤i<j≤n}(x_{i} = x_{j}) for some (standard) n (R is for Bertrand Russell).

There is a canonical example of R-finiteness, the higgs object, H ⊆ Ω^{Ω}, defined as the automorphism group of Ω (not as an object with structure, just as an object). H satisfies

∀_{x_{0},x_{1},x_{2}}[(x_{0} = x_{1}) ∨ (x_{0} = x_{2}) ∨ (x_{1} = x_{2})]

hence is R-finite.^{3} In the category S^{N}, the category of sets with distinguished endomorphisms, H is the two-element set whose distinguished endomorphism is not an automorphism. In the exacting topos S^{N}/N, K̃_{H} is easily seen to be 0.

In S^{N} we may construct the elements of Ω as the set of subobjects of N. In the exacting topos, S^{N}/N, it is easy to see that Ω totally fails R-finiteness, that is, R_{Ω} = 0 and, more to the point, ¬R_{Ω} = 1. If n is a numeral, then it is an NNO iff K_{n} = 0. Hence it is possible for num_{Ω} to be an NNO.

If 𝔽 is the free topos on nothing, that is no generators, no NNO, then, as just observed, 𝔽/¬R_{Ω} has an NNO. This last topos is exacting because for any U ⊆ 1 in 𝔽 either ¬U = 0 or 𝔽/¬U is exacting. By the standard method of using A^{∗} to construct free things in a topos. we may construct the free NNO-topos, T, in 𝔽/¬U. Exact functors from NNOtopoi preserve free things (at least those constructed from A^{∗}) hence (1, T) is the free NNO-topos in the category of sets. But 𝔽 ^{\underline{Δ}} →𝔽/¬U has a right-adjoint, Π, and Π(T) is an NNO-topos in 𝔽. ^{4} (The extent to which 0 = 1 in Π(T) is ¬¬R_{Ω}.) Since the global-section functor from 𝔽/¬U factors through Π we see that Π(T) is a topos-object in 𝔽 such that (1, Π(T)) is the free NNO-topos in sets. Yielding:

3See Choice and Well-Ordering Freyd, Peter, Ann. Pure Appl. Logic 35 (1987), no. 2, 149–166.

12. Theorem. There is a “rewrite” rule that converts any sentence in the logic of topoi with NNO (sometimes called intuitionistic type theory with the axiom of infinity) to an equally provable sentence in the logic of topoi (no axiom of infinity).

Restated: After one drops excluded middle, there is no great gain in dropping the axiom of infinity.

12.0.1. Diversion. How many notions of finiteness are there? I’ll say that an object is exactly finite if it becomes finite upon application of any exact functor to a boolean topos. Exact finiteness implies a lot (e.g. integral domains are commutative) but it is my present belief that it is not equivalent to an elementary notion. If A is an object in any topos, A×R_{A} is (obviously) exactly finite, but in the free topos Ω×R_{Ω} is not R-finite. (If it were, then Ω in 𝔽/R_{Ω} would satisfy ⋁_{0≤i<j≤n}(x_{i} = x_{j}) for some (standard) n. But for every finite monoid, M, there exists logical 𝔽/R_{Ω} → S^{M}.)

Define R_{A}^{1} to be the R-finiteness of A in 𝔸_{(R_{A})} the topos of closed sheaves complementary to R_{A}. If R_{A}^{1} = 1 then A is exactly finite. We may iterate the process: let R_{A}^{n+1} be the R-finiteness of A in 𝔸_{(R_{A}^{n})}. Define a relation S from Ω to Ω by USV iff V ⊆ U and the interval from V to U is boolean. Let B ⊆ Ω be the S-closure of the name of the entire object. Then R_{B}^{n} ≠ R_{B}^{n+1} in the free topos (consider B in S^{(ω^{2})^{∘}}). In a Grothendieck topos we may extend the definition to arbitrary ordinals. {R_{B}^{β}}_{β<α} is a strictly ascending chain in S^{(ω×α)^{∘}}.

I’ll say that an object is geometric finite if it becomes finite upon application of any cogeometric morphism^{5} targeted at a boolean topos. R^{α}-finiteness, for any ordinal α, implies geometric finiteness. But not even R_{A}^{∞} = ⋃ R_{A}^{α} measures geometric finiteness. In sheaves on the reals let A be the sheaf of germs of functions ℝ ^{\underline{f}} →N such that fx = 0 for all but finitely many rational x and further, f(p/q) ≤ q. Then A is geometrically finite, but R^{α} = 0 all α.

End of Diversion

The poset of numerals in any topos has more than the structure of a distributive lattice. We may define n times m as num_{n×m} and their sum as num_{P} where P is defined via the pushout:

4The right adjoint for 𝔸 → 𝔸/V when V ⊆ 1 is easy to describe if we identify 𝔸/V with the full subcategory of 𝔸 of those objects with a map to V. Then Π(A) is just A^{V}.

5 that is, an exact functor with a right adjoint

\xymatrix{ & 1 \ar[dl]_{0} \ar[dr]^{0} \\ n \ar[dr] &  & m \ar[dl] \\  & P}

The predecessor n − 1 can be constructed as the image of n ^{\underline{s}} → n (with s0, of course, as the “new” 0).

The poset of numerals is an upside-down Heyting algebra (possibly missing one of its extremal elements). If f : n → m is a map of numerals let F ⊆ m be the inverse image of the equalizer, E, of 1_{n} and s. Then s(F) ⊆ F and

\xymatrix{F \ar[r] \ar[d] & n \ar[d] \\ E \ar[r] & m}

is a pushout. Conversely, given any s-invariant F ⊆ m we may construct a numeral m/F. The set of s-invariant subobjects is a Heyting algebra (but not a sub lattice of Sub(m)). Bearing in mind the order-reversal, one sees that all sorts of minimization constructions can be carried through and, in particular, we may define m − n as the smallest numeral whose sum with n is at least m. (m − n ≃ num_{F} − 1 where m/F ≃ m ∧ n.)

The poset of numerals between 0 and 1 is anti-isomorphic to Sub(1) with 1 − n corresponding to negation. The formula

1 − (1 − n) = 1 ∧ n is thus equivalent to booleaness and hence exact functors need not preserve m − n. So why should they preserve sums and times? The problem is that for an exact functor T, the natural map

T (num_{A}) → num_{T A} need not be an isomorphism. The problem goes back to the numeral associated with a reflexive relation. We are saved, however, by the following lemma in which 1 denotes the top element of KA.

13. Lemma. If A is K-finite then num_{A} is characterized among numerals by the existence of a relation from KA to num_{A} denoted x ∈ K_{i}A such that:

x ∈ K_{0}A ⟺ x = 0

x ∈ K_{si}A ⟺ (x = 0) ∨ ∃_{a∈A, y∈K_{i}A} (ay = x)

1 ∈ K_{i}A ⟺ i = si

14. Corollary. If A is K-finite and T an exact functor then T (num_{A}) ≃ num_{T A}.

The construction of sum and times for finite numerals is thus preserved by exact functors and the boolean case is a safe guide to much of \underline{primitive} recursive functions on numerals. The full numerology, however, of a topos—unlike the standard number theory (that is, decidable numerology)—reflects the failure of excluded middle.

In a topos with NNO let { \atop N UM} denote the object of all s-invariant subobjects of N and N UM ⊆ { \atop N UM} the subobject defined by F ∈ N UM iff F → 1 is epi. { \atop N UM} is the object of numerals and N UM the object of finite numerals. (The notation is forced by the fact that { \atop N UM} is the partial-map classifier of N UM .) In the topos of sheaves on a space X, N UM may be constructed as the sheaf of germs of upper semi-continuous functions from X to N. The unit interval of N UM is anti-isomorphic to Ω.

15. Theorem. For a lattice L define an L-set as an action L×B ^{\underline{+}} →B such that 0+x = x and a + (b + x) = (a ∧ b) + ((a ∨ b) + x). Then [0, 1]×N UM → N UM is the free L-set on a point for L ≃ Ω^{∘} ≃ [0, 1].

Let ℝ be the Dedekind reals and L the lattice of closed subfields. In imitation of KA, L acquires an ℝ-action. Define DIM to be the numeral associated with the sub action generated by the Cantor reals. For a CW-complex X, DIM, viewed as a section of { \atop N UM} is the dimension function.

Department of Mathematics, University of Pennsylvania Philadelphia, PA, 19104

Email: pjf@saul.cis.upenn.edu

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/16/19/16-19.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@mathstat.uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca