Professor Warren Esty, one of the authors of our main textbook, has made available a list of solutions to some of the problems from Chapter 1. They are most of the odd numbered problems. Please let him (or me) know if you find errors or typos, or if you have suggestions for alternative solutions or different approaches.
187 – The resolution method
September 19, 2011This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.
We would like to have a mechanical procedure (algorithm) for checking whether a given set of formulas logically implies another, that is, given , whether
is a tautology (i.e., it is true under all truth-value assignments.)
This happens iff
So it suffices to have an algorithm to check the (un)satisfiability of a single propositional formula. The method of truth tables gives one such algorithm. We will now develop another method which is often (with various improvements) more efficient in practice.
It will be also an example of a formal calculus. By that we mean a set of rules for generating a sequence of strings in a language. Formal calculi usually start with a certain string or strings as given, and then allow the application of one or more “rules of production” to generate other strings.
A formula is in conjunctive normal form iff it has the form
where each has the form
and each is either a propositional variable, or its negation. So
is in conjunctive normal form iff it is a conjunction of disjunctions of variables and negated variables. The common terminology is to call a propositional variable or its negation a literal.
Suppose is a propositional statement which we want to test for satisfiability. First we note (without proof) that although there is no known efficient algorithm for finding
in cnf (conjunctive normal form) equivalent to
, it is not hard to show that there is an efficient algorithm for finding
in cnf such that:
is satisfiable iff
is satisfiable.
(But, in general, has more variables than
.)
So from now on we will only consider s in cnf, and the Resolution Method applies to such formulas only. Say
with literals. Since order and repetition in each conjunct (1):
are irrelevant, we can replace (1) by the set of literals
Such a set of literals is called a clause. It corresponds to the formula (1). So the formula above can be simply written as a set of clauses (again since the order of the conjunctions is irrelevant):
Satisfiability of means then simultaneous satisfiability of all of its clauses
, i.e., finding a valuation
which makes
true for each
, i.e., which for each
makes some
true.
Example 1
From now on we will deal only with a set of clauses . It is possible to consider also infinite sets
, but we will not do that here.
Satisfying means (again) that there is a valuation which satisfies all
, i.e. if
, then for all
there is
so that it makes
true.
Notice that if the set of clauses is associated as above to
(in cnf) and
to
, then
By convention we also have the empty clause , which contains no literals. The empty clause is (by definition) unsatisfiable, since for a clause to be satisfied by a valuation, there has to be some literal in the clause which it makes true, but this is impossible for the empty clause, which has no literals. For a literal
, let
denote its “conjugate”, i.e.
if
and
if
Definition 1 Suppose now
are three clauses. We say that
is a resolvent of
if there is a
such that
,
and
We allow here the case , i.e.
.
187 – The P vs NP problem
September 19, 2011This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.
1. Decision problems
Consider a finite alphabet , and “words” on that alphabet (the “alphabet” may consist of digits, of abstract symbols, of actual letters, etc).
We use the notation to indicate the set of all “words” from the alphabet
. Here, a word is simply a finite sequence of symbols from
. For example, if
is the usual alphabet, then
would be a word.
We are also given a set of words, and we say that the words in
are valid. (
may be infinite.)
In the decision problem associated to , we are given as input a word in this alphabet. As output we say yes or no, depending on whether the word is in
or not (i.e., whether it is “valid”).
We are interested in whether there is an algorithm that allows us to decide the right answer.
414/514 – Metric spaces
September 19, 2011This is homework 2, due Monday September 26 at the beginning of lecture.
Let be a metric space.
- Show that if
is defined by
, then
is also a metric on
.
- Show that if
is open in
then it is open in
, and viceversa.
Recall that is open iff it is a union of open balls. Use this to explain why it suffices to show that if
is open in
then for any
there is an
such that
,
and similarly, if is open in
then for any
there is a
such that
.
In turn, explain why to show this it suffices to prove that for any and any
there is a
such that
and, similarly, for any there is a
such that
.
Finally, prove this by showing that we can take (no matter what
is) and similarly, find an appropriate
that works for
(again, independently of
).
- Illustrate the above in
as accurately as possible.
- Suppose that a sequence
converges to
in
and to
in
. Show that
.
- Is it true that a sequence
is Cauchy in
iff it is Cauchy in
? (Give a proof or else exhibit a counterexample, with a proof that it is indeed a counterexample.)
Show that any dense
subset of
has the same size as
.
Alan Turing year
September 5, 2011Alan Turing was born in London on June 23, 1912. The Alan Turing Year 2012 celebrates his life and scientific achievements. Here is a link to the official page.
Widely recognize for his contributions during the Second War to the solving of German ciphers, Turing is also responsible for the development of computer science, having isolated the key notion of Turing machine, the mathematical formalization of algorithm. He is also known for the notion of Turing test, aimed at “recognizing” artificial intelligence.
Unfortunately, Turing’s story is marred by his end. Rather than being held as a war hero (or a renown academic), being a homosexual, in 1952 Turing was charged with gross indecency under Section 11 of the Criminal Law Amendment Act of 1885 and required to undergo hormonal treatment, including chemical castration. Turing committed suicide on June 7, 1954. On September 10, 2009, the British government finally issued an apology.
Here is a link to the excellent Wikipedia entry on Turing. And here is a link to the Alan Turing page, maintained by Andrew Hodges, author of Alan Turing: The Enigma.
414/514 – Cauchy sequences
September 2, 2011This is homework 1, due Friday September 9 at the beginning of lecture.
We define absolute value as usual: Given a real , we say that
is
if
and is
otherwise.
Absolute values have useful properties: for any
. Also,
iff
. The key property is the triangle inequality:
.
Formally, a sequence is a function . As usual, we write the sequence as
rather than
A sequence is a Cauchy sequence iff for all
there is an
such that whenever
and
, we have
A sequence converges iff there is a real
such that for all
there is an
such that whenever
and
, we have
.
Note that these concepts also make sense in . Now we require all the
to be rational, and we require
and
to be rational as well.
- Show that if a sequence converges, then it is Cauchy.
- Give an example of a Cauchy sequence in
that does not converge.
- Show that any Cauchy sequence in
converges.
Cauchy’s way of defining the reals was to use Cauchy sequences as the basic building blocks rather than cuts. Again, the idea is that we want to have all the limits, and in some of these limits are missing. In the case of cuts, the way of solving the presence of gaps in
was by giving names to all the gaps (the cuts), and adding the names. The easiest repair to the lack of limits here will be the same: We give a name to the limits (the sequences themselves) and the reals will be just the sequences.
There is a problem here that does not occur with the construction using cuts, namely different sequences may have the same limit. We should identify all of them.
Recall that an equivalence relation on a set is a binary relation
that is:
- Reflexive: For any
,
.
- Symmetric: For any
, if
then also
.
- Transitive: For any
, if
and
, then
.
If is an equivalence relation, the equivalence classes determined by
are the sets
. An intuitive way of thinking about this is that we are looking at
from a distance, and so we cannot distinguish points that are close to one another, we just see them smashed together as a single point. Here, two points
are close iff
.
Let and
be two Cauchy sequences of rationals. Say that
iff
converges to
. Here, of course,
is the sequence
with
.
- Show that
is an equivalence relation. Check that any Cauchy sequence
is equivalent to infinitely many other sequences.
- Define
as the set of equivalence classes of the relation
. The elements of
are then Cauchy sequences or, more precisely, collections of Cauchy sequences. A typical element of
is a class
, and we think of
as the limit of
. Of course, we have a copy of
inside
: We can identify the rational
with the class
of all sequences
that converge to
.
- Define
in
and verify that with these definitions we have an ordered field.
- Verify that
is complete, meaning that the least upper bound property holds.
This gives a second sense in which is complete: It contains the limits of all Cauchy sequences. A small but important point not mentioned above is the following: Given a sequence
of rationals, let
be its “copy” inside
, i.e.,
. Then
is Cauchy iff
is Cauchy, and
converges to a rational
iff
converges to
.
Sets and games
September 1, 2011I just finished a talk at the Department Colloquium on Sets and Games. I have posted the slides in my talks page. About a year ago I gave a talk in the Graduate Student Seminar on Determinacy (also available in my talks page). Though that talk was significantly less technical, it covers a nice bit of history that I had to skip in this case, and I think the two complement each other well.
The talk today covered some of my recent results with Richard Ketchersid on the structure of natural models of determinacy. (I have discussed technical details of the proofs in other talks, also available at the page linked to above.) At the end I touched on some recent results with Boban Velickovic on failures of square principles (inspired by similar recent results of Dilip Raghavan), and on the results of the SQuaRE group I am a part of: