2 A meaning explanation

Intuitionistic logic is often explained informally (e.g., in [Reference Troelstra and van Dalen49]) by the so-called Brouwer–Heyting–Kolmogorov (BHK) interpretation, which explains the meaning of the logical connectives and quantifiers “pragmatically” in terms of what counts as a proof of them. For instance, a few of the rules are:

• • A proof of $P\to Q$ is a method converting any proof of P into a proof of Q.

• • A proof of $P\lor Q$ is either a proof of P or a proof of Q.

• • A proof of $\neg P$ is a method converting any proof of P into a proof of an absurdity.

This leads to the rules of intuitionistic logic; for instance, we cannot prove $P\lor \neg P$ in general since we cannot decide whether to give a proof of P or a proof of $\neg P$ .

Practicing constructive mathematicians, however, have found that it is often not sufficient to know what counts as a proof of a statement: it is often just as important, if not more so, to know what counts as a refutation of a statement. For instance, while it is of course essential to know that two real numbers are equal if they agree to any desired degree of approximation, it is also essential to know that they are unequal if there is some finite degree of approximation at which they disagree. If real numbers are defined using Cauchy sequences $x,y:\mathbb {N}\to \mathbb {Q}$ with specified rate of convergence $|x_n-x_m|< {\textstyle \frac {1}{n}}+{\textstyle \frac {1}{m}}$ , then we want to separately define

In classical logic, a refutation of P means a proof of $\neg P$ , and these two definitions are each other’s negations. But intuitionistic negation is not involutive, and this “ $x\neq y$ ” is not the logical negation of $x=y$ . Thus, when constructive mathematics is done in intuitionistic logic—as it usually is—we must define inequality as a new apartness relation with which the set of reals is equipped. In Bishop’s words:

Similar things happen all throughout constructive mathematics. In addition to knowing when an element is in a subgroup, we need to know when an element is not in a subgroup; thus we introduce antisubgroups (and similarly anti-ideals, etc.). In addition to knowing when a point is in the interior of a set, we need to know when it is in the exterior of a set; thus we introduce apartness spaces [Reference Bridges and Vîţă11].

To repeat, the problem is that the BHK interpretation and resulting intuitionistic logic privilege proofs over refutations. In the words of Patterson [Reference Patterson42]:

This suggests a BHK-like explanation of logical connectives in terms of both what counts as a proof and what counts as a refutation. We now explore what such an explanation might look like. The only requirement we impose is that no formula should be both provable and refutable (but see Remarks 3.9 and 3.13).

We start with the following explanations of conjunction and disjunction, which we denote $\sqcap $ and $\sqcup $ rather than $\land $ and $\lor $ as a warning that they will not behave quite like the usual intuitionistic or classical connectives.

• • A proof of $P\sqcap Q$ is a proof of P together with a proof of Q.

• • A refutation of $P\sqcap Q$ is either a refutation of P or a refutation of Q.

• • A proof of $P\sqcup Q$ is either a proof of P or a proof of Q.

• • A refutation of $P\sqcup Q$ is a refutation of P together with a refutation of Q.

These “proof” clauses are the usual BHK ones, while the “refutation” clauses are natural-seeming De Morgan duals. The most natural clauses for negation are:

• • A proof of $\smash {{P}^{\perp }}$ is a refutation of P.

• • A refutation of $\smash {{P}^{\perp }}$ is a proof of P.

This negation is involutive, $\smash {{P}^{\perp \perp }} \equiv P$ , with strict De Morgan duality: $\smash {{(P\sqcap Q)}^{\perp }} \equiv \smash {{P}^{\perp }} \sqcup \smash {{Q}^{\perp }}$ and $\smash {{(P\sqcup Q)}^{\perp }} \equiv \smash {{P}^{\perp }} \sqcap \smash {{Q}^{\perp }}$ . ( $\equiv $ denotes inter-derivability.)

A little thought suggests that one natural explanation of implication (which we indulge in some foreshadowing by writing as ) is:

• • A proof of is a method converting any proof of P into a proof of Q, together with a method converting any refutation of Q into a refutation of P.

• • A refutation of is a proof of P together with a refutation of Q.

Building contraposition into the definition of implication makes it unsurprising that we get . So it might seem that we are going to fall into classical logic, but this is not the case. For instance, classically we have $\neg (P \to Q) \equiv P \land \neg Q$ ; but despite the apparent presence of this law in the “refutation” clause for , we do not have . Instead we have , where $\boxtimes $ is a different kind of conjunction:

• • A proof of $P\boxtimes Q$ is a proof of P together with a proof of Q.

• • A refutation of $P\boxtimes Q$ is a method converting any proof of P into a refutation of Q, together with a method converting any proof of Q into a refutation of P.

Note that $P\sqcap Q$ and $P\boxtimes Q$ have the same proofs, but different refutations. Both refutation clauses are based on the idea that P and Q cannot both be true, but to refute $P\sqcap Q$ we must specify which of them fails to be true, whereas to refute $P\boxtimes Q$ we simply have to show that if one of them is true then the other cannot be.

This suggests that $P\boxtimes Q$ is stronger than $P\sqcap Q$ , and in fact we can justify on the basis of our informal explanations. Since $P\boxtimes Q$ and $P\sqcap Q$ have the same proofs, it suffices to transform any refutation of $P\sqcap Q$ into a refutation of $P\boxtimes Q$ . The former is either a refutation of P or of Q; without loss of generality assume the latter. Then we can certainly produce a refutation of Q that doesn’t even need to use a proof of P. On the other hand, given a refutation of Q it is impossible that we could also have a proof of Q; so by ex contradictione quodlibet from any proof of Q we can vacuously produce a refutation of P.

It follows that the De Morgan dual of $\boxtimes $ is a different kind of disjunction that is weaker than $\sqcup $ . (For a discussion of notation, see Notation 2.2.) Its explanation is:

• • A proof of is a method converting any refutation of P into a proof of Q, together with a method converting any refutation of Q into a proof of P.

• • A refutation of is a refutation of P together with a refutation of Q.

Thus has the same refutations as $P\sqcup Q$ , but more proofs: while $P\sqcup Q$ supports proof by cases, supports only the disjunctive syllogism. As noted in Section 1, encapsulates a common constructive pattern for weakening definitions when the intuitionistic “or” is too strong: rather than asserting that one of two conditions holds, we assert that if either one of two conditions fails then the other must hold. We have , a version of the classical law $(P \to Q) \equiv (\neg P \lor Q)$ .

A reader familiar with linear logic may recognize $\boxtimes $ and as its multiplicatives, while $\sqcap $ and $\sqcup $ are its additives,Footnote ⁴ with as its linear implication. Indeed, this explanation is similar to the “game semantics” of linear logic, in which a “proposition” is regarded as a game or interaction between a “prover” and a “refuter.”

Actually, our explanation justifies not fully general linear logic but affine logic, because in the nullary case (“true” and “false”) the distinctions collapse:

• • There is exactly one proof of $\top $ .

• • There is no refutation of $\top $ .

• • There is no proof of $\bot $ .

• • There is exactly one refutation of $\bot $ .

These are units for both additive and multiplicative connectives: $P \sqcap \top \equiv P \boxtimes \top \equiv P$ and . The most nontrivial part of this is the refutations of $P\boxtimes \top $ (or dually the proofs of ), which by definition consist of a method transforming any proof of $\top $ into a refutation of P, together with a method transforming any proof of P into a refutation of $\top $ . The former is essentially just a refutation of P; but given this, there can be no proof of P, so the latter method is vacuous.

The quantifiers are essentially additive; we write them as

instead of $\exists /\forall $ .

• • A proof of ${\textstyle \bigsqcup } x. P(x)$ is a value a together with a proof of $P(a)$ .

• • A refutation of ${\textstyle \bigsqcup } x. P(x)$ consists of a refutation of $P(a)$ for an arbitrary a.

• • A proof of consists of a proof of $P(a)$ for an arbitrary a.

• • A refutation of is a value a together with a refutation of $P(a)$ .

The most novel of these clauses is the one for refutations of

: just as a constructive proof of an existence statement should supply a witness, we stipulate that a constructive disproof of a universal statement should supply a counterexample. This yields De Morgan dualities

and also “Frobenius” laws involving the multiplicative connectives:

But

fails: a refutation of ${\textstyle \bigsqcup } x. (P \sqcap Q(x))$ consists of, for every a, either a refutation of P or a refutation of $Q(a)$ , while a refutation of $P \sqcap {\textstyle \bigsqcup } x.Q(x)$ must decide at the outset whether to refute P or to refute all $Q(a)$ ’s.

This explanation of the connectives and quantifiers solves the problem mentioned above with equality and inequality of real numbers. If we define

then we find that (assuming that $\smash {{(p\le q)}^{\perp }} \equiv (p> q)$ for $p,q\in \mathbb {Q}$ )

$$\begin{align*}\smash{{(x=y)}^{\perp}} \equiv {\textstyle\bigsqcup} n. |x_n-y_n|> \textstyle{\textstyle\frac{2}{n}}. \end{align*}$$

Thus, the correct notions of equality and inequality for real numbers are each other’s negations, relieving us of the need for a separate “apartness relation.”

The names linear and affine logic refer to the fact that $\boxtimes $ and are not idempotent: $P\boxtimes P {\not\equiv } P$ and . (More precisely, what fails are and .) A proof of consists of a method (well, technically two methods) for converting any refutation of P into a proof of P. Since P cannot be both provable and refutable, this is equivalently a method showing that P cannot be refuted—which is, of course, different from saying that it can be proven. Note that linear logic always satisfies the “multiplicative law of excluded middle” and the “multiplicative law of non-contradiction” $\smash {{(P\boxtimes \smash {{P}^{\perp }})}^{\perp }}$ (in fact, they are essentially the same statement). We call a proposition decidable if it satisfies the additive law of excluded middle $P\sqcup \smash {{P}^{\perp }}$ , or equivalently the additive law of non-contradiction $\smash {{(P\sqcap \smash {{P}^{\perp }})}^{\perp }}$ . According to the above informal explanations, decidability means that we have either a proof of P or a refutation of P.

It may help to understand $\boxtimes $ if we write out the meaning of , which the reader can verify is equivalent to :

• • A proof of consists of methods for:

  • – converting any proofs of P and Q into a proof of R,

  • – converting any proof of P and refutation of R into a refutation of Q, and

  • – converting any proof of P and refutation of Q into a refutation of R.

• • A refutation of consists of a proof of P, a proof of Q, and a refutation of R.

More generally, a proof of consists of “all possible direct or by-contrapositive proofs” that contradict one of the hypotheses. By contrast:

• • A proof of consists of:

  • – a method converting any proofs of P and Q into a proof of R, and

  • – a method converting any refutation of R into either a refutation of P or a refutation of Q.

• • A refutation of consists of a proof of P, a proof of Q, and a refutation of R.

That is, when proving the (stronger) statement , the by-contrapositive direction must use R to determine which of P or Q fails, whereas when proving we are allowed to assume one of P and Q and contradict the other.

We define , with the following meaning:

• • A proof of consists of methods for converting:

  • – any proof of P into a proof of Q, and vice versa, plus

  • – any refutation of P into a refutation of Q, and vice versa.

• • A refutation of consists of either:

  • – a proof of P and a refutation of Q, or

  • – a refutation of P and a proof of Q.

Often in linear logic one defines to be instead. However, for us is preferable, due in part to its more informative disjunctive notion of refutation; see also Examples 6.7 and 6.14 and Section 8.

Finally, following Girard [Reference Girard19] we introduce two unary connectives and called exponential modalities, with the following meanings:

• • A proof of is a proof of P.

• • A refutation of is a method converting any proof of P into an absurdity.

• • A refutation of is a refutation of P.

• • A proof of is a method converting any refutation of P into an absurdity.

These exponentials deal with the potential objection that not every constructive proposition has a “strong dual.” For instance, not every set has an apartness relation. But there is always the Heyting negation , and the propositions are those whose refutations are the “tautological” ones of this form. We will call a proposition in affine logic P affirmative if . For instance, a set in the antithesis model whose affine equality is affirmative will correspond to a set in intuitionistic logic equipped with the denial inequality, .

It is also common to encounter propositions that are the Heyting negation of their strong dual. For instance, while real numbers do not satisfy , they do satisfy $(x= y) \equiv \neg (x\neq y)$ (the inequality is tight). In the antithesis model these are the propositions with , which we call refutative.

We can also understand by considering . Since Q cannot be both provable and refutable, if we can transform proofs of P into proofs of Q, then any refutation of Q already entails the impossibility of a proof of P. Thus, in proving the contrapositive direction is subsumed by the forwards direction, giving:

• • A proof of is a method converting any proof of P into a proof of Q.

• • A refutation of is a proof of P together with a refutation of Q.

Unlike , we only have . Thus is “usable multiple times” (since ) but “not contraposable.”

Note the proofs of are just the ordinary BHK interpretation of $P\to Q$ . This foreshadows the Girard translation of intuitionistic logic into linear logic.

3 The antithesis translation for propositional logic

Like the BHK interpretation of intuitionistic logic, the explanation of the affine connectives and quantifiers in Section 2 is informal, and nonspecific about what constitutes a “method.” However, the relationship between the two interpretations can be made precise, in the form of a “translation” of affine logic into intuitionistic logic. This is analogous to the Gödel–Gentzen double-negation translation of classical logic into intuitionistic logic and the Girard translations of intuitionistic logic into linear logic, and like them it has both a semantic and a syntactic side.

Consider the Gödel–Gentzen translation, restricted to propositional logic for simplicity. On the semantic side, this constructs a Boolean algebra from a Heyting algebra. More generally, let $\mathbf {H}$ be any bicartesian closed category, meaning a cartesian closed category with finite coproducts; a Heyting algebra is the special case of a bicartesian closed poset. We regard the objects of $\mathbf {H}$ as intuitionistic propositions, and hence use logical notations for its structure: $\land $ for cartesian products, $\lor $ for coproducts, $\mathbf {1}$ and $\mathbf {0}$ for terminal and initial object, and $\to $ for exponentials.

Returning to the Gödel–Gentzen translation, any bicartesian closed category $\mathbf {H}$ is distributive [Reference Carboni, Lack and Walters12], so its initial object is strict, meaning any morphism with codomain $\mathbf {0}$ is an isomorphism. In particular, $\mathbf {0}$ is subterminal, and thus so is the Heyting negation

of any object. Thus the full subcategory

consists of subterminal objects, and hence is a preorder. It is closed in $\mathbf {H}$ under $\land $ and $\to $ , and contains $\mathbf {1}$ and $\mathbf {0}$ ; it is not closed under $\lor $ but it does have binary joins defined in H by $\neg \neg (P\lor Q)$ . With these operations it (or more precisely its skeleton) is a Boolean algebra. Moreover, this construction defines a left adjoint, in a suitable sense, to the forgetful functor from Boolean algebras to bicartesian closed categories. This is the semantic side of the (propositional) Gödel–Gentzen translation: it makes a model of intuitionistic logic into a model of classical logic.

The syntactic side goes in reverse, translating any formula in classical logic into a formula in intuitionistic logic. It can be obtained automatically from the semantic side, by considering the free bicartesian closed category $\mathbb {H}[\Sigma ]$ generated by some signature $\Sigma $ , whose objects and morphisms are formulas and proofs in intuitionistic logic, and its resulting Boolean algebra $\mathbb {H}[\Sigma ]_{\neg \neg }$ . Then if $\mathbb {B}[\Sigma ]$ is the free Boolean algebra generated by the same signature, whose elements and inequalities are formulas and entailments in classical logic, its universality means there is a unique Boolean algebra homomorphism $(-)^{\mathrm {N}} : \mathbb {B}[\Sigma ] \to \mathbb {H}[\Sigma ]_{\neg \neg }$ .

This is the syntactic side of the Gödel–Gentzen translation, which maps formulas and entailments in classical logic into formulas and proofs in intuitionistic logic. Its usual explicit definition can be read off from the Boolean algebra structure of $\mathbb {H}[\Sigma ]_{\neg \neg }$ above, e.g., $(P\land Q)^{\mathrm {N}} = P^{\mathrm {N}} \land Q^{\mathrm {N}}$ and $(P\lor Q)^{\mathrm {N}} = \neg \neg (P^{\mathrm {N}} \lor Q^{\mathrm {N}})$ . In particular, deriving these formulas semantically in this way means that the translation is automatically sound, i.e., maps proofs to proofs.

The situation with the Girard translation is similar. We recall the relevant category-theoretic models of (propositional) linear logic.

In a $\ast $ -autonomous category we write and , and if it has a Seely comonad we write . Since $\smash {{(-)}^{\perp }}$ is a self-duality, if a $\ast $ -autonomous category has products then it also has coproducts; as in Section 2 we write its products as $\sqcap $ and its coproducts as $\sqcup $ .

If we identify the objects of with objects of L as usual, with and the forgetful functor acting on objects by , then the cartesian product in must take objects P and Q to $P\sqcap Q$ ; hence we have in L.Footnote ⁷ It follows that is a cartesian closed category, with exponential .

This is the semantic side of the Girard translation. Its syntactic side can be deduced as before, as a map from the free cartesian closed category $\mathbb {H}'[\Sigma ]$ on some signature to the cartesian closed category underlying the free $\ast $ -autonomous category with finite products and Seely comonad on the same signature. This yields a map from formulas and proofs in intuitionistic logicFootnote ⁸ to those in linear logic, whose syntactic rules can be read off of the cartesian closed structure of , e.g., $(P\land Q)^{\mathrm {G}} = P^{\mathrm {G}} \sqcap Q^{\mathrm {G}}$ and .

The semantic side of the antithesis translation, therefore, will be a construction of a model of affine logic from a model of intuitionistic logic. By a model of affine logic we mean a $\ast $ -autonomous category with finite products and Seely comonad that is semicartesian, meaning that its monoidal unit is also its terminal object (and hence the dualizing object $\bot $ is also the initial object).

The semantic antithesis translation is actually an instance of both the Chu construction [Reference Chu13, Reference Chu14] and the Dialectica construction in the form of [Reference de Paiva41]. We will not describe these constructions in general, but only the specific case of interest to us, in which they coincide. On the side of subsets rather than predicates, a similar notion was already introduced by [Reference Bishop and Bridges10, Chapter 3, Section 2] under the name complemented subset; see Theorem 6.11.

Thus, a morphism $f : P\to Q$ in $\mathbf {H}_{\pm }$ consists of maps ${f}^+ : {P}^+ \to {Q}^+$ and ${f}^- : {Q}^- \to {P}^-$ in $\mathbf {H}$ . In general, Chu and Dialectica constructions impose additional constraints on such morphisms—the difference between the two being in the constraints—but since $\mathbf {0}$ is subterminal, those constraints are vacuous for us.

Proof They are inherited from $\mathbf {H}\times \mathbf {H}^{\mathrm {op}}$ , with the following definitions:

$$\begin{alignat*}{2} \top &= (\mathbf{1},\mathbf{0}), & \qquad P \sqcap Q &= ({P}^+ \land {Q}^+, {P}^- \lor {Q}^-), \\ \bot &= (\mathbf{0},\mathbf{1}), & P \sqcup Q &= ({P}^+ \lor {Q}^+, {P}^- \land {Q}^-). \end{alignat*} $$

Note that we use Notation 2.2 for these.

Proof The monoidal structure is defined by

A general Chu construction requires a pullback rather than a product in the refutations of $P\boxtimes Q$ , but subterminality of $\mathbf {0}$ makes that unnecessary here. We leave associativity and symmetry to the reader (or standard references on the Chu and Dialectica constructions). For the unit, since $\top = (\mathbf {1},\mathbf {0})$ we have

$$ \begin{align*} P \boxtimes \top &= ({P}^+ \land \mathbf{1}, ({P}^+ \to \mathbf{0}) \land (\mathbf{1} \to {P}^-))\\ &\cong ({P}^+, ({P}^+ \to \mathbf{0}) \land {P}^-)\\ &\cong ({P}^+, {P}^-). \end{align*} $$

Here the final isomorphism is because ${P}^+ \to \mathbf {0}$ is subterminal and there is a morphism ${P}^- \to ({P}^+ \to \mathbf {0})$ . The closed structure is defined by

We leave the verification of adjointness to the reader. Now since $\bot = (\mathbf {0},\mathbf {1})$ , we have

from which it follows immediately that

.

Proof The forgetful map ${(-)}^+ : \mathbf {H}_{\pm } \to \mathbf {H}$ has a fully faithful left adjoint sending P to $(P,\neg P)$ , where

is the Heyting negation. The induced comonad and monad are

Since the left adjoint is fully faithful, this comonad and monad are idempotent, and their Kleisli (and also Eilenberg–Moore) adjunctions coincide with the adjunction we started with. The definition of $\boxtimes $ makes it clear that the right adjoint ${(-)}^+$ is strong symmetric monoidal, while for the left adjoint F we have

$$ \begin{align*} F P \boxtimes F Q &= ( P \land Q, ( P \to \neg Q) \land ( Q \to \neg P))\\ &\cong ( P \land Q, ( P \to Q \to \mathbf{0}) \land ( Q \to P \to \mathbf{0}))\\ &\cong ( P \land Q, (P \land Q \to \mathbf{0}) \land (P \land Q \to \mathbf{0}))\\ &\cong ( P \land Q, \neg (P \land Q))\\ &= F(P\land Q) \end{align*} $$

using that since $P \land Q \to \mathbf {0}$ is subterminal, it is its own cartesian square.

Lemmas 3.4–3.6 define the semantic antithesis translation, which in fact is a right adjoint to a suitable forgetful functor. As before, we obtain the syntactic antithesis translation as the unique morphism $(-)^{\pm } : \mathbb {A}[\Sigma ] \to \mathbb {H}[\Sigma ]_{\pm }$ , where $\mathbb {A}[\Sigma ]$ is the free semicartesian $\ast $ -autonomous category with products and a Seely comonad on the signature $\Sigma $ . This is a translation that maps formulas and proofs in affine logic to pairs of formulas and proofs in intuitionistic logic. It is given by explicit formulas that can be read off of the structure of $\mathbf {H}_{\pm }$ , and which are shown in Figure 1. As with the Gödel–Gentzen and Girard translations, the semantic derivation of these formulas automatically ensures soundness: any proof in affine logic automatically translates to a pair of proofs in intuitionistic logic.

Figure 1

The syntactic antithesis translation for propositional logic.

