Proof of Fact 5 Concerning the Weak Ancestral: A Supplement to Frege's Logic, Theorem, and Foundations for Arithmetic

This is a file in the archives of the Stanford Encyclopedia of Philosophy.

Stanford Encyclopedia of Philosophy
Supplement to Frege's Logic, Theorem, and Foundations for Arithmetic

Proof of Fact 5 Concerning the Weak Ancestral

Fact 5 concerning the weak ancestral R⁺ of Rasserts:

Fact 5 (R⁺):
R*(x,y) z[Rzy & R⁺(x,z)]

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

Fact 5 (R*):
[R*(x,y) & u(Rxu Fu) & Her(F,R)] Fy,

for any concept F and objects x and y:

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

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

Notice that by

-Conversion, it suffices to show:

[w z[Rzw & R⁺(a,z)]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 5 (R*) to P, a, and b and establishing the antecedent of the result. In other words, by Fact (R*), we know:

[R*(a,b) & u(Rau Pu) & 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(Rau Pu)
(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(Rzu & R⁺(a,z))]

So assume Rau, to show the consequent of (1). But it is an immediate consequence of the definition of the weak ancestral R⁺ that R⁺ is reflexive. (This is Fact 8 concerning the weak ancestral, in Section 4, "The Weak Ancestral of R".) So we may conjoin and conclude Rau & R⁺(a,a). From this, we may infer consequent of (1), 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:

(2) Rxy [z(Rzx & R⁺(a,z)) z(Rzy & R⁺(a,z))]

So assume

(A) Rxy & z(Rzx & R⁺(a,z))

to show:

z(Rzy & R⁺(a,z)). From the second conjunct of (A), we know that there is some object, say d, such that:

Rdx & R⁺(a,d); i.e.,
R⁺(a,d) & Rdx

So, by Fact 2 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 appealing to the first conjunct of (A), we have:

Rxy & R⁺(a,x),

from which it follows that:

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

which is what we had to show.

Return to Frege's Logic, Theorem, and Foundations for Arithmetic

First published: June 10, 1998
Content last modified: May 9, 2002

Stanford Encyclopedia of Philosophy Supplement to Frege's Logic, Theorem, and Foundations for Arithmetic

Proof of Fact 5 Concerning the Weak Ancestral

Stanford Encyclopedia of Philosophy
Supplement to Frege's Logic, Theorem, and Foundations for Arithmetic