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
x
Turn on thread page Beta

Drederick Tatum
 Follow
 0 followers
 12 badges
 Send a private message to Drederick Tatum
Offline12ReputationRep: Follow
 21
 25072009 22:55

generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 22
 25072009 22:59
I would also (rather mysteriously, so as not to give away the point of the question) recommend Q7 on that sheet.

Oh I Really Don't Care
 Follow
 2 followers
 2 badges
 Send a private message to Oh I Really Don't Care
Offline2ReputationRep: Follow
 23
 26072009 02:03
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
which you can download free after looking hard enough 
 Follow
 24
 26072009 06:56
I'm (onandoff) reading Lawvere and Rosebrugh's Sets for Mathematics. It takes an... interesting (namely, category/topostheoretical) approach to set theory. I'm not sure whether it's axiomatic or naïve though.

Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 25
 26072009 14:21
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.Last edited by Simplicity; 26072009 at 14:24. 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Offline17ReputationRep: Follow
 26
 26072009 14:32
(Original post by Simplicity)
On the question sheet is 8.(a) valid.
I don't see whats wrong with the proof.
Spoiler:ShowYou might also want to think about specific (small) cases. 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 27
 26072009 14:43
(Original post by DFranklin)
Well, do you think all positive integers are equal?
(Original post by DFranklin)
Then you're not paying attention to the details in it.
I think thats valid since for all nonempty set A.Last edited by Simplicity; 26072009 at 14:47. 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 28
 26072009 18:24
(Original post by Simplicity)
Well, if you have set n=1 {x,}. But, then that would mean {x}={}. 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 29
 26072009 18:34
(Original post by generalebriety)
You seem to be trying to put two elements into your 1element 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.
So if then the set is
{x_1,x_2,...,x_k}={x_k}. So the set is size 1, instead of k, contradiction!?
Is this right?Last edited by Simplicity; 26072009 at 18:41. 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 30
 26072009 18:43
(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
{x_1,x_2,...,x_k}={x_k}. So the set is size 1, instead of k, contradiction!?
Is this right? 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 31
 26072009 19:13
(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.Last edited by Simplicity; 26072009 at 19:15. 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 32
 26072009 19:53
Think again.Last edited by generalebriety; 26072009 at 20:03. 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 33
 26072009 20:10
(Original post by generalebriety)
Of course it can, it's a set of size <= k.
Think again.
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. 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 34
 26072009 20:12
(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.
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? 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 35
 26072009 20:20
(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?
So I think the mistake is going from to as this hasen't been shown for a set n=k+1. 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 36
 26072009 20:32
(Original post by Simplicity)
Inductive step proves that n=k implies n=k+1. 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 37
 26072009 20:40
(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? 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 38
 26072009 20:48
(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?
Have a look at the case n=2, see what that tells us. 
Simplicity
 Follow
 5 followers
 15 badges
 Send a private message to Simplicity
 Thread Starter
Offline15ReputationRep: Follow
 39
 26072009 20:54
(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.
Is this it? 
generalebriety
 Follow
 15 followers
 14 badges
 Send a private message to generalebriety
 Wiki Support Team
Offline14ReputationRep:Wiki Support Team Follow
 40
 26072009 20:56
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.
Reply
Submit reply
Turn on thread page Beta
Related discussions:
 Can you answer this composite functions question?
 GCSE Maths question on composite functions
 quick composite functions question.
 C3  ocr  composite functions question help
 Composite functions....help????!!!
 Composite functions (ranges)
 Composite functions
 Integration question
 C3 Composite functions
 C3 functions question
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:
 SherlockHolmes
 Notnek
 charco
 Mr M
 TSR Moderator
 Nirgilis
 usycool1
 Changing Skies
 James A
 rayquaza17
 RDKGames
 randdom
 davros
 Gingerbread101
 Kvothe the Arcane
 TeeEff
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Labrador99
 EmilySarah00
Updated: July 26, 2009
Share this discussion:
Tweet