Of course, all the definitions in Figure 1 match our informal explanations of the connectives in Section 2. Thus any rigorous version of the BHK interpretation, yielding a bicartesian closed category that models propositional intuitionistic logic, can be enhanced to a model of propositional affine logic matching our meaning explanation.

Moreover, since the Kleisli category of $\mathbf {H}_{\pm }$ recovers $\mathbf {H}$ again, the Girard translation undoes the antithesis translation:

In other words, we can regard affine logic as an extension of intuitionistic logic.

A very important point, however, is that unlike the Gödel–Gentzen and Girard translation, the antithesis translation is not conservative in the logical sense. That is, there are statements in affine logic that always hold under the antithesis translation (i.e., in categories of the form $\mathbf {H}_{\pm }$ ), but are not provable in general affine logic. Some such statements include:

To a linear logician, this makes the logic look quite degenerate: much of the potential richness of the exponentials is invisible to the antithesis translation. Therefore, unlike the Gödel–Gentzen and Girard translations, we should not view the antithesis translation as a way to study affine logic by “embedding” it into intuitionistic logic. Instead, we view it as a way to use affine logic as a tool for stating and proving definitions and theorems in intuitionistic logic. (But we will return to this in Section 11.)

4 The antithesis translation for predicate logic

To do substantial mathematics we require not just propositional logic, but at least first-order logic, and often higher-order logic or even dependent types. While attempting not to get bogged down by detail, in this section we describe antithesis translations for these richer theories. I encourage a reader who is not already an afficionado of categorical semantics to skim this section on a first reading.

4.1 First-order logic

This corresponds semantically to the following notion, due essentially to Lawvere [Reference Lawvere29].

Definition 4.1.1. Let $\mathcal {K}$ be a 2-category with a forgetful functor $U:\mathcal {K} \to \mathcal {C}\mathit {at}$ . A $\mathcal {K}$ -valued hyperdoctrine consists of:

• • A category T with finite products.

• • A pseudofunctor $\mathcal {P} : \mathbf {T}^{\mathrm {op}} \to \mathcal {K}$ .

• • For any product projection $\pi :A\times B \to A$ in T, the functor

  $$\begin{align*}U\pi^* : U\mathcal{P}(B) \to U\mathcal{P}(A\times B) \end{align*}$$
  has both a left adjoint $\Sigma _B$ and a right adjoint $\Pi _B$ .

• • The Beck–Chevalley condition holds, meaning that for any $f:A'\to A$ in T the induced maps are isomorphisms:

  

