CSC 341 (Fall 2021)

Reading: Constructive and Classical Proof

Whether we adopt the perspective of programmer or mathematician, we rely on modeling techniques such as mathematical sets or data structures to represent a subject, e.g., general computation, in a way that is amendable for subsequent analysis. However, whereas programmers are primarily interested in implementing algorithms that operate over these subjects, mathematicians are primarily interested in stating and proving properties of our subjects. Mathematical proof, therefore, is our primary activity in this course.

There are two broad classes of proof we will employ in this course:

Of special interest to us as computer scientists are constructive proof. Aconstruction of an abstract object that fulfills a property is really an algorithm for building objects that satisfies those properties. Thus, the study of constructive proof allows us to unite our two perspectives, programmer and mathematician, on the theory of computation.

Regardless of the technique employed, all of our reasoning must obey the following mantra:

Go to definition!

That is, our reasoning must be rooted in the formal definitions of the objects involved. For example, we will write down precisely what a machine contains. Therefore, when we write a constructive proof involving such machines, we will need to specify all of the machines’ components in some form or another.

In preparation for today’s class,

Definition (\(k\)-colorability): let a coloring of a graph \(G = (V, E)\) be a function \(f : V \rightarrow C\) from the vertices \(V\) of \(G\) to an abstract finite set of colors \(C\) such that vertices connected together by an edge from \(E\) have distinct colors. Call a graph \(k\)-colorable if there exists such a set of colors \(C\) and coloring function \(f\) with \(|C| = k\).

Definition (Cycle): a cycle in a graph \(G\) is a sequence of vertices \(v_1, v_2, \ldots, v_k\) of \(G\) such that each adjacent pair of vertices \(v_i\) and \(v_{i+1}\) are connected by an edge in \(E\) and \(v_k\) and \(v_1\) are also connected by an edge.

Claim: If a graph contains an odd-length cycle, then it is not 2-colorable.