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:

x = ιyφ(y) =abbr φ(x) & ∀z(φ(z/y) → z=x)

We may read this as follows:

x is identical to the object y which satisfies the condition φ if and only if both x satisfies the condition φ and everything which satisfies the condition φ is identical to x

It will be seen how this abbreviation is employed 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 = ιyφ(y) → φ(x/y)

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

Proof of Equinumerosity Lemma. Assume that PQ, 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 Pa to designate [λz Pz & za], and we use Qb to designate [λz Qz & zb]. We want to show that PaQb. By the definition of equinumerosity, we have to show that there is a functional relation R′ which is one-to-one from the objects falling under Pa onto the objects falling under Qb. 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 functional relation from the objects of Pa to the objects of Qb. But the proof can be given as follows. We show: (A) that R is a functional relation from the objects of Pa to the objects of Qb, and then (B) that R is a one-to-one functional relation from the objects of Pa onto the objects of Qb.

(A) Pick an arbitrary object, say c, such that Pac. We want to show that there is a unique object which falls under Qb and to which c bears R. Since Pac, we know that Pc & ca, by the definition of Pa. 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 ca, it follows by the one-to-one character of R that bd. So we have that Qd and db, which establishes that Qbd. And we have also established that Rcd. So it remains to show that every other object that falls under Qb to which c bears R just is identical to d. So suppose Qbe and Rce. Then by definition of Qb, 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 Qb and to which c bears R.

(B) Pick an arbitrary object, say d, such that Qbd. We want to show that there is a unique object falling under Pa that bears R to d. Since Qbd, we know Qd and db. 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 db, it follows that ac, by the fact that R is a functional relation. Since we now have Pc and ca, we have established that c falls under Pa, and moreover, that Rcd. So it remains to prove that any other object that falls under Pa and which bears R to d just is (identical to) c. But if f, say, falls under Pa and bears R to d, then Pf, by definition of Pa. 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 (xa & yb & 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 functional relation from the objects of Pa onto the objects of Qb. We show (A) that R′ is a functional relation from the objects of Pa to the objects of Qb, and then (B) that R′ is a one-to-one functional relation from the objects of Pa onto the objects of Qb.

(A) To show that R′ is a functional relation from the objects of Pa to the objects of Qb, pick an arbitrary object, say c, such that Pac. Then by definition of Pa, we know that Pc and ca. We need to find an object, say d for which the following three things hold: (i) Qbd, (ii) Rcd, and (iii) ∀w(Qbw & Rcww=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&Raww=d). We now show that (i), (ii) and (iii) hold for d:

  1. Since we know Qd, all we have to do to establish Qbd is to show db. But we know Rad and we are considering the case where ¬Rab. So, by the laws of identity, db.
  2. To show Rcd, we need to establish:

    (ca & db & Rcd) ∨ (c=ιu(Pu & Rub) & d=ιu(Qu&Rau))

    But the conjunctions of the right disjunct are true (by assumption and by definition, respectively). So Rcd.

  3. Suppose Qbe (i.e., Qe and eb) and Rce. We want to show: e=d. Since Rce, then:

    (ca & eb & 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 eb, 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=ιu(Qu& Rau) that e=d, by the definition of d.

Case 2: ¬Rcb. We are under the assumption Pac (i.e., Pc and ca), 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 & Rcww=d). We can now show that (i), (ii) and (iii) hold for d:

  1. Since we know Qd, all we have to do to establish that Qbd is to show db. We know that Rcd and we are considering the case where ¬Rcb. So it follows that d≠=b, by the laws of identity. So Qbd.
  2. To show Rcd, we need to establish:

    (ca & db & Rcd) ∨ (c=ιu(Pu&Rub) & d=ιu(Qu&Rau))

    But the conjuncts of the left disjunct are true, for ca (by assumption), db (we just proved this), and Rcd (by the definition of d). So Rcd.

  3. Suppose Qbe (i.e., Qe and eb) and Rce. We want to show: e=d. Since Rce, then:

    (ca & eb & 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 ca & eb & 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 functional relation from the objects of Pa onto the objects of Qb, pick an arbitrary object, say d, such that Qbd. Then by definition of Qb, we know that Qd and db. We need to find an object, say c, for which the following three things hold: (i) Pac, (ii) Rcd, and (iii) ∀w(Paw & Rwdw=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 & Rwbw=c). We now show that (i), (ii) and (iii) hold for c:

  1. Since we know Pc, all we have to do to establish Pac is to show ca. But we know Rcb, and we are considering the case where ¬Rab. So, by the laws of identity, it follows that ca.
  2. To show Rcd, we need to establish:

    (ca & db & Rcd) ∨ (c=ιu(Pu&Rub) & d=ιu(Qu&Rau))

    But the conjuncts of the right disjunct are true (by definition and by assumption, respectively). So Rcd.

  3. Suppose Paf (i.e., Pf and fa) and Rfd. We want to show: f=c. Since Rfd, then:

    (fa & db & 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 fa, 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 Qbd (i.e., Qd and db), 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 & Rwdw=c). We can now show that (i), (ii), and (iii) hold for c:

  1. Since we know Pc, all we have to do to establish that Pac is to show ca. But we know that Rcd, and we are considering the case in which ¬Rad. So it follows that ca, by the laws of identity. So Pac.
  2. To show Rcd, we need to establish:

    (ca & db & Rcd) ∨ (c=ιu(Pu&Rub) & d=ιu(Qu&Rau))

    But the conjuncts of the left disjunct are true, for ca (we just proved this), db (by assumption), and Rcd (by the definition of c). So Rcd.

  3. Suppose Paf (i.e., Pf and fa) and Rfd. We want to show: f=c. Since Rfd, then:

    (fa & db & 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 fa & db & 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.

Copyright © 2013 by
Edward N. Zalta <zalta@stanford.edu>

Open access to the SEP is made possible by a world-wide funding initiative.
Please Read How You Can Help Keep the Encyclopedia Free