A.1. find the set number of possible functions from
the set A of cardinality to a set B of cardinality n
Answers
Answer:
If A and B are both finite, |A| = a and |B| = b, then if f is a function from A to B, there are b possible images under f for each element of A. By the Multiplication Principle of Counting, the total number of functions from A to B is
b x b x b x b x … x b
where b is multiplied by itself a times. Thus the total number of functions from A to B is b^a, that is |B|^|A|.
So it makes sense to use the same notation |B|^|A| to represent the cardinality of the set of all functions from one set A to another set B.
But what is the value of |B|^|A| if A and/or B is infinite?
Let’s take a look at the simplest examples — where one of A and B consists of 2 elements, and the other consists of a countably infinite set, like the set N of natural numbers.
One of those is easy: If A is a 2-element set and B = N, then |N|^|2|, the number of functions from a 2-element set to N, is just countable, since it really the same as the set of all ordered pairs of natural numbers … if we use aleph-sub-zero to refer to the cardinality of the natural numbers, then (aleph-sub-zero)^2 = aleph-sub-zero.
On the other hand: if we think of the two element set B as {0,1}, then |2|^|N| is the set of all infinite sequences of 0’s and 1’s, which is not really different from the set of all infinite sequences of numbers between 0 and 9, which is the set of all infinite decimals between 0 and 1, and that has the same cardinality as the set of real numbers R.
So |2|^|N| = |R|. You might think that the simplest infinite exponent would be aleph-sub-one, and many mathematicians tried to prove that this was so, but they failed. The statement that the first uncountable infinite cardinal is the cardinality of the real numbers is called the continuum hypothesis, where the real number line is called the continuum.
The continuum hypothesis was never proved, but Kurt Godel proved in 1940 that it was consistent with the axioms of set theory. However, in 1963 Paul Cohen proved that the continuum hypothesis was independent of the axioms of set theory. His proof of independence was first publicly announced at Cohen’s presentation on Independence Day, July 4, 1963 at Berkeley. I was there!
So we can provide notation that represents the cardinality of the set of all functions from A to B, but if either A or B is infinite, we really can’t definitely say which cardinal number |B|^|A| actually is. In some models of set theory, it may have a certain value and in other models of set theory, it may have a different value.