Month: December 2024

Corrections to the Proof of Cantor’s Theorem

/ erdosfan / Leave a comment

I was reading my absolute favorite book on mathematics, Mathematical Problems and Proofs, and it mentions Cantor’s Theorem, that the cardinality of a set is always less than the cardinality of its power set. So for example, the cardinality of |\{1,2\}| = 2, which is less than |\{ \{\emptyset \}, \{1\}, \{2\}, \{1,2\}\}| = 4. There is however no proof in that book of the general case, and instead only a proof of the finite case, expressed as a counting argument. I looked up proofs, and all the proofs I could find seem to have the same hole, which I’ll discuss.

Let A be a set, and let P(A) denote the power set of A, i.e., the set of all of its subsets. Now assume that |A| \geq |P(A)|. That is, we are assuming arguendo that the cardinality of A is not less than the cardinality of its power set, in contradiction to Cantor’s Theorem. It follows that there must be some function \psi: A \rightarrow P(A) such that \psi is surjective, which means that all elements of P(A) are mapped to by \psi, and such a function must exist, because we have assumed that |A| \geq |P(A)|. That is, because |A| \geq |P(A)|, there are enough elements in A to map to every element in P(A).

Now the next step of the proof (at least the few versions I saw this morning) all universally define the set B below, without addressing the possibility that the set is empty, though it’s possible the original proof addresses this case. My issue with this, is that there doesn’t seem to be any difference between an empty set, and a set that is provably non-existent. As such, I don’t think empty sets should be used as the basis of a proof, unless the proof follows only from the non-existence of the set, and other true theorems, true axioms, or additional assumptions (in the case of a line of reasoning being considered arguendo). In this case, proving the set in question is non-empty, changes the scope of the proof, in that it only applies to sets with a cardinality of two or greater. Most importantly, consistent with this, the accepted proof fails in the case of the power set of the empty set, and in the case of the power set of a singleton, because of this hole. This is very serious, the proof is literally wrong, and fails in two cases, that are plainly intended to be covered by the proof.

The Modified Proof

Specifically, proofs of Cantor’s theorem define B = \{x \in A | x \notin \psi(x)\}. That is, because we know \psi (defined above) must exist, we know that we can define B, using \psi. However, it’s possible that B is empty, since there might not be any such x \in A. That said, a simple additional step will prove that we can always define \hat{\psi}, which will produce a non-empty set \hat{B}.

Assume that B is empty and that |A| \geq 2. Because A \subset P(A), there must be x,y \in P(A), such that x \neq y , and x,y \in A. Because \psi is surjective, there must be a,b such that \psi(a) = x and \psi(b) = y. If a \notin x or b \notin y, then B is non-empty. As such, assume that a \in x and b \in y. Now define \hat{\psi}, such that \hat{\psi}(x) = y and \hat{\psi}(y) = x , but otherwise \hat{\psi}(z) = \psi(z) for z \notin \{x,y\}. If x and y are both singletons, then x \notin y and y \notin x. If either is not a singleton (or both are not singletons), then it must be the case that either x \notin y or y \notin x, or both. This implies that \hat{B} is not empty. Because this can be done for any surjective function \psi, we are always guaranteed a non-empty set \hat{B}. Note that \hat{\psi} is still surjective.

Now we can complete the proof as it is usually stated. Because \hat{\psi} is surjective, there must be some x_0 such that \hat{\psi}(x_0) = \hat{B} \subset P(A). It must be the case that either x_0 \in \hat{B} or x_0 \notin \hat{B}. If x_0 \in \hat{B}, then x_0 fails the criteria for inclusion in \hat{B}, namely \hat{B} = \{x \in A | x \notin \hat{\psi}(x)\}, since by definition, \hat{\psi}(x_0) = \hat{B}. If x_0 \notin \hat{B}, then x_0 satisfies the criteria for inclusion in \hat{B}. In both cases, we have a contradiction. The assumption that |A| \geq |P(A)| implies the existence of \psi, which in turn implies the existence of \hat{\psi} and \hat{B}, which leads to a contradiction. In order to resolve this contradiction, we must therefore assume instead that |A| < |P(A)|, which completes the proof.

The Case of the Empty Set

Now assume that A = \emptyset, and let’s apply the proof above. Generally speaking, we would assume that the power set of the empty set contains one element, namely a set that contains the empty set as a singleton, represented as P(A) = \{\{\emptyset\}\}. Assuming we can even define \psi in this case, it must be that \psi(\emptyset) = \{\emptyset\}. Because \emptyset \in \{\emptyset\}, it must be the case that B = \emptyset. However, if we want A \neq P(A), it must be the case that \emptyset \neq \{\emptyset\}, even though \emptyset \in \{\emptyset\}. Therefore, \emptyset \notin P(A), and instead, \emptyset \in \{\emptyset\}, and as a result, the proof fails in the case of |A| = 0 since B = \emptyset \notin P(A). That is, the accepted proof assumes B is contained in the power set, which is just not true in this case, suggesting that there really are problems deriving theorems from empty sets.

