• Support PF! Buy your school textbooks, materials and every day products Here!

Basic Modern Algebra Proof

  • Thread starter Gale
  • Start date
  • #1
658
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] 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]


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!
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
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).
 
  • #3
658
2
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).
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:
  • #4
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
Looks good. Makes it easy, eh?
 
  • #5
658
2
Looks good. Makes it easy, eh?
Too easy... I thought it was a much more complicated problem.... hah.
 

Related Threads for: Basic Modern Algebra Proof

Replies
2
Views
316
Replies
5
Views
2K
Replies
22
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
2
Views
861
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
2K
Top