even and odd numbers

[Manifold]

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?

[jordan]

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.

[bloodhound]

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

[Manifold]

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)

[BrainMan]

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.

[bloodhound]

a simple one to one function from odds to even would be , where n is odd. and f(n)=n+1.

[Manifold]

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]

[bloodhound]

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

[pulkit]

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.

[Manifold]

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.

[bloodhound]

sorry. yeah. i should have less that equal to. i might have a look into the history of this "Theorem" then

[Manifold]

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...

[bloodhound]

had a look. dont really know what u want us to discuss

[Manifold]

...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...

[Dave]

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.

[pulkit]

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)

[Dave]

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.

[bloodhound]

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.

[pulkit]

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).

[Dave]

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.

[pulkit]

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.

[bloodhound]

i have two semesters

[pulkit]

Are you studying in the same place as dave ?

[Dave]

Nope, he's at Nottingham Uni, I'm over at Warwick. We have 3 terms over here, I guess you call it trimesters.

[Dapthar]

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!