Manifold Posted September 17, 2004 Share Posted September 17, 2004 Hello! I've worked on a problem concerning even and odd numbers recently...sounds quite simple actually...though I'm not sure whether my (more or less formal) solution is right. It is asked to find out whether there are more even or odd numbers...The result I came to is that there is an equal number of them...How would you solve this problem? Link to comment Share on other sites More sharing options...

jordan Posted September 17, 2004 Share Posted September 17, 2004 Let's see: If I give you a number X, you could tell me that there are X positive integers less than or equal to that number. (Example: If X is 8, than there are 8 positive integers less than or equal to 8). To find all the even integers would require the formula 2Y=X. X will be the integer and Y will be the number of evens it has taken you to get there. (Example: If you want to find the 4^{th} even number, multiply 2(4) and get 8.) If we rearange the previous equation for Y, we get Y=.5X. This means that any for any number X, exactly half of the numbers below it will be even. If you'll remember, Y have been defined as the number of even integers it takes to get to the number X. Some of the more advanced math members might rip this apart later, but it took a little thinking and I believe my proof is reasonable. Either way, it was good to take a minute to think about it. I wish there were more threads about proving relatively simple stuff like this. Link to comment Share on other sites More sharing options...

bloodhound Posted September 17, 2004 Share Posted September 17, 2004 i dont know. you could probably argue that both sets have the cardinal number aleph nought. so are equal. you will have to ask MandrakeRoot or matt grime or e(hoon3. they see to be experts in set theory in here Link to comment Share on other sites More sharing options...

Manifold Posted September 17, 2004 Author Share Posted September 17, 2004 Alright...as I said my proof is a bit formal...The thing is that I'm studying set theory on my own at the moment...and that problem has been part of my work, so to speak...though I found it on another forum...I decided to take it as another exersise to test methods of set theory. The core of my solution is work with infinite sets and relations between them...I just need a check for correctness... (to be continued) Link to comment Share on other sites More sharing options...

BrainMan Posted September 17, 2004 Share Posted September 17, 2004 If you can place the sets in one-to-one correspondence with each other, then you have proven that they have the same cardinality. (I think.) All you need to provide is a function that maps one set onto the other in such a manner (one-to-one). If the sets have a different cardinality, there will be no such function. Link to comment Share on other sites More sharing options...

bloodhound Posted September 17, 2004 Share Posted September 17, 2004 a simple one to one function from odds to even would be , where n is odd. and f(n)=n+1. Link to comment Share on other sites More sharing options...

Manifold Posted September 17, 2004 Author Share Posted September 17, 2004 This should go: 1. Take the set N(2k+1)={1,3,5,...}...We construct the bijective mapping from N (N={1,2,3,...} is the set of natural numbers, =the set of positive integers, for those, who are accustomed to another terminology) into N(2k+1). By doing this we assign to each element from N an element from N(2k+1)...thus we introduced an equivalence relation between these sets. From the condition that both sets are infinite and equipollent, it follows that they possess the same number of elements, i.e. they have the same cardinality: card N=card N(2k+1); 2. Now take the set N(2k)={2,4,6,...}. We procede in the same manner...constructing the mapping and showing that card N=card N(2k); 3. We see that from card N=card N(2k+1) and card N=card N(2k) follows the fact that card N(2k+1)=card N(2k). Thus we can claim that there is an equal number of odd and even numbers. This is a more or less intuitive approach to this task...because the latter assertion in 3. should be proved strictly...and there is in fact a theorem extending the property from 3. on any set. This is the so called Schröder-Bernstein theorem: [math](cardX\le{cardY})\wedge(cardY\le{cardX}) \Rightarrow (cardX=cardY)[/math] Link to comment Share on other sites More sharing options...

bloodhound Posted September 17, 2004 Share Posted September 17, 2004 This should go:1. Take the set N(2k+1)={1' date='3,5,...}. We construct the bijective mapping from N into N(2k+1). By doing this we assign to each element from N an element from N(2k+1)...thus we introduced an equivalence relation between these sets. From the condition that both sets are infinite and equipollent, it follows that they possess the same number of elements, i.e. they have the same cardinality: card N=card N(2k+1); 2. Now take the set N(2k)={2,4,6,...}. We procede in the same manner...constructing the mapping and showing that card N=card N(2k); 3. We see that from card N=card N(2k+1) and card N=card N(2k) follows the fact that card N(2k+1)=card N(2k). Thus we can claim that there is an equal number of odd and even numbers. This is a more or less intuitive approach to this task...because the latter assertion in 3. should be proved strictly...and there is in fact a theorem extending the property from 3. on any set. This is the so called Schröder-Bernstein theorem: [math'](cardX\le{cardY})\wedge(cardY\le{cardX}) \Rightarrow (cardX=cardY)[/math] i cant believe that thas a theorem name. its just this a less than b , and b less than a implies a=b. i have seen this before for like showing that a set A=B. but can't believe a trivial thing like this should have a name Link to comment Share on other sites More sharing options...

pulkit Posted September 18, 2004 Share Posted September 18, 2004 i cant believe that thas a theorem name. its just this a less than b ' date=' and b less than a implies a=b. i have seen this before for like showing that a set A=B. but can't believe a trivial thing like this should have a name[/quote'] I find it strange that you are doing a major in maths and you haven't heard of this theorem. Its one of the first things you do when you start axiomatic set theory. Link to comment Share on other sites More sharing options...

Manifold Posted September 18, 2004 Author Share Posted September 18, 2004 i cant believe that thas a theorem name. its just this a less than b , and b less than a implies a=b. i have seen this before for like showing that a set A=B. but can't believe a trivial thing like this should have a name Well...[math](a<b)\wedge(b<a) \Rightarrow (a=b)[/math] is actually wrong, since you can't find a number that is greater and fewer than the given one at the same time...it would then hold: [math](1<2)\wedge(2<1) \Rightarrow (1=2)[/math] ...which is a double nonsense... In fact, for any x and y in R precisely one of the following holds: a) x<y, b) x=y, c) x>y Proof: Consider the axioms for the set of real numbers: 1. [math]\forall{x}\in\mathbb{R} (x\le{x})[/math], ; 2. [math](x\le{y})\wedge(y\le{x}) \Rightarrow (x=y)[/math], from this follows b)...this axiom is justified by the first one, and it is what you seem to have meant; 3. [math]\forall{x}\in\mathbb{R} \forall{y}\in\mathbb{R} (x\le{y})\vee(y\le{x})[/math], from this follows a) and c); ...the first axiom is quite tricky...in fact, [math]1\le{1}[/math] is a bit confusing at first...but it shows that what you assumed is impossible. As for the Schröder-Bernstein theorem it's not less meaningful than any other theorem...sets are objects, which are more complex than numbers...infinite sets in particular. It's more difficult to compare them with one another, than to do the same with numbers...I mean comparing the number of elements of two, their cardinality...and not showing that they are the same. For example, X is a proper subset of Y doesn't imply that the number of elements in X is less than that in Y...sometimes the converse is true...it's much more difficult to show that something like axiom 2. also holds for sets, both finite and infinite...so I think it's still meaningful to prove a theorem which backs up both cases, as in the example. Link to comment Share on other sites More sharing options...

