Thread: Countability/Cardinality Help!

I don't understand how to do the following things,

(a) Let $\displaystyle f: X \rightarrow Y$ be a surjection. Show that if X is an infinite countable set then Y is either countable or finite. (set A is countable defined as |A| = |N|)

(b) By enumerating elements, or otherwise, show that the set of all ordered pairs of positive integers $\displaystyle Z^+ \times Z^+ = \{(a,b): a,b \in Z^+\}$ is countable.

(c) Deduce that the set of positive rationals $\displaystyle Q^+$ is countable.

(d) Show that the set of all subsets of $\displaystyle Z^+$ is uncountable [argue by contradiction]
------------------------------------------------------------------------
I don't understand how to do this stuff, any help is much appreciated.

Originally Posted by Jason Bourne

I don't understand how to do the following things,

(a) Let $\displaystyle f: X \rightarrow Y$ be a surjection. Show that if X is an infinite countable set then Y is either countable or finite. (set A is countable defined as |A| = |N|)

(b) By enumerating elements, or otherwise, show that the set of all ordered pairs of positive integers $\displaystyle Z^+ \times Z^+ = \{(a,b): a,b \in Z^+\}$ is countable.

(c) Deduce that the set of positive rationals $\displaystyle Q^+$ is countable.

(d) Show that the set of all subsets of $\displaystyle Z^+$ is uncountable [argue by contradiction]
------------------------------------------------------------------------
I don't understand how to do this stuff, any help is much appreciated.

Before we start, just note that whenever I mention $\displaystyle N$, or the naturals, I am referring to: 0,1,2,3,... (also known as the set of positive integers, or $\displaystyle Z^+$).

(a): We know that if exists a surjection $\displaystyle f: X \rightarrow Y$, then we deduce something about the cardinality of the two sets, specifically that $\displaystyle card(X) \geq card(Y)$. Since $\displaystyle X$ is countable, and the size of set $\displaystyle Y$ can be no bigger than that, $\displaystyle Y$ must be countably infinite (that is, there is also a bijection between $\displaystyle X$ and $\displaystyle Y$) or finite.

You can try to list the elements of $\displaystyle Y$ like $\displaystyle Y: (y_1, y_2, y_3, ...)$. If they correspond bijectively to the naturals, they are countable by definition of having the same cardinality.

Conversely, there exists an element in the naturals, say $\displaystyle k$, that is not hit by an element in $\displaystyle Y$, then $\displaystyle Y$ is finite with a cardinality of $\displaystyle k-1$. For example, say that $\displaystyle k=100$, meaning there is no 100th element in set $\displaystyle Y$, so that means that $\displaystyle Y$ must have 99 elements or have a cardinality of 99.


(b): Simply use the fact that a finite Cartesian product of countable sets is countable. So in this case, you have a Cartesian product of the naturals with the naturals (both of which are countable and it is a finite product because you are multiplying only two terms together). So it is countable.

If that is not sufficiently convincing, recall that the Cartesian of two sets represents the set of all pairs with elements from the two sets: $\displaystyle (a_1, a_2)$ where $\displaystyle a_1 \in A_1, a_2 \in A_2$. Thus, we can enumerate the elements of the Cartesian product of the positive integers as such:

$\displaystyle (0,0), (0,1), (0,2), (0,3), ...$
$\displaystyle (1,0), (1,1), (1,2), (1,3), ...$
$\displaystyle (2,0), (2,1), (2,2), (2,3), ...$
$\displaystyle (3,0), (3,1), (3,2), (3,3), ...$

Then count them by going diagonally and eliminating redundant elements. So we enumerate by: $\displaystyle (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3), (1,2), (2,1), (3,0), ...$ and then removing redundant elements, we get something like $\displaystyle (0,0), (0,1), (0,2), (1,1), (0,3), (1,2), ...$. Obviously if we can do this type of counting, the set is countable, lol