We think of the objects of T as representing types and its morphisms as terms, with the objects of $\mathcal {P}(A)$ being predicates on A. The morphism $f^* : \mathcal {P}(A) \to \mathcal {P}(A')$ of $\mathcal {K}$ induced by $f:A'\to A$ represents substitution into a predicate, while the adjoints $\Sigma _B$ and $\Pi _B$ act like existential and universal quantification. Note that $\Sigma _B$ and $\Pi _B$ are not in general morphisms of $\mathcal {K}$ .

If $\mathcal {K}=\mathcal {I}\mathit {nt}$ is the 2-category of bicartesian closed categories, with functors preserving finite products, coproducts, and exponentials, and natural isomorphisms between them, we speak of an intuitionistic hyperdoctrine, and write $\Sigma _B = \exists _B$ and $\Pi _B = \forall _B$ . Similarly, if $\mathcal {K}=\mathcal {A}\mathit {ff}$ is the 2-category of semicartesian $\ast $ -autonomous categories with finite products and a Seely comonad, with functors that preserve all this structure up to isomorphism, and natural isomorphisms between them, we speak of an affine hyperdoctrine, and write $\Sigma _B = {\textstyle \bigsqcup }_B$ and .

Example 4.1.2. If H is a complete and cocomplete cartesian closed category, then there is an intuitionistic hyperdoctrine with $\mathbf {T} = \mathbf {Set}$ and $\mathcal {P}(A) = \mathbf {H}^A$ . The adjoints $\Pi _B$ and $\Sigma _B$ are given by products and coproducts. Similarly, if L is a complete and cocomplete semicartesian $\ast $ -autonomous category with a Seely comonad, then $\mathbf {T} = \mathbf {Set}$ and $\mathcal {P}(A) = \mathbf {L}^A$ defines an affine hyperdoctrine.

Examples 4.1.3. Suppose T is a category with finite limits. Then there is a pseudofunctor $\mathcal {P} : \mathbf {T}^{\mathrm {op}} \to \mathcal {C}\mathit {at}$ sending A to the poset of subobjects of A, which is an intuitionistic hyperdoctrine if and only if T is a Heyting category. There is also such a pseudofunctor sending A to the slice category $\mathbf {T}/A$ , which is an intuitionistic hyperdoctrine if and only if T is locally cartesian closed with finite coproducts.

More generally, any full comprehension category having $\Sigma $ -types, $\Pi $ -types (with function extensionality), and finite sum types is an intuitionistic hyperdoctrine. If it also has propositional truncations, in the sense of [52], then its “h-propositions” (types with at most one element) also form an intuitionistic hyperdoctrine. If it has universe objects closed under the relevant type formers, the elements of any particular universe also form an intuitionistic hyperdoctrine.

Remark 4.1.4. Even in an affine hyperdoctrine, the base category T is still cartesian monoidal. We could allow T to be semicartesian monoidal, as then it would still have “projections” whose adjoints would supply quantifiers; something similar appears in first-order Bunched Implication [Reference O’Hearn and Pym37]. But since the antithesis translation leaves the base category T unchanged, we have no need for this generality, although we will mention it again in Remark 6.18.

We now extend the antithesis translation to hyperdoctrines.

Lemma 4.1.5. The semantic antithesis translation from Section 3 defines a 2-functor

$$\begin{align*}(-)_{\pm} : \mathcal{I}\mathit{nt} \to \mathcal{A}\mathit{ff}. \end{align*}$$

Proof Immediate. Note that since $\mathbf {H}_{\pm }$ , like its substrate $\mathbf {H}\times \mathbf {H}^{\mathrm {op}}$ , is partly covariant and partly contravariant, it can only be 2-functorial on natural isomorphisms; this is why we defined $\mathcal {I}\mathit {nt}$ and $\mathcal {A}\mathit {ff}$ to contain only these.

Theorem 4.6. If $\mathcal {P} : \mathbf {T}^{\mathrm {op}} \to \mathcal {I}\mathit {nt}$ is an intuitionistic hyperdoctrine, the composite

is an affine hyperdoctrine $\mathcal {P}_{\pm }$ .

Proof It remains to show that if $\pi ^* : \mathcal {P}(A) \to \mathcal {P}(A\times B)$ is a bicartesian closed functor with left and right adjoints $\exists _B$ and $\forall _B$ , then $(\pi ^*)_{\pm } : \mathcal {P}(A)_{\pm } \to \mathcal {P}(A\times B)_{\pm }$ also has left and right adjoints satisfying the Beck–Chevalley condition. We define these by the expected formulas:

We leave it to the reader to verify that this works.

This defines the semantic antithesis interpretation for first-order logic.

Moving now to syntax, we consider a formal system of first-order logic with types, each containing terms or elements $t:A$ that may involve variables belonging to other types, and a class of propositions that may also involve variables belonging to types. We assume finite product types $A\times B$ , whose elements are ordered pairs, and a unit type $1$ that has one element. Propositions are related by entailments

$$\begin{align*}P, Q \vdash_{x:A, y:B} R, \end{align*}$$

where $P,Q,R$ are propositions involving only the variables x (of type A) and y (of type B). In intuitionistic first-order logic, we equip the propositions with the usual intuitionistic logical operations:

$$\begin{align*}\land, \lor, \mathbf{1}, \mathbf{0}, \to, \neg, \forall, \exists \end{align*}$$

and the usual intuitionistic rules of deduction. Similarly, in affine first-order logic, we equip the propositions with the affine logical operations:

together with the usual affine rules of deduction (that is, the rules of [Reference Girard19] for linear logic, plus weakening).

Notation 4.1.7. For clarity, we sometimes annotate a quantified variable by the type to which it belongs, e.g., $\exists x^A. P(x)$ if $x:A$ .

By standard arguments (see, e.g., [Reference Jacobs25]), the syntax of either kind of first-order logic, starting from some signature of base types, terms, and propositions, presents a free hyperdoctrine of the appropriate sort. (We gloss over coherence questions here, which can be resolved as in [Reference Hofmann22, Reference Lumsdaine and Warren31], and are automatic in the proof-irrelevant case when the categories $\mathcal {P}(A)$ are posets.) Thus, as in the propositional case, by applying the semantic antithesis translation to the syntactic intuitionistic hyperdoctrine, we obtain a syntactic antithesis translation of affine first-order logic into intuitionistic first-order logic. This translation leaves the types unchanged, acts on the propositional connectives as in Figure 1, and acts on the quantifiers as shown in Figure 2. As before, the derivation of this translation from the semantic version means that it is automatically sound for proofs (though not complete).

Figure 2

The syntactic antithesis translation for first-order logic.

We now consider various additional structure that can be added to a hyperdoctrine, and their corresponding operations in syntax.

4.2 Comprehension

Let $\mathcal {C}\mathit {at}_t$ be the 2-category of categories with a terminal object.Footnote ¹⁰ We denote such terminal objects generically by $1$ .

Definition 4.2.1 [Reference Lawvere28].

Suppose $U:\mathcal {K} \to \mathcal {C}\mathit {at}$ factors through $\mathcal {C}\mathit {at}_t$ . A $\mathcal {K}$ -valued hyperdoctrine $\mathcal {P} : \mathbf {T}^{\mathrm {op}}\to \mathcal {K}$ has comprehension if for all $A\in \mathbf {T}$ and $P\in \mathcal {P}(A)$ , the following functor is representable:

$$ \begin{align*} (\mathbf{T}/A)^{\mathrm{op}} &\to \mathbf{Set},\\ (f:B\to A) &\mapsto \mathcal{P}(B)(1,f^*(P)). \end{align*} $$

We denote a representing object by $i_P : \{P\} \to P$ : it can be thought of as the subtype of A consisting of those elements that satisfy P.

Example 4.2.2. The intuitionistic hyperdoctrine $\mathcal {P}(A) = \mathbf {H}^A$ has comprehension, with $\{P\}$ the set of pairs $(a,p)$ where $a\in A$ and $p\in \mathbf {H}(\mathbf {1},P_a)$ . The same is true for the affine hyperdoctrine $\mathcal {P}(A) = \mathbf {L}^A$ .

Example 4.2.3. Examples 4.1.3 all have comprehension. The comprehension of a subobject or object of a slice category is itself, while a comprehension category includes as data a comprehension operation.

Proposition 4.2.4. If $\mathcal {P}$ is an intuitionistic hyperdoctrine with comprehension, then $\mathcal {P}_{\pm }$ is an affine hyperdoctrine with comprehension.

Proof Since $\top = (\mathbf {1},\mathbf {0})$ in $\mathcal {P}(A)$ , a morphism $\top \to P$ in $\mathcal {P}(A)$ consists of morphisms $\mathbf {1} \to {P}^+$ and ${P}^-\to \mathbf {0}$ . But the latter is unique if it exists, which it does if there is a morphism $\mathbf {1} \to {P}^+$ since ${P}^+\land {P}^- \to \mathbf {0}$ . Thus, we can define .

Note that comprehension in the antithesis model discards all information about refutations; hence in particular . More generally, we have:

Proposition 4.2.5. For $P\in \mathcal {P}(A)$ in any affine hyperdoctrine with comprehension, there is a morphism from $\top $ to in $\mathcal {P}(\{P\})$ .

Proof By definition, there is a morphism from $\top $ to $i_P^*(P)$ in $\mathcal {P}(\{P\})$ . Now we apply the functor and use the fact that .

Since is not in general idempotent (though it is in the antithesis model), this does not imply . But it does make P arbitrarily duplicable over $\{P\}$ , i.e., we have over $\{P\}$ . Thus, we have to be careful to avoid comprehension whenever we want to retain “refutational” information. This leads in particular to a wider gap between “subsets of A” and “sets that inject into A.” We will return to this point in Remark 4.7.1 and Section 5.

Nevertheless, we cannot really do mathematics without comprehension. Fortunately, it is a fairly harmless assumption: even if we start from a hyperdoctrine without comprehension, we can add comprehensions “freely,” replacing the types by “formal comprehensions” or “pre-sets” (types with an “existence predicate”).

Proposition 4.2.6. For any intuitionistic hyperdoctrine $\mathcal {P} : \mathbf {T}^{\mathrm {op}} \to \mathcal {I}\mathit {nt}$ , there is an intuitionistic hyperdoctrine with comprehension $\mathcal {P}^{\{\}} : (\mathbf {T}^{\{\}})^{\mathrm {op}} \to \mathcal {I}\mathit {nt}$ in which:

• • The objects of $\mathbf {T}^{\{\}}$ are pairs $(A,P)$ with $A\in \mathbf {T}$ and $P \in \mathcal {P}(A)$ .

• • The morphisms $(A,P) \to (B,Q)$ are pairs of $f:A\to B$ and $g:P \to f^*Q$ .

• • The objects of $\mathcal {P}^{\{\}}(A,P)$ are those of $\mathcal {P}(A)$ .

• • The morphisms $Q\to R$ in $\mathcal {P}^{\{\}}(A,P)$ are morphisms $P\land Q \to R$ in $\mathcal {P}(A)$ .

Proof The product in $\mathbf {T}^{\{\}}$ is , and the terminal object is $(1,\mathbf {1})$ . It is straightforward to show that $\mathcal {P}^{\{\}}(A,P)$ is bicartesian closed and that $\mathcal {P}^{\{\}}$ is a functor. The quantifiers are and . The comprehension of $Q \in \mathcal {P}^{\{\}}(A,P) = \mathcal {P}(A)$ is $(A, P\land Q)$ .

Remark 4.2.7. The construction of Proposition 4.2.6 appears in many places with many names. Categorically, $\mathbf {T}^{\{\}}$ is the “Grothendieck construction” of the composite ; for the Calculus of Constructions it is the “first-order deliverables” of [Reference McKinna33]. The general construction has a universal property of adding comprehensions “freely”; see, e.g., [Reference Trotta51] for the posetal version.

Proposition 4.2.8. For any affine hyperdoctrine $\mathcal {P} : \mathbf {T}^{\mathrm {op}} \to \mathcal {A}\mathit {ff}$ , there is an affine hyperdoctrine with comprehension $\mathcal {P}^{\{\}} : (\mathbf {T}^{\{\}})^{\mathrm {op}} \to \mathcal {A}\mathit {ff}$ in which:

• • The objects of $\mathbf {T}^{\{\}}$ are pairs $(A,P)$ with $A\in \mathbf {T}$ and $P \in \mathcal {P}(A)$ .

• • The morphisms $(A,P) \to (B,Q)$ are pairs of $f:A\to B$ and .

• • The objects of $\mathcal {P}^{\{\}}(A,P)$ are those of $\mathcal {P}(A)$ .

• • The morphisms $Q\to R$ in $\mathcal {P}^{\{\}}(A,P)$ are morphisms in $\mathcal {P}(A)$ .

Proof The product in $\mathbf {T}^{\{\}}$ is , and the terminal object is $(1,\top )$ . Note that . The same operations as in $\mathcal {P}(A)$ lift to make $\mathcal {P}^{\{\}}(A,P)$ semicartesian $\ast $ -autonomous with products and a Seely comonad. The quantifiers are and .

Syntactically, comprehension corresponds to an operation taking a proposition P in the context of a variable $x:A$ to a type $\{ x:A | P(x) \}$ . In the intuitionistic case, rules for this operation can be found in [Reference Jacobs25, Section 4.6]; note that P cannot contain any variables other than x. (It is possible to formulate a more general kind of comprehension without this restriction, at the expense of introducing dependent types.) The affine case is essentially identical, but due to Proposition 4.2.5 we will emphasize the essentially affirmative nature of affine comprehension by writing it as

4.4 Higher-order structures

Many higher-order structures are properties of the base category T that don’t affect the hyperdoctrine over it; these are automatically preserved by the antithesis construction. For instance, we can ask that T be cartesian closed; this corresponds syntactically to enhancing the base type theory of our first-order logic to a simply typed $\lambda $ -calculus, with operation types $B^A$ whose canonical elements are abstractions $\lambda x.t$ , satisfying $\beta $ and $\eta $ conversion rules.Footnote ¹¹ (These are usually called function types, but for us “functions” will be defined to be operations that respect a given equality relation; see Sections 5 and 6.) We observe:

Proposition 4.4.1. If T is cartesian closed, then so is the $\mathbf {T}^{\{\}}$ defined in Propositions 4.2.6 and 4.2.8.

Proof The exponentials in the two cases are

where $\mathsf {ev} : B^A \times A \to B$ is the evaluation in T.

Similarly, we can ask that T be equipped with a comprehension category or category with families, unrelatedly to the hyperdoctrine. This corresponds syntactically (again, modulo coherence issues that can be addressed as in [Reference Hofmann22, Reference Lumsdaine and Warren31]) to enhancing the base type theory with dependent types, possibly with any desired type formers such as $\Sigma $ -types, $\Pi $ -types, identity types, etc. (which are, at least a priori, unrelated to the hyperdoctrine and its quantifiers). Put differently, this results in a logic-enriched dependent type theory in the sense of [Reference Aczel and Gambino3] in which the logic is that of the hyperdoctrine. Since this structure is likewise undisturbed by the antithesis construction on the hyperdoctrine, we have an antithesis translation from affine-logic-enriched type theory into intuitionistic-logic-enriched type theory. We leave it to the reader to extend Proposition 4.4.1 to such cases.

Example 4.4.2. In particular, as in Examples 4.1.3, we can regard a comprehension category with $\Sigma $ - and $\Pi $ -types as itself an intuitionistic hyperdoctrine with comprehension. That is, any type theory admits an intuitionistic-logic enrichment given by propositions-as-types. Applying the antithesis construction, we obtain a translation from affine-logic-enriched dependent type theory into ordinary intuitionistic dependent type theory. Similarly, we can apply the antithesis construction to the hyperdoctrine of h-propositions, or the elements of some fixed universe.

Remark 4.4.3. This way of applying the antithesis construction to dependent type theory acts only on the “top level” of type dependency, and we will not attempt to extend it further in this paper (although see Remark 6.18). In particular, there are by now many different approaches to “linear dependent type theory,” and it is unclear which, if any, of them would be appropriate for such an extended translation. The lack of a definite answer to this question is one obstacle to a native “affine constructive mathematics,” since dependent type theory has definite advantages over higher-order logic as a foundational system for all of mathematics. But we can still use affine logic, by way of the antithesis translation, to say useful things about the top-level logic of intuitionistic dependent type theory.

4.5 Generic predicates

This is the primary higher-order structure that does interact with a hyperdoctrine.

Definition 4.5.1. A generic predicate Footnote ¹² in a hyperdoctrine $\mathcal {P} : \mathbf {T}^{\mathrm {op}}\to \mathcal {K}$ is an object $\Omega \in \mathbf {T}$ with an element such that for any $A\in \mathbf {T}$ and $P\in \mathcal {P}(A)$ , there exists a (not necessarily unique) $f:A\to \Omega $ and isomorphism .

Example 4.5.2. If H is a small complete Heyting algebra, the intuitionistic hyperdoctrine $\mathcal {P}(A) = \mathbf {H}^A$ has a generic predicate with $\Omega $ the underlying set of H and the identity function. A similar argument applies to the affine hyperdoctrine $\mathcal {P}(A) = \mathbf {L}^A$ , if $\mathbb {L}$ is a small $\ast $ -autonomous complete lattice with a Seely comonad.

Example 4.5.3. The subobject classifier of an elementary topos is a generic predicate for the hyperdoctrine of subobjects. More generally, a preorder-valued intuitionistic hyperdoctrine with cartesian closed base and a generic predicate is a tripos [Reference Hyland, Johnstone and Pitts24].

Example 4.5.4. A comprehension category, regarded as an intuitionistic hyperdoctrine, does not generally have a generic predicate. However, its restricted hyperdoctrine of elements of some universe does have one, namely the universe.

Proposition 4.5.5. If $\Omega $ is a generic predicate for $\mathcal {P}$ , then $(\Omega ,1)$ is a generic predicate for the $\mathcal {P}^{\{\}}$ defined in Propositions 4.2.6 and 4.2.8, where $1$ is the terminal object of $\mathcal {P}(\Omega )$ .

Proposition 4.5.6. If $\mathcal {P}$ is an intuitionistic hyperdoctrine with comprehension and a generic predicate, then $\mathcal {P}_{\pm }$ also has a generic predicate.

Proof Over $\Omega \times \Omega $ we have two canonical predicates and . Let $\Omega _{\pm }$ be the comprehension of . Then to give a morphism $f:A \to \Omega _{\pm }$ is the same as to give two morphisms ${f}^+ : A\to \Omega $ and ${f}^- : A \to \Omega $ , corresponding to predicates and over A, such that is initial in $\mathcal {P}(A)$ . Thus, $\Omega _{\pm }$ is a generic predicate for $\mathcal {P}_{\pm }$ .

Example 4.5.7. In the hyperdoctrine of subobjects in a topos, $\Omega _{\pm }$ is the subobject of $\Omega \times \Omega $ consisting internally of pairs of incompatible propositions.

Syntactically, a generic predicate corresponds to having an (impredicative) type $\Omega $ of all propositions. The usual way of presenting a higher-order type theory of this sort is to define the propositions to be the terms of type $\Omega $ , or at least bijective to them. In a hyperdoctrine with a generic predicate, we have only an essentially surjective function $\mathbf {T}(A,\Omega ) \to \mathcal {P}(A)$ , but as in [Reference Hyland, Johnstone and Pitts24] we can use this to replace $\mathcal {P}(A)$ by an equivalent category whose set of objects is precisely $\mathbf {T}(A,\Omega )$ .

Thus, with Proposition 4.5.6 we can translate affine higher-order logic into intuitionistic higher-order logic, where both have comprehensions and a type of propositions. The syntactic expression of the type of propositions derived from Proposition 4.5.6 is

Note that unlike the syntactic antithesis translations for propositional and first-order logic in Figures 1 and 2, this is a definition of a type, not a proposition or predicate. The antithesis translation does not modify the collection of types or most of the operations on them, but it does change the type of propositions.

4.6 Infinity

Finally, as a starting point for concrete mathematics, we require at least a type of natural numbers that permits definitions by recursion and proofs by induction. The intuitionistic version of this is straightforward.

Definition 4.6.1. In an intuitionistic hyperdoctrine, a natural numbers type is an object $N\in \mathbf {T}$ together with morphisms $o:1\to N$ and $s:N\to N$ such that:

1. (i) For any objects $A,B\in \mathbf {T}$ with $f:A\to B$ and $g:A\times N\times B\to B$ , there exists a morphism $h:A\times N\to B$ making the following diagrams commute:

   

2. (ii) For any predicate $P\in \mathcal {P}(A\times N)$ , the following entailment holds:

   (4.2) $$ \begin{align} P_a(0)\,\land\, \forall k. (P_a(k) \to P_a(k+1)) \;\vdash_{a:A}\; \forall n. P_a(n). \end{align} $$

Syntactically, the diagrams in (i) say that $h(a,0) = f(a)$ and $h(a,n+1) = g(a,n,h(a,n))$ , as we expect for an operation defined recursively. We have expressed the induction rule (4.2) in syntax already; the reader is free to re-express it in more semantic language. Note that h in (i) is not required to be unique; thus N is only a “weak natural numbers object” in T. Such uniqueness is irrelevant for us, as with a defined equality on the codomain (see Sections 5 and 6) operations defined by recursion will always be unique as functions.

The affine version of induction is somewhat less obvious, but the following will be appropriate for us.

Definition 4.6.3. In an affine hyperdoctrine, a natural numbers type is $(N,o,s)$ satisfying (i) of Definition 4.6.1 and such that for any predicate $P\in \mathcal {P}(A\times N)$ , the following entailment holds:

(4.4)

Note that the induction step is marked with the modality . This is natural if we think of as denoting a hypothesis that can be used more than once, as the induction step must certainly be “used” n times in order to conclude $P(n)$ . But it is also mandated by the antithesis translation.

Lemma 4.6.5. If an intuitionistic hyperdoctrine $\mathcal {P}$ contains a natural numbers type, so does its antithesis translation $\mathcal {P}_{\pm }$ .

Proof The antithesis translation of (4.4) consists of the following two entailments:

$$ \begin{align*} {P}^+(0)\,\land\, \forall k. (({P}^+(k) \to {P}^+(k+1)) \land ({P}^-(k+1) \to {P}^-(k))) \;&\vdash_{P:\Omega^{\mathbb{N}}}\; \forall n. {P}^+(n), \\ \exists n. {P}^-(n)\,\land\, \forall k. (({P}^+(k) \to {P}^+(k+1)) \land ({P}^-(k+1) \to {P}^-(k))) \;&\vdash_{P:\Omega^{\mathbb{N}}}\; {P}^-(0). \end{align*} $$

Both can be proven easily from (4.2).

On the other hand, if we drop the in (4.4), then its antithesis translation would also include a third entailment

(4.6) $$ \begin{align} {P}^+(0)\,\land\, \exists n. {P}^-(n) \;\vdash_{P:\Omega^{\mathbb{N}}} \exists k. ({P}^+(k) \land {P}^-(k+1)), \end{align} $$

which is equivalent to excluded middle. Specifically, let $P(0) = (\top ,\bot )$ and $P(n) = (\bot ,\top )$ for $n\ge 2$ , while $P(1) = (Q,\neg Q)$ for some arbitrary statement Q; then by (4.6) we have either $\neg Q$ (if $k=0$ ) or Q (if $k=1$ ). Thus, we are forced to formulate affine induction as in (4.4).

Proposition 4.6.7. If $\mathcal {P}$ has a natural numbers type, so does the $\mathcal {P}^{\{\}}$ defined in Propositions 4.2.6 and 4.2.8.

5 Intuitionistic sets and functions

In most of the rest of the paper, we will first state definitions in affine logic and then translate them into intuitionistic logic. But for sets and equality, we begin with the intuitionistic context to fix conventions.

As mentioned after Proposition 4.3.3, we follow Bishop’s dictum:

Thus a “Bishop set” has two ingredients: the “requirements,” which we regard as the specification of a type, and the equality, which is an equivalence relation.

Definition 5.1. A set is a type A with a predicate $=$ on $A\times A$ such that

$$ \begin{align*} \begin{array}{rll} &\vdash_{x: A}& x= x\\ x= y &\vdash_{x,y: A}& y= x\\ (x= y) \land (y= z) &\vdash_{x,y,z: A}& x= z. \end{array} \end{align*} $$

Definition 5.7. A relation on a set A is a predicate P on its underlying type such that

$$\begin{align*}(x= y) \land P(x) \vdash_{x,y: A} P(y). \end{align*}$$

A relation is also called a subset of A, with $x\in P$ meaning $P(x)$ . We overload notation by writing P as $\{ x: A | P(x) \}$ , though a subset is not itself a set.

The relations on a given set are closed under all the logical operations. Put differently, the subsets of a set are a sub-Heyting-algebra of the predicates on its underlying type. We write and so on.

Definition 5.8. A function between two sets is an operation $f:B^A$ such that

$$\begin{align*}\begin{array}{rll} &\vdash_{x: A} & f(x) \in B\\ (x_1= x_2) & \vdash_{x_1,x_2: A}& (f(x_1)= f(x_2)). \end{array} \end{align*}$$

The function set is defined by

Note the notation: the operation type is $B^A$ , and the function set is $A\to B$ .

One final remark concerns the following alternative definition of “function.”

Definition 5.10. For sets $A,B$ , an anafunction Footnote ¹³ is a relation F on $A\times B$ that is total and functional, i.e., such that

$$\begin{align*}\begin{array}{rll} &\vdash_{x: A}& \exists y^B. F(x,y)\\ F(x,y_1) \land F(x,y_2) &\vdash_{x: A, y_1:B,y_2: B} & (y_1= y_2). \end{array}\end{align*}$$

If $f:A\to B$ is a function, then $(f(x)= y)$ is an anafunction; the principle of function comprehension (a.k.a. unique choice) says that every anafunction is of this form. Function comprehension is not provable in first-order logic, higher-order logic, or logic-enriched type theory, and indeed fails in many triposes. Nevertheless, constructivists of Bishop’s school often assume it implicitly (one can argue for it by positing a closer relationship between “operations” and the existential quantifier than is implied by first-order or higher-order logic).

In the absence of function comprehension, it is often preferable to use anafunctions rather than functions. For instance, this is how one builds the topos represented by a tripos (such as a realizability topos), and in particular how one recovers the correct internal logic of a topos from its tripos of subobjects.

6 Affine sets and functions

We now switch to the affine context, for this section and the rest of the paper, except when discussing the antithesis translation. In the definition of $\mathfrak {A}$ -sets we find our first additive/multiplicative bifurcation.

Definition 6.1. A set is a type with a predicate $\circeq $ on $A\times A$ such that

$$\begin{alignat*}{2} &\;\vdash_{x: A}\;&\;& x\circeq x\\ x\circeq y &\;\vdash_{x,y: A}&\;& y\circeq x\\ (x\circeq y) \boxtimes (y\circeq z) &\;\vdash_{x,y,z: A}&\;& x\circeq z.\\ \end{alignat*} $$

A set is strong if it satisfies the stronger transitivity axiom

$$\begin{alignat*}{2} (x\circeq y) \sqcap (y\circeq z) &\;\vdash_{x,y,z: A}&\;& x\circeq z. \end{alignat*} $$

Under the antithesis translation, an $\mathfrak {A}$ -set is an $\mathfrak {I}$ -type with two binary predicates $(=,\neq )$ such that

$$\begin{align*}\begin{array}{rll} &\vdash_{x,y: A}& \neg ((x= y)\land (x\neq y))\\ &\vdash_{x: A}& x= x\\ x= y &\vdash_{x,y: A} & y= x\\ x\neq y &\vdash_{x,y: A} & y\neq x\\ (x= y) \land (y= z) &\vdash_{x,y,z: A}& x= z\\ (x\neq z) \land (y= z) &\vdash_{x,y,z: A}& x\neq y\\ (x\neq z) \land (x= y) &\vdash_{x,y,z: A}& y\neq z. \end{array} \end{align*}$$

The axioms involving only $= $ say that $(A,= )$ is an $\mathfrak {I}$ -set, and the last two axioms say that $\neq $ is an $\mathfrak {I}$ -relation (Definition 5.7) on $A\times A$ . Given this, the first axiom is equivalent to $\vdash _{x: A}\neg (x\neq x)$ . Thus we have:

Example 6.5. If A and B are sets, their cartesian product set is the cartesian product type $A\times B$ with

Under the antithesis translation, this yields the cartesian product of $\mathfrak {I}$ -sets with the disjunctive product inequality (or product apartness):

Example 6.6. The tensor product set $A\boxtimes B$ has the same underlying type, but with equalities combined multiplicatively:

In the antithesis translation, thus yields the weaker inequality

If A and B have affirmative equality, so does $A\boxtimes B$ , but $A\times B$ need not. If A and B have strong or refutative equality, so does $A\times B$ , but $A\boxtimes B$ need not.

Example 6.7. The type $\Omega $ is a set with

(6.8)

In the antithesis translation, this yields

$$ \begin{align*} (P= Q) &\equiv ({P}^+ \leftrightarrow {Q}^+) \land ({P}^- \leftrightarrow {Q}^-),\\ (P\neq Q) &\equiv ({P}^+ \land {Q}^-) \lor ({P}^- \land {Q}^+). \end{align*} $$

We could also use $\boxtimes $ in (6.8), but using $\sqcap $ yields a more useful $\neq $ and has better formal properties (see Example 6.14 and Section 8). In neither case is the equality strong, nor is it affirmative nor refutative even if P and Q are both one or the other.

Remark 6.9. The notion of “strong set” is quite natural under the antithesis translation, since apartness relations are well-studied in intuitionistic constructive mathematics. However, to a reader familiar with linear logic (and particularly with linear proof theory), the $\sqcap $ -transitivity of a strong set may seem unreasonably strong. An assumption of $(x\circeq y)\sqcap (y\circeq z)$ means that we can choose to use either $x\circeq y$ or $y\circeq z$ but not both, so how could we ever hope to prove $x\circeq z$ ?

In fact, however, there are many sets that can be proven to be strong inside affine logic. The key is that we don’t have to start by deciding which of $x\circeq y$ and $y\circeq z$ to use: we can decompose x, y, and z and use the definition of $\circeq $ to make case distinctions, and then make different choices of $x\circeq y$ and $y\circeq z$ in different cases.

A paradigmatic example is the natural numbers $\mathbb {N}$ , for which we define equality recursively in the usual way:

We prove $(x\circeq y)\sqcap (y\circeq z) \vdash _{x,y,z:\mathbb {N}} (x\circeq z)$ by induction on $x,y,z$ . The case when x and z are both $0$ is trivial. If x is $0$ but z is a successor, then either y is $0$ , in which case we can use $y\circeq z$ to get a contradiction, or y is a successor, in which we can use $x\circeq y$ to get a contradiction. The case when x is a successor and z is $0$ is symmetric. Finally, if x is $x'+1$ and z is $z'+1$ , then if y is $0$ we can use either $x\circeq y$ or $y\circeq z$ to get a contradiction, while if y is a successor $y'+1$ then our goal reduces to the inductive hypothesis $(x'\circeq y')\sqcap (y'\circeq z') \vdash _{x',y',z':\mathbb {N}} (x'\circeq z')$ .

