Cantor's diagonal argument Assume an infinite list L of sequences si, where each si is an infinite sequence of characters from the set {0, 1}. L is complete since it contains all possible combinations of 0 and 1. A random listing begins as s1 = 001010... s2 = 111000... s3 = 010111... s4 = 110101... s5 = 011101... s6 = 010101... A partial sequence s0 is formed from the diagonal elements by applying the rule, if 0 then 1 else 0, to each position from left to right. The diagonal elements 010101 are transformed to s0 = 101010 which is not included in the portion of L shown. Cantor concludes: 1. since s0 differs at the intersection of the diagonal with each si in the list L by construction, s0 is not included in the list. 2. If L has a one to one relation to the set of integers N, then L plus s0 is greater than N. Statement 1 is false since only 6 of 64 possible combinations have been compared. The partial sequence s0 is different from some of the sequences in L but not all. In L, there are an infinite number of sequences prefixed with 101010, 1010100... thru 1010101..., which have not been compared. Comparison of either subset, and swapping characters will still leave a match for s0. The sequence s0 remains incomplete since at each step, there are more comparisons to do than have been done. Statement 2 dependent on statement 1 is therefore false. Comments: The diagonal method is very redundant when using a random listing. After s1 any s prefixed with 0 can be skipped since they already differ in one position. After s2 any s prefixed with 10 can be skipped since they already differ in two positions. The goal is to compare the next s that matches s0, then swap characters. A more efficient method is L as an ordered list beginning with subsets L0 and L1, then L00, L01, L10, L11, etc. A pattern will emerge showing s0 converging to a specific limit, equivalent to forming an element of L using a random binary selection process. Please Register or Log in to view the hidden image!
That's provably false, if by "list" you mean a mapping from the set of natural numbers 1, 2, 3, ... to the set of binary sequences. That's not what Cantor concludes. It's not even true, since adding one to an infinite cardinal does not change its cardinality. Consider the set of odd numbers 1, 3, 5, 7, ... This set has the same cardinality as the set of natural numbers via the bijection n -> 2n - 1. If we add in the number 2, it does not change the cardinality of the set. If we add in all the rest of the even numbers, it still doesn't change the cardinality. What Cantor concludes is that the assumption that all the binary sequences were listed, must in fact be false. And since L was arbitrary, no list can possibly contain all the binary sequences. Therefore there can be no one-to-one correspondence between the natural numbers and the set of binary sequences. The two collections must have different cardinality. It's easy to show that the set of all subsets of the natural numbers is in one-to-one correspondence with the set of all binary sequences. (Just consider the 1's as selecting a particular subset of the digit positions). And it turns out to be true in general that the collection of subsets of a set can never be in one-to-one correspondence with the set itself. This gives us an endless hierarchy of transfinite cardinals, none of them in bijective correspondence with any of the others. The rest of your post was not understandable to me. But if I'm understanding your \(L_{00}\)'s correctly, where is \(L_{0101010101010101010...}\) in your scheme? It's a common error to show that you can form a bijection between the natural numbers and the set of finite binary sequences. That's perfectly correct. But you are leaving out a lot of sequences, namely the ones that can't be truncated.
You misunderstand some of the finer points. What is to be proved: For any set, R, there is no way to map \(R\) as an onto relation to \(2^R = \left\{ 0,1 \right\}^R\), the set of all functions from R to the set \( \left\{ 0,1 \right\}\). All that is needed of R to qualify is that R has to be a concrete set. The positive integers are but one example. Any ordinal number qualifies. So does any subset of the ordinal numbers. Thus if we prove this, then we prove there is no way to map \(\mathbb{N}\) as an onto relation to \(2^{\mathbb{N}} = \left\{ 0,1 \right\}^{\mathbb{N}}\). It's particularly nice to think of the integers because they have a natural order, but we don't need make use of the property of listing them. If \(R = \mathbb{N}\), then \(2^R \) is the set of all infinite sequences of binary digits, but we don't make use of that assumption. Proof: Proof follows by contradiction arising from the single assumption that there is at least one way to map \(R\) as an onto relation to \(\left\{ 0,1 \right\}^R\). At this level we assume \(\exists L, \quad L : R { {\textstyle{\:} } \atop{ \textstyle{ \longrightarrow }\atop{\textstyle{}^{\mbox{onto}}}} } \left\{ 0,1 \right\}^R \). We have assumed that L is a onto relationship between \(R\) and \(\left\{ 0,1 \right\}^R\). Thus, non-controversially, \(\forall n \in R \quad s_n \equiv L(n) \in \left\{ 0,1 \right\}^R\) and \(\forall n,m \in R, \quad s_n(m) \equiv L(n)(m) \in \left\{ 0,1 \right\} \). That's non-controversial since that's satisfied trivially by \(L(n)(m) = 0\) and many other mappings, including useful ones (in the case \(R = \mathbb{N}\)) that are equivalent to binary representation of the positive integers. We don't care about the particulars, only that the relationship exists and is onto. But because of the controversial onto property, \(\forall z \in \left\{ 0,1 \right\}^R, \quad \forall n \in R, \quad s_n \equiv L(n) = z\). That's controversial since if R is finite, say a set of size 3, it's saying every element of set \(2^R\), a set of size 8, has a corresponding element in R given by the mapping L. That's crazy for finite sets, and Cantor wanted to prove it was crazy for infinite sets as well. Cantor's problem was to prove that that is impossible, given that he doesn't know anything more about R or L. So Cantor creates a special \(z_L\). \(\forall m \in R, \quad z_L(m) = 1 - s_m(m) = 1 - L(m)(m)\). Then \(z_L \in \left\{ 0,1 \right\}^R\) because for every positive element of R called m, \(z_L(m)\) is either 0 or 1. So if L exists, \(z_L\) is well-defined. But \(\not\exists n \in R \quad s_n \equiv L(n) = z_L\). To prove this, Cantor needs a second layer of proof-by-contradiction. Because, at this second level, we assume such a element of R, n, exists, then \(L(n) = z_L\). By the definition of equivalence of sequences (or mappings, or functions) then this means \(\forall k \in R, L(n)(k) = z(k)\). So \(L(n)(n) = z_L(n)\). But by the definition of z, \(1 - L(n)(n) = z_L(n)\). So \(1-L(n)(n) = L(n)(n)\) which contradicts the assumption that \(L(n)(n) \in \left\{ 0,1 \right\} \). Because there is no such n in R such that \(L(n)\) is the same as \(z_L\) which is an element of the set of all mappings from R to \(\left\{ 0, 1 \right\}\), then it follows that L cannot be the onto mapping as assumed. Thus \(\not\exists L, \quad L : R { {\textstyle{\:} } \atop{ \textstyle{ \longrightarrow }\atop{\textstyle{}^{\mbox{onto}}}} } \left\{ 0,1 \right\}^R\). QED. Thus \(2^{\omega}\) has a strictly greater cardinality than \(\omega\). This is the key sticking point. It's not enough to say L is infinite therefore it contains all possible combinations. You have to assume its properties. Noone said L had to be random. And actually it doesn't need to be a listing. R can be any set, even one where we don't know how to give them all in sequence, like the real numbers. Or rather, since L cannot be an onto relationship between N and \(2^N\), as was assumed, then \(2^N\) has a strictly larger cardinality than N. You only need to check one -- the one that makes sense to compare is the entry of L which is claimed matches. That entry corresponds to an element of R and that element of R is also the place where s0 must not match L's entry. So your conclusion that statement 1 is false rests on a fundamental misunderstanding of the proof. s0 (or \(z_L\) in my proof) is in no way a partial sequence. That claim rests perhaps on your assumption of randomness, but that is not part of Cantor's proof. I've already corrected the difference between your statement 2 and Cantor's argument. As far as cardinality matters \(1 + \omega\) does not have a different cardinality than \(\omega\). This exercise was about comparing \(2^\omega\) and \(\omega\). None of that matters. Neither is "efficiency" at stake. Neither is there a "limit" at work here. // Edit -- I'm done editing. // Edit -- OK, Really done.
I think the diagonal argument might lead some to think it's related to a way to arrange or order binary strings, when it's really about showing that you can always construct a string which isn't in the list because it differs from all the list entries by one bit, no matter how the list is arranged. But let's entertain the idea that there is a way to arrange binary strings which are infinite in length, rather than any old way, what's the rule then? Does arranging them amount to enumerating them, and if they can't be arranged according to some rule, does that prove you can't count them either?
"Enumerating" means putting into bijection with the natural numbers. So only countable sets can ever be enumerated, by definition. But what's interesting is that some uncountable sets can be well-ordered, which is the next best thing to enumerating them. A totally ordered set is well-ordered, by definition, if every nonempty subset has a least member. The natural numbers (with the usual order '<') are well-ordered. The integers aren't, since the set of negative integers is nonempty but has no smallest member. It's easy to well-order any countable set, even one that's not usually well-ordered. We just biject it to the natural numbers and use the order of the natural numbers. So the integers with the usual order are not well-ordered; but they can be well-ordered as 0, -1, 1, -2, 2, -3, 3, -4, 4, ... Now what about uncountable sets? If you assume the Axiom of Choice, then any set whatsoever can be well-ordered. That means, for example, that it's possible to arrange the real numbers (and equivalently, the set of all binary sequences) in a well-order. A first one, a second one, a third one, dot dot dot long past the natural numbers to the very last real number (* see my ps below). This is counterintuitive; but before objecting to the Axiom of Choice (AC), one must realize that assuming the negation of AC is problematic too. For example if AC is false, then there's a vector space that has no basis. That's a bad thing. So mathematicians generally accept AC, accept that we can well-order the reals, and don't worry too much about the fact that it's impossible to ever imagine or visualize such a well order. It can be proven in logic that a well-order of the real numbers could never be definable. You can't write it down or explain it or characterize it in symbols. You can only prove that it exists, given AC. So if we don't use AC, could there be an uncountable well-ordered set? The answer is yes. This is the first uncountable ordinal that I mentioned in passing in the other thread. The Wiki article isn't particularly helpful, but here it is. http://en.wikipedia.org/wiki/First_uncountable_ordinal To sum up, yes it is possible using AC to well-order the set of binary sequences. However any such well-order cannot be expressed or visualized. And there is some uncountable set that can be well-ordered even in the absence of AC. (ps) I didn't want to give the impression that every well-order is one element directly after another like the natural numbers. Consider the well-order on the naturals that looks like this: 1, 2, 3, 4, 5, 7, 8,..., 2, 4, 6, 8, 10,... in other words all the odds and then all the evens. You can convince yourself that this is a well-order (every nonempty subset has a least element). However, not every element has an immediate predecessor. In this case 2 has no immediate predecessor. That's how we can get ordinals that are larger than the usual order type of the naturals. If we call the usual order type of the natural numbers \(\omega\) (lower-case omega), you can see that the above odd/even ordering is one copy of \(\omega\) followed by another. We call this \(\omega + \omega\) or \(2 \omega\). In this way we could build up \(n \omega\) and even \(\omega * \omega = \omega^2\), then \(\omega^3\), etc. These are all countable ordinals, different ways of ordering the natural numbers. The countable ordinals are a very strange mathematical object, very hard to get a mental picture of. Let alone the uncountable ordinals. Ordinals are a whole different (but strongly related) class of transfinite numbers than the cardinals. Cardinals tell you "how many," and ordinals tell you what order the elements are in. By the way, ordinal numbers DO have the property that if you add one, they get bigger!! So you'll like them Please Register or Log in to view the hidden image! For example suppose we take the natural numbers 1, 2, 3, ..., which has order-type \(\omega\), and we add one more element. The element traditionally used for this is \(\omega\) itself; so we have a new countable (same cardinality!) set that looks like this: 1, 2, 3, 4, 5, 6, ..., \(\omega\). This is a well-ordered set, but it has a different order-type than the natural numbers. For example, \(\omega\) is the largest element; and the natural numbers have no largest element. We call this order type \(\omega + 1\). It's a different ordinal than \(\omega\). So the ordinals satisfy your intuition that adding one makes them bigger. But adding 1 to an infinite cardinal does not make it bigger. However what if I add \(\omega\) at the begining, like this: \(\omega\), 1, 2, 3, 4, 5, ... You can see that this is the exact same order-type as \(\omega\). There's an order-preserving bijection that sends \(\omega\) to 1, 1 to 2, 2 to 3, ... so that this is really the same well-order. Putting a new element at the beginning of the natural numbers doesn't change the order type; but putting it at the end does. So \(\omega + 1 \neq 1 + \omega\). Ordinal addition is not commutative. Can't have everything.
I think this is connected to Turing's proof of the halting problem. Which restated a little, says that you can't decide if a given Turing machine will output some real number (i.e. halt), you can't guarantee either, that you can distinguish the output of one machine from another and find a diagonal number because that's equivalent to "solving" the halting problem (which is impossible). Is this any insight into the Axiom of Choice (you have to choose a set of Turing machines from all of them)?
I'm afraid I never studied computability theory. My understanding is that Turing's proof and Cantor's diagonal argument are related, essentially the same argument in disguise. I don't think they're related to the Axiom of Choice (AC). Neither Turing's nor Cantor's result requires Choice. I also don't think that they are related to the problem of definability of sets. That's a different area of study as I understand it. I did want to mention (off topic from your comment) that this is the point of departure for the constructivists. A mainstream mathematician says that there is a well-order of the reals but that we can never write it down or compute it or describe it. A constructivist says that if we can't construct or describe something, we can hardly say that it exists. Constructivism fell out of favor in mainstream math in the second half of the twentieth century. But there's renewed interest in it, driven in part by advances in computer science. So who knows how people will feel about these things in thirty or forty years.
That isn't, somehow, what I actually meant to say which is, given a Turing machine you can decide (write a program that decides) if it will halt and output a real number, even what that number is. What you can't do is write a program that tells you if n Turing machines will halt with n different real numbers for any n. So you can't define a well-ordered set of real numbers with Turing machines, or according to you, you can't at all.
From the current Wiki page for "Cantor's diagonal argument": "An infinite set may have the same cardinality as a proper subset of itself, as the depicted bijection f(x)=2x from the natural to the even numbers demonstrates." This is accompanied by a graphic showing the mapping (with X and Y replaced by N and E) N{1, 2, 3, 4, 5, ... x, ...} to E{2, 4, 6, 8, 10, ... 2x, ...} The usual concluding statement is "there are as many even integers as integers" , although it's missing from this page. (It depends on who was editing at that time!) Statistics does not agree with that conclusion. In 100 samples of 100 random integers, the even represent 50% of the population. If D is the set of odd numbers, and N=D U E, then N > E. This seems confusing.
Excellent points. Let me see if I can put all this into its proper context. I've written yet another long-assed post so if there's anything I can clear up, please ask. [Here's the tl;dr: "Same number of elements" is just a figure of speech. All we really mean is that there exists a bijection between two sets. If there is, we say they have the same number of elements; but that phrase has no actual meaning. It's a shorthand for "there exists a bijection." There are also other ways of analyzing infinite sets that are closer to intuition. We can make sense of the frequency of the even numbers in the integers being 1/2; or one interval being twice as long as another.] There is no question that the set of positive integers {1,2,3,...} can be put into one-to-one correspondence with a proper subset of itself. Galileo noted this in 1638. http://en.wikipedia.org/wiki/Galileo's_paradox. I have also read that this phenomenon was noted much earlier, by non-Western mathematicians. I couldn't find a link, but it should be noted that Galileo has this fact named after him but he was likely not the first person to think of it. It's a very old observation. We just write down all the positive integers: 1 2 3 4 5 ... and all the even integers 2 4 6 8 10 ... and it's clear that we could correspond these two sets pairwise vertically: 1 <-> 2, 2 <-> 4, etc. So there is a one-to-one correspondence between the positive integers and one of its proper subsets, namely the even integers. In set theory, this property is taken as the very definition of an infinite set. If a set can be put into bijection (another word for one-to-one correspondence) with a proper subset of itself, then we call the set infinite. This definition was proposed in 1888 by a mathematician named Richard Dedekind, so we call a set that has this property, Dedekind infinite. http://en.wikipedia.org/wiki/Dedekind-infinite_set Note that there is no reference to any notion of something being "unlimited," or anything of the sort. Every since 1888 we have a very precise and mathematically accepted notion of what it means for a set to be infinite; and this is the definition that should be used in scientific discussions. Note also that this is the definition of mathematical infinity. It may or may not be your idea of the philosophical infinity. It's not God. It's not the Alpha and the Omega and the Everything of the Everything of our mystical dreams. It's only a technical definition that applies to mathematical objects. If a set admits a bijection to one of its proper subsets ... we call that set infinite. Otherwise we call it finite. That's all it means. Now with that understood, we often casually say, "The positive integers and the even positive integers have the same number of elements." Whenever a mathematician says that, she is thinking in the back of her mind: "There is a bijection between the two sets." That's it. That's all it means. It's a casual figure of speech ... if two sets can be bijected, we say they have "the same number of elements." But this statement should be taken very loosely! It has NOTHING to do with the two infinite sets having the same number of elements -- because we don't even know what that would mean! No. Rather, we SAY that "X and Y have the same number of elements" exactly when there happens to be a bijection between X and Y. That's it. "Same number of elements" is a definition, not a fact. Does that make sense? Please tell me if my argument was sufficiently clear to this point. It's very simple. We are not CLAIMING that X and Y have "the same number of elements." We don't even know what that means. Rather, we SAY that X and Y have the same number elements if there happens to be a bijection between them. That's all it means. In math, things only mean what we say they mean; and they mean nothing else. That's an excellent point and a great example. We can see that as n gets arbitrarily large, the percentage of positive integers that are even tends to the limit 1/2. That's yet another way of talking about infinite sets called asymptotic density. http://en.wikipedia.org/wiki/Natural_density The article is a little technical but the main point is that you're right. We have cardinality, which is one way of analyzing infinite sets; and we have asymptotic density, which is another. Here's another interesting example. Using the same trick of mapping a number x to the number 2x, we can prove that there are as many real numbers in the unit interval [0,1] as there are in the interval [0,2]. So even though the second set is clearly "twice as large" as the other, they have the same cardinality. There's a bijection, end of story. But there's an area of math called Measure theory in which the measure of [0,1] is 1, and the measure of [0,2] is 2, just like we were taught in high school. So measure is yet another way to analyze infinite sets. So the even numbers have the same cardinality as all of the integers. But their asymptotic density is 1/2. Another good point. If I add a set with cardinality \(\kappa\) (Greek letter lower-case kappa is traditional for cardinals) to another set with cardinality \(\kappa\), the resulting set has cardinality \(\kappa\). That's the kind of thing they make you prove when you're an undergrad math major. So yes, the set of odds plus the set of evens is no bigger (in terms of cardinality) than either set alone. However the set of integers has asymptotic density one, of course; and the evens only have asymptotic density 1/2. In our other example using the real numbers, if we combine the intervals [0,1] and [1,2], the resulting set has exactly the same cardinality as either of the two intervals alone. But the measure of the combined interval is indeed 2, while each of the two intervals has measure 1. So measures are additive. (In fact that's a necessary property of measures.) http://en.wikipedia.org/wiki/Measure_(mathematics) Mathematicians have many ways to analyze infinite sets. But the question of "how many elements" is answered by the theory of cardinality; which admittedly is not a very precise instrument. It doesn't distinguish between the integers and the even integers. You're right about that. It is what it is. The idea's barely 140 years old, maybe someone will find something more clever in the future. It is confusing. Humans have been wondering about infinity for thousands of years ... and only a moment ago in the scheme of things, we developed a logically rigorous theory of infinite numbers. Cantor in 1874, working alone. These ideas were very controversial at the time. Today, they're accepted. It takes some getting used to.
This Axiom of Choice thing seems a bit vacuous; it says you can always choose an element from any non-empty subset of a given set, more or less. I think it's related to Turing machines as follows: since there is always a way to enumerate them, given some encoding of the instruction set, although enumerating them isn't the problem, the problem is deciding which machines to use; given some algorithm there are many ways to design a Turing machine equivalent, there is a minimal machine with a least number of states and all the machines equivalent to it. So you choose one of the equivalents. But you want a subset of Turing machines that output real numbers as a possibly infinite string of digits. Then, if you want a one-to-one correspondence between the machines and the reals, you want to ensure that each output is unique and that all the machines halt successfully. It's hard to see at first why this can't be done.
It says that you can simultaneously choose an element from each one of a collection of nonempty sets. That turns out to be independent of the other axioms of set theory; and it leads to a number of counterintuitive conclusions. The set of Turing machines is countable. The set of reals is uncountable. There can be no bijection between the set of Turing machines and the set of reals. No Choice is needed. The Axiom of Choice has nothing to do with Turing machines. There are only countably many finite-length strings over some finite alphabet, and any algorithm is a finite-length string. http://cs.stackexchange.com/questions/14517/are-turing-machine-really-countable
Almost, but not quite; it says you can always choose an element from each of every non-empty subset of a given set, even if the elements have no distinguishing properties and even if the collection of sets is infinite. An A-indexed family of sets B is a mapping (function) between elements a of set A and sets which can be written as B(a). The Cartesian product of an A-indexed family of sets B is a set, C, of all functions, c, where c(a) is a single element of B(a). Naturally, if even one of the families B(a) is the empty set, then the set C of all such functions c(a) is empty. Also, naturally, if A is a finite set, then we may prove via induction that #C = ∏ #B(a) so it follows that if all the B(a) are non-empty then so is C. But adopting the axiom of choice is equivalent to assuming that if all the B(a) are non-empty then C is also non-empty even if A is an uncountably infinite set. This was once controversial for mathematicians near the start of the 20th century, but most today find it a natural axiom even if rather awkward to phrase for a supposedly fundamental assumption about set theory. It was controversial, much like Euclid's parallel postulate, because it seemed too long to be a natural simplest assumption for talking about sets. It feels pretentious to throw around a word like "vacuous" when you make no comparison to other mathematical axioms or even connect the topics of a single post with reasoned exposition.
someguy1 #10 I never accepted the statement of a ratio for (even integers)/integers being 1. I thought I should get a second opinion. There is an abundance of "figures of speech".
The original post was lacking. Cantor's diagonal argument Assume an infinite list L of sequences si, where each si is an infinite sequence of characters from the set {0, 1}. L is complete since it contains all possible sequences of 0 and 1. A random listing begins as s1 = 001010... s2 = 111000... s3 = 010111... s4 = 110101... s5 = 011101... s6 = 010101... A partial sequence ps0 is formed from the diagonal elements (underlined) by applying the rule, if 0 then 1 else 0, to each position from left to right. The diagonal elements 010101 are transformed to ps0 = 101010 which is not included in the portion of L shown. Cantor states: since s0 will differ at the intersection of the diagonal with each si in the list L by construction, the list L is incomplete, i.e. a new sequence has been formed. There is a subset P6 in the remainder of L containing 2^6 = 64 sequences prefixed with 101010. Therefore ps0 differs from some but not all si at step 6. Now there is a subset P7 in the remainder of L containing 128 sequences prefixed with 1010101. The preceding method is repeated perpetually, always producing a subset that grows exponentially, and contains sequences prefixed with ps0. The swapping of characters shuffles ps0 between subsets of L, but always within L. The graphic using an ordered set L, shows a pattern that is obscured by the use of a random set L. Both the original method and the modified method are equivalent to forming a random sequence in L using a binary choice. The difference is the modified method avoids redundant comparisons by selecting subsets. The graphic also shows each element of s0 is selected from a subset that contains all possible sequences of 0 and 1, i.e. L contains copies of itself. The sequence s0 remains incomplete since at each step, there are more comparisons to do than have been done. Using the diagonal method is equivalent to running in place. If a single sequence can't be constructed, then there is no list. Please Register or Log in to view the hidden image!
I've managed to reason to my own satisfaction, after reading some posts at the likes of mathforum, that Cantor's diagonal argument does not require choice. Naively, one might assume that since you form a new number by choosing one digit from each infinite string of them, then changing that digit, that there is some kind of axiomatic choice, but everything is decided already so to speak. However, I haven't been satisfied that Turing's (use of Cantor's) diagonal argument is not related to AC. Perhaps someone has a definitive answer?
Nor has anyone made any such claim or used any such phrasing. This is a straw man argument, arguing against a position nobody has taken. Surely you agree that there is a bijection between the two sets given by n -> 2n.
A claim, not demonstrated. A crucial realization that s0 is admissible and yet not in the list L. Also crucial is that s0 is constructed from the particular form of L, therefore s0 is a function of the list. !!!! This contradicts the previous claim. STOP HERE. You have proved by contradiction that L does not contain all possible sequences of 0 and 1. But because you didn't use the correct starting point you didn't complete Cantor's proof. Cantor set out to prove that there was no possible onto relation between a set like \(\mathbb{N}\) and all possible functions between \(\mathbb{N}\) and {0, 1}. So he assumed there was one, and called it L. He didn't say it was random, just that the assumed relation L was that every element on the left had the tail of an arrow and every element on the right had the head of an arrow. By the diagonal argument, Cantor showed no matter what L was, there was always at least one function between \(\mathbb{N}\) and {0, 1}, such that no arrow in L pointed to it. But since that contradicts the claim that L was complete and the claim that L was complete rested only on the claim that something like L was possible, then no such L is possible. QED. That doesn't follow. s0 is not a "new" sequence, just not one contained in the supposed listing of "all of them." The rest of your post falls apart because you make unwarranted assumptions.
When expressed in terms of a powerset and not functions to {0,1}, Cantor's theorem can be proven in ZF theory without relying on the Axioms of Choice or Infinity at any point. Likewise the equinumerosity of the powerset of a set and of the set of all functions from that set to {0,1} can be proven without those axioms. http://us.metamath.org/mpegif/canth.html http://us.metamath.org/mpegif/canth2.html http://us.metamath.org/mpegif/pw2en.html Turing's use of the diagonal argument in the first proof is his 1937 paper is not closely related to Cantor's diagonal argument. Turing wants to compute a diagonal number. The nth digit of this number is the nth output of the nth acceptable machine for producing computable numbers when all such machines are listed in lexicographic order. He assumes we have a Number Loop over a Decision maker over Universal Computer all represented by a number. At some point that machine loops to the point where it needs to make a decision on the basis of a simulation of itself up to the crucial point, which at some point must make a decision on the basis of a simulation of itself up to the crucial point, which at some point must make a decision on the basis of a simulation of itself up to the crucial point, which at some point must make a decision on the basis of a simulation of itself up to the crucial point, etc. Thus the machine is unsatisfactory even through by definition it is. Thus the assumption that the output of such a machine is a computable quantity is a flawed assumption. This argument doesn't need the axiom of choice because at all points the sets are necessarily finite.
