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:
x is identical to the object y which satisfies the condition φ =df there exists a y such that: (a) y satisfies the condition φ, (b) everything which satisfies the condition φ is identical to y, and (c) x is identical to y
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−ac. We want to show that there is a unique object which falls under Q−b and to which c bears R. Since P−ac, 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−bd. 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−be 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−bd. We want to show that there is a unique object falling under P−a that bears R to d. Since Q−bd, 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−ac. 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−bd, (ii) R′cd, and (iii) ∀w(Q−bw & 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 under Q is such that there is a unique object falling under P that is R-related to it, we know that c= ιu(Pu&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=ιu(Qu&Rau). So Qd, Rad, and ∀w(Qw&Raw → 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−bd is to show d≠b. But we know Rad and 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−be (i.e., Qe and e≠b) and R′ce. We want to show: e=d. Since R′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 asserts Rce and e≠b, which together contradict the functionality of R). So the right disjunct must be true, in which case it follows from the fact that e=ιu(Qu& Rau) that e=d, by the definition of d.
Case 2: ¬Rcb. We are under the assumption P−ac (i.e., Pc and c≠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 ∀w(Qw & Rcw → 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−bd is to show d≠b. We know that Rcd and we are considering the case where ¬Rcb. So it follows that d≠=b, by the laws of identity. So Q−bd.
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), and Rcd (by the definition of d). So R′cd.
Suppose Q−be (i.e., Qe and e≠b) and R′ce. We want to show: e=d. Since R′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 asserts c=ιu(Pu&Rub), which implies Rcb, a contradiction). So c≠a & e≠b & 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 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−bd. 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−ac, (ii) R′cd, and (iii) ∀w(P−aw & R′wd → w=c). We find such a c in each of the following, mutually exclusive cases:
Case 1: Rad. So d=ιu(Qu&Rau). Then choose c=ιu(Pu&Rub) (we know there is such an object). So Pc, Rcb, and ∀ w(Pw & Rwb → 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−ac is to show c≠a. But we know Rcb, and we are considering the case where ¬Rab. So, by the laws of identity, it follows that c≠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−af (i.e., Pf and f≠a) and R′fd. We want to show: f=c. Since R′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 asserts Rfd and f≠a, which together contradict the fact that R is one-to-one). So the right disjunct must be true, in which case it follows from the fact that f=ιu(Pu&Rub) that f=c, by the definition of c.
Case 2: ¬Rad. We are under the assumption Q−bd (i.e., Qd and d≠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 ∀w(Pw & Rwd → 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−ac is to show c≠a. But we know that Rcd, and we are considering the case in which ¬Rad. So it follows that c≠a, by the laws of identity. So P−ac.
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), and Rcd (by the definition of c). So R′cd.
Suppose P−af (i.e., Pf and f≠a) and R′fd. We want to show: f=c. Since R′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 asserts d=ιu(Qu&Rau), which implies Rad, a contradiction). So f≠a & d≠b & 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.