# Math Help - denumerable sets

1. ## denumerable sets

ok im confused on how to start with this
we had previously proved that A is a denumerable set and x is an element not in A, then A union {x} is also deumerable.
Prove that if S = {x1, x2, ...,xn} is a set of n elements, none of which are in A, then A union S is denumerable

2. Originally Posted by mathcnc
ok im confused on how to start with this
we had previously proved that A is a denumerable set and x is an element not in A, then A union {x} is also deumerable.
Prove that if S = {x1, x2, ...,xn} is a set of n elements, none of which are in A, then A union S is denumerable
prove by induction on the "size" of S

3. Originally Posted by mathcnc
ok im confused on how to start with this
we had previously proved that A is a denumerable set and x is an element not in A, then A union {x} is also deumerable.
Prove that if S = {x1, x2, ...,xn} is a set of n elements, none of which are in A, then A union S is denumerable
Since $A\cup\left\{x\right\}=A_1$ is countable it follows that $A_1\cup\left\{x_1\right\}$ is countable and it follows that $A_{n}\cup\left\{x_n\right\}$ is countable assuming that $n$ is finite. The reason for the finiteness of $n$ is that any finite set is countable since if you have a set with $n$ elements you can easily find a bijection with the $n$th natural number. If $n$ were infinite then we could have that $S=\mathbb{R}-\mathbb{Q}$ or any other uncountable set, the only way to guarantee countability is finitness. In fact, it is true that if both $A,B$ are countable then so is $A\cup B$ regardless of their individual cardinalities, but since $S$ was not given as either countable or uncountable we may not use this argument.

EDIT: I completely missed you post Jhevon, my apologies.

4. Originally Posted by Mathstud28
if you have a set with $n$ elements you can easily find a bijection with the $n$th natural number.
???

5. Originally Posted by Moo
???
in set theory, natural numbers are defined in terms of sets. zero is the null set, and every natural number after that is defined as the set containing all previous sets, so for instance, 1 = {0}, 2 = {0,1}, 3 = {0,1,2}, ...

so that if we have a set with n elements, we can find a bijection between that set and the nth natural number, since the natural number n is itself a set with n elements. thus we can do with finite sets and natural numbers the same thing we can do with infinite countable sets (a.k.a denumerable sets) and the set $\mathbb{N}$

6. Originally Posted by Jhevon
in set theory, natural numbers are defined in terms of sets. zero is the null set, and every natural number after that is defined as the set containing all previous sets, so for instance, 1 = {0}, 2 = {0,1}, 3 = {0,1,2}, ...
You need an initial element, in this case:

$
0=\{\}=\emptyset
$

but this is not the only way to define the natural numbers, some of us prefer the Peano axioms, so in a general setting we should avoid terminology that depends on a particular means of setting up the Naturals.

CB

7. Originally Posted by CaptainBlack
but this is not the only way to define the natural numbers, some of us prefer the Peano axioms, so in a general setting we should avoid terminology that depends on a particular means of setting up the Naturals.

CB
Agree

8. Originally Posted by CaptainBlack
You need an initial element, in this case:

$
0=\{\}=\emptyset
$
yes, i mentioned that

but this is not the only way to define the natural numbers, some of us prefer the Peano axioms, so in a general setting we should avoid terminology that depends on a particular means of setting up the Naturals.

CB
indeed. i was merely explaining where Mathstud was coming from. i believe he was thinking of natural numbers in this context.

of course, i do not think that this is how the OP would have the natural numbers defined in his/her course. which is why i suggested induction in the first place, to avoid this issue altogether.

9. Originally Posted by Jhevon
yes, i mentioned that
Well I have looked at your post again and I still can't see it

CB

10. Originally Posted by CaptainBlack
Well I have looked at your post again and I still can't see it

CB
zero is the null set

The reason for the finiteness of n is that any finite set is countable
There is something disturbing me above, why wouldn't n be finite ? ^^'
If one defines a set of n elements, doesn't it mean it's finite ?
Oh right, again, it may be something related to the definition of natural numbers...

11. Originally Posted by Moo
There is something disturbing me above, why wouldn't n be finite ? ^^'
If one defines a set of n elements, doesn't it mean it's finite ?
Oh right, again, it may be something related to the definition of natural numbers...
Finite set is which is equipotent to a natural number (where the natural numbers are defined in terms of sets above).
Infinite set is not finite.

12. Originally Posted by ThePerfectHacker
Finite set is which is equipotent to a natural number (where the natural numbers are defined in terms of sets above).
Infinite set is not finite.
But n designs a natural number... ><
Nevermind

13. Hows this?

We are given that a set $A$ is countable, as well as the set $A_1=A\cup\left\{x_1\right\}$. Now let us prove that for finite $n\in\mathbb{N}$ that $A_n=A\cup\left\{x_1,x_2,\cdots,x_n\right\}$ is finite. To do this we use induction:

$\bullet$ It is given that the base case, $A\cup x_1$, is true.
$\bullet$ Now let us restate our inductve hypothesis: If $n\in\mathbb{N}$ is finite and $A$ countable then $A_n=A\cup\left\{x_1,x_2,\cdots,x_n\right\}$ is countable.
$\bullet$ We left to prove that if $A_n$ is countable then so is $A_{n+1}$. To do this we first observe that $A_{n+1}=A_n\cup\left\{x_{n+1}\right\}$. Now if $A_n$ is countably infinite this is obviously true because the cardinality of $A_{n+1}$ would be $\aleph_0+1=\aleph_0$. Now suppose that $A_n$ is finite with cardinality $m$. Then by the countability of $A_n$ we may find a bijection between the $m$th natural number and $A_n$. Let's call this bijection $f(k)$. Now it is clear then that if we define the cardinality of $A_n$ as $m$ that we can construct the following function: $g(k)=\left\{ \begin{array}{rcl} f(k) & \mbox{if} & 1\leqslant k \leqslant m\\
A_{n+1} & \mbox{if} & k=m+1 \end{array}\right.$
which is bijective. Thus we have shown that there is a bijection between the $m+1$th natural number and $A_{n+1}$, thus it is countable.

Note: The neccessity of the finiteness of $n$ is that if $n$ were infinite then $\left\{x_1,x_2,\cdots,x_n\right\}$ could be any number of uncountable sets such as the irrationals or the reals. The only way to guarantee the coutability of $\left\{x_1,x_2,\cdots,x_n\right\}$ is to restrict its cardinality.

14. ok that helps me out a lot
but im still having trouble what this means
i understand the steps to prove it
but what does it mean!?

15. Originally Posted by mathcnc
ok that helps me out a lot
but im still having trouble what this means
i understand the steps to prove it
but what does it mean!?
How do you understand the steps to prove it but don't understand it? It is basically saying that if $A$ is countable and $B$ has finite cardinality then $A\cup B$ is countable.

Page 1 of 2 12 Last