1
$\begingroup$

Given the set $B$ of all possible sequences of binary digits of finite length ("finite binary sequences"), construct a finite binary sequence $S$ such that each member of the sequence is the logical negation of the corresponding submember of the corresponding member of $B$, or because that sounds a bit ridiculous: $$\textrm{let}\ S = \{ S_n \ | \ S_n = \neg{B_{n_n}} \forall n \in [1, 2, 3,...] \}$$

$$B_1 = {\color{blue}{1}, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,...} \\ B_2 = {0, \color{blue}{1}, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0,...} \\ B_3 = {1, 0, \color{blue}{0}, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0,...} \\ B_4 = {1, 0, 0, \color{blue}{1}, 1, 0, 0, 1, 0, 0, 1, 0, 1,...} \\ B_5 = {1, 1, 0, 0, \color{blue}{1}, 1, 1, 0, 1, 1, 1, 1, 0,...} \\ B_6 = {0, 1, 1, 1, 1, \color{blue}{0}, 0, 1, 0, 1, 0, 1, 0,...} \\ B_7 = {1, 1, 0, 0, 0, 0, \color{blue}{1}, 0, 1, 0, 1, 0, 1,...} \\ B_8 = {1, 1, 1, 0, 1, 0, 1, \color{blue}{0}, 0, 0, 1, 1, 0,...} \\ B_9 = {1, 0, 0, 0, 0, 0, 0, 1, \color{blue}{1}, 1, 0, 1, 0,...} \\ B_{10} = {0, 1, 1, 0, 0, 0, 0, 1, 0, \color{blue}{1}, 0, 0, 1,...} \\ B_{11} = {0, 0, 1, 0, 0, 1, 0, 1, 1, 0, \color{blue}{1}, 0, 0,...} \\ B_{12} = {1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, \color{blue}{1}, 1,...} \\ B_{13} = {0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, \color{blue}{0},...} \\ \vdots \\ ------------------- \\ \ \ \ S = {\color{red}{0}, \color{red}{0}, \color{red}{1}, \color{red}{0}, \color{red}{0}, \color{red}{1}, \color{red}{0}, \color{red}{1}, \color{red}{0}, \color{red}{0}, \color{red}{0}, \color{red}{0}, \color{red}{1},...}$$

Because each member $S_n$ of $S$ is defined as the logical negation of the corresponding value in the corresponding member of $B$, $S$ cannot be equal to any member of $B$. $S$ differs from $B_1$ at position $1$, $B_2$ at position $2$, $B_3$ at position $3$, and so on. So $S$ is not in $B$. And we've got a contradiction.

We defined $B$ as the set of possible finite binary sequences, and yet we created a set $S$ that is both a finite binary sequence and not in $B$, so where's the contradiction? Considering I never tried to construct $B$ but was simply provided it as the set of all possible binary sequences, am I to conclude that it is simply impossible for a set to contain all possible binary sequences? Or that it is impossible to evaluate membership of such a set? Or perhaps that because the sequences are by definition of finite length, there simply aren't enough digits to accommodate negating all possible members of $B$?

I'm a bit confused, because while I understand the theory behind the use of this diagonal argument in proof, there's a logical contradiction where it seems all math is sound. Things get even more odd when the requirement for the sequences to be of finite length is dropped and $B$ is made to be the set of all possible binary sequences. What am I missing?

$\endgroup$
  • 2
    $\begingroup$ Why should $S$, defined this way, be finite? $\endgroup$ – G Tony Jacobs Jul 18 '17 at 1:11
  • $\begingroup$ Do you have a typo somewhere in this sentence? We defined B as the set of possible finite binary sequences, and yet we created a set S that is both a finite binary sequence and not in B, so where's the contradiction? $\endgroup$ – tilper Jul 18 '17 at 1:13
  • 1
    $\begingroup$ What is "the last member of $B$"? $\endgroup$ – Noah Schweber Jul 18 '17 at 1:44
  • 1
    $\begingroup$ Instead of listing all sequences lets list some sequences. And lets list them so that $B_1$ has length 1. And let $B_2$ have length $2$ and $B_k$ has lenghth $k$. So how long are the longest members? $\endgroup$ – fleablood Jul 18 '17 at 1:52
  • 1
    $\begingroup$ @TheEnvironmentalist "And yet $S$ can't be longer than every member of $B$, because it needs sources for its members." That's nonsense. $S$ can indeed be longer than every element in $B$, because there's no single element of $B$ that $S$ relies on. $S$ gets to draw on all the elements of $B$, and $B$ has arbitrarily long elements. $\endgroup$ – Noah Schweber Jul 18 '17 at 3:41
2
$\begingroup$

We defined $B$ as the set of possible finite binary sequences, and yet we created a set $S$ that is both a finite binary sequence and not in $B$, so where's the contradiction?

The contradiction is exactly what you said: You constructed an $S$ that by definition of $B$ should be in $B$ but is not in $B$.

