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 <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