Supplement to Frege's Theorem and Foundations for Arithmetic
Proof of Equinumerosity Lemma
In this proof of the Equinumerosity Lemma, we utilize the following abbreviation, where \(\mathrm{\phi}\) is any formula in which the variable \(y\) may or may not be free and \(\mathrm{\phi}^{\nu}_{\upsilon}\) is the result of replacing the free occurrences of \(\upsilon\) in \(\mathrm{\phi}\) by \(\nu\):
\(x\eqclose \mathit{\iota}y\mathrm{\phi} \eqabbr \mathrm{\phi}\amp \forall z(\mathrm{\phi}^z_y \rightarrow z\eqclose x)\)
We may read this as follows:
\(x\) is identical to the object \(y\) which is such that \(\mathrm{\phi}\) if and only if both \(x\) is such that \(\mathrm{\phi}\) and everything which is such that \(\mathrm{\phi}\) is identical to \(x\).
This abbreviation is employed below to simplify the definition of new relations. Given this new notation, we will use only the following simple consequence of this definition:
Principle of Descriptions:
\(x\eqclose \mathit{\iota} y\mathrm{\phi}\rightarrow \mathrm{\phi}^x_y \)
In other words, if \(x\) is the object \(y\) such that \(\mathrm{\phi} (y)\), then \(x\) is such that \(\mathrm{\phi}\). The use of this principle will be obvious in what follows.
Proof of Equinumerosity Lemma. Assume that \(P\approx Q, Pa\), and \(Qb\). So there is a relation, say \(R\), such that (a) \(R\) maps every object falling under \(P\) to a unique object falling under \(Q\) and (b) for every object falling under \(Q\) there is a unique object falling under \(P\) which is \(R\)-related to it. Now we use \(P^{-a}\) to designate \([\lambda z \, Pz\amp z\neq a]\), and we use \(Q^{-b}\) to designate \([\lambda z \, Qz\amp z\neq b]\). We want to show that \(P^{-a}\approx Q^{-b}\). By the definition of equinumerosity, we have to show that there is a functional relation \(R'\) which is 1-1 from the objects falling under \(P^{-a}\) onto the objects falling under \(Q^{-b}\). We prove this by cases.
Case 1: Suppose \(Rab\). Then we choose \(R'\) to be \(R\) itself. Clearly, \(R\) is then a 1-1 functional relation from the objects of \(P^{-a}\) to the objects of \(Q^{-b}\). But the proof can be given as follows. We show: (A) that \(R\) is a functional relation from the objects of \(P^{-a}\) to the objects of \(Q^{-b}\), and then (B) that \(R\) is a 1-1 functional relation from the objects of \(P^{-a}\) onto the objects of \(Q^{-b}\).
(A) Pick an arbitrary object, say \(c\), such that \(P^{-a}c\). We want to show that there is a unique object which falls under \(Q^{-b}\) and to which \(c\) bears \(R\). Since \(P^{-a}c\), we know that \(Pc\amp c\neq a\), by the definition of \(P^{-a}\). But if \(Pc\), then by our hypothesis that \(R\) is a witness to the equinumerosity of \(P\) and \(Q\), it follows that there is a unique object, say \(d\), such that \(Qd\) and \(Rcd\). But we are considering the case in which \(Rab\) and so from the established facts that \(Rcd\) and \(c\neq a\), it follows by the 1-1 character of \(R\) that \(b\neq d\). So we have that \(Qd\) and \(d\neq b\), which establishes that \(Q^{-b}d\). And we have also established that \(Rcd\). So it remains to show that every other object that falls under \(Q^{-b}\) to which \(c\) bears \(R\) just is identical to \(d\). So suppose \(Q^{-b}e\) and \(Rce\). Then by definition of \(Q^{-b}\), it follows that \(Qe\). But now \(e=d\), for \(d\) is the unique object falling under \(Q\) to which \(c\) bears \(R\). So there is a unique object which falls under \(Q^{-b}\) and to which \(c\) bears \(R\).
(B) Pick an arbitrary object, say \(d\), such that \(Q^{-b}d\). We want to show that there is a unique object falling under \(P^{-a}\)that bears \(R\) to \(d\). Since \(Q^{-b}d\), we know \(Qd\) and \(d\neq b\). From \(Qd\) and the fact that \(R\) witnesses the equinumerosity of \(P\) and \(Q\), we know that there is a unique object, say \(c\), that falls under \(P\) and which bears \(R\) to \(d\). Since we are considering the case in which \(Rab\), and we’ve established \(Rcd\) and \(d\neq b\), it follows that \(a\neq c\), by the fact that \(R\) is a functional relation. Since we now have \(Pc\) and \(c\neq a\), we have established that \(c\) falls under \(P^{-a}\), and moreover, that \(Rcd\). So it remains to prove that any other object that falls under \(P^{-a}\) and which bears \(R\) to \(d\) just is (identical to) \(c\). But if \(f\), say, falls under \(P^{-a}\) and bears \(R\) to \(d\), then \(Pf\), by definition of \(P^{-a}\). But recall that \(c\) is the unique object falling under \(P\) which bears \(R\) to \(d\). So \(f=c\).
Case 2: Suppose \(\neg Rab\). Then we choose \(R’\) to be the relation:
To see that there is such a relation, note that once we replace the abbreviations \(x=\mathit{\iota}u(Pu\amp Rub)\) and \(y=\mathit{\iota}u(Qu\amp Rau)\) by primitive notation, the matrix of the \(\lambda\)-expression is a formula of the form \(\mathrm{\phi}(x,y)\) which can be used in an instance of the Comprehension Principle for Relations.
Now we want to show that \(R’\) is a 1-1 functional relation from the objects of \(P^{-a}\) onto the objects of \(Q^{-b}\). We show (A) that \(R’\) is a functional relation from the objects of \(P^{-a}\) to the objects of \(Q^{-b}\), and then (B) that \(R’\) is a 1-1 functional relation from the objects of \(P^{-a}\) onto the objects of \(Q^{-b}\).
(A) To show that \(R’\) is a functional relation from the objects of \(P^{-a}\) to the objects of \(Q^{-b}\), pick an arbitrary object, say \(c\), such that \(P^{-a}c\). Then by definition of \(P^{-a}\), we know that \(Pc\) and \(c\neq a\). We need to find an object, say \(d\) for which the following three things hold: (i) \(Q^{-b}d\), (ii) \(R’cd\), and (iii) \(\forall w(Q^{-b}w \amp R’cw\rightarrow w=d)\). We find such a \(d\) in each of the following, mutually exclusive subcases:
Subcase 1: \(Rcb\). So, since we know that each object falling under \(Q\) is such that there is a unique object falling under \(P\) that is \(R\)-related to it, we know that \(c= \mathit{\iota}u(Pu\amp Rub)\). Then, since we know R maps \(a\) to a unique object falling under \(Q\), we let \(d\) be that object. That is, \(d\) satisfies the defined condition \(d=\mathit{\iota}u(Qu\amp Rau)\). So \(Qd\), \(Rad\), and \(\forall w(Qw\amp Raw\rightarrow w=d)\). We now show that (i), (ii) and (iii) hold for \(d\):
- Since we know \(Qd\), all we have to do to establish \(Q^{-b}d\) is to show \(d\neq b\). But we know \(Rad\) and we are considering the case where \(\neg Rab\). So, by the laws of identity, \(d\neq b\).
-
To show \(R’cd\), we need to establish:
\[\begin{align*} &(c\neqclose a\amp d\neqclose b\amp Rcd)\ \lor \\ &\quad (c\eqclose \mathit{\iota}u(Pu\amp Rub)\amp d\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the conjunctions of the right disjunct are true (by assumption and by definition, respectively). So \(R'cd\).
-
Suppose \(Q^{-b}e\) (i.e., \(Qe\) and \(e\neq b\)) and \(R'ce\). We want to show: \(e=d\). Since \(R'ce\), then:
\[\begin{align*} &(c\neqclose a\amp e\neqclose b\amp Rce)\ \lor \\ &\quad (c\eqclose \mathit{\iota}u(Pu\amp Rub)\amp e\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the left disjunct is impossible (we’re considering the subcase where \(Rcb\), yet the left disjunct asserts \(Rce\) and \(e\neq b\), which together contradict the fact that \(R\) is a functional relation). So the right disjunct must be true, in which case it follows from the fact that \(e=\mathit{\iota}u(Qu\amp Rau)\) that \(e=d\), by the definition of \(d\).
Subcase 2: \(\neg Rcb\). We are under the assumption \(P^{-a}c\) (i.e., \(Pc\) and \(c\neq a\)), and so we know by the definition of \(R\) and the fact that \(Pc\) that there is a unique object which falls under \(Q\) and to which \(c\) bears \(R\). Choose \(d\) to be this object. So \(Qd\), \(Rcd\), and \(\forall w(Qw\amp Rcw\rightarrow w=d)\). We can now show that (i), (ii) and (iii) hold for \(d\):
- Since we know \(Qd\), all we have to do to establish that \(Q^{-b}d\) is to show \(d\neq b\). We know that \(Rcd\) and we are considering the subcase where \(\neg Rcb\). So it follows that \(d\neqclose b\), by the laws of identity. So \(Q^{-b}d\).
-
To show \(R’cd\), we need to establish:
\[\begin{align*} &(c\neqclose a\amp d\neqclose b\amp Rcd)\ \lor \\ &\quad (c\eqclose \mathit{\iota}u(Pu\amp Rub)\amp d\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the conjuncts of the left disjunct are true, for \(c\neq a\) (by assumption), \(d\neq b\) (we just proved this), and \(Rcd\) (by the definition of \(d\)). So \(R’cd\).
-
Suppose \(Q^{-b}e\) (i.e., \(Qe\) and \(e\neq b)\) and \(R’ce\). We want to show: \(e=d\). Since \(R’ce\), then:
\[\begin{align*} &(c\neqclose a\amp e\neqclose b\amp Rce)\ \lor \\ &\quad (c\eqclose \mathit{\iota}u(Pu\amp Rub)\amp e\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the right disjunct is impossible (we’re considering the subcase where \(\neg Rcb\), yet the right disjunct asserts \(c=\mathit{\iota}u(Pu\amp Rub)\), which implies \(Rcb\), a contradiction). So \(c\neq a\amp e\neq b \amp Rce\). Since we now know that \(Qe\) and \(Rce\), we know that \(e=d\), since \(d\) is, by definition, the unique object falling under \(Q\) to which \(c\) bears \(R\).
(B) To show that \(R’\) is a 1-1 functional relation from the objects of \(P^{-a}\) onto the objects of \(Q^{-b}\), pick an arbitrary object, say \(d\), such that \(Q^{-b}d\). Then by definition of \(Q^{-b}\), we know that \(Qd\) and \(d\neq b\). We need to find an object, say \(c\), for which the following three things hold: (i) \(P^{-a}c\), (ii) \(R’cd\), and (iii) \(\forall w(P^{-a}w\amp R’wd\rightarrow w=c)\). We find such a \(c\) in each of the following, mutually exclusive cases:
Subcase 1: \(Rad\). So \(d=\mathit{\iota}u(Qu\amp Rau)\). Then choose \(c=\mathit{\iota}u(Pu\amp Rub)\) (we know there is such an object). So \(Pc\), \(Rcb\), and \(\forall w(Pw\amp Rwb\rightarrow w=c)\). We now show that (i), (ii) and (iii) hold for \(c\):
- Since we know \(Pc\), all we have to do to establish \(P^{-a}c\) is to show \(c\neq a\). But we know \(Rcb\), and we are considering the case where \(\neg Rab\). So, by the laws of identity, it follows that \(c\neq a\).
-
To show \(R’cd\), we need to establish:
\[\begin{align*} &(c\neqclose a\amp d\neqclose b\amp Rcd)\ \lor \\ &\quad (c\eqclose \mathit{\iota}u(Pu\amp Rub)\amp d\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the conjuncts of the right disjunct are true (by definition and by assumption, respectively). So \(R’cd\).
-
Suppose \(P^{-a}f\) (i.e., \(Pf\) and \(f\neq a)\) and \(R’fd\). We want to show: \(f=c\). Since \(R’fd\), then:
\[\begin{align*} &(f\neqclose a\amp d\neqclose b\amp Rfd)\ \lor \\ &\quad (f\eqclose \mathit{\iota}u(Pu\amp Rub)\amp d\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the left disjunct is impossible (we’re considering the subcase where \(Rad\), yet the left disjunct asserts \(Rfd\) and \(f\neq a\), which together contradict the fact that \(R\) is 1-1). So the right disjunct must be true, in which case it follows from the fact that \(f=\mathit{\iota}u(Pu\amp Rub)\) that \(f=c\), by the definition of \(c\).
Subcase 2: \(\neg Rad\). We are under the assumption \(Q^{-b}d\) (i.e., \(Qd\) and \(d\neq b)\), and so we know by the definition of \(R\) and the fact that \(Qd\) that there is a unique object which falls under \(P\) and which bears \(R\) to \(d\). Choose \(c\) to be this object. So \(Pc\), \(Rcd\), and \(\forall w(Pw\amp Rwd\rightarrow w=c)\). We can now show that (i), (ii), and (iii) hold for \(c\):
- Since we know \(Pc\), all we have to do to establish that \(P^{-a}c\) is to show \(c\neq a\). But we know that \(Rcd\), and we are considering the subcase in which \(\neg Rad\). So it follows that \(c\neq a\), by the laws of identity. So \(P^{-a}c\).
-
To show \(R’cd\), we need to establish:
\[\begin{align*} &(c\neqclose a\amp d\neqclose b\amp Rcd)\ \lor \\ &\quad (c\eqclose \mathit{\iota}u(Pu\amp Rub)\amp d\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the conjuncts of the left disjunct are true, for \(c\neq a\) (we just proved this), \(d\neq b\) (by assumption), and \(Rcd\) (by the definition of \(c\)). So \(R’cd\).
-
Suppose \(P^{-a}f\) (i.e., \(Pf\) and \(f\neq a)\) and \(R’fd\). We want to show: \(f=c\). Since \(R’fd\), then:
\[\begin{align*} &(f\neqclose a\amp d\neqclose b\amp Rfd)\ \lor \\ &\quad (f\eqclose \mathit{\iota}u(Pu\amp Rub)\amp d\eqclose \mathit{\iota}u(Qu\amp Rau)) \end{align*}\]But the right disjunct is impossible (we’re considering the subcase where \(\neg Rad\), yet the right disjunct asserts \(d=\mathit{\iota}u(Qu\amp Rau)\), which implies \(Rad\), a contradiction). So \(f\neq a\amp d\neq b\amp Rfd\). Since we now know that \(Pf\) and \(Rfd\), we know that \(f=c\), since \(c\) is, by definition, the unique object falling under \(P\) which bears \(R\) to \(d\).
