Supplement to Frege's Theorem and Foundations for Arithmetic

Proof of Fact 6 Concerning the Weak Ancestral

Fact 6 concerning the weak ancestral R+ of R asserts:

Fact 6 (R+):
R*(x,y) → ∃z[R+(x,z) & Rzy]

To prove this, we shall appeal to Fact 3 concerning the ancestral R* of R:

Fact 3 (R*):
[R*(x,y) & ∀u(RxuFu) & Her(F,R)] → Fy,

for any concept F and objects x and y:

Now to prove Fact 6 (R+), assume R*(a,b). We want to show:

z[R+(a,z) & Rzb]

Notice that by λ-Conversion, it suffices to show:

w  ∃z[R+(a,z) & Rzw]]b

Let us use ‘P’ to denote this concept under which (we have to show) b falls. Notice that we could prove Pb by instantiating Fact 3 (R*) to P, a, and b and establishing the antecedent of the result. In other words, by Fact 3 (R*), we know:

[R*(a,b) & ∀u(RauPu) & Her(P,R)] → Pb

So if we can show the conjuncts of the antecedent, we are done. The first conjunct is already established, by hypothesis. So we have to show:

(1)   ∀u(RauPu)
(2)   Her(P,R)

To see what we have to show for (1), we expand our defined notation and simplify by using λ-Conversion. Thus, we have to show:

(1)   ∀u[Rau → ∃z(R+(a,z) & Rzu)]

So assume Rau, to show ∃z(R+(a,z) & Rzu). But it is an immediate consequence of the definition of the weak ancestral R+ that R+ is reflexive. (This is Fact 4 concerning the weak ancestral, in Section 4, "The Weak Ancestral of R".) So we may conjoin and conclude R+(a,a) & Rau. From this, we may infer ∃z(R+(a,z) & Rzu), by existential generalization, which is what we had to show.

To show (2), we have to show that P is hereditary on R. If we expand our defined notation and simplify by using λ-Conversion), then we have to show, for arbitrarily chosen objects x,y:

(2)   Rxy → [∃z(R+(a,z) & Rzx) → ∃z(R+(a,z) & Rzy)]

So assume

(A)   Rxy
(B)   ∃z(R+(a,z) & Rzx)

to show: ∃z(R+(a,z) & Rzy). From (B), we know that there is some object, say d, such that:

R+(a,d) & Rdx

So, by Fact 3 about the weak ancestral (Section 4, "The Weak Ancestral of R"), it follows that R*(a,x), from which it immediately follows that R+(a,x), by definition of R+. So, by conjoining (A), we have:

R+(a,x) & Rxy.

But since x was arbitrarily chosen, it follows that:

z(R+(a,z) & Rzy),

which is what we had to show.

Return to Frege's Theorem and Foundations for Arithmetic

Copyright © 2013 by
Edward N. Zalta <>

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

The SEP would like to congratulate the National Endowment for the Humanities on its 50th anniversary and express our indebtedness for the five generous grants it awarded our project from 1997 to 2007. Readers who have benefited from the SEP are encouraged to examine the NEH’s anniversary page and, if inspired to do so, send a testimonial to