Set Theory: Proving h is Surjective Implies f & g

In summary: It's easy to show that f is not necessarily surjective: just take any function f that is not onto and let g be the identity function Z-->Z. Then h is the function that is not onto.In summary, the given conversation discusses the functions f: X ----> Y and g: Y ----> Z and their composition h = g o f: X ----> Z. The homework equations state that if h is surjective, then both g and f are surjective. The proof for a) shows that if h is surjective, then g is also surjective. For b), it is suggested to try disproving the statement, which can be done by taking a non-surjective function f and letting g
  • #1
BubblesAreUs
43
1

Homework Statement


Let

f: X ----> Y and g: Y ----> Z

be functions and let

h = g o f: X ----> Z

Homework Equations



a. If h is surjective then g is surjective

b. If h is surjective then f is surjective.

The Attempt at a Solution



Here

h: X ----> Z

a.
Suppose h: x ---> z is surjective for ∈ Z. Since h is surjective ∃a ∈ X such that
h(a) = g(f(a)) = k

Now let y = f(a) ∈ Y so...
g(y) = g(f(a)) = k; as declared QED.

b.
Suppose h: x ---> z is surjective for y...I'm not even sure how to start.

PS: To be honest, I really need to find a good textbook on proofs because my lecturer is outright atrocious. If anyone knows of any texts, do post me some recommendations as well.
 
Physics news on Phys.org
  • #2
BubblesAreUs said:

Homework Statement


Let

f: X ----> Y and g: Y ----> Z

be functions and let

h = g o f: X ----> Z

Homework Equations



a. If h is surjective then g is surjective

b. If h is surjective then f is surjective.

The Attempt at a Solution



Here

h: X ----> Z

a.
Suppose h: x ---> z is surjective for ∈ Z. Since h is surjective ∃a ∈ X such that
h(a) = g(f(a)) = k

Now let y = f(a) ∈ Y so...
g(y) = g(f(a)) = k; as declared QED.

b.
Suppose h: x ---> z is surjective for y...I'm not even sure how to start.

PS: To be honest, I really need to find a good textbook on proofs because my lecturer is outright atrocious. If anyone knows of any texts, do post me some recommendations as well.

Your proof of a) looks quite good. You didn't say what k is, but it's fairly obvious.

Why do you think b) is true?
 
  • Like
Likes BubblesAreUs
  • #3
k is just an integer that belongs to set Z.

As for b, I think f is surjective because h is. Since f is an input of g, I'm not exactly sure how I can re-utilise my proof from part a.
 
  • #4
BubblesAreUs said:
k is just an integer that belongs to set Z.

As for b, I think f is surjective because h is. Since f is an input of g, I'm not exactly sure how I can re-utilise my proof from part a.

If I can't see how to prove something, I usually try to disprove it and see what happens.
 

1. What is set theory?

Set theory is a branch of mathematics that deals with the study of sets, which are collections of objects. It is used to understand the relationships between different sets and how they can be manipulated and combined to form new sets.

2. What does it mean for a function to be surjective?

A function is surjective if every element in the codomain (the set of all possible output values) is mapped to by at least one element in the domain (the set of possible input values). In other words, every element in the codomain has a corresponding input value.

3. How does proving h is surjective imply f & g?

If h is surjective, it means that every element in the codomain of h is mapped to by at least one element in the domain of h. This means that for any element in the codomain of h, we can find a corresponding input value in the domain of h. Since f and g are both functions that operate on the same sets as h, this also means that f and g must also be surjective. This is because if f and g were not surjective, there would be elements in their codomains that are not mapped to by any element in their domains, which would contradict the fact that h is surjective.

4. What is the significance of proving surjectivity in set theory?

Proving surjectivity in set theory is important because it allows us to understand the full range of a function. It ensures that every element in the output set is actually reached by the function, and it also helps us to determine whether a function is invertible (able to be reversed). Additionally, surjectivity is a key concept in many other areas of mathematics, such as topology and algebra.

5. What are some common methods for proving surjectivity in set theory?

There are several methods for proving surjectivity in set theory, including direct proof, proof by contradiction, and proof by exhaustion. In a direct proof, we show that for every element in the codomain, there exists at least one element in the domain that maps to it. In a proof by contradiction, we assume that the function is not surjective and then show that this leads to a contradiction. In a proof by exhaustion, we systematically show that every element in the codomain is mapped to by at least one element in the domain.

Similar threads

Show injectivity, surjectivity and kernel of groups
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
2
Views
283
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
512
Having all subgroups normal is isomorphism invariant
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Injective & Surjective Functions
    • Calculus and Beyond Homework Help
Replies
9
Views
2K
Prove ##(a+b) + c = a + (b+c)## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
9
Views
1K
Prove ##(a\cdot b)\cdot c =a\cdot (b \cdot c)## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
1
Views
463
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
525
Show that if ##f:A\rightarrow B## is surjective then....
    • Calculus and Beyond Homework Help
Replies
24
Views
3K
F bijective <=> f has an inverse
    • Calculus and Beyond Homework Help
Replies
7
Views
2K

Hot Threads

Recent Insights

Back
Top