Discrete Mathematics

A math textbook will assume you know the basics of representation theory and then a page later write ${\varnothing}$ is the empty set, just in case you'd forgotten.

The overarching focus in the following materials is with proof. Question: What is a proof? A proof is a method of ascertaining the truth. One method of proof is a mathematical proof — a logically valid path from assumptions to conclusions, collectively forming a sound argument. But there are other methods of proof. The scientific method is one method of proof. We begin with a question, form a hypothesis, conduct experiments confirming or denying that hypothesis, and reach a conclusion. A trial is another method of proof. It begins with a complaint, then a defense, then an adverserial proceeding before a fact-finder presenting arguments and evidence, then a verdict by the fact-finder, then a decision from the court.

Here, we are focused on just one method: mathematical proof. A mathematical proof is the verification of a proposition by a chain of logical deductions from a set of axioms. In mathematics, the proof is a showing that something is true always. Regardess of creed, ethnicity, beliefs, gender, country, planet, universe, time — anything that differentiates another — a proposition mathematically proven to be true is true. Always. This is an extremely stringent and rigorous standard. The only field more formal and stringent than mathematics is logic. The logician is to the mathematician what the mathematician is to the layperson. If we think mathematics is abstract, take a look at what the logicians in the philosophy department are up to. A proposition is a statement that is either true or false. For example, ${2 + 3 = 5.}$ This is a true proposition. Here is another proposition:

The proposition above reads, "For all ${n}$ in the set of natural numbers, ${n^2 + n + 41}$ is a prime number." The part of the proposition ${prime(n^2 + n + 41)}$ is called a predicate. A predicate is a proposition whose truth depends on the value of a variable. In this case, the truth of the predicate ${prime(n^2 + n + 41)}$ depends on the variable ${n.}$

The part of the proposition ${\forall n \in \nat}$ is called the domain of discourse. This tells us that the predicate ${prime(n^2 + n + 41)}$ relates only to ${n \in \nat.}$ We're not talking about the real numbers, we're not talking about the integers, we're not talking about the complex numbers. We're talking about the natural numbers. The symbol ${\forall}$ means "for all" and it is called a quantifier. More specifically, it is called a universal quantifier.

To show that ${\forall \in \nat: prime(n^2 + n + 41)}$ is true, we have to determine whether the predicate ${prime(n^2 + n + 41)}$ is true for any natural number ${n.}$ In other words, no matter what natural number value of ${n}$ is, ${prime(n^2 + n + 41)}$ is true. We can try some values:

This method of verification is called the method of exhaustion — we exhaust all of the possibilities before we exhaust ourselves.

We could keep going, and it seems as if no matter what natural number we put in, it's always prime. In a lot of other fields, this check would have been enough. In physics, if we ran 20 experiments, that would have been more than enough. In criminal law, a single trial would have been not only enough, but mandatory (double jeopardy). Mathematics, however, is rigorous. Repeated observation is not enough. As the philosopher David Hume famously argued, the repeated past observation of a phenomenon in does not imply that the phenomenon will always occur.

In fact, the proposition above is a good example:

Or, an even more obvious example:

The proposition ${\forall n \in \nat: prime(n^2 + n + 41)}$ is false. Here is another very famous proposition:

has no positive integer solutions.

This proposition is called Euler's sum of powers conjecture. The legendary mathematician Leonard Euler conjectured the proposition above to be true in 1769. It was unsolved for over two hundred years before a very clever mathematician named Noam Elkies disproved it in 1988. His solution:

In disproving Euler's sum of powers conjecture, the correct proposition is now:

Here, we see a new quantifier, ${\exists.}$ This symbol means "there exists." This is called an existential quantifier. Here is another proposition:

has no positive integer solutions.

In formal notation: ${\nexists x, y, z \in \uint^{+} : 313(x^3 + y^3 = z^3).}$ A line crossing out the existential quantifer, ${\nexists,}$ means "there does not exist." This proposition turns out to be false, but the earliest counterexample has over a thousand digits. There is simply no way to verify this by the method of exhaustion; a computer can't do it, let alone ourselves.

