tag:blogger.com,1999:blog-36907121773772561682017-07-16T23:26:52.981+02:00Ramblings IncWhere I ramble away on things and stuff.Clément Polgenoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3690712177377256168.post-26667857609224382482014-06-27T20:52:00.000+02:002014-07-01T04:38:56.604+02:00Group theory and fractalsSo, it's been a long time since my triptych of posts on set theory and infinity. The reason was that I didn't really find the tone I was looking for, and I couldn't decide whether I was too technical, or not enough. I've had an idea in my brain for a while though, and I thought it was best to just keep trying, so without further ado, I'll just pretend last post isn't about 6 months ago, and jump right into it.<br /><br />What I want to talk about this time is something called group theory. In this article, I plan to first explain <b>what </b>is group theory, which will be the rather technical part, but hopefully not <b>too </b>complicated, I'll try to give a few clues as to why is it super duper interesting, and I'll end up tying group theory with a cool thing about fractals I actually learned this year, which (hopefully) will be easy enough to comprehend.<br /><br />The most obvious thing I can say, is that group theory is the study of groups. Now that I've effectively dodged the question, it's time to explain what a group is:<br /><br />I've already explained what a set is, at its core, it's really just "a thing containing stuff". By which I mean that the elements of the set don't interact with each other, they're abstract stuff and that's it. So the only thing that can distinguish a set from the other, is its cardinality, which means the number of elements within the set.<br /><br />A group is one of the simplest structure we can put on top of a set, basically, it's about creating (or having) a law that tells us how elements interact. A law is something that takes 2 elements in, and spit one out.<br /><br />An example of this would be the set of all integers, with the addition. If I give you two numbers, and tell you to add them, you are effectively applying the "addition" law to 2 elements of the set.<br /><br />A group is usually noted between parenthesis, with first the name of the set, and then the name of the law, like this: (G, +), unless the operation is obvious, in which case we'll simply call it G.<br /><br />To be a group though, this law needs to satisfy a few conditions:<br /><br />Let G be a set, and $\circ$ a law on the elements of G, then (G, $\circ$) is a group if:<br />1) For all a, b, and c in G, (a $\circ$ b) $\circ$ c = a $\circ$ (b $\circ$ c); (associativity)<br /><br />2) There is an element e in G so that for all a in G, a $\circ$ e = a; (identity element)<br /><br />3) For all a in G, there is an element b in G so that a $\circ$ b = e. (inverse element)<br /><br />Back to our first example of integers and addition, we can now see that is indeed a group:<br /><br />1) The addition is clearly associative, this is primary stuff.<br />2) 0 is the identity element: adding 0 to any integer does not change the integer.<br />3) For any integer, adding its opposite will give 0.<br /><br />The addition does satisfy each of the 3 conditions, so integers with the addition form a group.<br /><br />Do note though, that the set of all integers with the multiplication is NOT a group, because:<br />1) The multiplication is clearly associative (again, primary stuff);<br />2) 1 is the identity element;<br />3) If you take any integer other than 1 or -1; its inverse will <b>not </b>be an integer. The inverse element of 2 for instance would be $\frac{1}{2}$, which is clearly not an integer.<br /><br />So integers with the multiplication can not be a group, because there are some elements who do not have an inverse within the set, which means the 3rd condition isn't satisfied.<br /><br />Another thing worth mentioning: it is never, at any point, said that a group needs to be commutative. Which means that if (G, $\circ$) is a group, you do <b>not </b>necessarily have $a \circ b = b \circ a$. The easiest example of this that I know of is matrices multiplication, which isn't a very hard thing, but is mind-numbingly boring, so I'll refrain.<br /><br />Now that we have our structure, and know how it works, we might be interested in trying to see what we can study given a group, here a few classic question that may arise when dealing with groups:<br />1) The existence of what we call a "subgroup". Basically, if you have (G, $\circ$) a group and you're able to pick some elements from G to form a subset G', and the result (G', $\circ$) is still a group, we'll say that G' is a subgroup of G.<br /><br />If we stick to the example of the group of all integers, we could consider the group of all <b>even</b> integers. If you add two even numbers, you'll still get an even number, and you're obviously still satisfying all the conditions.<br /><br />If you take all the odd integers though, it doesn't work. One reason might be that you don't have the zero. So let's consider all odd integers, plus zero. We're still stuck, because then, what does 1+1 equals to ? It can't be 2, since, in that new set G' containing only odd integers and zero, the two doesn't exist. Our law actually becomes ill-defined, which means we don't have a law, so this can't be a group.<br /><br />2) The existence of a generating set. Again, let's take (G, $\circ $) a group. Can we create a subset A of elements of G so that, by using ONLY those elements and their inverse, and combining them using our law, we're able to reach every element of G ?<br /><br />Again, back to our example. The set A is pretty easy to find here: $\lbrace 1 \rbrace $ actually fits the bill. You can reach any positive integer by just adding 1 again and again, and you reach any negative integer by adding its inverse, -1, again and again.<br /><br />Do note that it's the only generating set though. Apart from all the obvious one (who would consist of just taking a generating set and just adding stuff on top of it), we can see that $ \lbrace 4, 7 \rbrace$ would also be a generating set. That's because 4 + 4 - 7 = 1, so if we want to reach a positive integer n, we just need to add 2n worth of 4, and n worth of -7. Actually, any pair of number who have no common divisor would make a generator set, that's just <a href="http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity">Bézout's identity</a>.<br /><br />3) If the group isn't commutative, a lot more questions present themselves, we may for example wonder if there's a subgroup of elements who actually are commutative (what we'll call the "center" of the group). Again, the easiest example for this comes with matrices, since we know that at least every multiples of the identity matrix will be in the center. That's a bit more technical though, and definitely something I want to talk about, but probably in another article.<br /><br />So, that was basically my introduction to group theory. I'll try to find an interesting approach to it next time, probably introduce some interesting (and a bit less obvious) groups, and try to get some fun stuff to do with our definitions. But for now, I promised fractals ! But how can we go from such a dry concept to fractals ? Well, pretty easily actually.<br /><br />We'll use something called the Cayley graph. Let's say we have our usual (G, $\circ$) a group. Let's also say that we have A a set of generators of G. Now we take up a sheet of paper, and we make a point, representing the identity element. Our first step will be easy: from the identity, we apply our operation to every element of A and our point. Once we've done that, we repeat that step from the points we just reached. Again, example:<br /><br />Let's keep with our example of all integers, and $A = \lbrace 1 \rbrace$, our original point will be the 0.<br /><br />1st step: we add 1 to 0 by drawing a line from 0 to 1, and we also subtract 1 from 0 by drawing a line from 0 to -1.<br /><br />2nd step: we do the same operation, but starting from the points we just reached, which are 1 and -1. First, we add 1 to 1, and we reach 2. We also subtract 1 from 1, and get back to 0. We do the same from -1, we reach 0 again, and -2.<br /><br />3rd step, same operation, starting from -2, 0, 2. The points we reach are now -3, -1, 1, and 3.<br /><br />And now me iterate that process.<br /><br />After applying that operation infinity times, we'll have drawn a line. Not very exciting... But that's because we took the boringest of all groups.<br /><br />So let's take a different group this time, we won't bother saying what G is, because G will be a hot mess, let's just say that the operation will be a multiplication, that it is <b>not </b>commutative, and that our group will basically be the group generated by all the way of multiplying 2 elements, named a and b.<br /><br />This is actually a VERY BIG groupe, since we are not assuming commutativity, it means that $ab \neq ba$. So basically the elements of our group will be all the words you can write using only a and b, without the right to move them around. So this would be an element of our group: aaababaababbabbabaababa. And it equals nothing except itself. And since you have no upper bound to the number of letters you can use to write a word, you clearly have an infinity of elements. Actually, you could make words using only a, and as long as you write "a" a different number of times, the numbers would not be equal. Which means we already have an infinite numbers of words using only the letter a...<br /><br />So now, back to drawing our graph, we start from writing the identity element, and we have $A = \lbrace a, b \rbrace$, which means that we have 4 things to do to our neutral element: multiply by a, multiply by b, multiply by $a^{-1}$ (or "divide by a", if you prefer) and multiply by $b^{-1}$ (or divide by b).<br /><br />Here are the results, in which I also reveal that I write like a 7 year old:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-7RPmd0ek7F8/U60UL-FBk_I/AAAAAAAAAwU/wCHGhhPHdC0/s1600/IMG_20140627_084735.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-7RPmd0ek7F8/U60UL-FBk_I/AAAAAAAAAwU/wCHGhhPHdC0/s1600/IMG_20140627_084735.jpg" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-nLxVtFMYXIQ/U7IfC-sZd2I/AAAAAAAAA3Q/A84ShfBAw0U/s1600/IMG_20140701_043648.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-nLxVtFMYXIQ/U7IfC-sZd2I/AAAAAAAAA3Q/A84ShfBAw0U/s1600/IMG_20140701_043648.jpg" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><br /><br /><br />I did not label all extremities in the last one because 1) I'm lazy and 2) it only overcharges the drawing, and is not really necessary.<br /><br />For those who don't know what exactly is a fractal, the rough idea is that it's a geometrical construction that usually has a iterative process, can always fit within a certain area, and yet have an infinite "length of line". For the curious, I'll add the proof that what I've defined is indeed a fractal, but it's probably safe to skip if you don't really care about that.<br /><br />So, the exact process of drawing that fractals is actually as follow:<br /><i>Initialization: </i>Create a point. From that point, multiply it by each element of the set of generators of your group, and their inverse.<br /><i>Iteration:</i> From the points you've created on last step, multiply each of those by each element of the set of generators of your group, and their inverse. <b>If you reach new points, draw them at a distance $\frac{1}{2^n}$, where n is the number of times you've iterated.</b><br /><b><br /></b>First of all, let's prove we can iterate ad nauseam on my drawing, an always fit within a certain area. For that, we'll calculate the maximum distance a point can be from the original point on the plane. Obviously, the furthest point at any given time will always be the one going straight forward (so, powers of a, powers of b, as well as their negative powers). So we just need to prove that those don't go at infinity. It's a pretty simple calculation, take it the way you want it, it's either <a href="http://en.wikipedia.org/wiki/Zenon%27s_paradox">Zenon's paradox</a>, or it's a <a href="http://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#P-series">p-series</a> or ("série de Riemann" for us Frenchies) for the math-savviest amongst us, anyway, we can easily say that <b>no point will be further than a distance 2</b>, so our drawing will <b>always </b>be contained within a circle of radius 2.<br /><br />Now let's prove we have an infinite length of line. For that, we need to calculate the length we'll draw at each iteration. Which mean counting how many new lines we draw each time. Again, the calculation is fairly easy: either a point is "old", in which case it has 4 "neighbours", and will never draw any new line, or it's new, in which case it has one neighbour, and will draw 3 new ones on this iteration. So we need to count, at each step, how many point have only one neighbour.<br /><br />After initialization, we have 4 points. Each of these will have one operation bouncing them back, and will create 3 new isolated points. On the next step, each of these points will also have one operation bouncing them back to an old point, and 3 operations who will create new isolated points. Which means that, at the n-th step, we'll create $4 \times 3^n$ new isolated points. So the length of line we'll actually draw at the n-th step will be:<br /><br />$\underbrace{4 \times 3^n}_{number\ of\ lines} \times \underbrace{\frac{1}{2^n}}_{length\ of\ each\ line} = 4 \times \frac{3^n}{2^n} = 4 \times (\frac{3}{2})^n $<br /><br />Which, again, pretty obviously goes to infinity. If you need to convince yourself, you can just valuate it for a few values:<br /><br />At 1st step, we'll draw 14 units of line.<br />At 10th step, we'll draw $\approx$ 228 units of line.<br />At 100th step, we'll draw $\approx$ 1626244710140860949 units of line. Don't draw a 100 steps.<br /><br /><br />Finally, for an already long post, a quick return to group theory, for a quick proof. I said that there had to be an identity element, but can there be 2 ? The answer is no, and here's the proof why:<br /><br />Let's take (G, +) a group, and let's assume we have $e_1$ and $e_2$ two identity elements. Then we have the following:<br /><br />$e_1 + e_2 = e_1$<br /><br />Because $e_2$ is the identity element, so $e_1$ has to be unchanged by the operation. But we also have:<br /><br />$e_1 + e_2 = e_ 2$<br /><br />Because $e_1$ is the identity element, so $e_2$ has to be unchanged by the operation. We then have:<br /><br />$$\begin{cases}<br />e_1 + e_2 = e_1\\<br />e_1 + e_2 = e_1<br />\end{cases}<br />\Longrightarrow<br />e_1 = e_2$$<br /><br /><br />So there you go, introductive crash course to group theory, and an easy way to generate fractals with just letters and an operation. Hope you liked it, and maybe it'll take me less than half a year to write the sequel to this.Clément Polgehttps://plus.google.com/117118578638770449658noreply@blogger.com0tag:blogger.com,1999:blog-3690712177377256168.post-4424358807225156862014-01-18T21:07:00.001+01:002014-01-18T21:07:44.905+01:00An infinity of infinities.So, I mentioned that there was an infinity of infinities. This is atually fairly technical to prove, but the reason why can be explained in a sort-of-intuitive manner, so that's what I'm setting out to do in this post: actually give a manner to, given a set, build a new, bigger set from it.<br /><br />In the first post, I mentioned that set are defined by their cardinality, and that we can't make their elements interacts, this is true, but there is actually one operation we can do on a set: we can take a part of it.<br /><br />For instance, if we have the set $\{a,b,c\}$, a part of it could be $\{a,b\}$. So let's consider that set $\{a,b,c\}$, and look at all the different parts it may have:<br /><br />The part with 0 element: $\varnothing$<br />The parts with 1 element: $\{a\}, \{b\}, \{c\}$<br />The parts with 2 elements: $\{a,b\}, \{a,c\}, \{b,c\}$<br />The part with all 3 elements: $\{a,b,c\}$<br /><br />(note: $\varnothing$ is a notation for the empty set, containing no element)<br /><br />Now, and this is the funny part, all those things can now be considered elements... And we can build a new set containing those, so if X is a set, we can consider $\mathcal{P}(X)$, the <i>set made of all the parts of the set X</i>. So in our example, we would have:<br /><br />$$X = \{a,b,c\} \\<br />\mathcal{P}(X)= \{\,\varnothing, \{a\}, \{b\}, \{c\},\{a,b\}, \{a,c\}, \{b,c\},\{a,b,c\}\, \}$$<br /><br />So we can see what we managed to do: we had a set of size 3, and we've used it to build a set of size 8. Note that the process can be re-iterated, our $\mathcal{P}(X)$ is, itself, a set, so we can consider its parts, and create a new set containing all the parts of this set (what we would note $\mathcal{P(P}(X))$, but that's not important). And if I'm not mistaken, this new set would probably contain 256 elements.<br /><br />Now the fact that a set is infinite can't stop up from considering its parts... Though obviously, they might be very weird-looking. For instance, in the case of the integers, a part might be just a finite number of integers, or it might be everything except a finite number of integers, or it can be an infinite part of the integers with an infinite part leftover (like, all odd integers for instance), it can be basically ANYTHING, it doesn't even have to be expressable as a formula, it could be an infinite set or arbitrarily chosen integer, it doesn't matter.<br /><br />So already, we can see that there are a LOT of parts we can take, with a set as simple as "the integers".<br /><br />Now the leap of faith, for which you'll have to take my word for it (partly because I don't remember the proof, but also because what I remember of it is too technical for this blog): but whatever your set X is, the set $\mathcal{P}(X)$ is always <i>strictly bigger </i>than the set X. And that is true for infinite sets too.<br /><br />So our set of all integers $\mathbb{N}$ is infinite, but the set $\mathcal{P}(\mathbb{N})$ is a bigger infinite.<br /><br />And now we just have to reiterate this process over and over again... The set $\mathcal{P}(\mathcal{P}(\mathbb{N}))$ is a bigger infinite than $\mathcal{P}(\mathbb{N})$, and is "two steps" bigger than $\mathbb{N}$, and so on... So here we have it, our infinite number of infinities. It's not very visual, so it might not be really satisfactory, but it still works.Clément Polgehttps://plus.google.com/117118578638770449658noreply@blogger.com0tag:blogger.com,1999:blog-3690712177377256168.post-6185552715014467192014-01-07T20:56:00.000+01:002014-01-07T23:55:18.567+01:00To infinity... And beyond !<span style="font-family: inherit;"><a href="http://ramblingsinc.blogspot.fr/2014/01/some-math-y-weirdness-part-1.html">Last time</a> I mentioned that there are an infinity of infinities, and yet, the only proof I gave was of two infinities who were the same... In this post, I'll show an example of a bigger infinity (which, surprisingly, won't be that big) as well as prove that it is, indeed, bigger.</span><br /><div><span style="font-family: inherit;"><br /></span></div><div><span style="font-family: inherit;">But first things first, let's remember what it means for two sets to have the same cardinal: it means that we're able to create a function that has a one-to-one correspondence between the elements of the first set, and the elements of the second set.</span><br /><span style="font-family: inherit;"><br />Also, before we even start, I'd like to explain what I'm going to do: it's called a <i>proof by contradiction,</i> though I like our french expression better which would translate by "reasoning to the absurd". The point is that we have something we want to prove is false, so we consider it true and we reason from there. The goal being to end up with a contradiction, something absurd. In which case one of two things happened: either we went wrong during our proof, or our original assumption was not true (thus false).</span></div><div><span style="font-family: inherit;"><br /></span></div><div><span style="font-family: inherit;">First, a tiny bit a of notation. The set of all positive integers is usually noted $\mathbb{N}$. The set containing all numbers (including decimals, and so on) between 2 numbers is noted between square brackets, like this: $[0,1]$. This would be the set containing any real number between 0 and 1, including 0 and 1, as well as every fraction between 0 and 1, as well as some numbers that aren't even possible to write as a fraction (and there's a metric shit-ton of those). </span></div><div><span style="font-family: inherit;"><br /></span></div><div><span style="font-family: inherit;">Anyway, what we're going to do is prove that the second set is bigger than the first. Sounds counter-intuitive ? That's half the fun ! Here we go.</span></div><div><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div><div><span style="font-family: Arial, Helvetica, sans-serif;">Let </span><br />$$X = \mathbb{N}<br />\\<br />Y = [ 0, 1]<br />\\<br />f: X \rightarrow Y $$<br /><br />That last notation means that f is a function that takes an element of X and associates it an element of Y. On top of that, let's ask for that function to be a bijection.<br /><br />Now comes the hard part. We're going to prove that even though the function is supposed to be a bijection, so among other things supposed to reach every number between 0 and 1, we can actually find a number between 0 and 1 that <i>isn't reached by the function</i>.<br /><br />The argument we're going to use is both pretty cool and pretty weird at the same time, it's called <i>Cantor's diagonal argument.</i> We're going to look at all the numbers between 0 and 1 that are reached by our function, and create a new one from that.<br /><br />The first thing to consider, is that every number can be written with an infinite decimals. It's actually pretty stupid: if you consider 0,5, nothing's stopping you from writing it "0,500000000...". What we're going to do is this: for each integer, we'll look at the number it's associated to, and look at the number of the decimal part at the position equal to the integer we're considering. Read that sentence several times, realise it's still not super-clear, and let me give you an example.<br /><br />Let's say that 1 is associated to 0,<b>7</b>23; then we'll look at the first number of the decimal part, which is 7. If 5 is associated to 0,2 3 6 4 <b>2 </b>3 7 3; we'll consider the 5th number, which is 2. Clearer ? If not, don't worry, an other example is coming.<br /><br />And now, on to building our new number. We'll build it bit by bit: first we're going to look at the number associated to 1, and look at the 1st number of his decimal writing. If it's a 1, the number we're building will get a 2, and if it's not a 1, we'll write a 1. Then we'll do that for 2, but by looking the 2nd number of the decimal part, and so on... Like this:<br /><br />$$\begin{align}<br />&1 \rightarrow 0,\; \textbf{7}\; 2\; 3\dots \\<br />&2 \rightarrow 0,\; 3\;\textbf{2}\;1\;5\;6\;2 \dots \\<br />&3 \rightarrow 0,\;5\;4\;\textbf{1}\;5\;1\;6\;5 \dots \\<br />&4 \rightarrow 0,\;9\;8\;4\;\textbf{6}\;5\;1\;8 \dots \\<br />&5 \rightarrow 0,\;8\;9\;0\;0\;\textbf{1}\;0\;0 \dots \\<br />&\dots<br />\end{align}$$<br /><br />In this example, the number we're building would be 0,11212... And we can see the diagonal too (which explains the name). Each time a number in bold is different than 1 we put a 1 in the decimal writing, and when it's 1, we put a 2. Still following ? Good ! You've made it through the hard part !<br /><br />Because now the whole argument has been laid out, and if you think about it, REALLY think about it, you'll realise that absolutely no integer can reach the number we've built. I'll try and make it even clearer:<br /><br />Let's assume a certain integer, let's call him n, reached our mystery number, let's call him x. We would then have:<br /><br />$ n \rightarrow x = 0,\dots \underbrace{1}_\text{n-th position}\dots$<br /><br />In which case our mystery number should have, by construction, a 2 in this place. So this can't be true.<br /><br />OR we would have:<br /><br />$ n \rightarrow x = 0,\dots \underbrace{not \; one}_\text{n-th position}\dots$<br /><br />In which case our mystery number should have, by construction, a 1 in this place. So this can't be true either.<br /><br />It instantly follows that our mystery number is indeed not reached by an integer, so the function isn't a one-to-one correspondence, and we've actually found a set with a bigger infinity ! Yay us !<br /><br />And yes, it does mean that there are more numbers between 0 and 1 than there are integers.<br /><br />This is actually a pretty elaborate proof, so again, don't panic if you don't get it on first read, and maybe try to build a few examples, try to replace n by a small number and test it out, and you should be able to see why it works.<br /><br />I remember I promised to prove that there actually was an infinity of infinities, but this post is already quite long, so it'll have to wait for next time. But if you're definitely lost after this post, don't worry, none of this will be useful for the next and final one.</div><div><pre style="background-color: white; color: #333333; font-size: 15px; line-height: 20px;"></pre></div>Clément Polgehttps://plus.google.com/117118578638770449658noreply@blogger.com0tag:blogger.com,1999:blog-3690712177377256168.post-33096049650927765492014-01-05T12:47:00.001+01:002014-01-07T21:06:11.873+01:00Some math-y weirdness, part 1.<span style="font-family: inherit;">So yeah, I love maths. It's actually one of the reasons I started this whole thing: because I wanted to talk about maths. I've actually got a post in the works explaining my love for maths, but I'm starting to realise it's a bit too much for one post. I thought I might try to work my way through there by making a series of posts, each showing a different thing about maths, walking my way up in complexity (but trying to remain as pedagogic as possible) and to give as wide a picture of the reality of what maths are as possible.</span><br /><span style="font-family: inherit;"><br />One thing to realise is that maths works through logic, by which I mean that it's the science of inferring from the properties of the stuff you're given. So obviously these posts will be a bit dry, and filled with definitions, because if you don't know WHAT you're talking about, how can you deduce anything about it ?</span><br /><span style="font-family: inherit;"><br />So, here we go. I thought I'd begin with the crudest things: sets. This might get technical at times, there will be strange words with even stranger definitions, just breathe, take your time to read, and don't hesitate to ask for any clarification.</span><br /><span style="font-family: inherit;"><br />A set is just a thing filled with stuff, and nothing more really. You don't know how those stuff interact (by which I mean you don't have anything like an addition, you have NOTHING, just your stuff). </span><br /><span style="font-family: inherit;"><br />For instance, you can have numbers, like 1, 2, and 3, and if you take them collectively, you get the set containing the objects "1, 2, 3". What we will usually note {1,2,3} : the brackets denote a set. You forget any properties those elements might have. I used numbers, but we can totally imagine a set containing letters, like {a,b,c,d}. The objects inside do not really matter for the purpose of what a set is.</span><br /><span style="font-family: inherit;"><br />It follows that if you have two sets you want to compare, there aren't a lot of things you can do: you can see if one contains more objects than the others. It's what we call the cardinality, the size of a set.</span><br /><span style="font-family: inherit;"><br />If I give you these two sets for instance: {1,2,3} and {1,2}, you can easily tell that the first one have more elements than the second one... But what if they contained an infinity of elements ? How would you know if one is bigger ?</span><br /><span style="font-family: inherit;"><br />Or, more accurately, what does "bigger" even MEAN when we're talking infinity ?</span><br /><span style="font-family: inherit;"><br />The answer comes with a cool-looking word that will make you look smart if you manage to use it correctly: isomorph, "iso" comes from greek, and means "same", while "morph" also comes from greek, and means shape, or form. An isomorphism is a function something that tells us that two things are isomorph, which means they're basically the same, or at least indistinguishable when considering their properties.</span><br /><span style="font-family: inherit;"><br />So, for two sets, being "the same thing", would mean having the same properties. The only property a set have is its cardinality, so for two sets to be considered equivalent, they need only to have the same cardinality. </span><br /><span style="font-family: inherit;"><br />To compare the cardinality of two things, we actually have a pretty nice way: we create a function between these two things, and we try to give it certain properties.</span><br /><span style="font-family: inherit;"><br />A function at its core is a pretty simple thing: it takes something from set X, and associate it something else from set Y. You can see it as an arrow, pointing out from each element of X and arriving on elements on Y.</span><br /><span style="font-family: inherit;"><br />The first property is that we want to try and make it <i>injective, </i>this means that two distinct elements from set X are associated to two distinct elements of set Y.</span><br /><span style="font-family: inherit;"><br />The second property is that we want it to be <i>surjective, </i>it means that EVERY elements of set Y is reached by an element of set X.</span><br /><span style="font-family: inherit;"><br />If a function qualify for these two properties, it will be called <i>bijective.</i> Which basically means that every point of Y is reached, and that no two points of X are connected to the same point in Y. Or said differentely, that we have a one-to-one correspondance.</span><br /><span style="font-family: inherit;"><br />And because a drawing is worth a hundred words, here's a cool image I found on wikipedia:</span><br /><span style="font-family: inherit;"><br /></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-ebaXhSKGZRk/UsbFZXNLCvI/AAAAAAAAAkg/GMXKmohMeUo/s1600/1000px-Surjection_Injection_Bijection-fr.svg.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span style="font-family: inherit;"><img border="0" src="http://2.bp.blogspot.com/-ebaXhSKGZRk/UsbFZXNLCvI/AAAAAAAAAkg/GMXKmohMeUo/s1600/1000px-Surjection_Injection_Bijection-fr.svg.png" /></span></a></div><span style="font-family: inherit;"><br /><br /><br /><br />The first one is surjective because every element of set Y is reached, but not injective because the first two elements of set X reach the element of Y.</span><br /><span style="font-family: inherit;"><br />The second one is injective (every element of X is connected to a different element of Y), but not surjective, because some elements of Y aren't reached.</span><br /><span style="font-family: inherit;"><br />The last one is indeed bijective: each element of Y is reached, and no two elements of X are associated to the same thing.</span><br /><span style="font-family: inherit;"><br />Already we can see that when it comes to finite set, having the same cardinality is indeed the same as being able to link each element of X to an element of Y in a manner that no two elements are linked to the same thing.</span><br /><span style="font-family: inherit;"><br />So for sets, being <i>isomorph </i>actually mean <i>having a bijection </i>between the two sets.</span><br /><span style="font-family: inherit;"><br />Now let's just expand that to our infinite sets and see how that works... And we'll (FINALLY) get some funny results !</span><br /><span style="font-family: inherit;"><br />Let X be the set of all positive integers.</span><br /><span style="font-family: inherit;">Let Y be the set of all <b>even </b>positive integers.</span><br /><span style="font-family: inherit;"><br />Take your bets now, will one be bigger ? If so, which ? Will they be the same size ? The suspense is killer.</span><br /><span style="font-family: inherit;"><br />Well, to see that let's try and make a function that goes from X to Y, and be subjective.</span><br /><span style="font-family: inherit;"><br />The answer is actually pretty easy: the function f will be the function that, for each element of X, associate two times this element... So :</span><br /><span style="font-family: inherit;">0 will give 0</span><br /><span style="font-family: inherit;">1 will give 2</span><br /><span style="font-family: inherit;">2 will give 4</span><br /><span style="font-family: inherit;">3 will give 6</span><br /><span style="font-family: inherit;">and so on...</span><br /><span style="font-family: inherit;"><br />Our function is indeed injective: if you take two integers and multiply each by two, the only way you get the same result is if the two integers were equals to begin with.</span><br /><span style="font-family: inherit;">It is also surjective: if you take an element y from the set Y, you can find an element x in X such as f(x) = y. Namely, x = y/2.</span><br /><span style="font-family: inherit;">So it is injective and surjective, thus bijective, these two sets are actually of the same size. Which means there are as many *even* integers than there are positive integers.</span><br /><span style="font-family: inherit;"><br /></span><br /><span style="font-family: inherit;"><br />But that doesn't really answer my original question: can there be an infinity "bigger" than the other one ? Right now we've managed to split an infinity in two, and still have the same infinity... And yet, the answer is yes, it's not that easy to prove though. But what we're actually able to prove is that there exists an <i>infinity of infinities.</i> Try and wrap your brain around that. If someone's interested, I could try making a small post about it, but that might get really technical.</span><br /><span style="font-family: inherit;"><br />Basically, the set of all integers is the smallest infinity there is, it's what we call <i>countable</i>. So if you have an infinite set containing only integers, you already know its cardinality: it will be a countable set, and will have the same cardinality as the set of all integers. Strange, isn't ? You have an infinity of integers, you take an infinity away (in our example, all odds numbers), and yet you can be left with the same infinity you started with. How is that not wonderful ?</span><br /><span style="font-family: inherit;"><br />Still, an example of set of a "bigger infinity" would simply be what we call the set of <a href="http://en.wikipedia.org/wiki/Real_numbers">real numbers</a>, which is basically any number you can think of, and where you'll find strange numbers such as pi.</span><br /><span style="font-family: inherit;"><br /><br />And if it makes you feel better, one of the biggest name in this kind of thing was <a href="http://en.wikipedia.org/wiki/Georg_cantor">Georg Cantor</a>, and he died crazy, so don't feel bad if you don't get it all on first read. Some of these concepts aren't necessarily easy to grasp.</span><br /><span style="font-family: inherit;"><br />My point with this post was to show that maths aren't about numbers, we've barely used them here, and really about a vision of the mind. You begin by visualising a simple thing (a thing containing stuff), and then you just kick it up a notch by giving it a name, properties, a definition, and working out from there: how can you compare two items, what are their properties, and so on... </span><br /><span style="font-family: inherit;"><br />I am very familiar with each of these concepts because, well, that's kind of what I do, but it's totally normal to feel overwhelmed the first time, and to mix everything up. Just take it slow, one step at the time, and I hope you'll be all right !</span><br /><span style="font-family: inherit;"><br />Anyway, this was my first attempt at talking things maths, so tell me how that worked out for you ! Was it too technical ? Too superficial ? Too explain-y ?</span>Clément Polgehttps://plus.google.com/117118578638770449658noreply@blogger.com0tag:blogger.com,1999:blog-3690712177377256168.post-405297111441313092014-01-03T12:56:00.002+01:002014-06-29T06:21:15.493+02:00So... Yeah.Apparently, the thing I'm having the hardest time coming up with is the opening. Let's just assume I've done that and jump right into the fray.<br /><div><br /></div><div>So why this blog ? Well, simply put, there often are news events, cultural stuff, or various subjects on which I'd like to expand, and often can't, simply because I don't have the tools for it. Making a point on twitter is tantamount to baking cookies one at a time, and that really isn't the point of Facebook. So I needed a place to express myself, make the points I want to make, and I guess this will be it.</div><div><br /></div><div>I'm realising as I'm typing this the hardness of the task though: while a discussion is an iterative process, where you bounce off each other and amend or clarify your statements as you go, a blog post would need to be as extensive as possible on first try. Even this very post, where I'm honestly not saying much, took more time and iterations than I care to admit.</div><div><br /></div><div>And I haven't even started on the design yet. Can't I just put Clooney's bat-nipples on repeat in the background and call it a day ?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://gobbledygeekbtr.files.wordpress.com/2011/07/bat-nipples.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://gobbledygeekbtr.files.wordpress.com/2011/07/bat-nipples.jpg" height="185" width="320" /></a></div><br /></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div><br /></div>Clément Polgehttps://plus.google.com/117118578638770449658noreply@blogger.com0