countable sets

**TheRekz** · July 16th 2007, 08:46 AM

Show that the union of two countable sets is countable?

**galactus** · July 16th 2007, 09:06 AM

See here:

Biola University Academics

**TheRekz** · July 16th 2007, 09:19 AM

Originally Posted by galactus

See here:

Biola University Academics

Show that the union of two countable sets is countable.
Proof. Let A and B be the two countable sets. Then B\A is countable due to Prob. 34. From Thm. 1.7-A, the elements of A and B\A can be listed as A = {a0, a1, a2, . . . } and B\A = {c0, c1, c2, . . . } Then A È B = A È (B\A) = {a0, c0, a1, c1, a2, c2, . . . } is a list whose elements are all distinct and also includes all elements of A È B. Hence by Thm. 1.7-A, A È B is countable.

whats does B\A means here? can someone explain to me in a bit more detail

**Plato** · July 16th 2007, 09:21 AM

As the link in the previous posting shows (BTW: that is an awful proof!) any proof of this really dependents upon the definitions and theorems in your particular text. There many ways to show this some are easier than other. But they depend in particular definitions.

**Plato** · July 16th 2007, 09:50 AM

Here is one definition of countable: a set A is countable if there is a injection, one-to-one, function $f:A \mapsto N = \{ 0,1,2, \cdots \}$ .
Now suppose that each of A & B is countable set, now there is also an injection such that $g:B \mapsto N$ . We now define an injection $ h(x) = \left\{ {\begin{array}{lr} {2f(x)} & {x \in A\backslash B} \\ {2g(x) + 1} & {x \in B\backslash A} \\ \end{array}} \right. $ .
BTW: $A\backslash B$ is set of elements in A but not in B.
Now you must show that h is an injection.

**TheRekz** · July 16th 2007, 10:02 AM

Originally Posted by Plato

Here is one definition of countable: a set A is countable if there is a injection, one-to-one, function $f:A \mapsto N = \{ 0,1,2, \cdots \}$ .
Now suppose that each of A & B is countable set, now there is also an injection such that $g:B \mapsto N$ . We now define an injection $ h(x) = \left\{ {\begin{array}{lr} {2f(x)} & {x \in A\backslash B} \\ {2g(x) + 1} & {x \in B\backslash A} \\ \end{array}} \right. $ .
BTW: $A\backslash B$ is set of elements in A but not in B.
Now you must show that h is an injection.

My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?

**Plato** · July 16th 2007, 10:23 AM

Originally Posted by TheRekz

My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?

That is equivalent to the definition I used above. If you follow the proof I gave, then you do not have to consider cases.

**CaptainBlack** · July 16th 2007, 11:58 AM

Originally Posted by TheRekz

My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?

I would suppose I have enumerations of the two sets and take it from there.

RonL

**TheRekz** · July 16th 2007, 04:34 PM

Originally Posted by TheRekz

My professor mentions that a set is countable if it is either finite or countably infinite. What if A is finite and B is countably finite, would that be possible? Then how do I proof this?

I am getting more confused by your explanation.. If both A and B are countable because they are finite then it doesn't matter because then the union of both of them have a cardinality which then can be proofed to be a injection.. I am confused by the example of Plato here giving such function g(x), say that A\B is {1,2,3,4,5} and B\A is {7,8,9,10,11} I am confused to show this injection

**TheRekz** · July 17th 2007, 06:51 PM

anyone??

**CaptainBlack** · July 17th 2007, 07:48 PM

Originally Posted by TheRekz

anyone??

If both $A$ and $B-A$ are countably infinite, let: $\{ a_i, i \in \mathbb{N} \}$ $\{b_i, i \in \mathbb{N} \}$ be enumerations of $A$ and $B-A$ respectivly.

Then:

$ \{c_i, i \in \mathbb{N} \} $

where $c_{2j} = a_j, \ j \in \mathbb{N},\ c_{2k+1}=b_k, \ k \in \mathbb{N}$ is an enumeration of $A \cup B$ and so $A \cup B$ is countable.

The cases where one or both of $A$ and $B$ are finite is easily disposed of by an enumeration where the elements of $A$ or $B-A$ (whichever is finite or either if both are) are taken first follwed by the elements of the other.

RonL

**TheRekz** · July 17th 2007, 07:55 PM

Originally Posted by CaptainBlack

If both $A$ and $B-A$ are countably infinite, let: $\{ a_i, i \in \mathbb{N} \}$ $\{b_i, i \in \mathbb{N} \}$ be enumerations of $A$ and $B-A$ respectivly.

Then:

$ \{c_i, i \in \mathbb{N} \} $

where $c_{2j} = a_j, \ j \in \mathbb{N},\ c_{2k+1}=b_k, \ k \in \mathbb{N}$ is an enumeration of $A \cup B$ and so $A \cup B$ is countable.

The cases where one or both of $A$ and $B$ are finite is easily disposed of by an enumeration where the elements of $A$ or $B-A$ (whichever is finite or either if both are) are taken first follwed by the elements of the other.

RonL

why do you have to use A - B to proof this?? any reason?

**CaptainBlack** · July 17th 2007, 08:21 PM

Originally Posted by TheRekz

why do you have to use A - B to proof this?? any reason?

It gets rid of the duplicate elements. Its not strictly necessary but it cleans things up a bit.

RonL

**TheRekz** · July 17th 2007, 08:47 PM

Originally Posted by CaptainBlack

It gets rid of the duplicate elements. Its not strictly necessary but it cleans things up a bit.

RonL

and why is c2j = aj

**CaptainBlack** · July 17th 2007, 08:50 PM

Originally Posted by TheRekz

and why is c2j = aj

Because you are mapping one enumeration onto the even terms of the combined enumeration, and the other to the odd terms.

Thus $a_0, b_0, a_1, b_1, a_2, b_2, ...$ is the enumeration of $A \cup B$

RonL

Thread: countable sets

LinkBack

Thread Tools

Display

countable sets

Similar Math Help Forum Discussions

Prove a countable Cartesian product of countable sets is uncountable

[SOLVED] Countable union of closed sets/countable interesection of open sets

Proof that the intersection of infinitely many countable sets is countable.

Countable Sets

[SOLVED] I need help proving that the cross product of 2 countable sets is countable.

Search Tags