Skip to content

Mathematics

The Cali Garmo does Math
Introduction to Group Theory by Ledermann and Weir

Introduction to Group Theory by Ledermann and Weir

Ledermann and Weir take a slightly unique approach in the theory of groups. Their text is slightly difficult to follow in a lot of places as they tend to group things together in non-standard ways. The biggest difference I found with his use of symbols is when talking about homomorphisms. In particular most texts will look at a homomorphism: and when going from to they apply a function such as ; Ledermann and Weird on the other hand choose to use the notation of . Although this format might be more concise, it can at times be a little confusing as to what each symbol is supposed to stand for. My assumption is that he’s trying to show that a homomorphism is similar to group actions with the action being the map , but for an introductory piece, it can be particularly confusing.

The biggest part I did enjoy about this book was the list of topics. Not only did he cover the standard topics of groups, subgroups, cosets, normal groups, conjugacy classes, etc. he also threw in some topics you don’t normally see in an introductory course such as double cosets, free groups, the derived series, soluble and nilpotent groups. He tends to go through topics fairly quickly so it can be a little difficult to follow at times, but it’s not that bad to follow and can generally be followed on your own. Another part about this book I thoroughly enjoyed was that every exercise had a solution in the back of the book. Exercises are essential when learning any new topic and when you are trying to teach yourself, having questions without answers can be a little difficult at times because you can never be sure you’re actually doing it correctly.

All in all I think this book is a really good book for introductory group theory. If you’re willing to invest a little bit of time understanding the notation, you’ll learn more out of this book than most other books on group theory.

A Mathematical Introduction to Logic by Herbert Enderton

A Mathematical Introduction to Logic

I think Enderton does a really nice job introducing logic to those who have never studied it before. Although not always the easiest to follow Enderton lays out all the necessary topics in a nice organised fashion so it’s fairly simple to follow everything. I found his explanation of the pumping lemma to be lacking which made it difficult to follow, but his proof of the compactness theorem more than makes up for it. He does a good introduction of not only proposition and predicate logic, but also goes into second-order logic as well and tackles it the same way as his previous material so it’s easy to follow it all. Although this wasn’t my favourite logic book, it is a nice book to peruse.

Introduction to the theory of computation by Michael Sipser

Introduction to the Theory of Computation

This book was definitely one of the best books I’ve seen for introducing computation theory. Michael Sipser does an amazing job introducing not only Turing Machines, but also different types of machines such as RAM and Finite Automata. He not only gives a good intuitive description and explanation of different machines, but he also does a really good job explaining different languages. Although some of his proofs can be a little difficult to follow, they are all understandable to anyone who is coming at the topic for the first time. He also does a good job explaining the different issues that are relevant in computation theory. unlike most books that I’ve seen so far, he gives a very detailed proof of the Cook-Levin Theorem (That SAT is a NP-Complete language) and also gives multiple examples of proving NP-Completeness which is nice as that seems to be one of the more confusing parts of computation theory for most students. He also gives answers to many of his examples which makes it so that it’s easy to follow on your own and learn everything without needed secondary help.

Introduction to Mathematical Logic by Elliott Mendelson

Introduction to Mathematical Logic

This week we’re doing another book on Logic! Mendelson does an ok job with his book in introductory logic. He sets up a nice introduction to logic concepts, but then fails to deliver much needed exposition. Although the book is very descriptive and helps to get your hands very dirty in logic, it can sometimes be a little to follow what Mendelson is trying to prove and whether a certain problem is an exercise or a proof. Although at times it’s a little hard to follow this text does give an amazing introduction to the topic of logic. It doesn’t assume any presupposed knowledge and actually goes over almost every topic that a new student would be expected to know in the topic. Not only that, but he also breaks down Number Theory to prove Gödel’s incompleteness theorem and also does a fairly good job of showing the different axiomatizations of set theory. Not only that, but his introduction to second-order logic and modal theory are also fairly nicely laid out. I chose not to look at his computability section as it seemed that it would be lacking since it only seemed to barely touch on the subject and there are tons of books out there that go more in depth on the topic and do a phenomenal job. I’d definitely recommend this book with a secondary companion text to help guide you along if you have trouble understanding what Mendelson is trying to state.