(c) To show that the positive rationals are countable, it suffices to construct an injective function $\displaystyle f: Q \rightarrow N$. Let us define $\displaystyle f$ as:
$\displaystyle f(q) = 2^a 3^b$ where $\displaystyle q \in Q = a/b$
This function is injective, as whenever $\displaystyle f(q_1) = f(q_2)$ it must be the case that $\displaystyle q_1 = q_2$. So by virtue of an injective function, we argue that $\displaystyle card(Q) \leq card(N)$. But it is clear that the naturals are a subset of the positive rationals, so $\displaystyle card(N) \leq card(Q)$. Then from these two facts, we have $\displaystyle card(N) = card(Q)$, so the positive rationals must be countable.


(d) Google for "Cantor's Diagonalization Argument" or "Power set of the naturals" and you will find your answer. This is one of the most fundamental facts in set theory on countability and uncountability, so there will be a lot of available material on this =)

For (d), assume there exists $\displaystyle \phi$ a surjection from $\displaystyle \mathbb{N}$ to $\displaystyle \mathcal{P}(\mathbb{N})$ (the set of all subsets of $\displaystyle \mathbb{N}$).

What about $\displaystyle A=\{x\in \mathbb{N};\ x\notin \phi(x)\}\in \mathcal{P}(\mathbb{N})$ ?

First, if $\displaystyle A$ is empty, that means $\displaystyle \forall n\in \mathbb{N},\ \phi(n)=\{n\}$, and then $\displaystyle \phi^{-1}(\{1,2\})\notin \{1,2\}$ so $\displaystyle \phi^{-1}(\{1,2\})\in A$.
Conclusion: $\displaystyle A\neq \emptyset$.

Let $\displaystyle a$ be a positive integer such that $\displaystyle \phi(a)=A$.

$\displaystyle a\in A \Rightarrow a\notin \phi(a) \Rightarrow a\notin A$ (Contradiction)

$\displaystyle a\notin A \Rightarrow a\in \phi(a) \Rightarrow a\in A$ (Contradiction)

Conclusion: There is no such $\displaystyle \phi$. Therefore, no bijection between $\displaystyle \mathbb{N}$ and $\displaystyle \mathcal{P}(\mathbb{N})$: $\displaystyle \mathcal{P}(\mathbb{N})$ is uncountable.


That's a particular case of:

CANTOR'S THEOREM: Let $\displaystyle X$ be a set, and $\displaystyle \lambda$ its cardinality. Then $\displaystyle \lambda < 2^{\lambda}$

($\displaystyle 2^{\lambda}$ is the cardinality of $\displaystyle \mathcal{P}(X)$)

I forgot to mention that for part (c), you can simply proceed as you did in part (b). That is, for part (c), You can simply state that the positive rationals $\displaystyle q = a/b$ where $\displaystyle a,b \in Z^+$ are a subset of the Cartesian product of the naturals with themselves $\displaystyle Z^+ \times Z^+ = \{(a,b): a,b \in Z^+\}$. And since you proved in part (b) that such a product is countable, then the positive rationals should be too.

The positive rationals do differ from that product because the rationals must not contain zero in the denominator (as in, $\displaystyle b \neq 0$) and the greatest common divisor between the numerator (as in, $\displaystyle a,b$ must not have any common factor except for 1). So be sure to mention this in you proof. But this is without loss of generality; it does not change the result that the positive rationals are countable because it's still a Cartesian product of two countable sets.

So $\displaystyle QED$

Thank you both very much! Your replies were very detailed and helpful. I shall post here again if I have any more queries concerning countability.

I'm not sure with the following things:

(a) Given Schroder-Bernstein theorem:

$\displaystyle |A| \leq |B|$ AND $\displaystyle |B| \leq |A| \Rightarrow |A| = |B| $

(where $\displaystyle |A|$ means the cardinality of set A)

By defining two suitable injective mappings and applying this theorem, or otherwise, prove that open interval $\displaystyle (0,1)$ and the set $\displaystyle \mathcal{P}(\mathbb{N})$(the set of all subsets of $\displaystyle \mathbb{N}$) have the same cardinality.

