CSC 341: January 26, 2007

From CSWiki

1 Instructor's notes for the class session
- 1.1 Proof structures
- 1.2 Other activities
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

Proof structures

To prove a conditional, "If A then B," start by assuming its protasis (A), and take proving the apodosis (B) as your goal.

To prove a universal generalization, "All Xs have the property P," start by taking a representative X ("Let x be any X"), and take it as your goal to prove that that representative has property P. If you can do this without making any assumptions about the representative that aren't shared by all Xs, you're done.

To prove a universal negative, "No Xs have the property P," take a representative X and show that it can't have the property P. Often this inner proof is by contradiction -- ("Suppose that our representative x did have property P. Then it would follow that ... [something impossible or contrary to a previously proven theorem]").

To prove a biconditional, "A if, and only if, B," separate it into two conditionals ("If A, then B" and "If B, then A") and prove each conditional separately.

The proof of an existential statement, "There is some X that has property P," is often a proof by construction. A single instance is sufficient to prove an existential proposition.

Existentials are often embedded inside universal generalizations ("For every x that has property P, there is a y that has property Q"). Start with the outer quantifier -- "Let x be any object that has property P." Now the goal is to prove the inner existential -- try to prove it by constructing y, using x in the construction somehow.

To be complete, a proof by construction has to give an unambiguous recipe, leaving no steps or pieces unspecified.

In a proof by contradiction, you assume the exact negation of what you are trying to prove and show that it has a consequence that is impossible or inconsistent with previously established theorems. Be careful in negating the conclusion you want to draw. The negation of a proposition S has to cover absolutely all of the possibilities that S does not cover, and absolutely none of the possibilities that S does cover. For instance, the negation of "All Xs have property P" is not "No Xs have property P," but rather There is an X that does not have property P."

The structure of a proof by mathematical induction is very similar to the structure of a Scheme procedure defined by recursion over natural numbers: There is a base case, which is often trivial or obvious, and then there is an induction step, in which you assume that everything works (the proposition holds, or the recursive procedure returns the correct result) in the case of a given natural number k, and arrange somehow for everything also to work in the case of the next natural number, k + 1.

Since the reasoning has to work no matter what k is, you can't assume that it has any special properties of particular natural numbers in the reduction step.

The induction step in a proof by mathematical induction is actually a universal generalization with a conditional inside: "For every natural number k, if k has the property P, then k + 1 has the property P." (Note that this is a different generalization than the one that will ultimately follow from the base case and the induction step together -- that one says, unconditionally, that every natural number n has the property P.) So, to start the proof of the induction step, follow the advice given above for universal generalizations ("Let k be any natural number") and then the advice given above for conditionals ("Suppose that k has the property P, and aim for the apodosis -- "k + 1 has the property P" -- as the goal of the proof).

In formulating the induction hypothesis, it's almost always clearer to choose a different letter for the variable of induction from the one that you use to formulate the generalization, as I did above (k instead of n, so that the induction step is "If the proposition holds when n = k, then it also holds when n = k + 1"). The idea is that, in the induction hypothesis, you don't want even to appear to be assuming that the proposition holds for all natural numbers or whatever -- all you get to assume in the induction hypothesis is that it holds for a representative natural number k.

[edit]

Other activities

Do some exercises from the end of chapter 0.

[edit]

Study questions

Is the function in Example 0.8 onto?
Is the function in Example 0.9 onto?
The adjacency relation for a graph is a binary relation on the set of its nodes. Applied to nodes u and v, the adjacency relation returns TRUE if, and only if, u and v are the endpoints of some edge in the graph. Give an example of a graph that has an equivalence relation as its adjacency relation.
If the cardinality of an alphabet is m, what is the cardinality of the set of strings of length n over that alphabet?
By definition, every alphabet is finite and every string over an alphabet is finite. Is it possible, then, for a language to be infinite?
Is the Cartesian product of two languages a language?
Prove or disprove the statement that, for any strings z and w on the same alphabet, z is a substring of w if, and only if, zz is a substring of ww.
Prove or disprove the statement that, for any strings z and w on the same alphabet, z is a substring of w if, and only if, the reversal of z is a substring of the reversal of w.
Prove or disprove the statement that, for any strings z and w on the same alphabet, z is a substring of w if, and only if, z is a substring of ww.

[edit]

Proposed Solutions

Yes, example 0.8 is onto.
Example 0.9 is also onto. (Because f(g) can yield any integer from 0 through 3.)
Does the graph have to be directed inorder for the relation to be reflexive? If not, then the undirected, complete graph $K 3$ (a triangle) would satisfy the equivalence relation. Let $a, b, c$ be the vertices of the graph. If there is an edge between $a$ and $b$ , then there is certainly an edge between $b$ and $a$ (symmetric). If there is and edge between $a$ and $b$ , and there is an edge between $b$ and $c$ , then there is an edge between $a$ and $c$ (transitive).
$m n$ is the cardinality of the set of strings of length $n$ over an alphabet of cardinality of $m$ . (Consider a string of length $m$ over the binary alphabet of cardinality $2$ : we see that there are $2 n$ possible strings of length $n$ .)
Yes, it is possible for a language to be infinite. On a finite alphabet, there are a finite number of strings of any given length n. In fact, that number is at most the length of the alphabet to the nth power. However, no matter how large n is, you can always add one to it. Therefore, while there is only a finite number of strings of any given length, it is possible for the number of strings of all possible lengths to be infinite.
Yes. The "symbols" in the new language just become pairs $(x, y)$ where $x$ is from the first language and $y$ is from the second language.
This statement is false, and can be proved by construction. Let z = "foo" and w = "foobar". Clearly, "foofoo" is not a substring of "foobarfoobar", so z can be a substring of w without zz being a substring of ww.
This statement is true. Let $\mathcal{R}(x)$ designate the reversal of x. Suppose that z is a substring of w. $\mathcal{R}(z)$ must be a substring of $\mathcal{R}(w)$ because $\mathcal{R}( \mathcal{R}(z))$ is a substring of $\mathcal{R}(\mathcal{R}(w))$ whenever z is a substring of w.
This statement is true. If z occurs in w, z must also occur in ww. In fact, if z occurs in w, it must occur at twice in ww, as every set of characters that occurs in w occurs twice in ww. It is worth noting that the converse of this statement does not hold; z may be a substring of ww without being a substring of w. For example, z may equal "cab", and w may equal "abc".