The Red Viper's guide to mathematics - part 1: True or false?

Why am I doing this?

So, I've decided to do this after making a rather shocking (and some would say disturbing) discovery: Math is awesome, and I love it. Last October, I started my computer science studies, and my freshman year involves several courses (6 actually, maybe 7 if you count Data Structures) in different fields of math. I came on my first day scared out of my senses; math was the bane of me back in high-school. I mean, yeah, I passed my finals with an OK-ish grade, but it was nerve-racking and each and every moment was complete and utter suffering. I knew I'm going to have tons of math studies in my freshman year, but I figured I should just grit my teeth and get it over with, since I really wanted to take CS. But after my first lecture of the semester... I found out it wasn't all that bad. By the end of the semester, I found out that, despite myself, I'm actually starting to enjoy it. So, I figured I might as well share some of that nerdy enthusiasm with you, and pass on some of what I learned in a more "friendly" way than they do in school or in the academy.

I took the idea for this from the late ImpurestCheese, who shared her knowledge and love for animals with this community for quite a while before losing her battle against cancer not 2 years ago. I'm not much of an animal expert, and I've never really interacted with her all that much, but I hope to honor her in some way by sharing my growing knowledge of mathematics with you. It'll help me memorize it better myself as well, and you guys just might enjoy the read, so everyone's a winner.

What am I going to do here?

I'll focus mostly on logic, discrete mathematics, and set theory, at least for now. Maybe I'll add some calculus (AKA "evil") or linear algebra too, but those'll be a tad harder to pass on through forum threads - so I make no promises. I'll assume you have some basic knowledge from school, but you're more than welcome to ask me anything you don't understand, and I'll try my best to answer. If you ask a good question and I can't answer it, maybe I'll even ask my professors!

Anyway, let's start with formal proofs - pretty much the very basics of the basics. It was the very first thing I learned in discrete mathematics, which turned out to be my favorite subject last semester, so I figured I might as well start here.

Why do we need it?

Why do we need proofs? Well, my friends and I have this joke that math studies is like law studies: all you do is learn how to lie elegantly and call it a "proof". I like to think of math as the mommy and daddy of all science. It's probably the most precise field of science there is, and if you want precision, you can't do anything without basing it off some tangible, concrete evidence. Which is why every theorem, every corollary, everything in math requires proof. If you can't prove you're right, then you're wrong. There is (usually) no middle ground.

How do we do it?

How do you prove something in math, though? Well, first you need to know what you want to prove, obviously; then you need to gather everything that you already know that could help you prove it. Sounds easy, right?

Let's start with a very simple example, that might not look like it has anything to do with math at first glance: a vending machine. Dibs on the "Hershey's"!

Let's say that we have a vending machine and we want to know if it works properly. The only thing we know about vending machines is this: every time you insert a quarter into the vending machine, you should get a snack. Simple, right? Now, let's consider the following 4 possible situations:

1. You insert a quarter, and the machine drops a delicious Snickers bar. Awesome! Everything worked properly!
2. You insert a quarter, the machine does some machine-noises, but... nothing comes out. The machine must be broken!
3. You don't insert a quarter, and the machine drops nothing. What did you expect?
4. You don't insert a quarter, but the machine still drops a snack. Who doesn't love a free snack?

Now, in those 4 scenarios, it's quite obvious that in case 1 the machine worked properly, and in case 2 it was clearly broken. But... what about 3 and 4? Did the machine work, or did it not?