bloodhound Posted September 18, 2004 Share Posted September 18, 2004 sorry. yeah. i should have less that equal to. i might have a look into the history of this "Theorem" then Link to comment Share on other sites More sharing options...

Manifold Posted September 18, 2004 Author Share Posted September 18, 2004 I created a new thread on this topic..."Infinite Sets and the Schröder-Bernstein Theorem"...take a look at it...I think it all needs even more discussion... Link to comment Share on other sites More sharing options...

bloodhound Posted September 18, 2004 Share Posted September 18, 2004 had a look. dont really know what u want us to discuss Link to comment Share on other sites More sharing options...

Manifold Posted September 18, 2004 Author Share Posted September 18, 2004 ...well...the actual solution... how to perform the bijection in a)...and how to justify the proof in b)...I am myself confused about all that... Link to comment Share on other sites More sharing options...

Dave Posted September 18, 2004 Share Posted September 18, 2004 I find it strange that you are doing a major in maths and you haven't heard of this theorem. Its one of the first things you do when you start axiomatic set theory. As strange as it sounds, I haven't really touched on set theory a hell of a lot, although I've heard of this particular theorem in passing. As I understand it, at my uni it's more of an advanced topic studied after the first year. I have a feeling it's going to crop up this year. Link to comment Share on other sites More sharing options...

