Cardnality of Infinite Sets (4)

[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 2^c?

[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!

 

[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.

 

[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!

 

[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).

 

[kingwinner]

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).

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?

 

[Dick]

Define a new function by cases.

 

[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?)

 

[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.

 

[kingwinner]

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.

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?

 

[Dick]

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?

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

 

[kingwinner]

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

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...

 

[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.

 

[kingwinner]

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

 

[Dick]

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

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

 

[kingwinner]

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

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?

 

[Dick]

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?

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.

 

[kingwinner]

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.

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...

 

[Dick]

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...

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

 

[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.

 

[kingwinner]

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.

For your simplified problem,

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...

 

[Dick]

2^|N|=2^(aleph_0) IS the power set P(N). It's c. I'm not in your class, so I'm not sure how you showed it. One common way is just to say that it corresponds to binary expressions for the reals in [0,1]. Did you do it that way? BTW my problem is not very much simplified. It's almost the same as yours.

 

[Vid]

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...

2^aleph_o is c. That's a pretty fundamental fact you should have proven before moving on to these other things.

 

[kingwinner]

2^|N|=2^(aleph_0) IS the power set P(N). It's c. I'm not in your class, so I'm not sure how you showed it. One common way is just to say that it corresponds to binary expressions for the reals in [0,1]. Did you do it that way? BTW my problem is not very much simplified. It's almost the same as yours.

Yes, we did the proof that |P(N)|=c by comparing with sequences in 0 and 1.

I am pretty sure that the cardinal number 2^(aleph_0) is never mentioned in my class, but let me accept the definition that |P(N)|=2^(aleph_0).

If there are 2 elements in the codmain, we can map it with P(N).

Back to 1), if there are 3 elements in the codmain, which power set should I map it with?

 

[Dick]

Yes, we did the proof that |P(N)|=c by comparing with sequences in 0 and 1.

I am pretty sure that the cardinal number 2^(aleph_0) is never mentioned in my class, but let me accept the definition that |P(N)|=2^(aleph_0).

If there are 2 elements in the codmain, we can map it with P(N).

Back to 1), if there are 3 elements in the codmain, which power set should I map it with?

How did you make a correspondence between sequences of 0's and 1's with the reals? If it's a representation of the reals in base 2, then for three elements, make a correspondence with the elements of the reals in base 3. 2^|N| is the set of maps from a set with the cardinality of N to {0,1}. The cardinality of N is aleph_0. You really don't have to trust me on this, you know it.

 

[Vid]

|P(S)| = 2^(|S|) for any set S. This comes directly from the property you mentioned, that there is always a bijection between P(S) and the set of functions from S into {0,1}.

 

[kingwinner]

1) So I think the answer is 3^|N|, but |N| is not really a number, so I am still having a little trouble understanding this notion, do we just pretend |N| is a number and generalize the results of finite sets to infinite sets? Is this just a symbolic thing?

Furthermore, what does 3^|N| mean? The question is answering for one of the 3 choices: |N|, c, 2^c, but 3^|N| is none of the above...

 

[Dick]

3^|N| means the cardinality of the set of mappings from a set with cardinality N to a set of cardinality 3. That's all. It's not mysterious. 3^|N| is equal to one of your choices. Which one? You still didn't answer my question. How did you prove 2^N=c?

 

[kingwinner]

Proof of |P(N)|=c:

U={{s1,s2,s3,...}|si=0 or 1}
To each sequence in U, let it correspond to the subset of N consisting of {j|sj=1}
e.g.{1,1,0,1,1,...} <-> {1,2,4,5,...}
So |P(N)|=|U|


To each sequence in U, let it correspond to 0.s1s2s3... E [0,1]
=>|U|<|[0,1|=c
Write numbers in [0,1] as binary decimials => c=|[0,1]|<|U|

Thus |P(N)|=c



But 3^|N| = ?

 

[Dick]

That's what I thought. Think about writing the numbers in [0,1] as ternary decimals (base 3).

 

[kingwinner]

Let V={{s1,s2,s3,...}|si=0 or 1 or 2}
By ternary decimals..., |V|=|[0,1|=c

How about the analogous proof of |P(N)|=|U|? What should we do in this case? Correspond V with which set?

 

[Dick]

After all of these questions, you still can't think of a way to make a correspondence between ternary number is [0,1] and maps from N to {1,2,7} without posting a question and then waiting around for someone to tell you?

 

[kingwinner]

V={{s1,s2,s3,...}|si=0 or 1 or 2}
To each sequence in V, let it correspond to the subset of N consisting of {j|sj=2}
e.g.{1,2,0,1,2,...} <-> {2,5,...}

|V|=|P(N)|=c

But this only shows 2^|N|=c

 

[Dick]

V={{s1,s2,s3,...}|si=0 or 1 or 2}
To each sequence in V, let it correspond to the subset of N consisting of {j|sj=2}
e.g.{1,2,0,1,2,...} <-> {2,5,...}

|V|=|P(N)|=c

But this only shows 2^|N|=c

Sigh. If you meant e.g. {1,2,0,1,2,..}<->{2,7,1,2,7,..}. Yes. No, it DOESN'T show 2^|N|=c. Why would it show that? What does it show?

 

[kingwinner]

Sigh. If you meant e.g. {1,2,0,1,2,..}<->{2,7,1,2,7,..}. Yes. No, it DOESN'T show 2^|N|=c. Why would it show that? What does it show?

OK, I think I get the overall argument:

|{f| f: N -> {1,2,7} }|
=|{sqeuences of 1,2,7}|
=|{sequences of 0,1,2}|
=|{ternary decimals in [0,1]}|
=|[0,1]|
=c

I know this is easy for you, but not so for a student with only a 2-lecture intro to this topic without many practical examples. Thanks for your patience!

 

[Dick]

That's it exactly. You're welcome!