- #1

- 10

- 0

## Homework Statement

Let A = {1, 2, 3, 4} and let F be the set of all functions from A to A. Let R be the relation on F defined by:

For all functions f, g that are elements of F, (f, g) are only elements of R if and only if f(i) = g(i) for some i that is an element of A.

Let the functions α, β be elements of F, defined by α(i) = 1 and β(i) = 2, where i is an element of A.

a) How many functions f that are elements of F are there so that (f, α) is an element of R?

b) How many functions f that are elements of F are there so that (f, α) or (f, β) is an element of R?

c) How many functions f that are elements of F are there so that (f, α) and (f, β) is an element of R?

## Homework Equations

## The Attempt at a Solution

The one I'm having the most trouble with is b), but I use some numbers from part a so I just wanted to double check that.

To solve a, all I did was take the total number of functions from set A to A, which is 4^4 (each element has four choices as an output), and subtract that by the number of functions that do not output A, so 3^4. I get 175 functions that have some f(i) = 1.

For part B, so far I have figured out that I need to use the union equation that is used in statistics:

P(A U B) = P(A) + P(B) - P(AB)

However, I'm missing some method to solve for P(AB). So far, I have P(A U B) = 175 * 2 - P(AB), since the number of functions that output 1 is the same as the number of functions that output 2. Any assistance would be greatly appreciated. Thank you in advance.

Also, I solved part c by subtracting the number of functions that don't output 1 or 2 from the number of total functions, so 4^4 - 2^4 (since all four inputs can't map to 1 or 2, they can only map to 3 or 4).