Question

Prove if A and B are countable sets then \( A \cup B \) is countable

Answer 1

countable, i believe, has certain restrictions to it such that you have a means of logically keeping track of what youve done

Answer 2

ummm Kinda but not what is needed here

Answer 3

and i have no idea how to "prove" this setup :)

Answer 4

if countable refers to finite, then maybe ....

Answer 5

Thanks :P lol not quite

Answer 6

\[\lim_{n(A)\to inf}A = N_o\]
\[\lim_{n(B)\to inf}B = N_o\]
\[C = A \cup B\]
\[\lim_{n(C)\to inf}C =\lim(A+B)=\lim A+\lim B\]
...maybe? lol

Answer 7

n(A∪B ) = n(A) + n(B) - n(A intersection B)
n(A) and n(B) are finite so n(A∪B) is finite.By the way n represents the number of elements in the set.

Answer 8

there is not restrictions given as "finite" sets

Answer 9

Its countable not necessarily finite

Answer 10

but neways i think i got the proof

Answer 11

i hope you do :) good luck with it

Answer 12

@swissgirl could you share it with us?

Answer 13

Ya sorry my tutor was here so I cldnt but now that I am free I can

Answer 14

No problem.

Answer 15

Suppose A and B are countable sets. Let \( A \cup B \) be written as \( A \cup B-A \) which is a union of disjoint sets. Since \( B-A \subset B \) then B-A is countable by Theorem 5.3.2 Every subset of a countable set is countable.

Answer 16

ok so the next part I am a bit iffy on but I am like basing it on 2 theorems

Answer 17

Therefore by Theorem 5.3.4, which states that if A is denumerable then \( A \cup \{x\} \) is denumerable and Theorem 5.3.5 Which states if A is denumerable and B is finite then \( A \cup B \) is denumerable. weather A or B is denumerable or finite doesnt affect the union of A and B and therefore \(A \cup B \) is countable

Answer 18

ok this last part sucks but i had to use these 2 theorems

Answer 19

I am still trying to

Answer 20

figure out how to clean it up

Answer 21

There is another theorem that the union of two finite sets are finite

Answer 22

and countable sets include denumerable sets and finite sets. So in any case if its denumerable or finite or both the union of A and B will still be countable

Answer 23

ok its not soo clear idkk

Answer 24

KG can you help me put this proof together?

Answer 25

So you know that every subset of a countable set is countable correct?

Answer 26

ya its a theorem in my book

Answer 27

So really, we just need to show that \(A+B\) is countable where \(A+B\) is a multiset that may contain repetitions of elements. It is obvious that \(A\cup B\subseteq A+B\), so if we show \(A+B\) is countable it follows that \(A\cup B\) is countable.

Answer 28

i guess we can prove it like that. My textbook wanted me to prove using these 2 theorems but I guess we can just trash it

Answer 29

Wait, what are the two theorems? They might make it simpler.

Answer 30

Therefore by Theorem 5.3.4, which states that if A is denumerable then A∪{x} is denumerable and Theorem 5.3.5 Which states if A is denumerable and B is finite then A∪B is denumerable.

Answer 31

Ignore the Theorem #s its just for my brain

Answer 32

If they just confuse u lets trash them

Answer 33

{x} is a single element set?

Answer 34

yup

Answer 35

We can ignore the first theorem, since the second theorem actually says more. So we know that \(A\cup B\) is countable if B is finite. We just have to prove that it's still countable if \(B\) is infinite.

I think I have a better method rather than using multisets.

Answer 36

well wait like there are two options if its countable. It can either be finite or denumerable

Answer 37

So if A and B are both finite then \( A \cup B \) is finite by some theorem i saw in my book

Answer 38

If A is finite and B denumerable then \( A \cup B \) is denumerable by this theorem here

Answer 39

If and B are denumerable and countable then \( A \cup B \) is denumerable and countable by one of these theorems that i stated above

Answer 40

Since \(B\) is countable, it is the union of a countable number of finite, disjoint sets. Thus, we write \(B=B_1\cup B_2\cup B_3\cup...\). Each of these \(B_i\) is finite. Now, we look at \[\begin{align} A\cup B&=A\cup(B_1\cup B_2\cup B_3\cup...) \\ &=(A\cup B_1)\cup(B_2\cup B_3\cup...)\end{align}\]We can do this because union is transitive.

Notice that \(A\cup B_1=A_1\) is countable because \(B_1\) is finite. In general, call \(A\cup B_1\cup B_2\cup...\cup\; B_n=A_n\). Notice that \(A_n\) is countable because we have added a finite number of elements. Finally, notice that \(A_{n+1}\) is countable as well since \(B_{n+1}\) is finite, and \(A_n\) is countable. By induction, \(A\cup B\) is countable.

Answer 41

btw like countable implies that it can be finite or denumerable

Answer 42

This proof is assuming both \(A\) and \(B\) are denumerable.

Answer 43

yuppp okk i seee that, spoke too fast

Answer 44

hahah u took a totally diff approach

Answer 45

How were you able make the union equal A?
\( A \cup B_1 = A_1\)

Answer 46

I just let that be true. It's easier to say \(A_1\) than \(A\cup B_1\).

Answer 47

okkk I like your proof. Its clean but i am just wondering if like We can introduce another value instead of \( A_1 \) like for example \( C_1|)

Answer 48

That would work as well.

Answer 49

okkk I get it then
OK Thanks KGGGGGGGGG

Answer 50

You're welcome.

Answer 51

Wasted money on tutor that cldnt solve a thing :|
I had to teach her everything

Answer 52

That's unfortunate :(

Answer 53

Alrighty Thhhhaankksss seriousllly

Answer 54

You're welcome :)