Master Discrete Math 2020: More Than 5 Complete Courses In 1

In order to do mathematics, we must be able to talk and write about mathematics. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.

In this video, we’ll learn how to break apart statements into their individual components.

Easily the most common type of statement in mathematics is the implication. Even statements that do not at first look like they have this form conceal an implication at their heart. Consider the Pythagorean Theorem. Many a college freshman would quote this theorem as a squared plus b squared equals c squared. This is absolutely not correct. For one thing, that is not a statement since it has three unknowns in it. Perhaps they imply that this should be true for any values of the unknowns? So maybe like 1 squared plus 5 squared equals 2 squared? No, that can’t be right. How can we fix this? Well, the equation is true as long as a and b are the legs or a right triangle and c is the hypotenuse. In other words: If a and b are the legs of a right triangle with hypotenuse c, then a squared plus b squared equals c squared. This is a reasonable way to think about implications: our claim is that the conclusion (the “then” part) is true, but on the assumption that the hypothesis (the “if” part) is true. Now here is the part that is absolutely crucial: We make no claim about the conclusion in situations when the hypothesis is false... 2 Still, it is important to remember that an implication is connective in a statement, and therefore is either true or false. The truth value of the implication is determined by the truth values of its two parts, the if and the then parts. Technically, you can simplify the concept of an implication. We say that an implication is true either when the hypothesis is false, or when the conclusion is true. This leaves only one way for an implication to be false: when the hypothesis is true and the conclusion is false. Let’s go through an example.

This is definitely an implication: P is the truth value of the statement “Bob gets a 90 on the final,” and Q is the truth value of the statement “Bob will pass the class.” Suppose I made that statement to Bob. In what circumstances would it be fair to call me a liar? What if Bob really did get a 90 on the final, and he did pass the class? Then I have not lied; my statement is true. However, if Bob did get a 90 on the final and did not pass the class, then I lied, making the statement false. The tricky case is this: what if Bob did not get a 90 on the final? Maybe he passes the class, maybe he doesn't. Did I lie in either case? I think not. In these last two cases, P was false, and the statement P implies Q was true. In the first case, Q was true, and so was P implies Q. So here’s how this works. P implies Q is true when either P is false or Q is true… Now just to be clear, although we sometimes read P -> Q. As “P implies Q” we are not insisting that there is some causal relationship between the statements P and Q. In particular, if you claim that P implies Q is false, you are not saying that P does not imply Q. You are saying that it is not true that P implies Q. Later on in this course, we will show exactly why it is that P does not imply Q is not the same thing as P implies Q is false... Now, let’s go through some examples. Thank you so much, and I will see you in the next lecture.

It is important to understand the conditions under which an implication is true not only to decide whether a mathematical statement is true, but in order to prove that it is. Proofs might seem scary (especially if you have had a bad high school geometry experience) but all we are really doing is explaining (very carefully) why a statement is true. If you understand the truth conditions for an implication, you already have the outline for a proof. Now the crappy proving techniques that you learned in geometry.. You can just pretend that never happened. We will not be doing those proofs because they do not really reflect what a proof should be. A proof is just a logical defense of a statement. You can make that defense in the same way lawyers defend their clients. Just gather the facts of what you know and you that to show that a statement is true. That’s it… That is a proof. Now, in discrete math, we will be proving many implications with what are known as direct proofs. Perhaps a better way to say this is that to prove a statement of the form P→ Q, P→Q directly, you must explain why Q is true, but you get to assume P. P is true first. After all, you only care about whether Q. Q is true in the case that P. P is as well. There are other techniques to prove statements (implications and others) that we will encounter throughout our studies, and new proof techniques are discovered all the time. Direct proof is the easiest and most elegant style of proof and has the advantage that such a proof often does a great job of explaining why the statement is true. This sort of argument shows up outside of math as well. If you ever found yourself starting an argument with “hypothetically, let's assume …,” then you have attempted a direct proof of your desired conclusion. In the next lecture, we’ll discuss the converse and the contrapositive of implications. I’ll see you then.

We need some notation to make talking about sets easier.

Is it possible to add two sets? Not really, however there is something similar.

This video is the 1st part of the lesson on how to interpret functions with set theory. It is worth making a distinction between a function and its description. The function is the abstract mathematical object that in some way exists whether or not anyone ever talks about it. But when we do want to talk about the function, we need a way to describe it. A particular function can be described in multiple ways.

This video is the 2nd part of the lesson on how to interpret functions with set theory.

