#### Supplement to Frege's Logic, Theorem, and Foundations for Arithmetic

## Proof of Equinumerosity Lemma

In this proof of the Equinumerosity Lemma, we utilize the following abbreviation:

x=ιyφ(y) =_{abbr}∃y[φ(y) & ∀z(φ(z/y) →z=y) &x=y]

We may read this as follows:

xis identical totheobjectywhich satisfies the condition φ =_{df}there exists aysuch that: (a)ysatisfies the condition φ, (b) everything which satisfies the condition φ is identical toy, and (c)xis identical toy

It will be seen how this abbreviation is employed to simplify the definition of new relations. Given this new notation, it is straightforward to show:

Principle of Descriptions:x=ιyφ(y) → φ(x/y)

In other words, if *x* is *the* object *y*
that satisfies the condition φ(*y*), then *x*
satisfies the condition φ. (The proof is a simple exercise.) The
appeal to this principle will be obvious in what follows.

*Proof of Equinumerosity Lemma*. Assume that
*P*≈*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
[λ*z* *Pz* & *z*≠*a*], and
we use *Q*^{−b} to designate
[λ*z* *Qz* & *z*≠*b*]. We
want to show that *P*^{−a}
≈ *Q*^{−b}. By the definition of
equinumerosity, we have to show that there is a relation *R*′
which is a one-to-one function 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 one-to-one function 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 function from the objects
of *P*^{−a} to the objects
of *Q*^{−b}, and then (B) that R is a
one-to-one function 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* & *c*≠*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*≠*a*, it follows by the
one-to-one character of *R* that *b*≠*d*. So
we have that *Qd* and *d*≠*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*≠*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*≠*b*, it follows
that *a*≠*c*, by the functionality of *R*.
Since we now have *Pc* and *c*≠*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 ¬*Rab*. Then we
choose *R*′ to be the relation:

[λ*xy* (*x*≠*a*
& *y*≠*b* & *Rxy*) ∨ (*x* =
*ι**u*(*Pu*&*Rub*)
& *y*=*ι**u*(*Qu*&*Rau*))]

To see that there is such a relation, note that once we replace the
abbreviations *x*=*ι**u*(*Pu*&*Rub*)
and *y*=*ι**u*(*Qu*&*Rau*) by
primitive notation, the matrix of the λ-expression is a formula
of the form φ(*x*,*y*) which can be used in an
instance of the Comprehension Principle for Relations.

Now we want to show that *R*′ is a one-to-one function
from the objects of *P*^{−a} onto the
objects of *Q*^{−b}. We show (A) that
*R*′ is a function from the objects of
*P*^{−a} to the objects
of *Q*^{−b}, and then (B) that *R*′
is a one-to-one function from the objects
of *P*^{−a} onto the objects
of *Q*^{−b}.

(A) To show that *R*′ is a function 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*≠*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)
∀*w*(*Q*^{−b}*w*
& *R*′*cw* → *w*=*d*). We
find such a *d* in each of the following, mutually exclusive
cases:

Case 1:

Rcb. So, since we know that each object falling underQis such that there is a unique object falling underPthat isR-related to it, we know thatc=ιu(Pu&Rub). Then, since we knowRmaps a to a unique object falling underQ, we letdbe that object. That is,dsatisfies the defined conditiond=ιu(Qu&Rau). SoQd,Rad, and ∀w(Qw&Raw→w=d). We now show that (i), (ii) and (iii) hold ford:

- Since we know
Qd, all we have to do to establishQ^{−b}dis to showd≠b. But we knowRadand we are considering the case where ¬Rab. So, by the laws of identity,d≠b.To show

R′cd, we need to establish:(

c≠a&d≠b&Rcd) ∨ (c=ιu(Pu&Rub) &d=ιu(Qu&Rau))But the conjunctions of the right disjunct are true (by assumption and by choice, respectively). So

R′cd.Suppose

Q^{−b}e(i.e.,Qeande≠b) andR′ce. We want to show:e=d. SinceR′ce, then:(

c≠a&e≠b&Rce) ∨ (c=ιu(Pu&Rub) &e=ιu(Qu&Rau))But the left disjunct is impossible (we're considering the case where

Rcb, yet the left disjunct assertsRceande≠b, which together contradict the functionality ofR). So the right disjunct must be true, in which case it follows from the fact thate=ιu(Qu&Rau) thate=d, by the definition ofd.Case 2: ¬