We now move on to discuss $\mathfrak {A}$ -relations and subsets.

Definition 6.10. A relation on a set A is a predicate P such that

$$\begin{align*}(x\circeq y) \boxtimes P(x) \vdash_{x,y: A} P(y). \end{align*}$$

A relation is strong if

$$\begin{align*}(x\circeq y) \sqcap P(x) \vdash_{x,y: A} P(y). \end{align*}$$

We also refer to a relation as a subset, writing instead of $P(x)$ , and for P itself. (Unlike in the intuitionistic case, we distinguish this notationally from a comprehension , since the latter discards refutational information.)

Proof The subset condition

becomes

The first two say that U and

are $\mathfrak {I}$ -subsets, and the last is the “strong disjointness” condition in (i). The “strong extensionality” condition in (ii) is exactly the contrapositive information arising from the strong subset condition.

Definition 6.12. A function between two sets is an operation $f:B^A$ such that

$$\begin{align*}\begin{array}{rll} (x_1\circeq x_2) & \vdash_{x_1,x_2: A}& (f(x_1)\circeq f(x_2)). \end{array}\end{align*}$$

The function set is defined by

Example 6.14. We have $(x\circeq y)\boxtimes P(x) \vdash P(y)$ iff

, and symmetry of $\circeq $ then implies