(b) Deduce the open interval $\displaystyle (0,1)$ is uncountable.

(c) Prove that the set of polynomials of degree n with integer coefficients

$\displaystyle \{ a_0 +a_1x +a_2x^2 +...+ a_nx^n : a_i \in \mathbb{Z}\}$

is countable. Deduce that the set of all polynomials with integer coefficients is countable.

----------------------------------------------
I think for (a) that one of the injections should involve inverse tan but im not sure. I'm not sure about the rest. Can you help with these? Thanks everyone for help.

Originally Posted by Jason Bourne

I'm not sure with the following things:

(a) Given Schroder-Bernstein theorem:

$\displaystyle |A| \leq |B|$ AND $\displaystyle |B| \leq |A| \Rightarrow |A| = |B| $

(where $\displaystyle |A|$ means the cardinality of set A)

By defining two suitable injective mappings and applying this theorem, or otherwise, prove that open interval $\displaystyle (0,1)$ and the set $\displaystyle \mathcal{P}(\mathbb{N})$(the set of all subsets of $\displaystyle \mathbb{N}$) have the same cardinality.

(b) Deduce the open interval $\displaystyle (0,1)$ is uncountable.

(c) Prove that the set of polynomials of degree n with integer coefficients

$\displaystyle \{ a_0 +a_1x +a_2x^2 +...+ a_nx^n : a_i \in \mathbb{Z}\}$

is countable. Deduce that the set of all polynomials with integer coefficients is countable.

----------------------------------------------
I think for (a) that one of the injections should involve inverse tan but im not sure. I'm not sure about the rest. Can you help with these? Thanks everyone for help.

You know, they should have totally included the fact that Jason Bourne studies infinite cardinality set theory in The Bourne Ultimatum

(a) I can explain the premise behind constructing such a bijection - it is up to you to actually write it up, of course.

First, a little background on power sets. For any set $\displaystyle S$ with a cardinality of $\displaystyle card(S)$, its power set $\displaystyle 2^S$ has the same cardinality as
$\displaystyle \{0,1\}^{card(S)}$
The 0's and 1's are indicator functions telling you whether or not an element of $\displaystyle S$ in a particular subset or not.

For example, consider the set $\displaystyle S=\{x,y,z\}$, which a cardinality of 3 and a power set $\displaystyle 2^S$ which is
$\displaystyle \{$empty set$\displaystyle \}, \{x\}, \{y\}, \{z\}, \{x,y\}, \{y,z\}, \{x,z\}, \{x,y,z\}$

Then, $\displaystyle \{0,1\}^{card(S)}=\{0,1\}^3$
$\displaystyle = \{0,0,0\}, \{1,0,0\}, \{0,1,0\}, \{0,0,1\}, \{1,1,0\}, \{0,1,1\}, \{1,0,1\}, \{1,1,1\}$

Do you see how the set $\displaystyle \{$empty set$\displaystyle \}$ corresponds to $\displaystyle \{0,0,0\}$, $\displaystyle \{1,0,0\}$ to $\displaystyle \{x\}$, so forth?

Extending this principle to infinite sets is possible, so we conclude that $\displaystyle 2^N$ has the same cardinality as $\displaystyle \{0,1\} \times \{0,1\} \times ...$ (multiplied together countable times). But what is this set? This set is all the possible countably sequences of 0's and 1's that exist out there.

Note that if you convert any given real number into binary, you get the same thing: sequences of 0's and 1's. So that's your bijection.


(b) So if you have done part (a), part (b) follows immediately. If you show a bijection of one set to an uncountable set, then the first set must also be uncountable, of course.


(c) Approach this proof inductively. Consider the set of all polynomials with degree 1 (as opposed to degree $\displaystyle n$). That is, consider the set $\displaystyle \{ a_0: a_0 \in \mathbb{Z}\}$, which is just simply the set of all integers, which is clearly countable.