Now, if I were a vending machine technician, I might have given you a different answer. But, mathematically, the machine worked (or, at least, wasn't broken) in all cases other than case number 2. What we know is this: IF we insert a quarter, THEN the machine will drop a snack. Do we know what happens if we don't insert a quarter? Well, no, we don't, because we weren't told. In cases 3 and 4, we did not insert a quarter, and so the machine worked just fine as far as we care.

For another, more mathematical example, let's look at the following claim: let X be an integer. We say that X is odd if it yields a remainder when divided by 2. So, let's check whether X is odd, shall we? Again, 4 possible cases:

1. We divide X by 2 and the division yields a remainder. X must be odd!
2. We divide X by 2 and the division yields no remainder. Looks like X is even!
3. We divide X by 3 and the division yields a remainder. Is X odd? Well, could be! We weren't told what should happen if we divide it by 3.
4. We divide X by 3 and the division yields no remainder. Is X odd? Again, could be.

So, if we use the vending machine analogy, dividing by 2 is whether or not we insert the quarter, and getting the remainder or not is akin to getting our snack or not.

How do we write it?

Math is a universal language. Take a French mathematician and an Indian mathematician, I promise you they can communicate just fine if they keep it formal. Everything in math has its own unique marking, and this time we're talking about implications. Having a remainder when you divide X by 2 implies that X is odd, just like putting a quarter in the vending machine implies that you should get a snack.

We denote: P = our hypothesis (or assumption, or condition), and Q = our expected result (or conclusion). "P implies Q" is denoted: P⇒Q. Pretty intuitive, right? Another important symbol is "≡", which means "Is equivalent to", in the Boolean (true/false) sense. "True" and "False" are naturally denoted as just T and F respectively. Looking back at our vending machine example, we can properly denote it now:

So, with this in mind, we can conclude that:

• T⇒T≡T: The hypothesis held and we got the desired result - our assumption is true.
• T⇒F≡F: The hypothesis held and we did not get the desired result - our assumption is false.
• F⇒T≡T: The hypothesis did not hold but we still got the desired result - our assumption is true (but can still be refuted).
• F⇒F≡T: The hypothesis did not hold and we did not get the desired result - our assumption is true (but can still be refuted).

There are, of course, more symbols that are important to familiarize with. Here are a few:

• Equivalence/"If and only if": denoted "⇔". P⇔Q means P⇒Q and Q⇒P, basically a double-sided implication. For example, if we say: P = "Walks like a duck and quacks like a duck" and Q = "It is a duck", and then we say: "It walks like a duck and quacks like a duck IF AND ONLY IF it is a duck", we can write it as: P⇔Q. If it walks like a duck and quacks like a duck, then it is a duck - and if it is a duck, then of course it walks like a duck and quacks like a duck.
• Negation/"Not": denoted "¬". ¬P means "P is false". In general: (¬P≡T)⇔(P≡F). For example, if we say: P = "I'm happy", Q = "I cry", and also "If I'm NOT happy, then I cry", we can write it as: ¬P⇒Q. Do I cry if I am happy? Maybe. If I do, the claim still holds. Take note of double-negative: for example, if P = "I'm NOT happy", then ¬P = "I am happy", and naturally, ¬(¬P)≡P.
• And: denoted "^". P^Q means "P is true AND Q is true". In general: [(P^Q)≡T]⇔[(P≡T)^(Q≡T)]. For example, if we say: P = "I'm hungry", Q = "I'm tired", and R = "I'm cranky", and then we say: "If I'm hungry AND tired then I'm cranky", we can write it as: (P^Q)⇒R. Am I cranky when I'm just hungry, or just tired? Maybe. If I do, the claim still holds. We can now also write our claim about the ducks in another, more elegant way: we say: P = "Walks like a duck", Q = "Quacks like a duck", and R = "It is a duck", and then we say: "It walks like a duck and quacks like a duck IF AND ONLY IF it is a duck", we can write it as: (P^Q)⇔R.
• Or: denoted "∨". P∨Q means "P is true OR Q is true OR both of them are true". In general: [(P∨Q)≡T]⇔[(P≡T)∨(Q≡T)]. For example, if we say: P = "I'm hungry", Q = "I'm tired", and R = "I'm cranky", and then we say: "If I'm hungry OR tired then I'm cranky", we can write it as: (P∨Q)⇒R. Am I cranky when I'm just hungry, or just tired? Yes. Am I cranky in general? Also yes, but that's beside the point. An interesting note would be that standard implication, "P implies Q" is equivalent to "Not P, OR Q", i.e (P⇒Q)≡(¬P∨Q). Look at the table above if you don't believe me!
• Exclusive or/"Xor": denoted "⊕". P⊕Q means "P is true OR Q is true but NOT both". In general: [(P⊕Q)≡T]⇔[((P≡T)^(Q≡F))∨((P≡F)^(Q≡T))]. For example, if we say: P = "Alice will ask me to dance", Q = "Susie will ask me to dance", and R = "I will dance", and then we say: "I will dance IF Alice asks me OR Susie asks me but NOT if they both ask me", we can write it as: (P⊕Q)⇒R. Calm down there, ladies. "Xor" conditioning is pretty rare in mathematics, but it exists and is still relevant sometimes.

A few more examples:

1. Implication Is Coming:

• P = "You kill me"
• Q = "Your brother's a dead man"
• We write: P⇒Q

2. The Discrete Knight:

• P = "You die a hero"
• Q = "You live long enough to see yourself become the villain"
• We write: ¬P⇒Q

3. Fleetwood Math:

1. P = "You love me now"
2. Q = "You will love me again"
3. We write: ¬P⇒¬Q

4. Bye Bye, Ms. American π:

• P = "I had my chance"
• Q = "I could make those people dance"
• R = "Maybe those people would be happy for a while"
• We write: P⇒(Q^R)

Contrapositive:

Contrapositive is basically "proof by contradiction": switching and negating the hypothesis and conclusion of a conditional statement. With P being the hypothesis and Q being the conclusion, the contrapositive of P⇒Q is ¬Q⇒¬P. For example, if our statement is: "If you put a quarter in the vending machine, you'll get a snack", then its contrapositive will be: "If you did NOT get a snack, then you did NOT put a quarter in the vending machine". Our goal with using contrapositive is reaching a contradiction of out hypothesis: if we assumed the opposite of what we're trying to prove, and we see that it contradicts out hypothesis (or some other mathematical axiom), then we have our proof.

Many times, a theorem or a statement can be very hard to prove (or refute) directly, but contrapositive makes it a lot more easy - sometimes (rarely) trivial, even. Here's an example (mathematical and boring, there's a more entertaining one ahead):

