Problem from Session 10: Prove that if mankind will live forever, then there is a woman alive today who will have a daughter who will have a daughter who will have a daughter... for eternity!
Preface
In the field of human genetics, the most recent common ancestor of all living humans in the matrilineal line is termed the Mitochondrial Eve, so termed because the mitochondrial DNA (which is only passed from the mother to her children) of all living humans can be traced back to her. This concept draws attention to the fact that for every person alive today, there is an unbroken chain of mother-daughter relationships that links Mitochondrial Eve to their mother or to themselves, if the person is female. Today, we prove that this unbroken chain can be sustained forever, insofar as humanity survives forever.
Reasonable assumptions
1. No-one develops time-travel for the rest of eternity, so no one gives birth to her own grandmother or the like nonsense.
2. Humans will never attain immortality, hence the need for reproduction.
3. Everyone who will ever live must inherit one set of genes from each parent (one male, one female).
Model
We consider the entirety of humankind living from the present time and indefinitely into the future, ignoring the people who lived in the past, as a graph G. Each person is modelled as a vertex. Two persons are connected by an edge if one of the persons is directly descended (genetically, at least) from the other.
Proof: The matrilineal subset F of G is a forest
We now extract a subset of G containing only the matrilineal lines of descent, and call it the matrilineal graph F. To prove that F is a forest, it is sufficient to prove that F contains no cycles. First, note that we only consider edges that join a mother and daughter, and not those that join fathers to sons or daughters, or those that join mothers to sons. For the sake of simplicity, we can eliminate the male person-vertices from F.
Now suppose F is not a forest. Then, the matrilineal graph will contain a cycle. In this case, there will be a woman who gives birth to a daughter, who in turn gives birth to her granddaughter, and so on, until one of the (grand-)ndaughters eventually gives birth to the first woman. Time-travelling speculation aside, this makes no sense and so we should discount the possibility of a cycle occurring in F. Thus, F is a forest i.e. a graph in which all connected components are trees.
Organising the ladies in F into tiers
Having decided on the nature of the matrilineal graph F, we now try to organise the ladies into tiers, so that the ones who are alive today can be treated apart from those who will be born in the distant future. We sort every woman whose mother is no longer alive today into tier 1, their daughters into tier 2, their granddaughters into tier 3, and so on. All the vertices in F can thus be assigned a tier, as no cycles are present.
Proof: There will be infinite tiers in F
Suppose there will only be a finite number of tiers of women in F. This means that after a number of generations of humankind, there will be no new women in the world. By assumption 2, all the existing women will eventually die, leaving only men. By assumption 3, this means that humankind will die out, because men are incapable of reproduction without women. This contradicts the supposition that mankind will live forever. Therefore, the number of tiers in F is infinite.
Proof: There is a path from any vertex in tier N to a vertex in tier 1 (for all natural numbers N)
We perform a proof by induction on N from N=2. Every woman in tier 2 is descended from at least one woman in tier 1, thus they are connected to tier 1 by a path that consists of one edge. Suppose now that there is a path that connects everyone from tier K to tier 1. As everyone in tier K+1 is descended from at least one woman in tier K, they are connected by a path to tier 1 that consists of the path from tier 1 to their mothers and the edge shared between themselves and their mothers. By induction, there is a path connecting every woman in tier 2 or higher in the graph F to a person in tier 1 for any number of tiers.
No matter how much time passes and how many new generations are born, there will be a path linking a living person to a certain ancestor in tier 1, who is alive today. This shows that the existence of a certain unbroken mother-to-daughter lineage will hold indefinitely.
□!
(22 May 2013, Dorigny in the Switz)
