September | 2011 | A kind of library

187 – Selected solutions to problems from Chapter 1

September 19, 2011

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.

Solutions (Chapter 1)

187 – The resolution method

September 19, 2011

This 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 ${A_1, \dots, A_n, A}$ , whether

$\displaystyle (A_1\land \dots \land A_n)\Rightarrow A$

is a tautology (i.e., it is true under all truth-value assignments.)

This happens iff

$\displaystyle A_1\wedge\dots\wedge A_n\wedge\neg A\text{ is unsatisfiable.}$

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 ${A}$ is in conjunctive normal form iff it has the form

$\displaystyle A_1\land A_2\land\dots\land A_n$

where each ${A_i}$ has the form

$\displaystyle B_1\lor B_2\lor\dots\lor B_k$

and each ${B_i}$ is either a propositional variable, or its negation. So ${A}$ 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 ${A}$ 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 ${A'}$ in cnf (conjunctive normal form) equivalent to ${A}$ , it is not hard to show that there is an efficient algorithm for finding ${A^*}$ in cnf such that:

${A}$ is satisfiable iff ${A^*}$ is satisfiable.

(But, in general, ${A^*}$ has more variables than ${A}$ .)

So from now on we will only consider ${A}$ s in cnf, and the Resolution Method applies to such formulas only. Say

${A=(\ell_{1,1}\vee\dots\vee\ell_{1,n_1})\wedge\dots \wedge (\ell_{k,1}\vee\dots\vee\ell_{k,n_k})}$

with ${\ell_{i,j}}$ literals. Since order and repetition in each conjunct (1):

$\displaystyle \ell_{i,1}\vee\dots\vee\ell_{i,n_i}$

are irrelevant, we can replace (1) by the set of literals

$\displaystyle c_i=\{\ell_{i,1},\ell_{i,2},\dots ,\ell_{i,n_i}\}.$

Such a set of literals is called a clause. It corresponds to the formula (1). So the formula ${A}$ above can be simply written as a set of clauses (again since the order of the conjunctions is irrelevant): ${C=\{c_1,\dots ,c_k\}}$

$=\{\{\ell_{i,1},\dots \ell_{i,n_1}\},\dots ,\{\ell_{k,1},\dots , \ell_{k,n_k}\}\}$

Satisfiability of ${A}$ means then simultaneous satisfiability of all of its clauses ${c_1,\dots ,c_k}$ , i.e., finding a valuation ${\nu}$ which makes ${c_i}$ true for each ${i}$ , i.e., which for each ${i}$ makes some ${\ell_{i,j}}$ true.

Example 1 $A=(p_1\vee\neg p_2)\wedge (p_3\vee p_3)$

$c_1=\{p_1,\neg p_2\}$

$c_2=\{p_3\}$

$C=\{\{p_1,\neg p_2\},\{p_3\}\}.$

From now on we will deal only with a set of clauses ${C=\{c_1, c_2,\dots,c_n \}}$ . It is possible to consider also infinite sets ${C}$ , but we will not do that here.

Satisfying ${C}$ means (again) that there is a valuation which satisfies all ${c_1,c_2,\dots}$ , i.e. if ${c_i=\ell_{i,1}\vee\dots \vee\ell_{i,n_i}}$ , then for all ${i}$ there is ${j}$ so that it makes ${\ell_{i,j}}$ true.

Notice that if the set of clauses ${C_A}$ is associated as above to ${A}$ (in cnf) and ${C_B}$ to ${B}$ , then

$\displaystyle A\wedge B\text{ is satisfiable iff }C_A\cup C_B\text{ is satisfiable.}$

By convention we also have the empty clause ${\Box}$ , 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 ${u}$ , let ${\bar u}$ denote its “conjugate”, i.e. $\bar u=\neg p,$ if $u=p,$ and $\bar u=p$ if $u=\neg p.$

Definition 1 Suppose now ${c_1,c_2,c}$ are three clauses. We say that ${c}$ is a resolvent of ${c_1,c_2}$ if there is a ${u}$ such that ${u\in c_1}$ , ${\bar u\in c_2}$ and

$\displaystyle c=(c_1\setminus\{u\})\cup (c_2\setminus\{\bar u\}).$

We allow here the case ${c=\Box}$ , i.e. ${c_1=\{u\},\ c_2= \{\bar u\}}$ .

Read the rest of this entry »

Leave a Comment » | 187: Discrete mathematics | Tagged: resolution method, SAT | Permalink
Posted by andrescaicedo

187 – The P vs NP problem

September 19, 2011

This 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 ${A}$ , and “words” on that alphabet (the “alphabet” may consist of digits, of abstract symbols, of actual letters, etc).

We use the notation ${A^*}$ to indicate the set of all “words” from the alphabet ${A}$ . Here, a word is simply a finite sequence of symbols from ${A}$ . For example, if ${A}$ is the usual alphabet, then

$\displaystyle awwweeeedddfDDkH$

would be a word.

We are also given a set ${V}$ of words, and we say that the words in ${V}$ are valid. ( ${V}$ may be infinite.)

In the decision problem associated to ${V}$ , we are given as input a word in this alphabet. As output we say yes or no, depending on whether the word is in ${V}$ 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.

Read the rest of this entry »

Leave a Comment » | 187: Discrete mathematics | Tagged: p-np, SAT, Undecidability and incompleteness | Permalink
Posted by andrescaicedo

414/514 – Metric spaces

September 19, 2011

This is homework 2, due Monday September 26 at the beginning of lecture.

Let $(X,d)$ be a metric space.

Show that if $d_1:X\times X\to{\mathbb R}$ is defined by $\displaystyle d_1(x,y)=\frac{d(x,y)}{1+d(x,y)}$ , then $d_1$ is also a metric on $X$ .
Show that if $U$ is open in $(X,d)$ then it is open in $(X,d_1)$ , and viceversa.

Recall that $U$ is open iff it is a union of open balls. Use this to explain why it suffices to show that if $U$ is open in $(X,d)$ then for any $x\in U$ there is an $\epsilon>0$ such that

$B_\epsilon^{d_1}(x):=\{y\mid d_1(x,y)<\epsilon\}\subseteq U$ ,

and similarly, if $V$ is open in $(X,d_1)$ then for any $z\in V$ there is a $\delta>0$ such that

$B_\delta^d(z):=\{w\mid d(z,w)<\delta\}\subseteq V$ .

In turn, explain why to show this it suffices to prove that for any $x\in X$ and any $\eta>0$ there is a $\rho>0$ such that

$B^{d_1}_\eta(x)\supseteq B^d_\rho(x)$

and, similarly, for any $\tau>0$ there is a $\mu>0$ such that

$B_\tau^d(x)\supseteq B^{d_1}_\mu(x)$ .

Finally, prove this by showing that we can take $\rho=\epsilon$ (no matter what $x$ is) and similarly, find an appropriate $\mu$ that works for $\tau$ (again, independently of $x$ ).

Illustrate the above in ${\mathbb R}^2$ as accurately as possible.
Suppose that a sequence $(x_n)_{n\in{\mathbb N}}$ converges to $x$ in $(X,d)$ and to $x'$ in $(X,d_1)$ . Show that $x=x'$ .
Is it true that a sequence $(x_n)_{n\in{\mathbb N}}$ is Cauchy in $(X,d)$ iff it is Cauchy in $(X,d_1)$ ? (Give a proof or else exhibit a counterexample, with a proof that it is indeed a counterexample.)
$(*)$ Show that any dense $G_\delta$ subset of ${\mathbb R}$ has the same size as ${\mathbb R}$ .

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

Alan Turing year

September 5, 2011

Alan 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.

1 Comment | Conferences, Life | Permalink
Posted by andrescaicedo

414/514 – Cauchy sequences

September 2, 2011

This is homework 1, due Friday September 9 at the beginning of lecture.

We define absolute value as usual: Given a real $x$ , we say that ${}|x|$ is $x$ if $x\ge0$ and is $-x$ otherwise.

Absolute values have useful properties: ${}|x|=|-x|\ge0$ for any $x$ . Also, ${}|x|=0$ iff $x=0$ . The key property is the triangle inequality: ${}|a+b|\le|a|+|b|$ .

Formally, a sequence is a function $s:{\mathbb N}\to{\mathbb R}$ . As usual, we write the sequence as $s_1,s_2,\dots$ rather than $s(0),s(1),\dots$

A sequence $s$ is a Cauchy sequence iff for all $\epsilon>0$ there is an $N\in{\mathbb N}$ such that whenever $n,m\in{\mathbb N}$ and $n,m>N$ , we have $|s_n-s_m|<\epsilon.$

A sequence $s$ converges iff there is a real $r$ such that for all $\epsilon>0$ there is an $N\in{\mathbb N}$ such that whenever $n\in{\mathbb N}$ and $n>N$ , we have $|r-s_n|<\epsilon$ .

Note that these concepts also make sense in ${\mathbb Q}$ . Now we require all the $s_n$ to be rational, and we require $\epsilon$ and $r$ to be rational as well.

Show that if a sequence converges, then it is Cauchy.
Give an example of a Cauchy sequence in ${\mathbb Q}$ that does not converge.
Show that any Cauchy sequence in ${\mathbb R}$ 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 ${\mathbb Q}$ some of these limits are missing. In the case of cuts, the way of solving the presence of gaps in ${\mathbb Q}$ 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 $X$ is a binary relation $\sim$ that is:

Reflexive: For any $x\in X$ , $x\sim x$ .
Symmetric: For any $x,y\in X$ , if $x\sim y$ then also $y\sim x$ .
Transitive: For any $x,y,z\in X$ , if $x\sim y$ and $y\sim z$ , then $x\sim z$ .

If $\sim$ is an equivalence relation, the equivalence classes determined by $\sim$ are the sets ${}[x]=\{y\in X\mid x\sim y\}$ . An intuitive way of thinking about this is that we are looking at $X$ 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 $x,y$ are close iff $x\sim y$ .

Let $s$ and $t$ be two Cauchy sequences of rationals. Say that $s\sim t$ iff $s-t$ converges to $0$ . Here, of course, $s-t$ is the sequence $r_1,r_2,\dots$ with $r_n=s_n-t_n$ .

Show that $\sim$ is an equivalence relation. Check that any Cauchy sequence $s$ is equivalent to infinitely many other sequences.
Define ${\mathbb R}$ as the set of equivalence classes of the relation $\sim$ . The elements of ${\mathbb R}$ are then Cauchy sequences or, more precisely, collections of Cauchy sequences. A typical element of ${\mathbb R}$ is a class ${}[s]$ , and we think of ${}[s]$ as the limit of $s$ . Of course, we have a copy of ${\mathbb Q}$ inside ${\mathbb R}$ : We can identify the rational $q$ with the class $q^*=[s]$ of all sequences $s$ that converge to $q$ .
Define $+,\times,<$ in ${\mathbb R}$ and verify that with these definitions we have an ordered field.
Verify that ${\mathbb R}$ is complete, meaning that the least upper bound property holds.

This gives a second sense in which ${\mathbb R}$ is complete: It contains the limits of all Cauchy sequences. A small but important point not mentioned above is the following: Given a sequence $s$ of rationals, let $s'$ be its “copy” inside ${\mathbb R}$ , i.e., $(s')_n=s_n^*$ . Then $s'$ is Cauchy iff $s$ is Cauchy, and $s$ converges to a rational $q$ iff $s'$ converges to $q^*$ .

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