Now do it again for all polynomials with degree 2. So the set $\displaystyle \{ a_0 +a_1x: a_0, a_1 \in \mathbb{Z}\}$, which is the Cartesian product of the integers with itself: recall that $\displaystyle Z \times Z = \{(a_0,a_1): a_0,a_1 \in Z\}$ is countable from your previous problems. So this too is countable.

Then keep doing this until your balls drop off. Or you can just simply say that the set of all polynomials with integer coefficients is the union of the first set that I have described, with the second one, and so forth. That would be $\displaystyle \{a_0: a_0 \in Z\} \cup \{(a_0,a_1): a_0,a_1 \in Z\} \cup ...$, which is a countable union of countable sets. And we know that is countable, of course - $\displaystyle QED$

You know, they should have totally included the fact that Jason Bourne studies infinite cardinality set theory in The Bourne Ultimatum

LOL!!!!!!!!!!!!!!!!! I agree!

(a) I can explain the premise behind constructing such a bijection - it is up to you to actually write it up, of course.

First, a little background on power sets. For any set $\displaystyle S$ with a cardinality of $\displaystyle card(S)$, its power set $\displaystyle 2^S$ has the same cardinality as
$\displaystyle \{0,1\}^{card(S)}$
The 0's and 1's are indicator functions telling you whether or not an element of $\displaystyle S$ in a particular subset or not.

For example, consider the set $\displaystyle S=\{x,y,z\}$, which a cardinality of 3 and a power set $\displaystyle 2^S$ which is
$\displaystyle \{$empty set$\displaystyle \}, \{x\}, \{y\}, \{z\}, \{x,y\}, \{y,z\}, \{x,z\}, \{x,y,z\}$

Then, $\displaystyle \{0,1\}^{card(S)}=\{0,1\}^3$
$\displaystyle = \{0,0,0\}, \{1,0,0\}, \{0,1,0\}, \{0,0,1\}, \{1,1,0\}, \{0,1,1\}, \{1,0,1\}, \{1,1,1\}$

Do you see how the set $\displaystyle \{$empty set$\displaystyle \}$ corresponds to $\displaystyle \{0,0,0\}$, $\displaystyle \{1,0,0\}$ to $\displaystyle \{x\}$, so forth?

Extending this principle to infinite sets is possible, so we conclude that $\displaystyle 2^N$ has the same cardinality as $\displaystyle \{0,1\} \times \{0,1\} \times ...$ (multiplied together countable times). But what is this set? This set is all the possible countably sequences of 0's and 1's that exist out there.

Note that if you convert any given real number into binary, you get the same thing: sequences of 0's and 1's. So that's your bijection.

I wish you were my lecturer, that was quite helpful. Thanks to people like you who take their time to reply to me that I stand a better chance at understanding these things.

So, all I have to do is show that there is a mapping between (0,1) and $\displaystyle \mathcal{P}(\mathbb{N})$ and that this mapping is bijective?

Yes, you do this as follows:

1. Construct a function, say $\displaystyle b: (0,1) \rightarrow \{0,1\}$ which is a binary convert that maps any real number in the interval (0,1) into a countably long string of 0's and 1's.

For example, consider the real number 1/2, which is clearly within the open interval (0,1). Its binary expansion is: 0.100... because 1(1/2) + 0(1/4) + 0(1/8) + 0(1/16) + ... = 1/2. Another example: 3/4 or 0.75, when mapped into binary, becomes 0.11000... because 3/4 = 1(1/2) + 1(1/4) + 0(1/8) + 0(1/16) + ...

So now you have a string of 0's and 1's representing any real number within (0,1). You do this for every real number in (0,1), sending every base-10 real number into a base-2 (aka binary) system where they are each written as a countably long string of 0's and 1's.

2. Show that the set of all real numbers written in binary format is equivalent to: {0,1}x{0,1}x{0,1}x... (kind of obvious, right?)

3. Show that {0,1}x{0,1}x{0,1}x... has the same cardinality as $\displaystyle 2^N$.

So that basically says that the reals are equivalent to {0,1}x{0,1}x{0,1}x..., which have the same cardinality as the power set of the naturals. So then you're done.