Now we might be asking, why on earth would we ever want to ascertain the truth for these propositions? It turns out that the last example is something extremely important. The equation ${313(x^3 + y^3 = z^3)}$ is an equation for an elliptic curve. Knowing the proposition above is true turns out to be central to factoring extremely large integers. And factoring is something very important in the real world — it is how cryptographic systems are made and broken. GroupMe messages, private pictures, medical records, trade secrets, classified government information, they all depend on cryptography. Ascertaining the truth of the above proposition caused massive shift in how cryptographic systems were designed — we went from using hundred digit SSL numbers to thousand digit SSL numbers in the wake of the conclusion above.

Here is another famous proposition:

The regions in any map can be colored in 4 colors so that adjacent regions have different colors.

This is the famous four-color theorem. A mathematician named Francis Guthrie conjectured the proposition above to be true in 1852. For next century, mathematicians attempted to solve this problem, all of which were failed attempts. In 1879, the mathematician Alfred Kempe presented a proof-by-picture that was believed to be correct for over a decade. Kempe's idea was that all maps fell into certain types, and from that axiom, he concluded that any map could be colored according to the proposition. A proof-by-picture is a method of proof wherein the truth of a proposition is ascertained by pictoral evidence. They are almost always very, very wrong (but they are, of course, a helpful device for conjecturing). In 1890, a mathematician named Percy Heawood showed that Kempe's proof was wrong.

The four-color theorem was proved true by mathematicians Kenneth Appel and Wolfgang Haken in 1977. However, unlike the previous proofs we've discussed, Appel and Haken had to use a computer to check thousands of cases. Mathematicians were skeptical — how do we know that the computer did the right thing? What if the computer missed a case? Another proof was presented in 1997, and yet another proof was presented in 2005, but these too were done with programming. Mathematicians have accepted the theorem to be proved, but it is nowhere near as satisfying as a human proof.

Here is another proposition:

Every even integer greater than 2 is the sum of two prime numbers.

For example, ${24 = 11 + 13,}$ ${16 = 11 + 5,}$ ${32 = 13 + 19,}$ and so on. This is proposition is known as Goldbach's conjecture, and it is one of the most famous unsolved problems in all of mathematics. The proposition was conjectured to be true by German mathematician Christian Goldbach in a letter he wrote to Leonhard Euler in 1742. To this day, no one knows if the proposition is true or false.

Here is a simpler proposition:

The symbol ${\nc}$ means "implies." Thus, the proposition above reads, "For any integer ${n,}$ if ${n \geq 2,}$ then ${n^2 \geq 4.}$" An implication ${p \nc q}$ is true if ${p}$ is false or ${q}$ is true. Thus, if ${p}$ is true, and ${q}$ is true, then ${p \nc q}$ is true. If ${p}$ is false and ${q}$ is true, then ${p \nc q}$ is false. But if ${p}$ is false, then ${p \nc q}$ is true, regardless of whether ${q}$ is true or false. The last point is important to remember: False implies anything is true. This is strange thing to think about, so let's try and think about it in terms of an example.

Consider this proposition: "If fish can walk, then dogs are mammals." This implication is true. Why? Because dogs are mammals regardless of whether fish can walk. "If fish can walk, then the earth is flat." Again, this implication is true; "the earth is flat" is false regardless of whether fish can walk. False implies anything.

Here is another proposition:

The symbol ${\iff}$ means "if and only if." The proposition thus reads, "For any integer ${n,}$ ${n^2 \geq 2}$ if and only if ${n^2 \geq 4."}$ The ${\nc}$ tells us that there are implications both ways:

1. ${n \geq \nc n^2 \geq 4}$
2. ${n^2 \geq 4 \nc n \geq 2}$

Thus, to verify the original proposition, we must verify the two component propositions. Here, we see that the original proposition is false if we suppose ${n = -3.}$

We see that ${p}$ is true, but ${q}$ is false. Because the component proposition ${n^2 \geq 4 \nc n \geq 2}$ is false, the original proposition ${n \geq 2 \iff n \geq 4}$ is false. Thus, ${p \iff q}$ is true only if both ${p}$ and ${q}$ are true, or both ${p}$ and ${q}$ are false. The crucial point: Whenever we have an iff (if and only if) proposition, we must always check both ways.

