1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Basic Modern Algebra Proof

  1. Sep 6, 2012 #1
    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!
     
  2. jcsd
  3. Sep 6, 2012 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Why don't you start by first listing all the pairs of ##X\times Y##? Then literally list the subsets of that that represent the 9 (you are correct, there are 9) functions as it asks you to do. That will make it easy to answer all the parts of (i). Then you can start on (ii).
     
  4. Sep 7, 2012 #3
    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.
     
    Last edited: Sep 7, 2012
  5. Sep 7, 2012 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Looks good. Makes it easy, eh?
     
  6. Sep 7, 2012 #5
    Too easy... I thought it was a much more complicated problem.... hah.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Basic Modern Algebra Proof
Loading...