Sets and games

September 1, 2011

I 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:

5 Comments | Talks | Permalink
Posted by andrescaicedo

You are currently browsing the A kind of library blog archives for September, 2011.
Categories

Categories
Search

Mathematical links
My pages
Others
Mathoverflow
- Answer by Andrés E. Caicedo for Is $Z_3+{\rm AD}$ equiconsistent with $\text{ZFC+AD}^{L(\mathbb{R})}$ May 10, 2018
  The only reference I know for precisely these matters is the handbook chapter MR2768702. Koellner, Peter; Woodin, W. Hugh. Large cardinals from determinacy. In Handbook of set theory. Vols. 1, 2, 3, 1951–2119, Springer, Dordrecht, 2010. (Particularly, section 7.) For closely related topics, see also the work of Yong Cheng (and of Cheng and Schindler) on Harr […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Does constructing non-measurable sets require the axiom of choice? October 14, 2010
  As other answers point out, yes, one needs choice. The popular/natural examples of models of ZF+DC where all sets of reals are measurable are models of determinacy, and Solovay's model. They are related in deep ways, actually, through large cardinals. (Under enough large cardinals, $L({\mathbb R})$ of $V$ is a model of determinacy and (something stronge […]
  Andrés E. Caicedo
- Relative Densities September 12, 2013
  Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory. How can I count the relative density of those $p$ (of the form $3k+1$) such that the equation $2=3x^3$ has no solutions modulo $p$? Really, even pointers on how to say anything […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Solutions to the Continuum Hypothesis May 18, 2010
  (1) Patrick Dehornoy gave a nice talk at the Séminaire Bourbaki explaining Hugh Woodin's approach. It omits many technical details, so you may want to look at it before looking again at the Notices papers. I think looking at those slides and then at the Notices articles gives a reasonable picture of what the approach is and what kind of problems remain […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Are there any non-linear solutions of Cauchy's equation ($f(x+y)=f(x)+f(y)$) without assuming the Axiom of Choice? March 6, 2011
  It is not possible to provide an explicit expression for a non-linear solution. The reason is that (it is a folklore result that) an additive $f:{\mathbb R}\to{\mathbb R}$ is linear iff it is measurable. (This result can be found in a variety of places, it is a standard exercise in measure theory books. As of this writing, there is a short proof here (Intern […]
  Andrés E. Caicedo
Math.StackExchange
- Answer by Andrés E. Caicedo for Set of discontinuity of monotone function is countable May 23, 2018
  The usual definition of a series of nonnegative terms is as the supremum of the sums over finite subsets of the index set, $$\sum_{i\in I} x_i=\sup\biggl\{\sum_{j\in J}x_j:J\subseteq I\mbox{ is finite}\biggr\}.$$ (Note this definition does not quite work in general for series of positive and negative terms.) The point then is that is $a< x
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Hadwiger–Nelson problem 5 colors needed if color sets are Lesbeauge measureable November 11, 2017
  The result was proved by Kenneth J. Falconer. The reference is MR0629593 (82m:05031). Falconer, K. J. The realization of distances in measurable subsets covering $R^n$. J. Combin. Theory Ser. A 31 (1981), no. 2, 184–189. The argument is relatively simple, you need a decent understanding of the Lebesgue density theorem, and some basic properties of Lebesgue m […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Can there be an $\aleph_2$ or even greater? May 7, 2018
  Yes, there is an $\aleph_2$ and an $\aleph_3$, and there are alephs beyond all the $\aleph_n$. A suitable version of Cantor's diagonal proof is perfectly general and shows that, for any set $X$, $|X|
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Showing in $ZFC-Foundation$ that $V\neq R$ May 1, 2018
  Given a class $S$, to say that it can be proper means that it is consistent (with the axioms under consideration) that $S$ is a proper class, that is, there is a model $M$ of these axioms such that the interpretation $S^M$ of $S$ in $M$ is a proper class in the sense of $M$. It does not mean that $S$ is always a proper class. In fact, it could also be consis […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Constructible universe and the standard model April 30, 2018
  As the other answers point out, the question is imprecise because of its use of the undefined notion of "the standard model" of set theory. Indeed, if I were to encounter this phrase, I would think of two possible interpretations: The author actually meant "the minimal standard model of set theory", that is, $L_\Omega$ where $\Omega$ is e […]
  Andrés E. Caicedo
September 2011

M T W T F S S

« Aug Oct »

1 2 3 4

5 6 7 8 9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28 29 30
Archives
- February 2018 (1)
- October 2017 (1)
- July 2017 (1)
- September 2016 (2)
- August 2016 (3)
- July 2016 (2)
- April 2016 (1)
- October 2015 (1)
- June 2015 (1)
- May 2015 (1)
- April 2015 (7)
- March 2015 (5)
- February 2015 (7)
- January 2015 (11)
- December 2014 (2)
- November 2014 (5)
- October 2014 (6)
- September 2014 (3)
- August 2014 (3)
- April 2014 (3)
- March 2014 (5)
- February 2014 (2)
- January 2014 (2)
- December 2013 (2)
- November 2013 (10)
- October 2013 (6)
- September 2013 (7)
- August 2013 (5)
- June 2013 (1)
- May 2013 (8)
- April 2013 (7)
- March 2013 (5)
- February 2013 (9)
- January 2013 (2)
- November 2012 (1)
- September 2012 (1)
- August 2012 (3)
- May 2012 (3)
- April 2012 (10)
- March 2012 (4)
- February 2012 (13)
- January 2012 (15)
- November 2011 (8)
- October 2011 (14)
- September 2011 (7)
- August 2011 (1)
- April 2011 (1)
- March 2011 (3)
- February 2011 (4)
- January 2011 (7)
- December 2010 (1)
- November 2010 (7)
- October 2010 (12)
- September 2010 (13)
- August 2010 (3)
- May 2010 (4)
- April 2010 (11)
- March 2010 (6)
- February 2010 (12)
- December 2009 (9)
- November 2009 (11)
- October 2009 (13)
- September 2009 (19)
- August 2009 (10)
- June 2009 (1)
- May 2009 (2)
- April 2009 (14)
- March 2009 (17)
- February 2009 (19)
- January 2009 (15)
- December 2008 (5)
- November 2008 (12)
- October 2008 (17)
- September 2008 (10)
- August 2008 (3)
- June 2008 (3)
- May 2008 (15)
- April 2008 (21)
- March 2008 (10)
- February 2008 (13)
- January 2008 (11)
- September 2007 (1)
- July 2007 (1)
- March 2007 (4)
- February 2007 (20)
- January 2007 (23)
- December 2006 (4)
Alan Turing Alexander S. Kechris Alfred Tarski algebraic numbers Andras Hajnal Andreas Blass Andrew Michael Bruckner arithmetic mean-geometric mean inequality Arnoud C. M. van Rooij Augustin Cauchy Axel Thue Bernhard Riemann BEST bpfa Bukovsky-Hechler theorem compactness completeness covering property determinacy Donald A. Martin elementary embedding Emile Borel Euclidean algorithm extension field field field extension Francisco Frank Plumpton Ramsey Fred Galvin Galvin-Hajnal theorem GCH Georg Cantor Godfrey Harold Hardy Grigor Sargsyan Harvey Friedman ideal Isaac Newton James Baumgartner Jerome Keisler Johan Thim John R. Steel Karl Theodor Wilhelm Weierstrass Koenig's lemma Kurt Goedel Lech Maligranda Marion Scheepers measurable cardinal Menachem Magidor midterm mm Nowhere differentiable function Paul Erdos pfa propositional logic quartic equation Ramsey theorem Rene Baire Richard Rado Robert Solovay Saharon Shelah Samuel Coskey sch Silver's theorem Stefan Banach Stevo Todorcevic supercompact cardinals Tarski's conjecture Turing degrees ultrafilter ultrapower Undecidability and incompleteness Unsolvable problems W. Hugh Woodin Wacław Franciszek Sierpiński Wilhelmus Hendricus Schikhof

	116c- Homework 7 \| A… on 116c- Lecture 18
	116c- Lecture 17 \| A… on 116c: Mathematical Logic (Set…
	116c- Lecture 18 \| A… on 116c- Homework 7
	116c- Lecture 19 \| A… on 116c- Lecture 13
	580 -Partition calcu… on 580 -III. Partition calcu…
	580 -Partition calcu… on 580 -Partition calculus (…
	Nosferatu \| A kind o… on The cabinet of Doctor Cal…
	Monica Agana –… on 414/514 The theorems of Rieman…
	The Dalek invasion o… on The Dalek invasion of Boi…
	andrescaicedo on Help!
	Asaf Karagila on On anti-foundation and coding…
	andrescaicedo on On anti-foundation and coding…
	Asaf Karagila on On anti-foundation and coding…
	On anti-foundation a… on Interpretations
	andrescaicedo on MSC2020

September 2011
M	T	W	T	F	S	S
« Aug				Oct »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Categories

Recent Comments

Mathematical links

My pages

Others

Archives