Did you perhaps mean to say $S$ is an infinite binary sequence? In that case, yes, there is no contradiction. In fact, the set of all finite binary sequences is indeed countable.

I believe the confusion you're having is because you're applying Cantor's diagonal argument to the wrong thing. The original diagonal argument was applied to the set of all infinite binary sequences, not the set of all finite binary sequences. So your definition of $B$ must be adjusted.

$\endgroup$
  • $\begingroup$ I'm not trying to duplicate Cantor directly, I'm asking a reduced version, and one that, to the best I can tell, is a perfectly valid argument to make regardless of whether applied to the finite or to the infinite $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 4:41
  • $\begingroup$ @TheEnvironmentalist What do you mean by "reduced version"? It isn't valid for finite because (1) as you pointed out (assuming you did in fact mean to say that $S$ is infinite, which it is) there is no contradiction and (2) the set $B$ as you defined is not uncountable, so no proof that it is uncountable will be valid. $\endgroup$ – tilper Jul 18 '17 at 11:16
1
$\begingroup$

and yet we created a set $S$ that is both a finite binary sequence and not in $B$,

Why do you think $S$ is finite? In fact, it's easy to show that it won't be - and this resolves your difficulty.

$\endgroup$
  • $\begingroup$ The length of $S$ is, because of its member-by-member construction, no larger than the length of the longest elements in $B$, it qualifies as a member of $B$ just as much as any other member of $B$, no? $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 1:41
  • 1
    $\begingroup$ There is not longest element in B. Just as there is no largest finite number. $\endgroup$ – fleablood Jul 18 '17 at 1:41
  • 1
    $\begingroup$ The fact that the elements are themselves finite and bounded, does not mean the set of all of them is finite and bounded. There is no longest sequence as for any sequence of length k one can make a sequence of length k+1. As the list is infinitite the sequense S is infinite. $\endgroup$ – fleablood Jul 18 '17 at 1:44
  • 1
    $\begingroup$ Okay. Suppose S is finite. How long is it? Say it is $k$ long. But then what is $S_{k+1}$. If $S$ is finite there can not be any $S_{k+1}$ term. But you defined it so that $S_{k+1} = \lnot B_{k+1,k+1}$. So there is an $S_{k+1}$ term. S is not finite. For any $k$ there is a finite sequence that is $k$ long. ANd there are an infinite number of possible $k$s. There is *no* longest $k$. $\endgroup$ – fleablood Jul 18 '17 at 2:06
  • 1
    $\begingroup$ For any finite number $n$ there is another finite number $n+1$. So there is no largest natural number. And for any finite sequence that is $n$ long, there is another that is $n+1$ long. So there is no longest finite sequence. So S is not bounded by the longest sequences because there aren't any longest sequences. $\endgroup$ – fleablood Jul 18 '17 at 2:09
1
$\begingroup$

One inconsistancy, that is !!!!!NOT!!!!! the error, is that you define $S_n$ as $\lnot B_{n,n}$. But as $B_n$ is finite, what is $S_n$ if $B_n$ has length shorter than $n$ (and as there are $2^k$ sequences that are length $k$ and $2^k > k$ there must be some $B_n$ that are shorter than length $n$[$*$]).

!!!!THIS IS NOT THE ERROR!!!!!!.

We can define $S_1 = \lnot B_{1,1}$. Then $S \ne B_1$. If $B_{2}$ through $B_{k}$ are less than $2$ long, don't do anything. Let $i_2$ be such that $B_{i_2}$ is the first sequence after $B_1$ that is larger than equal to $2$. Then let $S_2 = \lnot B_{i_2, 2}$. This way $S \ne B_1$. $S \ne B_{2}$ through $B_{i_2-1}$ (as those are all shorter than length $2$ and $S \ne B_{i_2}$ as $S_2 \ne B_{i_2, 2}$.

Continue so that $S_n = \lnot B_{i_n, n}$. Then $S$ will not equal any of the $B_i$ and each term is well defined.

But as every $S_n$ exist, that means $S$ is INFINITE. Your insistence that $S$ is finite is bizarre as for every possible $n$ an $S_n$ term exist so there are an infinite number of terms. So $S$ is CLEARLY infinite.

You confusion seems to lie in that every finite SUBsequence of $S$ from $S_1.....S_m$ is finite and is shorter than some $B_{i_m}$ that somehow $S$ the sequence that contains all the terms must be shorter than some $B_{i_m}$. That is simply wrong.

For any $S_1.... S_n$ there is some $B_m$ that is longer but there is NOT !one! $B_m$ that is longer than all $S_1 ..... S_k$. For each $S_1..... S_n$ there is a DIFFERENT $B_m$ that is longer. And there is NO $B_m$ that is longer than ALL $S_1...S_n$.

Which really should be obvious... So $S$ is very clearly and inarguably infinite.