, i.e.,

. Therefore, relations on A are the same as functions from A to the set $\Omega $ from Example 6.7. (Note that this requires the $\sqcap $ in (6.8).) Thus we can define the power set of A to be

. Its induced equality is

In the antithesis translation, we have

Example 6.16. In particular, functions from B to $\mathscr {P} A = (A\to \Omega )$ classify subsets not of $A\times B$ , but of $A\boxtimes B$ . In the antithesis translation, an $\mathfrak {A}$ -subset of $A\boxtimes B$ is a pair of $\mathfrak {I}$ -subsets

such that

whereas an $\mathfrak {A}$ -subset of $A\times B$ satisfies the stronger condition

The $\mathfrak {A}$ -relations on an $\mathfrak {A}$ -set are closed under the additive connectives, as well as linear negation. This defines the additive operations of set algebra:

Here the index i in

and ${\textstyle \bigsqcup }_i$ belongs to some type I, while U is a predicate on $I\times A$ that respects the equality of A. In particular, it might be the case that I is itself an $\mathfrak {A}$ -set and U is a predicate on $I\times A$ or $I\boxtimes A$ .

We write to mean ; in the antithesis translation this means that $U\subseteq V$ and . Since commutes with $\sqcap $ , we have . By duality, means .

Like linear negation, the complement of $\mathfrak {A}$ -subsets is involutive ( ${U}^{\perp \perp } = U$ ) but not Boolean: and both assert that U is decidable.

Proof The definition of inequality on $\mathscr {P} A$ gives

Multiplicatives and exponentials do not generally preserve subsets, but they do induce operations on subsets by a reflection or coreflection process:

The poset of subsets of A thereby becomes semicartesian and $\ast $ -autonomous with a Seely comonad. In particular, as a replacement for the false equalities

and

we have the true ones

and

, and the

-coalgebras form a “Heyting algebra of affirmative subsets.” In the antithesis translation,

is the affirmative part of U with its inequality complement:

Thus an “affirmative subset” (i.e.,

) is determined by an ordinary $\mathfrak {I}$ -subset.

Finally, we note that unique existence and “anafunctions” (see Definition 5.10) also behave sensibly. Recall that classically we can express “there is at most one x with $P(x)$ ” either as “for all $x,y$ , if $P(x)$ and $P(y)$ , then $x=y$ ” or “there do not exist $x,y$ with $x\neq y$ such that $P(x)$ and $P(y)$ .” Intuitionistically these are no longer equivalent (unless $\neq $ is tight), and only the former is “correct.” But linearly they are again equivalent:

In the antithesis translation, these statements yield the “correct” intuitionistic version augmented by a strong uniqueness “if $x\neq y$ and $P(x)$ , then

.” An even stronger sort of uniqueness would arise from the strong linear condition

which in the antithesis translation yields “if $x\neq y$ , then either

or

.”

Definition 6.19. For $\mathfrak {A}$ -sets $A,B$ , an anafunction from A to B is a relation F on $A\boxtimes B$ that is total and functional, i.e., such that

$$\begin{align*}\begin{array}{rll} &\vdash_{x: A}& {\textstyle\bigsqcup} y^B. F(x,y)\\ F(x,y_1) \boxtimes F(x,y_2) &\vdash_{x: A, y_1:B ,y_2: B}& (y_1\circeq y_2). \end{array}\end{align*}$$

Theorem 6.20. In the antithesis translation, an $\mathfrak {A}$ -anafunction from A to B corresponds to an $\mathfrak {I}$ -anafunction that is “strongly extensional” in the sense that

$$\begin{align*}F(x_1,y_1) \land F(x_2,y_2) \land (y_1\neq y_2) \vdash_{x_1,x_2: A, y_1,y_2: B} (x_1\neq x_2). \end{align*}$$

Proof An $\mathfrak {A}$ -anafunction consists of two $\mathfrak {I}$ -relations

on $A\times B$ such that

The fourth and sixth axioms say that F is an $\mathfrak {I}$ -anafunction. Given this, the second and seventh say

, which implies the first and fifth, and unravels the third to the claimed strong extensionality property.

A function is strongly extensional just when its corresponding anafunction is. Thus, a function comprehension principle is equally sensible affinely as intuitionistically, and in its absence we can once again work with anafunctions instead. Moreover, Theorem 6.20 implies that function comprehension is preserved by the antithesis construction: if an intuitionistic hyperdoctrine $\mathcal {P}$ satisfies function comprehension, so does the affine hyperdoctrine $\mathcal {P}_{\pm }$ .

7 Algebra

Roughly speaking, there are two approaches to intuitionistic constructive algebra. The first uses apartness only minimally; inequality usually means denial $\neg (x= y)$ and is avoided as much as possible. For instance, apartness relations are absent from [Reference Johnstone26], and are only rarely used in [Reference Mines, Richman and Ruitenburg35]. The second approach equips all sets with inequalities (often tight apartnesses),Footnote ¹⁵ and all classical definitions are augmented by “strong negative” information such as anti-subgroups and anti-ideals. This is the tradition of Heyting; see [Reference Troelstra and van Dalen50, Chapter 8].

The second approach gives more refined information. For instance, the real numbers are a field in the strong sense that any number apart from $0$ is invertible; but without apartness, all we can say is that they are a local ring in which every noninvertible element is zero. However, carrying apartness relations around is tedious and error-prone, and not every algebraic structure admits a natural apartness:

Moreover, rewriting all of algebra in “dual” form looks very unfamiliar to the classical mathematician, and even a constructive mathematician may find it unaesthetic.

The antithesis translation resolves this by automatically handling the “bookkeeping” of apartness relations, allowing familiar-looking definitions (written in affine logic) to nevertheless carry the correct constructive meaning (when translated into intuitionistic logic). It also reveals the above two approaches as ends of a continuum: $\mathfrak {I}$ -sets with denial inequality are the $\mathfrak {A}$ -sets with affirmative equality, while $\mathfrak {I}$ -sets with a (tight) apartness are the $\mathfrak {A}$ -sets with a (refutative) strong equality. There are also natural examples in between; see Example 7.8.

Definition 7.1. A group is an ( $\mathfrak {A}$ -)set G together with an element $e: G$ and functions $m:G\boxtimes G\to G$ and $i:G\to G$ such that

$$\begin{alignat*}{4} &\vdash_{x: G}&\;& m(x,e) \circeq x &\qquad &\vdash_{x: G}&\;& m(x,i(x)) \circeq e\\ &\vdash_{x: G}&\;& m(e,x) \circeq x &\qquad &\vdash_{x: G}&\;& m(i(x),x) \circeq e\\ &\vdash_{x,y,z: G}&\;& m(m(x,y),z) \circeq m(x,m(y,z)). \end{alignat*} $$

A group is strong if m is a function on $G\times G$ .

As usual, we write $xy$ and $x^{-1}$ instead of $m(x,y)$ and $i(x)$ .

Theorem 7.2. In the antithesis translation, an $\mathfrak {A}$ -group consists of an $\mathfrak {I}$ -group equipped with an inequality relation such that

$$\begin{align*}\begin{array}{rll} x^{-1}\neq y^{-1} &\vdash_{x,y: G} & x\neq y,\\ x u \neq x v &\vdash_{x,u,v: G} & u\neq v,\\ x u \neq y u &\vdash_{x,y,u: G} & x\neq y. \end{array}\end{align*}$$

The extra condition for G to be strong is

(7.3) $$ \begin{alignat}{2} (x u \neq y v) &\vdash_{x,y,u,v: G} &\;& (x \neq y) \lor (u\neq v), \end{alignat} $$

which is equivalent to $\neq $ being an apartness. In particular:

• • An $\mathfrak {A}$ -group with affirmative equality is precisely an $\mathfrak {I}$ -group.

• • A strong $\mathfrak {A}$ -group with refutative equality is precisely a group with apartness relation in the sense of [Reference Troelstra and van Dalen50, Definition 8.2.2], i.e., an $\mathfrak {I}$ -group with a tight apartness for which the group operations are strongly extensional.

• • An arbitrary $\mathfrak {A}$ -group is precisely an $\mathfrak {I}$ -group with a (symmetric irreflexive) translation invariant inequality as in [Reference Mines, Richman and Ruitenburg35, Exercise II.2.5].

The fact that (7.3) is equivalent to $\neq $ being an apartness is a standard exercise in constructive algebra. In fact, it can be proven internally in affine logic that an $\mathfrak {A}$ -group is strong if and only if it has strong equality.

Definition 7.4. A subgroup of a group G is a subset

such that

A subgroup is strong if it satisfies the stronger condition

In the antithesis translation, if H and G are affirmative then normality reduces to ordinary normality, whereas if they are strong and refutative it reduces to normality for an antisubgroup [Reference Troelstra and van Dalen50, Definition 8.2.7].

Proof The closure axioms of a subgroup directly imply the axioms of an equality predicate. It remains to show that m and i are functions $G/H \boxtimes G/H \to G/H$ and $G/H \to G/H$ . For the first, we have

Similarly, for the second we have

Example 7.8. Let $G = \mathbf {2}^{\mathbb {N}}$ be the set of infinite binary sequences, with pointwise addition mod 2, and

. Then G is a strong group with refutative equality, while H is a normal subgroup that is neither strong, affirmative, nor refutative. In the quotient $G/H$ we have

That is, $x\circeq 0$ if x is eventually $0$ , and $x{{\not\circeq }} 0$ if x is $1$ infinitely often. Neither of these is the Heyting negation of the other, so $G/H$ is neither affirmative nor refutative. Similarly, $G/H$ is not strong, so in the antithesis translation its inequality is not an apartness and its multiplication is not strongly extensional for the disjunctive product inequality, though it is for the weaker equality on $G/H\boxtimes G/H$ .

In [Reference Mines, Richman and Ruitenburg35, p. 31] this example is used to argue that not all sets should have inequalities. From our perspective, it shows instead that not all groups should be required to be strong.

A (commutative) ring is an abelian group $(R,+,0)$ with a multiplication function $\cdot :R\boxtimes R\to R$ and unit $1:R$ satisfying the usual axioms; it is strong if both $+$ and $\cdot $ are defined on $R\times R$ . In the antithesis translation:

