Ancestral relation

In mathematical logic, the ancestral relation (often shortened to ancestral) of a binary relation R is its transitive closure, however defined in a different way, see below.

Ancestral relations make their first appearance in Frege's Begriffsschrift. Frege later employed them in his Grundgesetze as part of his definition of the finite cardinals. Hence the ancestral was a key part of his search for a logicist foundation of arithmetic.

Definition

The numbered propositions below are taken from his Begriffsschrift and recast in contemporary notation.

A property P is called R-hereditary if, whenever x is P and xRy holds, then y is also P:

(Px \land xRy) \rightarrow Py

Frege defined b to be an R-ancestor of a, written aR*b, if b has every R-hereditary property that all objects x such that aRx have:

\mathbf{76:}\ \vdash aR^*b \leftrightarrow \forall F [\forall x (aRx \to Fx) \land \forall x \forall y (Fx \land xRy \to Fy) \to Fb]

The ancestral is a transitive relation:

\mathbf{98:}\ \vdash (aR^*b \land bR^*c) \rightarrow aR^*c

Let the notation I(R) denote that R is functional (Frege calls such relations "many-one"):

\mathbf{115:}\ \vdash I(R) \leftrightarrow \forall x \forall y \forall z [(xRy \land xRz) \rightarrow y=z]

If R is functional, then the ancestral of R is what nowadays is called connected:

\mathbf{133:}\ \vdash (I(R) \land aR^*b \land aR^*c) \rightarrow (bR^*c \lor b=c \lor cR^*b)

Relationship to transitive closure

The Ancestral relation R^* is equal to the transitive closure R^+ of R. Indeed, R^* is transitive (see 98 above), R^* contains R (indeed, if aRb then, of course, b has every R-hereditary property that all objects x such that aRx have, because b is one of them), and finally, R^* is contained in R^+ (indeed, assume aR^*b; take the property Fx to be aR^+x; then the two premises, \forall x (aRx \to Fx) and \forall x \forall y (Fx \land xRy \to Fy), are obviously satisfied; therefore, Fb, which means aR^+b, by our choice of F). See also Boolos's book below, page 8.

Discussion

Principia Mathematica made repeated use of the ancestral, as does Quine's (1951) Mathematical Logic.

However, it is worth noting that the ancestral relation cannot be defined in first-order logic. It is controversial whether second-order logic is really "logic" at all. Quine famously claimed that it was not, despite his reliance upon it for his 1951 book (which largely retells Principia in abbreviated form, for which second-order logic is required to fit its theorems).

See also

References

External links

This article is issued from Wikipedia - version of the Thursday, June 25, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.