$\endgroup$
  • $\begingroup$ I really like this answer, the conclusion being that there simply aren't enough values of $B_n$ to construct S. But that would mean that $S$ cannot be drawn from $B$. The problem I have is stating that $S$ can be drawn from $B$, and $S$ can be infinite while all $B_n$ are not $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 3:45
  • 1
    $\begingroup$ But...no. that isn't the issue. The issue is simply that S is defined to have an infinite number of terms. So it isn't finite. $\endgroup$ – fleablood Jul 18 '17 at 4:19
  • $\begingroup$ Is an infinitely large sequence required to be strictly larger than any and all sequences of finite length? $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 4:43
  • 1
    $\begingroup$ What does "larger than all" mean? Yes, it is longer than any. But "longer than all" doesn't have any meaning. $\endgroup$ – fleablood Jul 18 '17 at 19:11
0
$\begingroup$

I sense you are not seeing the forest for the trees. Cantor's diagonal argument shows that the reals cannot be put in a list. The reals have the same cardinality as the power set of the integers. This shows the power set $P (\mathbb Z) $ has higher cardinality than $\mathbb Z $. The result generalizes to power sets of any set. It's easy to prove there is no surjection from a set to its power set. Given $f:X\rightarrow P (X) $, define y in P(X) by $y=\{x|x \notin f(x)\}.$ Then y is not in the image of f. No surjection means the power set has higher cardinality.

$\endgroup$
  • 1
    $\begingroup$ Would you mind explaining what "cannot be put in a list" means? I can understand that such a list cannot be constructed by any algorithm. That would be consistent with undecidability and Gödel incompleteness. I can accept that there's no way of making such a list, but how can they not be put in a list? {ℝ} there, that's the list. How doesn't that work? $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 3:42
  • $\begingroup$ @TheEnvironmentalist given such a list of numbers, I can produce a number you have left out... by simply going along the diagonal and constructing a number which differs from the ith number in the list in the ith place after the decimal. .. $\endgroup$ – Chris Custer Jul 18 '17 at 3:50
  • 1
    $\begingroup$ A list is broadly defined (and very intentionally so) as a collection of items, with or without an associated ordering. A collection of items is... just a collection of items. The pile of bananas on my counter is a collection of items. The keys on this keyboard are a collection of items. How are the reals not a collection of items? There's something profoundly nonsensical about the notation that a list, or set if you like, defined only as a collection of things, cannot contain a certain well-defined collection of things $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 4:02
  • $\begingroup$ They're an uncountable collection. .. $\endgroup$ – Chris Custer Jul 18 '17 at 4:09
  • $\begingroup$ That's vocabulary $\endgroup$ – TheEnvironmentalist Jul 18 '17 at 4:33
0
$\begingroup$

First understand that the proposed set $B$ is a countably infinite set of finite sets and is isomorphic to the rational numbers, and is possible to construct.

When you construct the diagonal $S$ across the entire list, that will produce another countably infinite set. So you are comparing apples to oranges. The list $B$ has finite sets and the diagonal $S$ is a countably infinite set.

If you still want to try to define a finite set $S$ out of the diagonal then that set will have a last element located at the end of some $B_X$ in the main set $B$. Later on at some at some point $B_Y$ the $S$ string will appear if the list is really complete.

Either way there is no contradiction involved.

$\endgroup$
0
$\begingroup$

Cantor's diagonal argument is almost always misrepresented, even by those who claim to understand it. This question get one point right - it is about binary strings, not real numbers. In fact, it was SPECIFICALLY INTENDED to NOT use real numbers.

But another thing that is misrepresented, is that it is a proof by contradiction. It isn't, and actually can't be. A proof by contradiction has to show that a contradiction follows from what was assumed, and it has to follow from ALL of what is assumed. Let me give a silly example. Assume the moon is made of a combination of bleu and green cheese, in a ratio that is equal to the square root of two. A well-known use of proof by contradiction is that if you assume a ratio is the square root of two, you get a contradiction about the factors in that ratio. This proves that there can't be a ratio equal to the square root of two. But it doesn't prove anything about the cheeses that make up the moon, even if you include that in your assumption. The contradiction does not follow from the assumed cheeses.

That the anti-diagonal string is not in your list does not follow from assuming you had a list of ALL strings. Only that you had a list of SOME strings. So all it proves is that any list of SOME strings can't be ALL. But that is enough: proving "if A, then B" also proves "if not B, then not A." This is called proof by controposition, not contradiction.

The basic outline of the proof is: 1) Assume T is the entire set you are interested in. 2) Assume S is a countable subset of T. 3) Create the anti-diagonal string of S, called D, which cannot be in S. 4) Prove that D is in T. 5) This proves "If S is Countable, it is not all of T." 6) By contraposition, "If S is all of T, it is not countable."

Where the argument in the original question fails, is step 4. The anti-diagonal it called S must be infinite since it is a function of the infinite set B. Therefore it isn't supposed to be in B.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.