• • An affirmative $\mathfrak {A}$ -ring is an ordinary $\mathfrak {I}$ -ring.

• • A strong refutative $\mathfrak {A}$ -ring is a ring with apartness as in [Reference Troelstra and van Dalen50, Definition 8.3.1] (except that they also assume $0\neq 1$ ).

• • A general $\mathfrak {A}$ -ring is an $\mathfrak {I}$ -ring with an inequality such that $(x\neq y) \leftrightarrow (x-y \neq 0)$ and $(xy \neq 0) \to (y\neq 0)$ .

An ideal is an additive subgroup J with . In the antithesis translation, in the affirmative case this is an ordinary $\mathfrak {I}$ -ideal, while in the strong refutative case it is an anti-ideal [Reference Troelstra and van Dalen50, Definition 8.3.6]: an additive antisubgroup with . The quotient $R/J$ of an $\mathfrak {A}$ -ring by an ideal is straightforward, and its antithesis translation yields the apartness on the quotient of an apartness ring by the complement of an anti-ideal [Reference Troelstra and van Dalen50, Proposition 8.3.8].

If J is proper, then $R/J$ is -integral or -integral exactly when J is -prime or -prime, respectively. In the antithesis translation:

• • A -prime affirmative $\mathfrak {A}$ -ideal in an affirmative $\mathfrak {A}$ -ring is a proper $\mathfrak {I}$ -ideal such that $(xy\in J) \vdash (x\in J) \lor (y\in J)$ . An affirmative $\mathfrak {A}$ -ring is -integral if $\neg (0= 1)$ and $(xy= 0) \vdash (x= 0)\lor (y= 0)$ ; this is [Reference Johnstone26, axiom I1].

• • Similarly, an affirmative $\mathfrak {A}$ -ring is -integral if it satisfies $\neg (0= 1)$ and [Reference Johnstone26, axiom I2]: $(xy= 0) \land \neg (x= 0) \to (y= 0)$ .

• • A -prime strong refutative $\mathfrak {A}$ -ideal in a strong refutative $\mathfrak {A}$ -ring is an anti-ideal in an $\mathfrak {I}$ -ring with apartness that is proper ( ) and such that , i.e., a prime anti-ideal as in [Reference Troelstra and van Dalen50, Proposition 8.3.10].

• • Finally, an arbitrary $\mathfrak {A}$ -ring is -integral if and only if $1\neq 0$ and we have $(x\neq 0) \land (xy = 0) \to (y= 0)$ and also $(x\neq 0) \land (y\neq 0) \to (x y \neq 0)$ . Combined with the above characterization of $\mathfrak {A}$ -rings, this is precisely an integral domain in the sense of [Reference Mines, Richman and Ruitenburg35, Exercise II.2.7].

We write for “x is invertible”; this is the second disjunct in (either kind of) maximality for $(0)$ . The quotient $R/J$ is a -field or -field if and only if J is -maximal or -maximal, respectively. In the antithesis translation:

• • An affirmative $\mathfrak {A}$ -ring is a -field just when its corresponding $\mathfrak {I}$ -ring satisfies $\neg (0= 1)$ and $(x= 0) \lor \mathsf {inv}(x)$ . These are called discrete fields (since they necessarily have decidable equality) or geometric fields [Reference Johnstone26, axiom F1].

• • A general $\mathfrak {A}$ -ring is a -field just when its corresponding $\mathfrak {I}$ -ring with inequality satisfies $0\neq 1$ and $(x\neq 0) \to \mathsf {inv}(x)$ . This is precisely a field as in [Reference Mines, Richman and Ruitenburg35] with $\neq $ irreflexive (in [Reference Mines, Richman and Ruitenburg35] the zero ring is a “field” with $0\neq 0$ ).

• • A -field has strong refutative equality just when its $\mathfrak {I}$ -ring has a tight apartness; these are the Heyting fields of [Reference Mines, Richman and Ruitenburg35] and the fields of [Reference Troelstra and van Dalen50, Definition 8.3.1].

• • Strong refutative -maximal $\mathfrak {A}$ -ideals are the minimal anti-ideals of [Reference Troelstra and van Dalen50, Definition 8.3.10].

• • Finally, the affirmative $\mathfrak {A}$ -rings that are -fields are the $\mathfrak {I}$ -rings satisfying $\neg (1= 0)$ and $\neg (x= 0) \to \mathsf {inv}(x)$ , which is [Reference Johnstone26, axiom F2].

8 Order

When equality is a defined relation, we can either introduce order and topology as structures on a type which induce an equality, or as structures on a set that might determine the equality by a “separation” axiom. We prefer the former.

Definition 8.1. A preorder on an $\mathfrak {A}$ -type A is a predicate

on $A\times A$ with

• • A preorder is strong if .

• • A linear order is a preorder such that .

• • A total order is a preorder such that .

If A has a preorder, then makes A into a set, and is then a relation defined on $A\boxtimes A$ . The sets-with-preorder we obtain in this way are exactly the partial orders: sets with a preorder such that is a relation on $A\boxtimes A$ and is $\sqcap $ -antisymmetric, i.e., .

In the antithesis translation, an $\mathfrak {A}$ -partial-order contains two relations $\le $ and ${\not\le }$ , but it is often more suggestive to write $x<y$ instead of $y{\not\le } x$ .

Theorem 8.3. In the antithesis translation, a partial order on an $\mathfrak {A}$ -set A consists of two $\mathfrak {I}$ -relations $\le $ and $<$ such that

$$\begin{alignat*}{2} &\vdash_{x: A} &\;&(x\le x)\\[-1pt] (x\le y)\land (y\le z) &\vdash_{x,y,z: A} &\;&(x\le z)\\[-1pt] (x\le y) \land (y\le x) &\vdash_{x,y: A}&\;& (x= y)\\[-1pt] (x<y)\land (y\le z) &\vdash_{x,y,z: A}&\;& (x<z)\\ (x\le y) \land (y<z) &\vdash_{x,y,z: A}&\;& (x<z)\\[-1pt] (x<y) &\vdash_{x,y: A}&\;& (x\neq y)\\[-1pt] (x\neq y) &\vdash_{x,y: A}&\;& ((x<y) \lor (y<x)). \end{alignat*} $$

That is, $\le $ is an $\mathfrak {I}$ -partial-order, $<$ is a “bimodule” over it, and for $x,y: A$ we have $(x\neq y) \equiv ((x<y) \lor (y<x))$ . Moreover, the $\mathfrak {A}$ -partial-order is…

• • …strong if and only if $<$ is cotransitive: $(x<z) \vdash (x<y) \lor (y<z)$ .

• • …linear if and only if $(x<y)\to (x\le y)$ (hence $<$ is transitive).

• • …total if and only if $\le $ is total, $(x\le y)\lor (y\le x)$ .

Such “order pairs” appear often in constructive mathematics, but the only abstract such definition I know of was in the Lean 2 proof assistant.Footnote ¹⁶ Often either $\le $ or $<$ is the other’s negation (i.e., is affirmative or refutative), but not always:

Example 8.4. Conway’s surreal numbers [Reference Conway16] are defined in classical logic by:

• – If $L,R$ are any two sets of numbers, and no member of L is $\ge $ any member of R, then there is a number $\{ L | R \}$ . All numbers are constructed in this way.

• – $x\ge y$ iff (no $x^R\le y$ and $x\le $ no $y^L$ ).

(For $x = \{L|R\}$ , $x^L$ and $x^R$ denote typical members of L or R respectively.) Leaving aside the problematic inductive nature of this definition, we can write it affinely as

where

is its negation

In the antithesis translation, this yields a simultaneous inductive definition of $\le $ and $<$ , neither of which is the Heyting negation of the other; see [Reference Forsberg and Setzer18] and [52, Section 11.6]. Omitting R yields the plump ordinals (see [Reference Taylor47] and [52, Example 11.17]).

Recall that classically, if $\le $ is a total order we can define $x<y$ by $\neg (y\le x)$ or by $(x\le y)\land (x\neq y)$ , and recover $x\le y$ as $\neg (y< x)$ or as $(x=y)\lor (x<y)$ . For an “order pair” as in Theorem 8.3 that is linear, the former holds, but the latter generally fails. However, in affine logic we can say:

Theorem 8.5. Let be a refutative linear order, and write . Then we have

(8.6)

(8.7)

Proof For any partial order we have

This certainly implies

. Conversely, linearity of

means

, while refutativity implies

, so that

implies

. This gives (8.6), while (8.7) is simply its De Morgan dual.

Thus, while the constructive $\le $ does not mean “less than or equal to,” at least in some cases (such as $\mathbb {R}$ ; see Section 9) it does mean “less than par equal to” (or perhaps, as suggested in Remark 3.8, “less than unless equal to” or “less than or else equal to”).

9 Real analysis

Recall from Remark 6.9 that the natural numbers type $\mathbb {N}$ is a strong set. In fact it is a strong total order, with order relation defined recursively:

The integers $\mathbb {Z}$ are the type $\mathbb {N}\times \mathbb {N}$ with

and the rational numbers $\mathbb {Q}$ are $\mathbb {Z}\times \mathbb {N}$ with

These total orders are affirmative, refutative, strong, and decidable, as are the induced equalities

. In the antithesis translation, they yield the usual posets of numbers.

We define addition and multiplication by recursion on $\mathbb {N}$ , and then by the usual formulas on $\mathbb {Z}$ and $\mathbb {Q}$ , making $\mathbb {Z}$ a -integral strong ring and $\mathbb {Q}$ a strong -field.

Definition 9.1. The Cauchy real numbers are the partially ordered $\mathfrak {A}$ -set

The set $\mathbb {R}_c$ is a strong linear order and a strong ring that is a -field.

The Dedekind real numbers are a little more surprising. We first note that, just as in classical logic (but not intuitionistic logic), the notion of “one-sided cut” in affine logic doesn’t depend on the side, or whether the cuts are open or closed.

Theorem 9.4. The following $\mathfrak {A}$ -sets are isomorphic:

Proof The isomorphisms are:

We give $\mathcal {C}$ the partial order induced from containment of lower sets. Thus, if we write $x_{\smash {\mathring {L}}},x_{\smash {\overline {L}}},x_{\smash {\mathring {U}}},x_{\smash {\overline {U}}}$ for the four representations of , we have

Using totality of the order on $\mathbb {Q}$ , we can show that this order on $\mathcal {C}$ is linear. If we identify

with the cut

, then $\mathbb {Q}$ is fully order-embedded in $\mathcal {C}$ , and moreover for any

and

we have

Thus, we can define a cut x by specifying any one of the relations

,

,

, and

on $\mathbb {Q}$ which has the appropriate property. This is usually more congenial than working explicitly with upper or lower subsets of $\mathbb {Q}$ .

In intuitionistic logic, it is common to work with two-sided cuts instead. But because an $\mathfrak {A}$ -subset is a complemented $\mathfrak {I}$ -subset, in the antithesis translation our one-sided $\mathfrak {A}$ -cuts become two-sided $\mathfrak {I}$ -cuts.

Theorem 9.6. In the antithesis translation, $\mathcal {C}$ corresponds to the set of pairs $(L,U)$ of $\mathfrak {I}$ -subsets of $\mathbb {Q}$ such that L is an upwards-open lower set, U is a downwards-open upper set, and $L<U$ . Its induced order is

