countability of a set

**surjective** · January 5th 2011, 02:11 AM

Hello to all

How do I prove that the set $S$ of real sequences $(x_{n})$ , where each $x_{n}$ is either 0 or 1, is not a countable set.

Hints/suggestions on how to start would be appreciated.

Are there any books on teqhniques on proving-methods?

Thanks a lot.

**CaptainBlack** · January 5th 2011, 02:27 AM

Originally Posted by surjective

Hello to all

How do I prove that the set $S$ of real sequences $(x_{n})$ , where each $x_{n}$ is either 0 or 1, is not a countable set.

Hints/suggestions on how to start would be appreciated.

Are there any books on teqhniques on proving-methods?

Thanks a lot.

You may consider an element of $$$S$ as a real in $[0,1]$ in binary, but the representation is not unique each terminating real will correspond to two elements of $$$S$ .

Hence $\text{card}(S) \ge \text{card}([0,1])$ ...

CB

**DrSteve** · January 5th 2011, 02:42 AM

There are lots of ways to do this. One way is to produce an injection from a set you already know is uncountable to this set. This is essentially what CaptainBlack was suggesting.

Here is a method that doesn't require any knowledge on the cardinality of other sets. It is called a diagonalization argument:

I will explain the argument and you see if you can write out the details. If you're still stuck I will help you fill them in.

We will use an indirect argument. Assume that the set S is countable. This means we can list the elements. Write down each sequence in this list (double subscripts will be helpful).
Now see if you can "diagonalize" to produce a sequence that is not on this list.

I'm not sure what kind of book you're looking for. If you're looking for a book on how to do proofs, then I'm not sure if there are any good sources currently out there (someone correct me if I'm wrong). If you're looking for a book that has cardinality arguments, then there are lots of them. Any book on introductory set theory will have these arguments, and many analysis books will have some arguments like this in the introductory chapter. Unfortunately I haven't really found a set theory book that I particularly like, so when I teach set theory I use my own material. I'm not saying that the books out there don't have good material - only that I don't know of a book that I would personally base a whole course around.

**surjective** · January 5th 2011, 04:17 PM

Hey,

Im not familiar with the principle of diagonalizing? How does that work?

**Drexel28** · January 5th 2011, 04:24 PM

Originally Posted by DrSteve

I'm not sure what kind of book you're looking for. If you're looking for a book on how to do proofs, then I'm not sure if there are any good sources currently out there (someone correct me if I'm wrong). If you're looking for a book that has cardinality arguments, then there are lots of them. Any book on introductory set theory will have these arguments, and many analysis books will have some arguments like this in the introductory chapter. Unfortunately I haven't really found a set theory book that I particularly like, so when I teach set theory I use my own material. I'm not saying that the books out there don't have good material - only that I don't know of a book that I would personally base a whole course around.

I am fond of set theory. The books I'd suggest you look at (most likely you already have, but it can't hurt to suggest

) are Halmos-Naive Set Theory, Stoll-Set Theory and Logic, Goldrei-Classical Set Theory, or if you're up for as serious challenge-Jech-Set Theory.

Originally Posted by surjective

Hey,

Im not familiar with the principle of diagonalizing? How does that work?

Diagonalizing is a term I haven't heard applied to this argument, but the following may be what Dr. Steve means. Suppose that $f:\mathbb{N}\to\{0,1\}^{\mathbb{N}}$ is surjective and define $a_n= \pi_n(f(n))+1\text{ mod }2$ . Deduce that $a_n\in \{0,1\}^{\mathbb{N}}-f\left(\mathbb{N}\right)$ contradicting surjectivity.

**Plato** · January 5th 2011, 04:54 PM

I enjoy this problem. Suppose each element of $S$ can be named with a positive integer: $S=\{x_k:k\in\mathbb{Z}^+\}$ .

Now say we look at $x_j=(x_{j,1}, x_{j,2}, x_{j,3},\cdots, x_{j,j},\cdots)$ .
So $x_{j,j}$ is either $0\text( or )1$ .

Now we define a new bit-sequence: $y_{k,j}=\left\{ {\begin{array}{*{20}c} 0 & {x_{j,j} = 1} \\1 & \text{else} \\ \end{array} } \right.$ .

How can $y$ be in the original list?

**CaptainBlack** · January 5th 2011, 07:00 PM

Originally Posted by Drexel28

Diagonalizing is a term I haven't heard applied to this argument, but..

Cantor's diagonal slash.

CB

**DrSteve** · January 6th 2011, 03:18 AM

Plato's solution is what I had in mind. His solution is correct of course, but it may seem confusing at first. So let me try to motivate what he has done with a specific list.

So our assumption is that we can list all such sequences. Let me write down a specific list (the "correct" list may look nothing like this of course):

10101010101010...
11111111111111...
01010101010101...
01001000100001...
10100100010000...
... ... .... ...

I will now show that this specific list cannot be correct. The main idea is that to come up with a new sequence that disagrees with each of these sequences we just need our new one to disagree with each of these in one position. So we will make it disagree with the first one in the first position, the second in the second position, and so on...

Since the first sequence has a 1 in the first position we will put a 0 in the first position of our new sequence

Since the second sequence has a 1 in the second position we will put a 0 in the second position, etc.

So our new sequence looks like this:

00111...

If you understand this specific list, you can now try to understand the general argument with an arbitrary list. See Plato's post for this.

Drexel's post is the same idea, but is a little more sophisticated.

Thread: countability of a set

LinkBack

Thread Tools

Display

countability of a set

Similar Math Help Forum Discussions

Countability

Countability

Bijection - Countability

Countability

Countability

Search Tags