Rcb. We are under the assumptionP^{−a}c(i.e.,Pcandc≠a), and so we know by the definition ofRand the fact thatPcthat there is a unique object which falls underQand to whichcbearsR. Choosedto be this object. SoQd,Rcd, and ∀w(Qw&Rcw→w=d). We can now show that (i), (ii) and (iii) hold ford:

- Since we know
Qd, all we have to do to establish thatQ^{−b}dis to showd≠b. We know thatRcdand we are considering the case where ¬Rcb. So it follows thatd≠=b, by the laws of identity. SoQ^{−b}d.To show

R′cd, we need to establish:(

c≠a&d≠b&Rcd) ∨ (c=ιu(Pu&Rub) &d=ιu(Qu&Rau))But the conjuncts of the left disjunct are true, for

c≠a(by assumption),d≠b(we just proved this), andRcd(by the definition ofd). SoR′cd.Suppose

Q^{−b}e(i.e.,Qeande≠b) andR′ce. We want to show:e=d. SinceR′ce, then:(

c≠a&e≠b&Rce) ∨ (c=ιu(Pu&Rub) &e=ιu(Qu&Rau))But the right disjunct is impossible (we're considering the case where ¬

Rcb, yet the right disjunct assertsc=ιu(Pu&Rub), which impliesRcb, a contradiction). Soc≠a&e≠b&Rce. Since we now know thatQeandRce, we know thate=d, sincedis, by definition, the unique object falling underQto whichcbearsR.

(B) To show that *R*′ is a one-to-one function 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*≠*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)
∀*w*(*P*^{−a}*w*
& *R*′*wd* → *w*=*c*). We
find such a *c* in each of the following, mutually exclusive
cases:

Case 1:

Rad. Sod=ιu(Qu&Rau). Then choosec=ιu(Pu&Rub) (we know there is such an object). SoPc,Rcb, and ∀w(Pw&Rwb→w=c). We now show that (i), (ii) and (iii) hold forc:

- Since we know
Pc, all we have to do to establishP^{−a}cis to showc≠a. But we knowRcb, and we are considering the case where ¬Rab. So, by the laws of identity, it follows thatc≠a.To show

R′cd, we need to establish:(

c≠a&d≠b&Rcd) ∨ (c=ιu(Pu&Rub) &d=ιu(Qu&Rau))But the conjuncts of the right disjunct are true (by choice and by assumption, respectively). So

R′cd.Suppose

P^{−a}f(i.e.,Pfandf≠a) andR′fd. We want to show:f=c. SinceR′fd, then:(

f≠a&d≠b&Rfd) ∨ (f=ιu(Pu&Rub) &d=ιu(Qu&Rau))But the left disjunct is impossible (we're considering the case where

Rad, yet the left disjunct assertsRfdandf≠a, which together contradict the fact thatRis one-to-one). So the right disjunct must be true, in which case it follows from the fact thatf=ιu(Pu&Rub) thatf=c, by the definition ofc.Case 2: ¬

Rad. We are under the assumptionQ^{−b}d(i.e.,Qdandd≠b), and so we know by the definition ofRand the fact thatQdthat there is a unique object which falls underPand which bearsRtod. Choosecto be this object. SoPc,Rcd, and ∀w(Pw&Rwd→w=c). We can now show that (i), (ii), and (iii) hold forc:

- Since we know
Pc, all we have to do to establish thatP^{−a}cis to showc≠a. But we know thatRcd, and we are considering the case in which ¬Rad. So it follows thatc≠a, by the laws of identity. SoP^{−a}c.To show

R′cd, we need to establish:(

c≠a&d≠b&Rcd) ∨ (c=ιu(Pu&Rub) &d=ιu(Qu&Rau))But the conjuncts of the left disjunct are true, for

c≠a(we just proved this),d≠b(by assumption), andRcd(by the definition ofc). SoR′cd.Suppose

P^{−a}f(i.e.,Pfandf≠a) andR′fd. We want to show:f=c. SinceR′fd, then:(

f≠a&d≠b&Rfd) ∨ (f=ιu(Pu&Rub) &d=ιu(Qu&Rau))But the right disjunct is impossible (we're considering the case where ¬

Rad, yet the right disjunct assertsd=ιu(Qu&Rau), which impliesRad, a contradiction). Sof≠a&d≠b&Rfd. Since we now know thatPfandRfd, we know thatf=c, sincecis, by definition, the unique object falling underPwhich bearsRtod.