Proofs about Discrete Structures

So far we have seen how the logical form of a statement can inform how to build the scaffolding of a proof. This can only get us so far though: To flesh out the proof skeleton requires an 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.

Why are we writing proofs? Besides practice in becoming better reasoners, diving into careful proofs about discrete structures is a way to learn more about the structures themselves. They are a playground for exploring mathematics, to help us build intuition for mathematical structures. So we study structures to help us write proofs about them, and we write proofs about them to help understand the structures. Bootstrapping!

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 between the proofs for some statements. This might 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 some standard proof techniques can 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.

Recall that a set is an unordered collection of elements. We can describe a set by listing these elements, or by specifying a property that all elements in the set satisfy. For example, \[A = \{1,2,3,4,5\}\], or \[B = \{x \in \N \st x \lt 10 \}\]. The second set here is the set of natural numbers (\(0, 1, 2, \ldots\)) less than 10. Notice that every element in \(A\) is also an element of \(B\). Here is a definition that captures that idea.

The sets in the example above were small, and it is 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\). Another way to say this: For all numbers \(n\), if \(n\) is an element of \(B\), then \(n\) is also an element of \(A\). 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!

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

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 rationale for it; we just need to match up elements from \(A\) to elements in \(B\). 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.

In the example below, we use two-line notation to describe a function. The top row contains the inputs, and the bottom row lists the corresponding outputs. So \(f:\{1,2,3,4\} \to \{a,b,c,d\}\) might be defined as, \[f = \twoline{1 \amp 2 \amp 3 \amp 4}{a \amp b \amp c \amp d}\], which means that \(f(1) = a\), \(f(2) = b\), \(f(3) = c\), and \(f(4) = d\).

Consider the student-to-birth-month function again. Could this possibly be 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\): the number of elements in \(A\).

Functions always have inputs from a set (called the domain) and outputs in a set as well (called the codomain). This naturally leads to facts to consider about the interaction between sets and functions.

Now let's prove something.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

A relation on a set \(A\) is a set of ordered pairs of elements from \(A\). We can think of a relation as a way to describe a type of relationship between elements of \(A\). 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\).

Relations permeate all of mathematics, often without us even thinking of them. Whenever we make a statement about two elements of a set, we 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\). In fact, using the language we developed in the subsection , we can 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\), or use a capital letter like \(R\), 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.

Proving that a relation is not transitive takes nothing more than finding a counterexample, which means finding three elements \(a\), \(b\), and \(c\) such that \(a \sim b\), \(b \sim c\), but \(a \not\sim c\) (remember, the only way for an implication to be false is for the hypothesis to be true and the conclusion to be false).

Perhaps slightly more interesting would be proof that a relation is transitive.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

We will spend all of 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 edge is a 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 15 people to each shake hands with exactly three people in their group? 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\). 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\). But the number of edges in a graph must be a whole number, so there is no such graph.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.