Topology question: finite sets

[zfolwick]

Homework Statement

If A and B are finite, show that the set of all functions f: A --> B is finite.

Homework Equations

finite unions and finite caretesian products of finite sets are finite

The Attempt at a Solution

If f: A -> B is finite, then there exists m functions f_m mapping to B. Let B_m = {f₁, f₂, ... , f_m: f_x(A) [itex]\in[/itex]B [itex]\forall[/itex] x[itex]\in[/itex] Z+}. There is a bijection from B_m to Z+ and g: B_m -- {1,. .. ,m} so the set of functions is finite.

I don't feel like this is enough. Could I get a little help? Thanks

 

[Dick]

It's not so much 'not enough' as just plain confusing. Let a be the number of elements in A and b be the number of elements in B. How many functions from A->B? You can just count them. Suppose a=2 and b=3? How many functions in that case?

 

[zfolwick]

do you mean if the cardinality of A is 2 and the cardinality of B is 3?

 

[SammyS]

do you mean if the cardinality of A is 2 and the cardinality of B is 3?

Yes. That's what Dick said.

 

[nickalh]

In my opinion, Dick has started an excellent method to learn how this works. Start there & understand where that's going thoroughly, then digest my post.

I used to get points taken off for things like notation which assumes m is finite.

Possible Workarounds,
A. there exists m functions, m is possibly infinite, f_m ...
B. restructure the proof, without using notation which implies m is finite, until finiteness is established.


One key, how does the Cartesian product of A & B, written A x B relate to the number of possible functions?

Minor point: in Dick's example, a=2, b=3, none of the functions will be onto. One might be tempted to use factorials, nCr or nPn, but those are only in the right subject area, not what we actually need.

 

[zfolwick]

"One key, how does the Cartesian product of A & B, written A x B relate to the number of possible functions?"

A x B must be countable since A and B are finite and countable. A x B must be finite.

Then the set F = {f: A -->B} can be injectively mapped to the integers to get {(a, f(a)), (b,f(b)), (c,f(c)),...}. Then since A = {a1, a2, a3,... , a_m}, then B=(f(a1), f(a2), ...f(a_m)} is finite.
But that isn't what I was looking for... :-\

the NUMBER of functions mapping A to B is finite. If cardinality of A is 2 and the cardinality of B is 3, then the number of different mappings should be "2 choose 3" right? so then if the cardinality of A is m and cardinality of B is n then the number of different ways should be "m choose n"? (I can't find the proper latex commands).

Is this just about right?

 

[nickalh]

Actually 2 choose 3, written ₂C₃ = 0.
Perhaps you meant ₃C₂ =3
At first I was tempted to use 3 choose 2, but the right formula is even simpler. If necessary, write out the various possible functions from A to B. For simplicity, let 1,2,3 be in A, and e,f be in B.
Have you included {(1,e), (2,e), (3,e)}?

 

[zfolwick]

thanks for the notation correction nickalh. I was assuming that the cardinality of A is 2 and the cardinality of B is 3, not the other way around (based on what dick said in post 2). But you're quite correct... now I'm confused... perhaps the combinatorics only works for injective functions?

Either way, the number of functions mapping a 3 element set to a 2 element set appears to be ₃C₂ = 3

 

[nickalh]

Whoops, I switched the cardinalities of A & B.
I have rewritten my previous post to be consistent with the rest of the thread.

At first I was tempted to use 3 choose 2, but the right formula is even simpler. If necessary, write out the various possible functions from A to B. For simplicity, let 1,2 be in A, and e,f,g be in B.
Have you included {(1,e), (2,e)}?
And ₃C₂ is *not* what we want.

To help clear up your confusion:
i. For f(1) how many possible choices are there?
ii. For f(2) how many possible choices are there?
(injectivity is not required unless that was left out of the original problem statement)
iii. Multiply the answer for i. * answer for ii.

Off the top of my head, I believe ₃C₂ is right for injective, 1 to 1, functions.Unrelated tangent:
Also, pretend for a moment we needed ₃C₂.
To get around the ₂C₃ dilemna, I would define a new piecewise function, C'.
C'(m,n) = _mC_n if m>=n
_nC_m if m<n
Why can we swap m & n so easily? Because | A X B | = |B X A|.
Does anyone know how to display piecewise functions on this board?