Favourite Mathematical Concept/trick? (2 Viewers)

[hayabusaboston]

Discuss, favourite concepts from HSC or Uni Maths and/or favourite maths tricks you found somewhere. Teach the wider BoS community of your wondrous mathematical marvels

 

[RealiseNothing]

I keep them secret.

 

[Carrotsticks]

I love infinite series.

Absolutely cannot get enough of them. Don't really know how it started.

 

[Pfortune35]

differntiaton by first principles, how do they come up with that shit?

 

[4025808]

Being able to cross a lot of numbers out in a series, thus making a very simplified expression. Oh them lovely patterns.

 

[Carrotsticks]

Being able to cross a lot of numbers out in a series, thus making a very simplified expression. Oh them lovely patterns.

Then you will love this: http://en.wikipedia.org/wiki/Telescoping_series

 

[4025808]

Then you will love this: http://en.wikipedia.org/wiki/Telescoping_series

Yes now that is the stuff I am talking about

 

[cutemouse]

I like stuff like

 

[russ3l]

don't hate because I'm only in year 10 but.....indices (i know you all love them too)

 

[russ3l]

quadratics comes next.....then polynomials

 

[Carrotsticks]

quadratics comes next.....then polynomials

A quadratic is a polynomial of degree 2 =p

 

[physicsman1200]

The Euler-lagrange equation is the shizz

 

[RealiseNothing]

I think I'm the only person who actually likes probability and perms/combs. It would be one of my favourite topics.

 

[Mature Lamb]

topology and analysis

 

[largarithmic]

I don't think there's any one particular thing that I love above all others - but I guess I really like really beautiful symmetric arguments, can't think of an amazing example right now.

But something that IS amazing: diagonalisation arguments. I mean the very idea that "some infinities are bigger/more infinite than others" is pretty mindblowing as it is, but Cantor's original proof for why there are more reals between 0 and 1 than there are integers is absolutely beautiful; as is the proof that the power set of a set is bigger than the original set. If enough people haven't heard of this / havent seen the proof, I'll post it

 

[Carrotsticks]

I don't think there's any one particular thing that I love above all others - but I guess I really like really beautiful symmetric arguments, can't think of an amazing example right now.

But something that IS amazing: diagonalisation arguments. I mean the very idea that "some infinities are bigger/more infinite than others" is pretty mindblowing as it is, but Cantor's original proof for why there are more reals between 0 and 1 than there are integers is absolutely beautiful; as is the proof that the power set of a set is bigger than the original set. If enough people haven't heard of this / havent seen the proof, I'll post it

Fractals.

 

[largarithmic]

Fractals.

Nah I meant like, an actual mathematical proof that uses sorta really abstract "symmetry". Can't really think of an example right now though

