Discrete Mathematics: An Open Introduction, 4th edition (preview)

So far we have seen how the logical form of a statement we wish to prove can inform how the build the scaffolding of a proof. The proof structure can only get us so far though: to flesh out the proof skeleton requires understanding of the mathematical objects and structures the proofs are about. Some of this can come from carefully reading definitions. Yet there is also some less concrete understanding and intuition that comes from working with the objects and structures that can lead to that “ah-ha!” moment of inspiration that suggests how to proceed with a proof.

Another reason to shift our focus toward proofs about discrete structures is that doing so illustrates an important feature of mathematics: abstraction. We have been proving particular facts about particular problems. We might even start to notice similarities about the proofs of some solutions. This very well could be due to the underlying mathematical structures that the problems are (secretly) about. If we prove the general facts about these structures, then we can apply these “theorems” to many different problems.

Some discrete structures lend themselves to particular styles of proof and there are some “standard” proof techniques that apply to particular structures. We will see some of this here, but mostly we take this opportunity to remind ourselves of some of the basic definitions and properties for discrete structures, and use the proofs about them to help understand these better.

The sets in the example above were small and easy enough to write down the elements of the sets. However, we can also prove subset relationships between sets if this isn’t practical or even possible (perhaps the sets are infinite). Let’s look carefully at how we could have reasoned about the example above.

We claimed that every element of \(B\) was also an element of \(A\text{.}\) Another way to say this: for all numbers \(n\text{,}\) if \(n\) is an element of \(B\text{,}\) then \(n\) is also an element of \(A\text{.}\) Recognizing this as a conditional statement, we can proceed to give a direct, contrapositive, or contradiction proof of the fact. Here a direct proof would be perfectly acceptable. Let’s try it:

To be clear, this proof is way more than we would normally do for this example, but its format should be illuminating. Proving that one set is a subset of another is really the same as proving an implication!

To give an example of how we can apply the definition of subset in a more general setting, let’s prove a basic fact about subsets.

Let’s now prove this fact about numbers: every multiple of 9100 is also a multiple of 13. We could factor 9100, but here is an easier way. The set of multiples of 9100 is a subset of the set of multiples of 91. And the set of multiples of 91 is a subset of the set of multiples of 13. Now apply the proposition above.

A function \(f:A \to B\) is a rule that assigns each element of the set \(A\) (the domain) to exactly one element of the set \(B\) (the codomain). It is any rule: there doesn’t have to be a formula or rational for it, we just need to match up elements from \(A\) to elements in \(B\text{.}\) For example, we could let \(A\) be the set of students enrolled in a particular Discrete Math course and let \(B\) be the set of months of the year. Now define the function \(f:A \to B\) to be the rule that assigns to each student the month in which their birthday falls. Since every student has an assigned month, and no more than one month, this is a function.

Here is a definition of a particular type of function.

Consider the student to birth month function again. Could this possibly injective? Or put another way, must there be two students in the course with the same birth month (which would say the function is not injective)? The answer seems to depend on how many students are in the class.

But let’s pause and think about the more general fact about functions we have here. Let’s prove the following fact. Recall that \(|A|\) denotes the cardinality (size) of the set \(A\text{:}\) the number of elements in \(A\text{.}\)

Does this proof remind you of our pigeonhole-like proofs? It should, since this is precisely (one of) the carful formulations of the pigeonhole principle. We could definitely have proved the fact about students sharing a birth month, but now we can just apply the proposition above and be done. When you apply a theorem or proposition to get directly prove another result, we call the latter result a corollary.

A relation on a set \(A\) is a set of ordered pairs of elements from \(A\text{.}\) We can think of a relation as a way to describe a type of relationship between elements of \(A\text{.}\) For example, we might have a relation on the set of people at a party that describes who is friends with whom. We might have a relation on the set of natural numbers that describes which pairs of numbers are related by the relation \(x \lt y\text{.}\)

Relations permeate all of mathematics, often without us even thinking of them. Whenever you make a statement about two elements of set, you are implicitly defining a relation. The statement is true when the pair is in the relation. For example, the statement “3 is less than 5” is true because the pair \((3,5)\) is in the relation \(\lt\text{.}\) In fact, using the language we developed in Section 1.3, we can now say that a relation is just a predicate, where the variables come from the same set.

Often relations have special symbols like “\(=\)” or “\(\le\)” or “\(\perp\)”. When we talk about a general relation, we will either use \(\sim\) and write \(x \sim y\text{,}\) or use a capital letter like \(R\text{,}\) and write \(R(x,y)\) or \(xRy\) or even \((x,y) \in R\) (these all mean the same thing).

When we study relations, we try to identify properties that relations might have. Here is an example of a very common property.

We will spend all of Chapter 2 studying proofs about graphs, since this is such a rich area of mathematics. As a preview, here is an example of how graph proofs can go.

A graph is a set \(V\) of vertices and a set \(E\) of edges. The edges are two-element subsets of the vertices, and we can think of them as representing relationships between the vertices. Note this is an abstract definition of a graph using sets, but we often draw graphs using dots for the vertices connected by lines for the edges, as this gives us a nice picture of what is going on.

Since graphs represent a type of relationship between elements (vertices), we can use graphs to represent many real world problems. For example, the vertices of a graph might represent people at a party. Each edge can represent a handshake between two people. So if we wondered whether it is possible for the 15 people at a party to each shake hands with exactly 3 people there, we are really asking whether there is a graph with 15 vertices where each vertex belongs to 3 edges. (“Belongs to”?? Yes, because an edges is two-element subset of the vertices, so if an edge “touches” or “comes out of” a vertex, that means the vertex belongs to that particular two-element subset.)

Here is a definition related to this idea.

So is it possible for among 15 people for everyone to shake hands with exactly three people? Well, is there a graph with 15 vertices, all of degree 3? The answer is no!

One way you can see this is if you ask how many edges such a graph would have. Each vertex is incident to three edges, so counting incidences, we get \(15\cdot 3 = 45\text{.}\) But every edge is incident to two vertices, so we have counted each edge twice. So the number of edges in such a graph would be \(45/2 = 22.5\text{.}\) But the number of edges in a graph must be a whole number, so there is no such graph.

This suggests that we can say something more in general. The following proposition is a simple consequence of the Handshake Lemma 2.1.5, which we will prove in Section 2.1. Here we give a complete proof of this particular formulation of it.