3
$\begingroup$

Set $S$ contains all the infinite binary sequences which must consist of infinite "ones" and infinite "zeros", first of all I am not sure if it is countable or not.. I thought about cantors diagonal but I am not sure about that, hope someone could help me here.

thank you in advance.

$\endgroup$
  • 1
    $\begingroup$ Hint: How many infinite binary sequences are not in $S$? (This should give you an intuitive idea of the answer. To prove it correct, I recommend the Cantor-Schröder-Bernstein theorem). $\endgroup$ – Henning Makholm Apr 15 '16 at 15:54
  • $\begingroup$ @HenningMakholm finite binary sequences I think..? $\endgroup$ – LiziPizi Apr 15 '16 at 15:56
  • $\begingroup$ If, when you said "infinite "ones" and infinite "zeroes", you actually meant that there must be an infinite number of "ones" and and infinite number of "zeroes" then, no, The set would contain the number 0 which has an infinite number of "zeroes" but NO "ones". $\endgroup$ – user247327 Apr 15 '16 at 16:10
  • 1
    $\begingroup$ I don't know what an "infinite zero" or an "infinite one" is. If you mean "infinitely many ones and zeros", then that is how you should write it. In mathematics it is not correct to say "infinite zeros" if you mean "infinitely many zeros". $\qquad$ $\endgroup$ – Michael Hardy Apr 15 '16 at 16:25
  • $\begingroup$ Well... I realize one shouldn't just give answers but, yes, it is uncountable. And yes, the prove is via Cantors diagonal. A very basic fact which you will rely on a lot in your future is the finite cross product (ordered n-tuples) of a countable set is countable (thus the rationals n/m ~ (n,m)) are countable) but the countably infinite cross product (infinite sequence) of finite sets is in not. Often the sequence of 1s and 0s is written $(0,1)^{\infty}$ and it has, theoretically, $2^{\infty}$ elements, and thus we often refer to the cardinality of uncountability as $2^{\infty}$ $\endgroup$ – fleablood Apr 15 '16 at 16:57
2
$\begingroup$

Let $U = $ the set of all infinite series

$S = $ the set of all infinite series with infinite 1s and 0s

$A = $ the set of all infinite series with finite 0s

$B = $ the set of all infinite series with finite 1s.

$U = S \cup A \cup B$.

Claim 1: U is uncountable.

Claim 2: A and B are countable

Claim 3: the countable union of countable set is countable.

Hence, if $S$ were countable, $U$ would be countable. It isn't so $S$ is uncountable.

===

Claim 1: This is Cantor's diagonal. If U were countable we could list all sequences so $U = \{A_i\} = \{\{a_{i_k}\}\}$. Then the sequence $B = \{1-a_{i_i}\} \not \in U$. A contradiction so $U$ is uncountable.

Claim 2: If an infinite sequence, {$a_n$} contains a finite number of 0s then there is an $a_m$ that is the last 0 value and all the remaining values are 1. Consider the finite sequence {$b_n$} that has $m$ terms were $b_i = a_i$. For every infinite sequence with finite number of 0 there is such a corresponding finite sequence. And for every finite sequence we can find a corresponding infinite sequence by "sticking" an infinite number of 1s on the end.

So there is a 1-1 correspondence between finite sequences and infinite sequences with finite 0s.

But the set of finite sequences is countable. ($t(\{b_n\})=\sum_{i=0}^m b_n*2^i \in \mathbb N$ is a 1-1 mapping from the finite sequences to the natural numbers.)

So there are countably many infinite sequences with finite 0s, and likewise there are countably many infinite sequences with finite 1.

Claim 3: Let $\{S_i\}$ be a class of countable sets so that each $S_j = \{s_{j,k}\}$ so $\cup_i S_i = \{s_{j,k}\}$ with some possibility of multiple representation. It suffices to show that $\mathbb N \times \mathbb N$ is countable. Basically the map (0,0)-> 0, (1,0) ->1, (0,1) ->2, (2,0)->3, (1,1) -> 4, (0,2)->5 etc or $(i,j) \rightarrow \sum_{l=0}^{j+k}l + k$ is a 1-1 mapping.

$\endgroup$
  • $\begingroup$ "1-1 mapping from the finite sequences to the natural numbers" What about the following 2 sequences: '010' and '0010'? Those are 2 finite sequences with a mapping to the same natural number (2)... $\endgroup$ – Rizon May 23 '17 at 21:30
  • $\begingroup$ Hmm, you're right. But easy to fix. Let $n = 2^k(2m - 1)$ then $t(n) = $ k leading zeros and then m expressed in binary. $\endgroup$ – fleablood May 23 '17 at 21:53
  • $\begingroup$ Also, "And for every finite sequence we can find a corresponding infinite sequence by "sticking" an infinite number of 1s on the end." is not 1-1 mapping. Take for example these two finite sequences: "0101" and "01011". They're both mapped to "01011111......" $\endgroup$ – Rizon May 23 '17 at 22:22
  • $\begingroup$ Oh, bfd. these are trivially fixed. I wrote this post 13 months ago. Stick a 01111111..... at the end. Then the only 1111..... and 011111..... aren't mapped to. But we can just shift those by 2. $\endgroup$ – fleablood May 23 '17 at 23:16
1
$\begingroup$

Let $S$ be the set of all binary sequences other than those with a finite number of ones or a finite number of zeros, and let $T$ be the set of all binary sequences minus $S$. The question is whether $S$ is countable.

Then $T$ is countable. Indeed, $T$ is the union of $U$ and $V$ where $U$ is the set of binary sequences with a finite number of ones, and $V$ is the set of binary sequences with a finite number of zeros.

To show that $U$ is countable, consider the counting function mapping each binary sequence $\{x_m\}$ with no $1$'s past position $k$ to the (finite) number $n = \sum_{n=0}^{k} x_n2^n$. (The usual diagonal proof that a counting function can't work does not say anything in this case, since we are not allowed to construct a sequence with arbitrarily late ones: Such a sequence must have infinite ones, hence is not in $U$.)

Since $U$ is countable, $T$ is countable, and $S = P(\omega) - T$ is uncountable. $S$ is 1-1 with $P(\omega)$, not $\omega$.

$\endgroup$
  • $\begingroup$ How do you know P(w) is uncountable? To my mind, that was the entire point of the OP. (And when did you define P(w) as equivalent the set of sequences of 1s and 0s?) $\endgroup$ – fleablood Apr 15 '16 at 17:08
  • $\begingroup$ The power set of any set assigns "in" or "not in" to each element of the set. Thus $P(\omega)$ assigns "in" or "not-in" to each integer. This is isomorphic to assiging $1$ or $0$ to each integer, which in trun is isomorphic to having each possible binary sequence, since the integer can represent the position within the sequence. And nobody would ask this question in a course or book, without earlier having considered the cleaner case of allowing arbitrary counts of zeros and ones including finite or infinite - the classic diagonal proof lives there. $\endgroup$ – Mark Fischler Apr 15 '16 at 23:14

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.