Let's think a bit more about propositions. Propositions come in several forms. Some propositions are called axioms. These are propositions that we assume are true. Axioms are effectively propositions that are treated as true without proof. The word axiom comes from the Greek word axioma, meaning "what is thought fitting" or "to think worthy." Essentially, something we think is worthy enough to be true.

In mathematics, we must make assumptions. Without assumptions, we can never reason about anything. The difference between mathematics and other fields, however, is the requirement of being hyper-vigilant and always identifying what assumptions we've made. There are numerous axioms, or assumptions, in mathematics:

If ${a = b}$ and ${b = c,}$ then ${a = c.}$

This is called the axiom of transitivity, or the transitive property, and there is no proof for it. But, we've accepted that it's a pretty good proposition that seems to hold up, so we accept it as true.

Axioms can be contradictory depending on context. In Euclidean geometry, we have the following axiom:

Given a line ${\ell}$ and a point ${p}$ not on ${\ell,}$ there is exactly one line passing through ${p}$ parallel to ${\ell.}$

Now, in spherical geometry, we have another axiom:

Given a line ${\ell}$ and a point ${p}$ not on ${\ell,}$ there is no line through ${p}$ parallel to ${\ell.}$

In hyperbolic geometry:

Given a line ${\ell}$ and a point ${p}$ not on ${\ell,}$ there are infinitely many lines through ${p}$ parallel to ${\ell.}$

Does this mean the axiom is wrong, or worse, that the entire mathematical field is wrong? Of course not. The axioms hold up their fields well. The key point, however, is that the axioms are restricted to their fields. In other words, the axioms are contained in a particular domain of discourse. But, there are two rules about using axioms:

1. A set of axioms must be consistent.
2. A set of axioms must be complete.
3. A set of axioms must be decidable.

A set of axioms is consistent if no proposition can be proved to be both true and false. A set of axioms is complete if it can be used to prove every proposition is either true or false. A set of axioms is decidable if it provides an algorithm for deciding the truth or falsity of any proposition. These rules seem straightforward, but they turn out to be incredibly difficult to satisfy. Logicians and philosophers like Bertrand Russell, Alfred Whitehead, and David Hilbert spent signficant parts of their lives trying to find just one set of axioms that satisfied these rules. The debates and wars between these thinkers inspired others to join the struggle.

In the 1930s, a German logician named Kurt Godel proved that no set of axioms was complete and consistent. Separately, the English mathematician Alan Turing proved that no set of axioms was decidable (Turing's work in this area spawned the modern computer).

Godel proved that if we want consistency, there will always be true facts that we will never be able to prove. This particular proof is just one of Godel's incompleteness theorems. Godel's proof is best left to a course on logic, but the effect of this proof is profound: Perhaps Goldbach's conjecture is true, and it is impossible to prove.

Discrete mathematics is the mathematics of discrete and finite mathematical objects. Mathematical objects are abstract concepts — concepts like numbers, functions, triangles, matrices, groups, vector spaces, series, etc. Unlike what we might think of when we hear the word "object" — maybe a car, a table, or a molecule — mathematical objects are not physical. They do not move; they do not change over time; and they do not physically interact with real world entities.

We can classify mathematical objects into two categories: (1) discrete (i.e., finite) and (2) continuous (i.e., infinite). Discrete mathematics is a branch of mathematics separate from continuous mathematics, which concerns infinite, or continuous, mathematical objects. This difference might seem vague at the moment, but this is expected. The distinction can only be clarified with experience in both areas.

All ideas in mathematics, discrete or continuous, are discovered through logic.¹ Accordingly, a strong logic background is invaluable to any serious student of mathematics. As we study logic, we might find ourselves asking questions about knowledge and truth. Play with those questions. They are a strong indicator of encountering a link between philosophy and mathematics. Because these questions are excellent opportunities for deeper and playful thinking, the text will occassionally present difficult questions that may or may not have any clear answers.