I really like number theory too, in particular arguments from polynomials and stuff when they get involved. Something I really enjoyed proving at one point (took a bloody long time) was that every the group of units in Z_p (the um, "modular arithmetic ring" of a prime) is cyclic. I.e. you prove that for a given prime number p, there exists some integer g, such that for each integer A where p does not divide A, there exists a positive integer n such that:
is divisible by p. (it sounds convoluted defined like this, but if you know any modular arithmetic, this is a really nice proposition: you need to prove there is some g such that is a sequence that covers all the residues of p except zero. The interesting part is this isnt just true for primes, but its not true for all numbers either - the set of positive integers for which there is such a g is actually pretty weird (its 2, 4, odd primes, powers of odd primes, and two times powers of odd primes).

 

[RealiseNothing]

I don't think there's any one particular thing that I love above all others - but I guess I really like really beautiful symmetric arguments, can't think of an amazing example right now.

But something that IS amazing: diagonalisation arguments. I mean the very idea that "some infinities are bigger/more infinite than others" is pretty mindblowing as it is, but Cantor's original proof for why there are more reals between 0 and 1 than there are integers is absolutely beautiful; as is the proof that the power set of a set is bigger than the original set. If enough people haven't heard of this / havent seen the proof, I'll post it

Could you post the proof for this? That's actually a really cool concept.

 

[RANK 1]

0.9999.....=1

 

[largarithmic]

Could you post the proof for this? That's actually a really cool concept.

Alright its pretty late but still, time for largarithmic does cardinality!

Basically we want to come up with an idea for what it means for a set to have "the same size" as another set. Now this is pretty obvious for finite sets: {1,2,3} has the same number of elements as {2,3,4}, for instance, but more than {1,2} and less than {1,2,3,4}. When stuff is finite you can just count the number of elements, right?

Now stuff isnt as clear when dealing with infinite sets; you can't simply give the size of a set as a number. So we need to come up with something else. A question would be, what has greater "size": {1,2,3,4,...} or {0,1,2,3,4,...}. Intuition would tell you the second one is bigger; it has all the elements of the first plus zero. So it "has more". But at the same time, if you moved each element of the first set one to the left on the number line, the first set becomes the second; this operation "obviously preserves size" so from another perspective, they're the same size. So we need to find a suitable and rigorous definition, right?

Well we use this: two sets A and B are said to have the same "cardinality" (i.e. size) if there is a bijection between them: in lay terms this means, you can pair each element of A with an element of B. So say, the sets {1,2,3} and {4,5,6} have the same cardinality, since theres a bijection between them - you pair 1 with 4, 2 with 5 and 3 with 6. Similarly, {1,2,3,...} and {0,1,2,3...} have the same cardinality as well: you can pair each element x in the first set with x-1 in the second (so 1 with 0, 2 with 1, 3 with 2, ...). I.e. the sets "match up" if you call it that. That's a pretty good definition of "size" right, and allows us to tackle infinite sets?

So some cool starting things to consider.
The cardinality of the positive integers is the same as the cardinality of the integers. You have {1,2,3,4,...} and {..., -2, -1, 0, 1, 2, ...}. Well you pair them like this:
Pair 1 with 0
Pair 2 with 1
Pair 3 with -1
Pair 4 with 2
Pair 5 with -2
Pair 6 with 3
Pair 7 with -3
etc... So clearly this is true.

The cardinality of the positive integers is the same as the cardinality of the positive rationals!!!
Rationals are a bit more interesting, because if you think about them, there seem to be heaaaps of them: on the number line, between any two rationals, theres another rational, for isntance. By contrast the integers are discrete and spread out. But this is actually true! Heres the pairing:

You consider the first quadrant of the number plane, and only its lattice points (i.e. all points (x,y) where x, y are positive integers). Now do you see that each point (x,y) can be mapped to a positive rational x/y? Now imagine a car that starts at (1,1). Basically, it travels along all the diagonals of this plane in succession, and if it comes across any new rational number it writes it down. It goes like this:
Starts at (1,1) and writes down the rational corresponding to this point (i.e. 1).
Goes to (2,1) and writes down the rational at this point (i.e. 2)
Goes to (1,2) and writes down the rational at this point (i.e. 1/2)
Goes to the next diagonal: starts at (3,1) and writes down 3.
Goes to (2,2) and writes down 2/2 = 1. But its already written down 1, so it rubs it out and moves on.
Goes to (1,3) and writes down 1/3: the car has now gone on three diagonals. Now for the next:
Goes to (4,1) and writes 4
Goes to (3,2) and writes 3/2
Goes to (2,3) and writes 2/3
Goes to (1,4) and writes 1/4. Completed this diagonal, goes to next
Goes to (5,1) and writes 5
Goes to (4,2) but it doesnt write 4/2 = 2, coz 2 is already on its list
Goes to (3,3) but it doesnt write 3/3 = 1, coz 1 is already on the list
Goes to (2,4) but doesnt write 2/4 = 1/2
Goes to (1,5) and writes 1/5, since this isnt on the list
Goes to next diagonal at (6,1)... etc

The car obviously goes on forever. But the crucial thing is that it visits every one of those (x,y) where x and y are positive integers, and it must then write down every single positive rational number at some point. Now look at the car's list. 1, 2, 1/2, 3, 1/3, 4, 3/2, 2/3, 1/4, 5,... this list if written out in full forms the entire set of positive rationals. But its in a list form: so we can pair the first one with 1, the second with 2, the third with 3, the fourth with 4, and suddenly we have a pairing/bijection between the positive integers and positive rationals. Pretty cool right? YOu can pretty easily add negatives and zero in the equation to prove that all the rationals are the same cardinality as the positive integers and integers. Pretty cool right?


Now it turns out, while the size of the rationals and the integers are the same, these sets are NOT of the same size as the reals and not even the reals between 0 and 1. Now the proof of this is actually simply ingenious. Basically, you assume to try get a contradiction the size of the positive integers were the same as the size of the reals between 0 and 1. Now the reals between 0 and 1 can be written in decimal form right: one half = 0.50000..., 1/3 = 0.666..., pi-3 = 0.14159... right? Now if the size of the positive integers and the reals between 0 and 1 were the same, you could write all the reals between 0 and 1 in a list and you'd list all of them successfully (because the first number on the list would be paired to 1, the second number to 2, the third to 3, etc...). Oh and in ambiguous cases like 0.999... = 1, you chose the version with repeating zeroes not repeating nines (so each number has a unique decimal representation according to this list). So by assumption such a list exists. Heres a sample of it, obtained via key bashing:

First number: 0.2298012397128740182...
Second number: 0.9873842701...
Third number: 0.6796247012840...
Fourth: 0.1276381726423...
Fifth: 0.417264162...
Sixth: 0.3128471205...
Seventh: 0.812893791824...

You get the picture. Now Im going to make the suggestion that if such a complete list exists, it follows that there is something NOT on the list and thus making the list incomplete. And this is the cool part. Given my list (which only exists by assumption), I'm going to construct a special real number X. Now the way I make X is like this:

We want to choose the first decimal digit of X. So we look at the first number of on our list: its first decimal digit is 2. And 2+1 is 3. So let's make the first decimal digit of X 3: so, so far X = 0.3...
Now we need to choose a second digit. So we look at the second number on the list: its second digit is 8. And 8+1 is 9. So let's make the second digit of X 9: so, so far X = 0.39...
Now for the third digit - lets look at the third number on the list. Its third digit is 9. 9+1 = 10, but 10 isnt a digit, so lets call it 0. So let's make the third digit of X 0, so so far X = 0.390...
You do the same stuff for all the other digits: to get the nth digit of X, you take the nth digit of the nth number on the list, and add one to it (where 9+1 = 0 for this purpose). So from the seven I've listed above, X = 0.3907687...
Basically you take the nth digit of the nth number on the list (i.e. you look at the main diagonal, hence the name of this argument, the "diagonalisation argument"), and change it to get that nth digit of X.

Now X is obviously between 0 and 1, and its a real number. So it has to appear on that list somewhere right? So lets say X is the kth number on the list, where k is probably really really big on the balance of probabilities. But do you see that the kth digit of X is different from the kth digit of the kth number on the list, so X can't actually appear in the kth position? So X can't appear on the list AT ALL?

This is an obvious contradiction: the original assumption, that there are the same number of integers as reals between 0 and 1, is false! You can then say there are "more" reals than integers: because there is obviously a mapping (i.e. function) for the integers to the reals, but this proof means there cant be one from the reals to the integers if you modify its specifications a bit. Also note the fact we restricted it to between 0 and 1 doesn't really matter either: you could make a list of all reals then 'delete' the parts of each number before the decimal points - youd obviously have repetitions in the list but the proof would still work! You could slightly modify this proof too actually (by choosing a "different diagonal" to go down other than a major one) to prove that the number of reals in any interval of the reals is greater than the integers. Cool stuff right?

But the really cool thing I reckon is that we've assumed the complete list exists, taken that hypothetical list and actually USED the list to construct something that should be on it but actually can't be. There's a whole family of proofs like this (diagonalisation arguments): you can use them to prove that you can get arbitrarily big cardinalities (i.e. for every set S theres another set T with a bigger cardinality; actually the power set of S, that is the set of all subsets of S, works for this); I believe a diagonalisation argument is used to solve the very famous Halting problem in theoretical computer science, courtesy of Turing. And if that's not an awesome piece of mathematical thinking I don't know what is.