Groups and Symmetry by M.A. Armstrong

Groups and Symmetry

Armstrong does an amazing job with his introduction to group theory. Unlike most texts he uses a geometric approach for a lot of his work in groups. With that he uses dihedral groups a lot in his exposition and is always going back to it (and symmetric groups) for examples. I thought it to be refreshing to see group theory presented from an alternative angle. Although he doesn’t provide answers for his exercises, all of the exercises are answerable using the text provided. Some of them were difficult enough to pose some fun challenges while reading the book. Although the book is not the best introductory text I’ve found out there, I thought Armstrong’s introduction of finitely generated abelian groups was very well done. It definitely was better than most of the ones I had seen out there and definitely worth reading more into. The final theorem he put in his book was the Nielsen-Schreier Theorem which states:

Every subgroup of a free group is free

Which is a super fun concept and is not fully introduced in a lot of the texts that I’ve read in the group theory world. If you want a text that does group theory from the slight angle of geometry I definitely recommend this book.

 

Beginning Logic

Beginning Logic

Edward John Lemmon was a logician whose main area of expertise was modal logic. His book ‘Beginning Logic‘ is likely one of the better ones out there for those just getting into logic in order to understand the different rules in modal logic. Lemmon begins with an introduction on logic and why it is necessary to talk about the subject. After giving a very well laid out overview of why logic is required he begins by talking about the rules of logic and why each one is necessary. Although the book on it’s own is likely difficult to understand, it is a good reference book to see why certain rules are the way they are. (By rules I refer to the rules of derivation from one set of formulae to another). Not only does he give a detailed explanation of each rule he also goes into the concepts of completion and why each set of rules are complete in their respective areas.

He covers 2 separate areas of logic: propositional and predicate. Propositional logic is logic that only uses ‘operators’ such as . (Here he uses instead of the now traditional ). Propositional logic is also sometimes referred to as sentential logic or propositional calculus. In predicate logic Lemmon adds the symbol for ‘there exists an x’, and for ‘for all x’. This format is not necessarily traditional, but Lemmon is working before standards were fully developed. His syntax can be slightly difficult to follow, but after working on it, it is not the worst syntax out there.

Who this book is for: This book should be used in conjunction with some other books and is good for someone who is looking for an english language description of logic and the different rules associated with proving results.

Every Monday I’m going to publish a book review on a book that I’ve been reading. Most likely they’ll match up with classes or topics I’m currently learning about, so most likely books will come in bunches on topics, but I’ll try and vary them as much as I can. So look out starting next week for my first book review!

When we last left off I had finished talking partially about prime numbers and how to find them. But some of you may have been wondering, how many primes there are in total? Is there some way to maybe find a formula to find a prime number?

If you look at the primes, they seem to go on forever! And thanks to amazing mathematicians from the past we know that they do! But HOW do we know that they actually do? How can you be sure there is a number after 97 that is prime? Some will just point to their computer and say, “Computers can prove that!” and they would be partially right. Computers have helped us find extraordinarily HUGE prime numbers. For example, remember those special prime numbers called Mersenne primes which are primes of the form where p is also prime? Well, a worldwide collaboration was started in order to find the largest prime known to man and they called themselves GIMPS.

The organization is called GIMPS or Great Internet Mersenne Prime Search. You can find their website here: [GIMPS] Quite recently they found the largest prime ever known to man. What is the prime number you may be wondering? It is: . You might be thinking that this looks like a small number, but it really isn’t. This prime is 17,425,170 digits long. That is HUGE! It is so big that if you were to print out the number on paper (without commas) it would be 4,283 pages long!

It took years for the computers to calculate that prime number, so as we questioned earlier, how do we know if there is a prime number greater than this or not? It is so large we can barely use computers to go any higher, and we can forget about writing the number down (you try writing out 4,283 pages of numbers!). So then how can we KNOW if there are infinite number of primes or not? Well this is exactly what a guy named Euclid was pondering over 2,000 years ago.  Euclid was able to prove that there are an infinite number of primes! So no matter how big of a prime number we find, there will always be a bigger one. So cool! But how did Euclid come up with this?