$$ \begin{align*} ((L_1,U_1) \le (L_2,U_2)) &\equiv ((L_1\subseteq L_2) \land (U_2 \subseteq U_1)),\\ ((L_1,U_1) < (L_2,U_2)) &\equiv \exists r. ((r\in L_2) \land (r\in U_1)). \end{align*} $$

Proof By Theorem 6.11, an element of $\mathscr {P}\mathbb {Q}$ is a disjoint pair

of subsets of $\mathbb {Q}$ . To say that it is an $\mathfrak {A}$ -lower-set means that L is an $\mathfrak {I}$ -lower-set and

is an $\mathfrak {I}$ -upper-set. Given this, disjointness is equivalent to

. And to say that it is $\mathfrak {A}$ -upwards-open means that L is $\mathfrak {I}$ -upwards-open and

is $\mathfrak {I}$ -downwards-closed. Finally, the bijection between open and closed upper cuts (or, dually, lower ones) is also true intuitionistically:

The $\mathfrak {I}$ -set of pairs $(L,U)$ in Theorem 9.6 is also called the set of (rational) cuts [Reference Richman43], or sometimes the interval domain. It is distinct from $\mathbb {R}$ even classically, containing additionally all closed intervals $[a,b]$ for $-\infty \le a\le b\le \infty $ .

All cuts are “ -located,” , by -excluded-middle. In the antithesis translation, $\mathbb {R}_d$ is the usual set of Dedekind reals.

Now, there are at least two natural ways to define addition on $\mathcal {C}$ :

If $x,y:\mathbb {R}_d$ , one can prove that , and in the antithesis translation they give the usual addition on Dedekind reals:

(9.9)

(9.10)

However, for cuts, and are distinct. In the antithesis translation, with $+$ for $\mathfrak {I}$ -cuts defined using (9.9) and (9.10), we have , but is weaker than $q < x+y$ . One place where this matters is in defining metric spaces.

Definition 9.11. A cut-metric on an $\mathfrak {A}$ -type X is an operation $d:\mathcal {C}^{X\times X}$ with

For any cut-metric, defines a preorder. If d is symmetric, this is already an equality making X a set; otherwise we can symmetrize it as in Section 8. (We can also symmetrize d directly with .) If X is already a set and d a function, the usual metric separation condition $(d(x,y)\circeq 0) \vdash (x\circeq y)$ makes its equality coincide with that obtained in this way.

In particular, if $d(x,y): \mathbb {R}_d$ for all $x,y$ , then the antithesis translation of X is an $\mathfrak {I}$ -quasi-metric space, and an $\mathfrak {I}$ -metric space if we impose symmetry.

Now suppose X is a cut-metric space and we have

and

. As observed intuitionistically in [Reference Richman43], $\mathcal {C}$ is a complete lattice (which $\mathbb {R}_d$ is not, constructivelyFootnote ¹⁷ ); thus we can define the distance from a to B as an infimum:

Rather than defining infima in $\mathfrak {A}$ -posets in general, we simply make this explicit:

Even if each $d(a,b)$ is a Dedekind real, $d(a,B)$ may not be. But the observation of Richman [Reference Richman43] is that if we treat $d(a,B)$ as a cut, then its inequality relations to rational (hence also real) numbers are exactly what we would expect of such a “distance.” In the antithesis translation, these become:

If B is affirmative, $q \le d(a,B)$ becomes Richman’s $\forall b^B. (q \le d(a,b))$ . We also have

At least in the Dedekind-real case, we can then write

to get

whose antithesis translation, when $B,B'$ are affirmative, reduces to Richman’s:

$$ \begin{align*} (d(a,B) \le d(a,B')) \equiv \forall \varepsilon. \forall \smash{b'}^X. ((b'\in B') \to \exists b^X. ((b\in B) \land (d(a,b) < d(a,b') + \varepsilon))). \end{align*} $$

Still following [Reference Richman43], we can define the (directed) Hausdorff distance between two subsets as

However, unlike Richman, we can show:

Proof The proof of the triangle inequality is essentially the same as that of its “upper portion” in [Reference Richman43, Section 6]. We must show if

then

. By definition of

, we have

. Now

and

yield

and

such that

Thus, for any

we get

with

, then from b we get

with

. Hence

, so that

.

In [Reference Richman43, Section 6] Richman notes that the cut-valued Hausdorff distance fails the triangle inequality if addition of cuts is defined by (9.9) and (9.10). He concludes that one should forget the “lower cut” part of the Hausdorff distance. We conclude instead that the relevant addition of cuts is , not (9.9) and (9.10). Indeed, (9.9) and (9.10) are suspect right away, as it is not even clear whether they can be obtained simultaneously as the antithesis translation of any single definition of addition for $\mathfrak {A}$ -cuts.

The other example in [Reference Richman43, Section 6] where cuts seem to have problems can also be resolved with affine logic. Suppose (intuitionistically) A is an abelian group and p a prime with $\bigcap _n p^n A = 0$ , i.e., $(\forall n. \exists c. (a = p^n c)) \vdash _{a\in A} (a= 0)$ . Define

In classical mathematics, this defines an “ultranorm,” i.e., $ |a+b| \le \sup (|a|,|b|).$ Intuitionistically, if we interpret $|a|$ as a cut and $\sup $ as the binary supremum (the union of lower parts and intersection of upper parts), then the upper part of $|a+b| \le \sup (|a|,|b|)$ holds but the lower part can fail.

Our solution is to replace this “additive” binary supremum with a multiplicative one. Returning to affine logic, for cuts $x,y$ we define

Now let A be an abelian $\mathfrak {A}$ -group and

, and define

I claim that then we have

This is again just like the “upper part” proof from [Reference Richman43]: if

and

, then $a \circeq p^n c$ and $b \circeq p^n d$ for some $c,d$ , so that $a+b \circeq p^n(c+d)$ and hence

. So in both cases, it is not that cuts are inadequate, but that the operations on cuts sometimes need to use multiplicative connectives rather than additive ones.

Remark 9.14. We end this section with an example where proof-relevance matters. An $\mathfrak {I}$ -sequence of real (or rational) numbers is Cauchy if

(9.15) $$ \begin{align} \forall \varepsilon. \exists k. \forall nm. (n>k\land m>k \to |x_n-x_m|\le \varepsilon), \end{align} $$

and diverges [Reference Bishop and Bridges10, Section 2.3] if

(9.16) $$ \begin{align} \exists \varepsilon. \forall k. \exists nm. (n>k \land m>k \land |x_n-x_m|>\varepsilon). \end{align} $$

These are formal De Morgan duals, so if we define Cauchy-ness of an $\mathfrak {A}$ -sequence by

(9.17)

then its linear negation is divergence.

However, in the absence of countable choice, it is often better to consider a Cauchy sequence as coming with a function $K_{\varepsilon }$ , and Bishop presumably understands a divergent sequence to come with functions $N_k,M_k$ . But if we write out the assertions of such functions by hand, the corresponding formulas

(9.18) $$ \begin{align}\exists K. \forall \varepsilon. \forall nm. (n>K_{\varepsilon} \land m>K_{\varepsilon} \to |x_n-x_m|\le\varepsilon), \end{align} $$

(9.19) $$ \begin{align}\exists \varepsilon. \exists NM. \forall k. (N_k>k \land M_k > k \land |x_{N_k}-x_{M_k}|>\varepsilon) \end{align}$$

are no longer De Morgan duals. Gödel’s “Dialectica” interpretation [Reference Gödel20, Reference Hofstra23, Reference de Paiva40, Reference de Paiva41] automatically does this sort of “Skolemization,” so that (9.15) and (9.16) would be interpreted as (9.18) and (9.19) respectively; but this doesn’t solve the problem that the two pairs are not each other’s negations.

Instead, we can write (9.15) and (9.16) using the propositions-as-types interpretation into dependent type theory. This gives

(9.20) $$ \begin{align}\textstyle \prod_{\varepsilon} \sum_k \prod_{n,m} (n>k\land m>k \to |x_n-x_m|\le \varepsilon), \end{align}$$

(9.21) $$ \begin{align}\textstyle\sum_{\varepsilon} \prod_k \sum_{n,m} (n>k \land m>k \land |x_n-x_m|>\varepsilon), \end{align}$$

which include the Skolem functions automatically, due to the “type-theoretic axiom of choice” $\prod _{x:A} \sum _{y:B} C(x,y) \cong \sum _{f:A\to B} \prod _{x:A} C(x,f(x))$ . Moreover, (9.20) and (9.21) are still De Morgan duals with respect to $\Sigma $ and $\Pi $ . Therefore, we can obtain them from the antithesis translation of (9.17) applied to the propositions-as-types hyperdoctrine mentioned in Examples 4.1.3.

10 Topology

Finally, we consider point-set topologies. There are many classically equivalent ways to define a topology; first we consider neighborhood relations.

Note that the preorder on $\Omega ^A$ makes sense even if A is only a type, making $\Omega ^A$ into a set.

Definition 10.1. A topology on a type A is a predicate

on $A\times \Omega ^A$ with

Isotony implies each

is a relation on the set $\Omega ^A$ . We define a preorder on A by

, making A into a set as well, such that

is a relation on $A \boxtimes \Omega ^A$ . Moreover, an arbitrary predicate $U:\Omega ^A$ is contained in a smallest relation

, and by definition of equality on A we have

. Thus,

is determined by its behavior on subsets, so we may consider it to be a relation on $A\boxtimes \mathscr {P} A$ . If we instead assume A is given as a set and

as a relation on $A\boxtimes \mathscr {P} A$ , then to ensure that the equality coincides with the one constructed above we must impose the $T_0$ axiom

Now a relation on $A\boxtimes \mathscr {P} A$ is equivalently a function $\mathsf {int} : \mathscr {P} A \to \mathscr {P} A$ , and Definition 10.1 translates into an affine version of an “interior operator”:

1. (i) ,

2. (ii) ,

3. (iii) $\mathsf {int}(A) \circeq A$ ,

4. (iv) ,

5. (v) $\mathsf {int}(\mathsf {int}(U)) \circeq \mathsf {int}(U)$

plus the following form of the $T_0$ axiom:

1. (vi) .

The most interesting of these axioms is (iv), which is a version of the classical

(10.2) $$ \begin{align} \mathsf{int}(U)\cap \mathsf{int}(V) \subseteq \mathsf{int}(U\cap V) \end{align} $$

that uses an additive intersection on the right but a multiplicative one on the left. This may look more surprising than the (equivalent) binary additivity axiom for in Definition 10.1, since in the latter $\boxtimes $ is a logical connective while $\sqcap $ is a set operation. However, the following example suggests that this odd-looking mixture of additive and multiplicative intersections is exactly right:

Example 10.3. Any cut-metric space (Definition 9.11) has a topology defined by

To prove binary additivity, from

we can get $\varepsilon _U$ and $\varepsilon _V$ , and then choose

to prove

. Note that here we need to use both hypotheses at once, so they must be combined with $\boxtimes $ rather than $\sqcap $ . We then have to show that given y with

we have

, i.e., that

. For

we use

and the hypothesis from

, and dually. Note that here we need to use the same hypothesis

in proving both subgoals

and

, so they must be combined with $\sqcap $ rather than $\boxtimes $ .