Standard array
In mathematical logic, the ancestral relation (often shortened to ancestral) of an arbitrary binary relation R is defined below.
The ancestral makes its first appearance in Frege's Begriffsschrift. Frege later employed it in his Grundgesetze as part of his definition of the natural numbers (actually 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 F is called "R-hereditary" if, whenever x is F and xRy holds, then y is also F:
- (Fx ∧ xRy) → Fy.
Frege then 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:
76: aR*b ↔ ∀F ∀x ∀y [((aRx → Fx) ∧ (Fx ∧ xRy → Fy)) → Fb].
The ancestral is transitive:
98: ⊢ (aR*b ∧ bR*c) → aR*c.
Let the notation I(R) denote that R is functional (Frege calls such relations "many-one"):
115: I(R) ↔ ∀x ∀y ∀z [(xRy ∧ xRz) → y=z],
If R is functional, then the ancestral of R is what nowadays is called connectedTemplate:Clarify:
133: ⊢ (I(R) ∧ aR*b ∧ aR*c) → (bR*c ∨ b=c ∨ cR*b).
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, and following the resolution of Russell's paradox both Frege and Quine largely considered the use of second-order logic a questionable approach. In particular, Quine did not consider second-order logic to be "logic" at all, 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
- Begriffsschrift
- Gottlob Frege
- Transitive closure - The ancestral of a relation is not to be confused with its Reflexive transitive closure, although the notation R* is used for both.
References
- George Boolos, 1998. Logic, Logic, and Logic. Harvard Univ. Press.
- Ivor Grattan-Guinness, 2000. In Search of Mathematical Roots. Princeton Univ. Press.
- Willard Van Orman Quine, 1951 (1940). Mathematical Logic. Harvard Univ. Press. ISBN 0-674-55451-5.