Below is a rough transcript of how Euclid created his proof, but before we go over the proof here a lemma that Euclid uses in order to prove it that you should know:
Lemma 1: Every number greater than 1 can be broken down into multiples of prime numbers. e.g: . Notice that prime numbers just equal themselves, and composite numbers are multiples of primes!

Euclid’s Proof: Suppose that there are only a finite number of primes. This means that there is a number x such that any number greater than x is not prime. All these numbers greater than x thus must be composite and by the lemma we just discussed must be a combination of prime numbers. So if we take every prime number less than x and multiply them together we get a number n. Now if we add 1 to n we get a prime number! (Notice that since 2 is a prime, thus multiplying all the primes together would get us an even number, which would automatically not be prime. So we add 1 to make it an odd number.) Why/how is n+1 prime?! Because no matter which prime number we select and we divide n + 1 by it we will get a remainder of 1. And since we have used every prime number less than x, and every number between x and n are composite, there are no other prime numbers that (n+1) can divide into. So (n+1) must be prime! But, we had stated earlier that x is the greatest prime and since (n+1)>x we see that our earlier thought was wrong (that there are a finite number of primes) and so there must be an infinite number of primes!

[Note: This type of proof is called proof by contradiction. I’ll eventually lay the groundwork for how this works, but for now you can look it up in google if you’d like.]

Wow, that was complex, but so rewarding! We can now for sure state that there are an infinite number of primes! Fun part is, that this was only 1 of many proofs that there are infinite primes! Any questions? Leave a comment!

Questionably yours,
The Cali Garmo

After more than 3 years hiatus, I’m back to deliver more maths goodness! I hope you’re ready, cause I have some fun things in store for you.

On Friday I asked you the following riddle. Assume there are 2 different types of lottery. Lotto A makes you choose 6 numbers out of a possible 75,and lotto B makes you choose 5 numbers out of a possible 60 and 1 ‘mega’ number out of a possible 40. Which lottery gives you the best odds? Original problem here.

I’m sure a lot of you said Lotto B. And this is how you probably came up with the answer:

  • Lotto A: 75 numbers, choose 6, so in order to choose the first number we have 75 options, for the second number, we have 74 options (since we just used up one number), etc. So we get:
    possibilities
  • Lotto B: Out of 60 numbers, choose 5, then out of 40 numbers, choose 1. So the same logic as in lotto A, we get:
    possibilities

Congratulations if you got this far! This is technically correct IF the lottery forced you to choose the numbers in a specific order. The lottery (luckily) doesn’t force you to get the order right though, you can choose the numbers in any order. So then what are the chances for each lotto? Let’s first look at an easier example.

Choose 2 numbers out of 1-10. The first number has 10 choices, the second number has 9 choices. So we get a total of 90 different options (). BUT again the order doesn’t matter. Pretend your numbers were 1 and 7. We’ll call this pair (1,7) for simplicity. Selecting number 1 and then selecting number 7 is the same thing as selecting number 7 and then selecting number 1! So for each pair […(1,7), (1,8), (1,9),(1,10), (2,2), (2,3)…] we have 2 different options. So we must divide 90 by 2 to get the real outcome of 45 different outcomes.

Now let’s take it one step further and pretend we picked a 3rd number. Let’s also pretend this number is the number 4. Earlier we saw that the outcome (1,7) could either show up as 1 then 7, or 7 then 1. Let’s suppose the first occurred (1 then 7), then by adding the number we get 3 different choices as to where to put it: 4 then 1 then 7, 1 then 4 then 7, 1 then 7 then 4. [Note that the same thing can be said if we had chosen 7 then 1]. So this time instead of having possibilities, we have possibilities. [We get 6 by multiplying 2 with 3. 2 since we can have 1 then 7 and 3 since we can put the number 4 first, middle, or last].

Now we can see that if we added a 4th number we would have .

The lottery follows this same principle. So applying this logic, lets reexamine our lottery:

  • Lotto A: Since 6 numbers were chosen we must take our original number and divide appropriately:
    possibilities
  • Lotto B: Since 5 numbers were chosen the first time, and only 1 the second time we must take our original number and divide appropriately:
    possibilities

So you have to buy over 17 million more tickets for Lotto B to give you a guaranteed winning ticket! So if you chose Lotto A, you just won the lotto!