Let X be a positive integer larger than 2. Assume X is even; therefore X is not prime (P = "X is an even integer greater than 2", Q = "X is not prime").

That example is actually easy to prove directly, but let's see how it can be done with contrapositive. We'll assume by contradiction that X is prime. Therefore, there does not exist any integer Y such that X/Y yields no remainder. Therefore, X/2 must yield a remainder. But we know X is even, so we reached a contradiction of our hypothesis that X is even, which means X cannot be prime!

Another example: Let's say I browsed the Battle forum the other day, and came upon an awesome CaV match, that had 4 great posts from each debater, and a very close competition on the votes. Therefore... Nick (@the_hajduk) was NOT one of the debaters. Proof:

Assume by contradiction that one of the debaters was @the_hajduk. We know that this debate ended after 4 posts from each debater and got as far as voting. But we also know Nick's track record at getting this far in a debate without quitting. That's a very obvious contradiction! Therefore Nick was most definitely not part of that debate, and our claim is proven.

So what does this whole implication thing have to do with proofs?

Well, everything! If I make a claim and I want to prove it, I need to know what my hypothesis is, and what the hypothesis implies. What we saw above is the basis for thousands of years in which all fields of math evolved. Every theorem we know started as P - a hypothesis, which people used to show the truth of some Q - a conclusion. And those theorems were used for finding other theorems, following the very same logic - and so on and so forth. It all started with a simple P, all those thousands of years ago, and is turned into P⇒Q⇒R⇒S⇒...⇒and now we have electric cars and space travel. Brilliant.

In conclusion:

Well, it isn't really a conclusion. This really is the very basics of it all, but there's still much and more to be said about proofs... but we will get there, this is just the first entry in this blog. Hopefully, there'll be enough feedback for me to make another, because I did enjoy making this one. I always enjoy sharing whatever knowledge I can with whoever I can. Don't worry, it'll get more and more interesting as we go on - but now the basics are out there for you to enjoy (or not). I'll again mention that I'm still on my freshman year, but even now I realize how much there is to it all that I really never knew back in high-school. I'm no expert on math - I don't even have a degree, heck I'm still on my freshman year. But I did gather knowledge of some really interesting stuff that I would love to share.

Anyway, that's it for now. Hope you liked it!

Well written and thought out...math still hurts my brain though=)

Wow. I am on my phone, so more to come, but I was an EE/Comp Sci major. This brings back memories of my discrete class.

Nice

