A Proof of the Schröder-Bernstein Theorem in ACL2
Grant Jurgensen · 2025
Read A Proof of the Schröder-Bernstein Theorem in ACL2 by Grant Jurgensen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19008.txt.
Introduction
Grant Jurgensen verifies a set theory theorem inside a computer proof checker, in a 2025 paper. The Schröder-Bernstein theorem says if each of two sets can be injected into the other, the sets can be matched one-to-one; it is why sizes of infinite sets behave sensibly. Jurgensen formalises a well-known proof in ACL2, a theorem-proving system. The decisive bijection, assembled from chains of the two injections, cannot be computed directly, so the work introduces a theory of chains to define that witness non-computably.
Catalog record
| CREATOR | Grant Jurgensen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-19008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Proof of the Schröder-Bernstein Theorem in ACL2 Grant Jurgensen Abstract The Schröder-Bernstein theorem states that, for any two sets P P and Q Q , if there exists an injection from P P to Q Q and an injection from Q Q to P P , then there must exist a bijection between the two sets. Classically, it follows that the ordering of the cardinal numbers is antisymmetric. We describe a formulation and verification of the Schröder-Bernstein theorem in ACL2 following a well-known proof, introducing a theory of chains to define a non-computable witness. 1 Introduction In this paper we present a formulation and verification of the Schröder-Bernstein theorem in ACL2. To our knowledge, this is the first proof of the theorem in the Boyer-Moore family of theorem provers, although it has been verified in a number of other theorem provers, including Isabelle [ 9 ] , Rocq (formerly Coq) [ 5 ] , Lean [ 2 ] , Metamath [ 8 ] , and Mizar [ 10 ] . This paper is organized as follows. In Section 2 , we outline the mathematical background and the general proof which will serve as the basis for the ACL2 formalization. In Section 3.1 , we describe the formulation of the theorem’s premises in ACL2. In Section 3.2 , we describe our approach to defining function inverses and present a macro to quickly introduce inverses and their essential theorems. In Section 3.3 , we present a theory of chains , mirroring the concept to be defined in the informal proof sketch. Finally, Section 3.4 defines the non-computable bijective function and summarizes the intermediate lemmas and final theorems which conclude the proof of the Schröder-Bernstein theorem. The full proof and surrounding theory can be found in the ACL2 community books under missing . 2 The Informal Proof Given two injective functions f:P\rightarrow Q and g:Q\rightarrow P , the Schröder-Bernstein theorem states there must exist a bijection h:P\rightarrow Q . Before presenting the formalization within ACL2, we begin with a proof sketch based upon [ 4 ] , which in turn closely follows Julius König’s original proof [ 7 ] . 2.1 A Theory of Chains This proof proceeds from a theory of chains . For convenience, let us assume sets P and Q are disjoint 1 1 1 To generalize the argument to arbitrary sets, we need only tag elements reflecting their association with one of the two sets. Indeed, we employ this strategy in the ACL2 formalization. . We define a chain C\subseteq P\cup Q as a set of elements which are mutually reachable via repeated application of f and g , or their inverses. So the element p\in P is a member of the following chain. \{\ldots,\;f^{-1}(g^{-1}(p)),\;g^{-1}(p),\;p,\;f(p),\;g(f(p)),\;\ldots\} Similarly, q\in Q belongs to the chain: \{\ldots,\;g^{-1}(f^{-1}(q)),\;f^{-1}(q),\;q,\;g(q),\;f(g(q)),\;\ldots\} Every chain falls in one of a number of categories: 1. Cyclic chains : After some finite number of steps, the chain cycles back to a previous element. 2. Infinite chains : All acyclic chains are (countably) infinite. Infinite chains all extend infinitely in the “rightward” direction and may be further subdivided into two categories: (a) Non-stoppers : Such chains extend infinitely in the leftward direction in addition to the rightward direction. (b) Stoppers : Such chains do not extend infinitely leftward and may therefore be said to possess an initial element. On such an element, neither f^{-1} nor g^{-1} is defined (i.e., the element is not in the image of f or g ). An ordering on chain elements is implied above which follows the order in which the elements of the two example chains were enumerated. This simple ordering may be more rigorously defined as the reflexive-transitive closure of the relation defined by the following two inference rules. \inference{p\in P}{p\sqsubseteq f(p)}\qquad\inference{q\in Q}{q\sqsubseteq g(q)} This order is neither symmetric nor antisymmetric in general and is therefore a preorder. (On infinite chains, however, the order is antisymmetric and therefore a partial order. On cyclic chains, it is symmetric and therefore an equivalence relation.) Let chain(x) denote the chain to which x belongs. We note that, for arbitrary x,y\in P\cup Q , the equality chain(x)=chain(y) holds if and only if x\sqsubseteq y or y\sqsubseteq x . It follows that the set of chains partition P\cup Q . Note that an initial element is minimal with respect to this ordering. That is, value i is initial if and only if x\sqsubseteq i implies x=i for arbitrary x . This definition is equivalent to the one given above. An initial element may reside either in P or Q . We further subdivide the category of stopper chains, referring to chains with initial elements in P as “ P -stoppers” and those with initial elements in Q as “ Q -stoppers”. Lemma 1 . The initial element of a chain is unique. Proof. This fact follows immediately from the minimality of initial elements. Let x and y be initial within the same chain. As noted above, we have x\sqsubseteq y or y\sqsubseteq x since the two share a chain. Without loss of generality, assume x\sqsubseteq y . Then by the minimality of initial element y , we have x=y . ∎ 2.2 Definition and Proof of the Bijection With the above theory of chains established, we are able to define our bijection. Let stoppers_{Q} denote the set of Q -stoppers. Then we define our proposed bijection h : h(p)=\begin{cases}g^{-1}(p)&\text{ if }chain(p)\in stoppers_{Q}\\ f(p)&\text{ otherwise}\end{cases} The decision to use this particular definition of h is, in part, arbitrary. When chain(p) is cyclic or a non-stopper, either f or g^{-1} are possible definitions. We choose to bias toward the use of f , which will be more convenient in the subsequent ACL2 formalization. We begin with a few prerequisite lemmas before proceeding to establish bijectivity. Lemma 2 . Let p\in P and chain(p)\in stoppers_{Q} . Then p is in the image of g . Proof. By the definition of a Q -stopper, the initial element of chain(p) resides in Q . Since the initial element is unique (Lemma 1 ) and p\notin Q , p must not be initial. Therefore, it is by definition in the image of g . ∎ Lemma 3 . Let q\in Q and chain(q)\notin stoppers_{Q} . Then q is in the image of f . Proof. If chain(q) has an initial element, then the initial element must be in P . Since q\notin P , it is not initial. If chain(q) does not have an initial element, then clearly q is again not initial. By definition then, q is in the image of f . ∎ These lemmas establish when we may safely take the inverse of f and g . Lemma 2 in particular shows that the first case of our bijection h is well-defined. Lemma 4 . Let p\in P . Then chain(h(p))=chain(p) . Proof. Either h(p)=g^{-1}(p) or h(p)=f(p) . By definition, p is in the same chain as f(p) as well as g^{-1}(p) , if it is defined. ∎ Lemma 5 (Injectivity of h ) . Let p_{0},p_{1}\in P , where h(p_{o})=h(p_{1}) . Then p_{0}=p_{1} . Proof. Case 1: h(p_{0}) is in a Q -stopper. By equality, h(p_{1}) is also in a Q