Cardnality of Infinite Sets (4)

1. May 2, 2008

kingwinner

I am trying to get some practice on this topic by looking at past exams, but I am completely stuck at the following:

1) Let N={natural numbers}. What is the cardnality of the set of all functions from N to {1,2,7}, |N| or c or 2c?

[attempt: If it's the other way around, i.e. {all functions from {1,2,7} to N}, then I know that it has cardnality |NxNxN|=|N|]

2) Assume that |A1|=|B1| and |A2|=|B2|.
2a) Prove that |A1 x A2| = |B1 x B2|.
2b) If A1 is disjoint from A2 and B1 is disjoint from B2, then |A1 U A2|=|B1 U B2|.

[attempt: |A1|=|B1| means there exsits f: A1->B1 that is one-to-one and onto]

Can someone give me some general hints on these questions, please? Any help would be greatly appreciated!

2. May 2, 2008

Dick

Those aren't 'attempts'. The first one just says you could solve it if it were a different problem (without even trying to solve the given one) and the other one is just a definition. You've asked dozens of question on this subject over the last week or so, try and show you've learned something.

3. May 2, 2008

kingwinner

2a) f:A1->B1
f(a1)=b1 bijection

g:A2->B2
g(a2)=b2 bijection

Define h: A1xA2->B1xB2
h(a1,a2)=(b1,b2)
Then h would be a bijection (one-to-one and onto) and we're done, right?

1) 2b) No clue and I can't even find a starting point. General hints would be appreicated!

4. May 2, 2008

Dick

Yes. You are done with 2a). That wasn't so bad, was it? If x is in the union of A1 and A2 then it's either in A1 or it's in A2, but not both since they are disjoint. So you can use either f or g (that you defined for 2a)) to map it into B1 union B2. It's no more complicated than 2a).

5. May 2, 2008

kingwinner

But to prove that|A1 U A2|=|B1 U B2|, I need a single function F: A1UA2 -> B1UB2 that is 1-1 and onto. f and g may be unrelated, how can I combine f and g into one function?

6. May 2, 2008

Dick

Define a new function by cases.

7. May 2, 2008

kingwinner

But how?

Let b1 E B1, b2 E B2

F: A1UA2->B1UB2
F(x)=b1 if x E A1
F(x)=b2 if x E A2

Would this work? (bijection?)

Last edited: May 2, 2008
8. May 2, 2008

Dick

Yes. Exactly like that. But put union instead of cross product. And I would put F(x)=f(x) and F(x)=g(x) with f and g defined as in 2a). You tell me if it's a bijection.

9. May 2, 2008

kingwinner

I think putting
F(x)=f(x)
F(x)=g(x)
is a very good idea

Since f, g are onto, F must be onto

f, g are 1-1 + disjoint => F is 1-1 ?? How can I prove this more rigorously?

10. May 2, 2008

Dick

The same way you usually prove a function is 1-1 or onto. Show me how.

11. May 2, 2008

kingwinner

f is 1-1 iff f(x)=f(y) always implies x=y

To prove f is 1-1:
Suppose f(x)=f(y)
Must show that this implies x=y

But here in our case,
F(x)=F(y) => ???

I've never encountered a problem on proving a "piecewise" function is 1-1 so far...

12. May 2, 2008

Dick

Keep going. F(x)=F(y) is an element of B1 union B2. So it's either in B1 or B2 but not both. Split into cases.

13. May 2, 2008

kingwinner

Are they both in B1? B2? or one in B1 and the other in B2?

14. May 2, 2008

Dick

F(x)=F(y). There's only ONE of 'them'.

15. May 2, 2008

kingwinner

But two different elements in the domain may be mapped to the same element in the codomain

If A1 is disjoint from A2 and B1 is disjoint from B2, why does this imply F defined above is one-to-one? What is going to change if the sets are not disjoint?

Last edited: May 2, 2008
16. May 2, 2008

Dick

A lot will change if they aren't disjoint. But that's not the problem you are working on. Don't get distracted. Under the conditions given, two different elements in the domain are NOT mapped to the same element in the codomain. That's what you are trying to prove. And I am not going to prove it for you.

17. May 2, 2008

kingwinner

F: A1UA2->B1UB2
F(x)=f(x) if x E A1
F(x)=g(x) if x E A2

If F(x)=F(y) is in B1
=> F(x)=f(x)=f(y)=F(y) ??
=> x=y since f is 1-1 ??

Similarly for B2...

18. May 2, 2008

Dick

Exactly. Again, not so hard, yes? Nicely done. And it's pretty much the same thing for onto.

Last edited: May 2, 2008
19. May 2, 2008

Dick

And since you did so well on that one, finally. I'll give you a free hint. On the first problem suppose it were, what's the cardinality of the set of maps from N->{0,1}? Isn't that 2^N? No extra charge.

Last edited: May 2, 2008
20. May 2, 2008

kingwinner

Let T={f|f: N->{0,1} }
T <-> {characteristic function of subsets of N} <-> {all subsets of N} <-> {power set of N}=P(N)
(<-> means a bijection exists)

And it's proven in my class that |P(N)|=c, so |T|=c. So I think I have a solid strategy for your simplified problem, but when one more element is added to the codmain, everything screws up...

I am not too sure about the meaning of 2^(aleph_0)...what is it?
The only cardinal numbers discussed in my class are aleph_0, c, 2^c, 2^(2^c), etc...

Last edited: May 2, 2008