I respect your post, even If my own interest in the subject is practically non-existent.

Math is absolutely necessary. I think one of the greatest challenges is appreciating it and even enjoying it. It’s problem solving at the perfect theoretical level. Awesome post!

Does this prove that the Earth is flat?

This is obviously wrong.

Lol. Mine too. I hope to develop an immunity =P

I'm sure they're very pleasant memories!

Thanks!

You might change your mind after I post some more entries. Set Theory is pretty fascinating, no joke.

Thanks! Yeah, once I started seeing the beauty in it, I started really enjoying it. Back in high-school all they taught me is some boring formulas and stuff, once I got to uni and started getting to the bottom of things, it got really interesting.

Absolutely.

Thank you!

Fixed.

Was this whole thing secretly just to savage Nick towards the end cause if so it makes it even better

@thorthunder98: ...maybe.

Did you get to calc 3 yet? I'm graduating with a cs degree in a few weeks and i have to say calc 3 was the most cancerous math course I've ever taken. The symbolic logic stuff was always fun though. Nice post anyways.

@johncena69swag: No, I'm taking calculus 2 right now. I don't have calculus 3 in my degree, maybe what you had distributed over 3 courses I have distributed over 2, or maybe you just had more calculus than me, lol.

But yeah, it's cancer. Calculus is absolutely evil. I like it, but it's evil.

What’s 1+1

Congrats on your degree. I personally found Calc 3 better than Calc 2, at least at my school. Calc 2 was the weed-out class. DE could be pretty bad, but our teacher was pretty laid back. I guess it depends on the school.

FREAking AWESOME!!!!

i am a cs student too and although math doesn't come easy for me i absolutely love it more than any other subject.

BTW this thread seems to focus on logic and proof or Discrete mathematics if i am being general.

imo graph theory is the most interesting side of discrete mathematics.

I haven't had graph theory, not yet anyway. Looking at it online it seems to resemble relations a lot though, which was a subject I really liked actually. My favorite so far though was set theory. Really fascinating, in my opinion. Combinatorics was blood-boiling but challenging in a good way. And calculus is pretty much the "Dark Souls" of mathematics: hard as all hell but highly rewarding, and boy did I love Dark Souls back in the day, lol.

Ahhh, thanks for bringing back all those memories of AP Calculus BC in high school.

Yeah, I also had this same sort of “epiphany” around 9th grade, where I suddenly began to view math in an entirely different way. Went from being barely above average to getting A’s just from changing the way I thought about it. Sometimes I even wonder if I’d smacked my head on a floor tile or something to unlock that part of my mind.

As dorky/nerdy as this may sound, I actually wish that more people get to experience this same thing too.

Well that was sorta off topic...

Well put together; I am in my final year of a maths undergraduate degree, specialising in logic and set theory as well as combinatorics and number theory- I hope to do a masters next year with a large emphasis on logic. Not that you seem to need it, but I'm happy to help with these posts in any way I can.

I think the Completeness Theorem could be an interesting result to try and reach with the posts as it's pretty mind-blowing, doesn't require much groundwork and seems to be a direction these posts are likely to take.

I haven't gotten to the completeness theorem yet, truth be told. I'm currently taking a course in logic and set theory, so I'm probably going to see it sooner or later. The more I progress, the more material I will have to write about. As I said, I'm still in my freshman year.

My thoughts were mostly to do some more entries on logic, functions, relations and set theory with maybe some basic calculus in between, and also combinatorics which is fun (when you don't have to do homework about it lol).

Thanks for your offer though, it's greatly appreciated!

@ourmanuel: Yeah, I've truly started to see the beauty in it which made it far more enjoyable and dare I say, easier. Not by much mind you, but easier to contend with.

Has to be in my top 10 things I never expected to see on Comic Vine.

@the_red_viper: Is this more math or simple logic?

I didn't read this properly at first, now I realize that I've studied this in my first year in high school.

@xlr87t3: Logic really is a field of math, but this is purely the basics which will be needed for future entries, including the 2nd one which I already posted several days ago.

Quite interessting.

I am also a math major and I find this post to be interesting.

Btw your explanation to proofs and logic could be improved by explaining validity and soundness first and foremost in your post.