Recursively defined functions are often easier to create from a “real world” problem, because they describe how the values of the functions are changing. However, this comes with a price. It is harder to calculate the image of a single input, since you need to know the images of other (previous) elements in the domain.

Let's investigate special properties functions might or might not possess. There’s a lot of terminology in this course, and it can be easy to get lost in the words and terms, so let’s do some examples to solidify what these three terms mean.

To illustrate the contrast between injective and surjective, consider a more formal definition of each, side by side, and we'll discuss what we notice.

In this video, we'll be taking a close look into the codomain.

In this video, we'll cover all of the main concepts and definitions within the context of functions.

Relations can be a tricky subject in discrete math because it seems so foreign to the mathematics that you are used to. I want to start off the discussion about relations with this: you already know relations. You just don’t know that you know.

So far, we’ve discussed how equivalence relations is fancy for the “equals symbol” and we’ve discussed how it is important for us to be very careful when defining the equals symbol, since it can be used loosely and can even be misused sometimes. In this video, we’ll define equivalence relations and we’ll cover some examples.

In the last lecture, we discussed equivalence relations and equivalence classes in much detail. In this lecture, we’ll discuss the final relation, which is the partial orderings.

In mathematics, I would argue that the genre of math that is framed far too often as “easy” is counting. In this course, you will likely find that counting is a lot harder than you think it is, and no I don’t mean counting to one million is hard, which it is. I mean that it is hard to count when it’s difficult to know what exactly it is you’re counting, or how to organize the objects you wish to count.

In this video, we will discuss the multiplicative principle. You can’t just rely on language to solve counting problems. You have to rely on your ability to organize collections.

Do you believe the additive and multiplicative principles? How would you convince someone they are correct? This is surprisingly difficult. They seem so simple, so obvious. But why do they work? To make things clearer, and more mathematically rigorous, we will use sets.

Let’s take a look at the Additive Principle using Set Notation.

In this video, we will look into the Multiplicative Principle using Set Notation. When it comes to combining sets using multiplication, the Cartesian Product is the best representation of this combination of two sets. Let’s take a look at the Cartesian Product and use the Cartesian Product to count, in an example.

While we are thinking about sets, consider what happens to the additive principle when the sets are NOT disjoint...

In the last video, we discussed the principle of inclusion and exclusion with two sets. In this video, we will discuss the Principle of Inclusion and Exclusion as it applies to three sets. Let’s start with the rule, and then we’ll approach this from a different perspective.

Suppose we look at the set A={1, 2, 3, 4, 5}. How many subsets of A contain exactly 3 elements? First, a simpler question: How many subsets of A are there total?

In this video, we will discuss bit strings.“Bit” is short for “binary digit,” so a bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1.

The integer lattice is the set of all points in the Cartesian plane for which both the x and y coordinates are integers. If you like to draw graphs on graph paper, the lattice can be thought of as the set of all the intersections of the grid lines. A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically.

Binomial coefficients are the coefficients in the expanded version of a binomial. What happens when we multiply a binomial out? This is done by multiplying everything out (which you might refer to as FOIL-ing) and then collecting like terms. In fact, there is a quicker way to expand the binomials.

In this video, we will synthesize all that we have learned so far about the binomial coefficient and how the binomial coefficient can be used.

If you recall from a previous lecture, we discussed a certain recurrence relation with bit strings. Since bit strings and binomial coefficients are analogous, this means that the recurrence relation for bit strings can also be applied to binomial coefficients.

Using the recurrence relation, and the fact that the sides of the triangle are 1’s, we can easily replace all the entries above with the correct values of n choose k. Doing so gives us Pascal’s triangle. We can use Pascal’s triangle to calculate binomial coefficients.

A permutation is a (possible) rearrangement of objects.

Sometimes we do not want to permute all of the letters/numbers/ elements we are given. In general, we can ask how many permutations exist of k objects choosing those objects from a larger collection of n objects. We write this number P(n, k) and sometimes call it a k-permutation of n elements.

Here is another way to find the number of k-permutations of n elements.

What Are The Patterns In Pascal's Triangle And Binomial Identities? Have a look again at Pascal’s triangle. Forget for a moment where it comes from. Just look at it as a mathematical object. What do you notice?

In this video. we'll go through examples with binomial identities and combinatorial proofs.

Consider the following counting problem: You have 7 cookies to give to 4 kids. How many ways can you do this? Take a moment to think about how you might solve this problem.

How many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie? What can you say about the corresponding stars and bars charts?

There are instances when we must use the Principle of Inclusion/Exclusion. The Principle of Inclusion/Exclusion gives a method for finding the cardinality of the union of not necessarily disjoint sets.