pulkit Posted September 18, 2004 Share Posted September 18, 2004 It was a part of my first year course on metric spaces (atleast we were supposed to know the result of the theorem-not its derivation) Now in the second year its cropped up again in my discrete mathematics course.. On second thought, I can understand why you may not have heard of it, the course I did in my first year is actually a post graduate course that was only a couple of years ago included in our under graduate curriculum (and then being in comp sci meant that we had to chose the more difficult of the two maths courses on offer namely the one mentioned above) Link to comment Share on other sites More sharing options...

Dave Posted September 18, 2004 Share Posted September 18, 2004 Our course is quite a lot slower than a lot of courses I've seen, but only because we're expected to prove more or less everything we see. We start metric spaces this year, so I guess I will almost certainly be running into it. Link to comment Share on other sites More sharing options...

bloodhound Posted September 18, 2004 Share Posted September 18, 2004 Metric spaces is well cool. We didnt do it as a module. but as a topic is mathematic structures module. but its really interesting. especially convergence of sequences. and the various metrics. Link to comment Share on other sites More sharing options...

pulkit Posted September 19, 2004 Share Posted September 19, 2004 Yes its a nice topic. The fact is that it has a lot of applications in computer sciences which also why we had to do it. Its used in all sorts of places like data mining and algorithm optimization. I think one of the fastest known multiplication algorithms uses metric spaces - but thats still too complex for me to understand yet. We actually diverged to multi variable calculus towards the end of the course as well as all the stuff with Taylor and McLauren series and then weird types of integration stuff - all that I am pretty sure won't be of any use to me later on (perhaps only the Taylor series part may be useful). Link to comment Share on other sites More sharing options...

Dave Posted September 19, 2004 Share Posted September 19, 2004 This year just gone, we mainly concentrated on fields, diverging off to matrices and various other bits and pieces along the way. I found that incredibly interesting, so maybe the metric spaces stuff will be good. This year we're getting into the nitty gritty of multivariate analysis and integration. If anyone's actually interested in what I'm doing, you have have a look here - in the second year section. Link to comment Share on other sites More sharing options...

pulkit Posted September 20, 2004 Share Posted September 20, 2004 Do you have trimesters or two semesters ? The site said talked about 3 terms. I did a alot of what you mentioned, metric spaces, groups fields diverging into matrices. Also some part of multi variable calculus. But of course you have a lot more maths courses for obvious reasons. In all I had 2 in my first year. As much as it is posible to appreciate the beauty of the topics, I am sure glad I don't have to do them anymore, cs courses are about enough for me. Link to comment Share on other sites More sharing options...

bloodhound Posted September 20, 2004 Share Posted September 20, 2004 i have two semesters Link to comment Share on other sites More sharing options...

pulkit Posted September 20, 2004 Share Posted September 20, 2004 Are you studying in the same place as dave ? Link to comment Share on other sites More sharing options...

Dave Posted September 20, 2004 Share Posted September 20, 2004 Nope, he's at Nottingham Uni, I'm over at Warwick. We have 3 terms over here, I guess you call it trimesters. Link to comment Share on other sites More sharing options...

Dapthar Posted September 20, 2004 Share Posted September 20, 2004 If anyone's actually interested in what I'm doing, you have have a look here[/url'] - in the second year section. Whoa. So during the first trimester of Year 3, you have to take 11 classes? Crazy. Would you mind explaining how the scheduling works, since, in the US, the absolute maximum number of classes one can take during a semester is six, since most have three 50 minute lectures three days a week, plus a (two hour) lab or a (50 minute) discussion once a week, so six classes would be around 20 hours of class a week. On top of that, one credit translates to approximately four hours of study, and most classes are four credits, therefore, subtracting lecture and discussion time, that makes for about 12 hours of work outside of class per week, therefore six classes means about 72 hours outside of class studying/doing homework. Adding in the 20 hours for class, that makes 92 hours a week. Recall that there are only 168 hours in a week! Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now