• Support PF! Buy your school textbooks, materials and every day products Here!

Cardnality of Infinite Sets (4)

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0
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!
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
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
1,270
0
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
Dick
Science Advisor
Homework Helper
26,258
618
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
1,270
0
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?
 
  • #6
Dick
Science Advisor
Homework Helper
26,258
618
Define a new function by cases.
 
  • #7
1,270
0
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:
  • #8
Dick
Science Advisor
Homework Helper
26,258
618
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
1,270
0
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?
 
  • #10
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #11
1,270
0
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...
 
  • #12
Dick
Science Advisor
Homework Helper
26,258
618
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
1,270
0
Are they both in B1? B2? or one in B1 and the other in B2?
 
  • #14
Dick
Science Advisor
Homework Helper
26,258
618
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'.
 
  • #15
1,270
0
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?
 
Last edited:
  • #16
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #17
1,270
0
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...
 
  • #18
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
Last edited:
  • #19
Dick
Science Advisor
Homework Helper
26,258
618
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:
  • #20
1,270
0
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...
 
Last edited:
  • #21
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
Last edited:
  • #22
Vid
401
0
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.
 
  • #23
1,270
0
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?
 
  • #24
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
Last edited:
  • #25
Vid
401
0
|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}.
 

Related Threads for: Cardnality of Infinite Sets (4)

  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
24
Views
4K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
8
Views
950
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
1
Views
1K
  • Last Post
2
Replies
29
Views
7K
Top