Homework Help: Basic Modern Algebra Proof

1. The problem statement, all variables and given/known data Let [itex] X = \{0,1 \} [/itex] and let [itex] Y =\{a, b, c\} [/itex] (where we assume that [itex] a, b, c [/itex] are three distinct elements of [itex]Y[/itex] .

(i) Write down all functions from [itex]X[/itex] to [itex]Y[/itex] , by writing down the set of all subsets of [itex] X \times Y [/itex] which are the graphs of the corresponding functions. How many functions are there? How many are injective? How many are surjective? Bijective? For each function [itex] f [/itex] find the image [itex] f(X)[/itex] the preimage [itex]f^{-1} (\{a,c\}) [/itex]; the preimage [itex]f^{-1}(a)[/itex].

(ii) Write down all functions from [itex]X[/itex] to [itex]Y[/itex] , by writing down the set of all subsets of [itex] X \times Y [/itex] which are the graphs of the corresponding functions. How many functions are there? How many are injective? How many are surjective? Bijective? For each function [itex] g[/itex], find: the image [itex]g(Y)[/itex]; the preimage [itex] g^{-1}(\{1\}) = g^{-1}(1).[/itex]


2. Relevant equations



3. The attempt at a solution

Part i)
Ok, so I just started class and I'm not very familiar with the wording of this or what I'm supposed to do. I started thinking like this:

[itex] \{f: X \rightarrow Y | \forall x \in X, \exists y \in Y: f(x) =y \}[/itex] But I don't really think that I'm saying anything with that... Nor do I know if I'm even working towards the right sort of answer.

As for how many are there? Well, I figured I could just count. The first element of [itex] X [/itex] can map to the first element of [itex] Y [/itex], then the second element of [itex] X [/itex] can then map to the first as well, or the second, or third. So three options. Similarly, the first element of [itex] X [/itex] can map to the second element of [itex] Y [/itex], but there are still 3 options for the second element of [itex] X [/itex]. And again you have three options if the first element maps to the third element. So 9 options. I figured it was easy enough to count, though I think mathematically it would be [itex] \# Y^{\#X} [/itex] or in this case [itex] 3^2= 9 [/itex]. I think?

None of the functions can be surjective because since the cardinality of [itex]X[/itex] is bigger than [itex]Y [/itex] not every element can be mapped to.

For Injective, the domain can only map to the same element in [itex]Y [/itex] 3 times, and since there are 9 total functions, 6 must be injective?

None are bijective because their cardinalities are different.

I don't know if those are rigorous enough proofs. I'd like to hold off on the rest until I'm sure I'm doing the first parts right. So thanks for any help!

 

Ok, so I started over. I wrote out all the ordered pairs from [itex] X \times Y [/itex]. Then I wrote out every function, ie [itex] f_1= \{(0,a),(1,a)\} \ , \ f_2= \{(0,a),(1,b)\}...[/itex] etc. Then I just individually answered whether each function was surjective, injective, bijective individually.

The image and pre-images were easy... I think. For example [itex] Imf_1= \{a\} , f^{-1}_1(\{a,c\})= \{0,1\} , f^{-1}_1(\{a\})= \{0,1\} , Imf_2= \{a,b\} , f^{-1}_2 (\{a,c\})= \{0\}, f^{-1}_2(\{a\})= \{0\}..... [/itex] so on.

If that's all right, I basically just did the same thing for part ii, except that I got 8 possible functions. 6 are surjective, and none are injective or bijective.

 

Too easy... I thought it was a much more complicated problem.... hah.