# Topology question: finite sets

1. Jul 20, 2011

### zfolwick

1. The problem statement, all variables and given/known data
If A and B are finite, show that the set of all functions f: A --> B is finite.

2. Relevant equations
finite unions and finite caretesian products of finite sets are finite

3. The attempt at a solution
If f: A -> B is finite, then there exists m functions fm mapping to B. Let Bm = {f1, f2, ... , fm: fx(A) $\in$B $\forall$ x$\in$ Z+}. There is a bijection from Bm to Z+ and g: Bm -- {1,. .. ,m} so the set of functions is finite.

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

1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Jul 20, 2011

### 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?

3. Jul 21, 2011

### zfolwick

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

4. Jul 21, 2011

### SammyS

Staff Emeritus
Yes. That's what Dick said.

5. Jul 22, 2011

### 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, fm ...
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.

6. Jul 23, 2011

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

7. Jul 23, 2011

### nickalh

Actually 2 choose 3, written 2C3 = 0.
Perhaps you meant 3C2 =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)}?

8. Jul 23, 2011

### 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 3C2 = 3

9. Jul 23, 2011

### 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 3C2 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)

Off the top of my head, I believe 3C2 is right for injective, 1 to 1, functions.

Unrelated tangent:
Also, pretend for a moment we needed 3C2.
To get around the 2C3 dilemna, I would define a new piecewise function, C'.
C'(m,n) = mCn if m>=n
nCm 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?

Last edited: Jul 23, 2011