x Turn on thread page Beta
 You are Here: Home >< Maths

# A question about composite functions watch

1. Question 3 on this problem sheet is probably a good one to go through to check you understand the words function, composition, injection surjection etc. The sheet also contains some questions on induction (questions 6 and 8) and basic set theory (question 2).

I think if you work through these you'll definitely have a better understanding of these topics (although they're all perhaps slightly harder than A level).

http://www.dpmms.cam.ac.uk/site2002/...-2009/N+S1.pdf
2. I would also (rather mysteriously, so as not to give away the point of the question) recommend Q7 on that sheet.
3. hhmmm - many of the things here are simply definitions and I don't see alot of theory (or any at all) in your OP or thereafter. If you would like to get an idea of what set theory is this is an amazing book;

http://www.amazon.co.uk/gp/product/0...ref=sib_rdr_dp

4. I'm (on-and-off) reading Lawvere and Rosebrugh's Sets for Mathematics. It takes an... interesting (namely, category/topos-theoretical) approach to set theory. I'm not sure whether it's axiomatic or naïve though.
5. Yeah, I think I have changed my picture of what a function is so it makes sense. Firstly, X to Y is like putting a ball in a box but then Y to Z is like putting that box into a bigger box. If you have Y to Z and the box at Y hasen't got a ball because X to Y is not a surjection then its like putting an empty box in a bigger box at Z. Yeah, that makes sense.

On the question sheet is 8.(a) valid. Because, both sets are k elements and so by induction hypothesis the elements most equal each other, hence then the and argument. Base case is trivially true. I don't see whats wrong with the proof.

3. I have done most of the proofs from a book about composite functions and injections. But, not about surjection.

I was thinking of learning set theory as I got a book called axiomatic set theory which says you don't need to know much about set theory or logic to learn the material in it. Ordinal arithmetic looks fun and I always wanted to know the fuss about axiom of choice however laziness. Plus, analysis would seem more useful to learn.
6. (Original post by Simplicity)
On the question sheet is 8.(a) valid.
Well, do you think all positive integers are equal?

I don't see whats wrong with the proof.
Then you're not paying attention to the details in it.

Spoiler:
Show
You might also want to think about specific (small) cases.
7. (Original post by DFranklin)
Well, do you think all positive integers are equal?
Maybe, maths is inconsistent. I will read it again. Oh yeah, it is saying that. I thought it was saying you can have a set n which contains the same element, but I guess there is an axiom in set theory that stops this.

(Original post by DFranklin)
Then you're not paying attention to the details in it.
Well, if you have set n=1 {x,}. But, then that would mean {x}={}. So x must not be an element. Hence, base case=fail.

I think thats valid since for all non-empty set A.
8. (Original post by Simplicity)
Well, if you have set n=1 {x,}. But, then that would mean {x}={}.
You seem to be trying to put two elements into your 1-element set there, but one of them is 'empty'. It doesn't work like that. The set is {x}. It is true that x is equal to itself - so don't look for a contradiction here.
9. (Original post by generalebriety)
You seem to be trying to put two elements into your 1-element set there, but one of them is 'empty'. It doesn't work like that. The set is {x}. It is true that x is equal to itself - so don't look for a contradiction here.
Okay. I was thinking a property of sets is that {1,2,2,3,4}={1,2,3,4}, I think.

So if then the set is

Is this right?
10. (Original post by Simplicity)
Okay. I was thinking a property of sets is that {1,2,2,3,4}={1,2,3,4}, I think.

So if [latex]x_1=x_2=x_3...=x_k[latex] then the set is

Is this right?
I see your point, I'm not sure precisely what you're contradicting. Are you contradicting the statement of the question? Either way, you're missing the point. There is a problem with the induction, and it's that problem that you're required to find.
11. (Original post by generalebriety)
I see your point, I'm not sure precisely what you're contradicting. Are you contradicting the statement of the question? Either way, you're missing the point. There is a problem with the induction, and it's that problem that you're required to find.
I guess it will be this therefore , as this can't be deduced from the induction hypothesis. As the induction hypothesis only says if you have a set size n=k and
12. (Original post by Simplicity)
I guess it will be this therefore , as this can't be deduced from the induction hypothesis.
Of course it can, it's a set of size <= k.

Think again.
13. (Original post by generalebriety)
Of course it can, it's a set of size <= k.

Think again.
Is it that it applies to set n=k+1. You know it applies to set n=k. But, then you can't conclude from the two sets that because they are in different sets.

The person hasen't shown that it applies to a set of size n=k+1. He has just shown that if you have to sets of n=k then both are equal from the induction hypothesis. But, then you can't conclude from that this applies to n=k+1.

Something along that line.
14. (Original post by Simplicity)
Is it that it applies to set n=k+1. You know it applies to set n=k. But, then you can't conclude from the two sets that because they are in different sets.

The person hasen't shown that it applies to a set of size n=k+1. He has just shown that if you have to sets of n=k then both are equal from the induction hypothesis. But, then you can't conclude from that this applies to n=k+1.

Something along that line.
The proof says that you can deduce that x_1 = x_2 = ... = x_k, and that x_2 = ... = x_k = x_(k+1). Looks like they're all equal to me.

Here's a hint. Think about how the induction actually works. Once you know it's true for n = 1, what does your inductive step prove?
15. (Original post by generalebriety)
The proof says that you can deduce that x_1 = x_2 = ... = x_k, and that x_2 = ... = x_k = x_(k+1). Looks like they're all equal to me.

Here's a hint. Think about how the induction actually works. Once you know it's true for n = 1, what does your inductive step prove?
Inductive step proves that n=k implies n=k+1.

So I think the mistake is going from to as this hasen't been shown for a set n=k+1.
16. (Original post by Simplicity)
Inductive step proves that n=k implies n=k+1.
More concretely? When we know the statement is true for n=1, what's the first thing our inductive step proves?
17. (Original post by generalebriety)
More concretely? When we know the statement is true for n=1, what's the first thing our inductive step proves?
That its true for n=k then its true for n=k+1. I don't know do I have to bring the fact that its natural numbers into this. Bigger hint?
18. (Original post by Simplicity)
That its true for n=k then its true for n=k+1. I don't know do I have to bring the fact that its natural numbers into this. Bigger hint?
I think I might just be confusing you. Suppose you've proven it for n=1, then proven that true for n=k => true for n=k+1. Then, because it's true for n=1, you immediately know it's true for n=2.

Have a look at the case n=2, see what that tells us.
19. (Original post by generalebriety)
I think I might just be confusing you. Suppose you've proven it for n=1, then proven that true for n=k => true for n=k+1. Then, because it's true for n=1, you immediately know it's true for n=2.

Have a look at the case n=2, see what that tells us.
So if n=1, then by induction n=2. So is size 2, but x_1=x_2 so, so this size of this set is 1, which is a contradiction because 1 doesn't equal 2.

Is this it?
20. (Original post by Simplicity)
So if n=1, then by induction n=2. So is size 2, but x_1=x_2 so, so this size of this set is 1, which is a contradiction because 1 doesn't equal 2.

Is this it?
You're not thinking at all. Look at how the inductive step takes us from n = 1 to n = 2. I can't give you a bigger hint than that.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 26, 2009
Today on TSR

### I've studied the wrong subject

...Should I go back to school?

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams