Set of all infinite bit strings with an equal number of $0$s and $1$s. Is the set of all infinite bit strings with an equal number of $0$s and $1$s countable or uncountable?
Not sure how to prove that is countable/uncountable. Any hints would be nice.
 A: What's your definition of "equal number of $0$s and $1$s"?
If you mean the index sets have the same cardinality, then it's definitely uncountable: Its complement is the set where either $0$ or $1$ appears only finitely many times, which is countable, as it's the countable union of finite sets $$\{a_1a_2...|a_n=1, \forall n\ge N\} \cup \{a_1a_2... |a_n=0, \forall n\ge N\}$$
It could mean that $\lim_{n\rightarrow\infty}\dfrac{\sum_{i=1}^na_i}{n}=\frac{1}{2}$, where $\sum_{i=1}^na_i$ counts the number of $1$'s among $a_1, \cdots, a_n$. This set is also uncountable: thanks to the strong law of large numbers, this set has probability $1$.
A: Using a stricter definition of “equal number of 0s and 1s” than Just a user:
Let $B$ be the set of all infinitely-long strings consisting of bi-bit strings “01” or “10”.  (So strings starting with 0101, 0110, 1001, and 1010 may be part of this set, but strings starting with any other 4-bit sequence may not.)  Clearly, if $x \in B$, then $x$ will have an equal number of 0's and 1's after any even number of bits.
Assume that $B$ is countable.  IOW, we can assign every $x \in B$ to an index $k$ in an ordered sequence $b$.
Now, apply Cantor's diagonal argument.  Let $y \in B$ be an infinite string such that the $n$th bi-bit in $y$ is the complement ($01 \rightarrow 10, 10 \rightarrow 01$) of the corresponding b-bit in $b_n$.  Then $\forall k \in \mathbb{N}, y \ne b_k$, as they must differ in at least two bits.  But this contradicts our assumption that every member of $B$ can be indexed by a $k$.
Therefore, $B$ is uncountable.
Any supersets of $B$, just as the two mentioned in Just a user's post, must also be uncountable.
A: Hint:

*

*Set of all functions $f:\Bbb{N}\to \{0,1\}$ is equivalent to ${\mathscr{P}}({\Bbb{N}})$.


*Then use Cantor's theorem , no injective map from $A$ to ${\mathscr{P}}(A)$ is onto.
Alternative:
$|\{f | f:\Bbb{N}\to\{0,1\}\}|=2^{\aleph_0}=\aleph_1$