The Case of a Singleton

Now assume that A = \{x\}, and let’s apply the proof above. The power set of a singleton is generally defined as P(A) = \{ \{\emptyset\}, \{x\}\}. Because the accepted proof does not explicitly define \psi, we are free to define \psi(x) = \{x\}. Because x \in \{x\}, B = \emptyset. As noted above, \emptyset \neq \{\emptyset\}, and therefore, B \notin P(A). Again, the accepted proof fails.

Because the accepted proof fails in two cases where B is empty, my axiom above requiring sets to be non-empty in order to derive theorems, must be true. Nothing else above within the proof is subject to meaningful criticism. Again, I have no idea whether Cantor’s original proof addressed these points, but it’s surprising that no one has bothered to apply these proofs to the case of the empty set and a singleton, which would make it clear it doesn’t work.

A thought on Existence versus Substance

/ erdosfan / Leave a comment

I’ve spent a significant amount of time thinking about how it is that the mind can consider objects that don’t seem to be obviously physically real. For example, Cantor’s cardinals don’t have any convenient corporeal form, yet there are theorems that rigorously govern their notion, that we can discern from other statements that are false about that very same topic. This, in my opinion, leads to the question of how it is that the mind, which science says should be entirely physical, can consider objects that don’t appear to be a part of 3-space, and derive apparently true statements about those objects. I think I have a sensible answer, which is that all true statements govern reality, and in that sense, they exist, even if they don’t have a location. For example, the rules of combinatorics govern at all points in space in time, and therefore exist in that sense. However, the rules of combinatorics are not embedded in some cosmic ledger, and instead, exist through the effects that they have on objects. We’re still in a bit of trouble with Cantor, because nothing within the human purview is infinite. So then we’re resigned to considering ideas that govern other ideas, under the assumption those latter ideas exist, and I’m fine with that, and perhaps that’s the right answer. But all of this points to the possibility that the human mind, distinct from the brain, is similarly without a location, and instead governs the behavior of a sentient person, including their brain. Perhaps this is a leap, but we need something to explain the fact that the mind can consider objects outside 3-space that have no finite expression, that we instead understand through reference. That is, when I write \aleph_0, I’m not encoding or representing anything, and I am instead referencing something that is in your memory as a reader, thereby conjuring a concept with which you’re already familiar, that cannot be expressed physically in finite time.

On the origins of modern human mtDNA

/ erdosfan / Leave a comment

In my paper, A New Model of Computational Genomics [1], I introduce a simple test for ancestry that cannot credibly be argued with. The argument is as follows: assume that we begin with genome A in location a, and that three groups of individuals with genome A all begin in location a. Now assume that two of those groups go to different locations, specifically, that one group goes to location b and the other group goes to location c. Because mtDNA is so stable, it could be the case that even over significant amounts of time, the populations in locations b and c, still have genome A, with basically no mutations. If however, any mutations occur, it cannot credibly be the case that genomes in location b (genome B) and location c (genome C) develop even more bases in common with each other. This becomes increasingly unlikely as a function of the number of new matching genomes between B and C, and is governed by the binomial distribution. As a consequence, if A is the common ancestor of genomes B and C, it must be the case that |AB| < |BC| and |AC| < |BC|, where |xy| denotes the number of matching bases between genomes x and y. That is, A must have more bases in common with B and C, than B and C have in common with each other, since B and C independently mutated away from genome A.

Applying this test, we find that the Old Kingdom Ancient Egyptians are the common ancestors of basically all Northern Europeans, many Africans, Asians, and in particular, South East Asians. I’ve also noted repeatedly that the Old Kingdom Ancient Egyptians appear to be Asian, which, superficially, makes no sense. Finally, I’ve noted that Heidelbergensis plainly evolved into Phoenicians, and then the Old Kingdom Ancient Egyptians. Phoenicians appear in Asia on the maternal line, in particular in Sri Lanka.

Putting it all together, tonight I tested which population is most likely to be the ancestor of the Old Kingdom Ancient Egyptians, and the clear answer is the Sri Lankans. The attached code runs the test, and produces a normalized score. The Sri Lankans scored 17.36, and the next best answer was the Vedda Aboriginals (also in Sri Lanka), with a score of 8.3064. The plain implication is that the mutation from the Phoenician maternal line, into the Old Kingdom Ancient Egyptian maternal line took place in Sri Lanka, or somewhere very close.

This completes the history of mankind, with the people of Cameroon the likely source population of all of mankind (including the Denisovans, Heidelbergensis, and Neanderthals), Heidelbergensis then evolving into the Phoenicians, the Phoenicians traveling to Asia, there evolving into the Old Kingdom Ancient Egyptian maternal line, who then migrated back to North East Africa, forming the cradle of modern human mtDNA all over the world, suggesting they were even more successful as a people than current history suggests.

Single Genome Anc TestDownload