- #1
Gale
- 676
- 2
Homework Statement
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] find 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], find: the image [itex]g(Y)[/itex]; the preimage [itex] g^{-1}(\{1\}) = g^{-1}(1).[/itex]
Homework Equations
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!