502 – Formal systems (3) | A kind of library

502 – Formal systems (3)

Theorem 2 (Completeness) Whenever ${\Sigma\models\tau,}$ then also ${\Sigma\vdash\tau.}$

Proof: We prove the contrapositive. Assume that ${\Sigma\not\vdash\tau.}$ We will find an ${x\in 2^{\mathbb N}}$ that extends ${\tau}$ and does not extend any ${\sigma\in\Sigma.}$

Towards this end, enumerate all finite strings as

$\displaystyle \{\sigma_i\mid i\in{\mathbb N}\}.$

Let ${\Sigma_0=\Sigma.}$ We define a sequence ${\Sigma_0\subseteq\Sigma_1\subseteq\dots}$ by recursion as follows:

Given ${\Sigma_i}$ with the property that ${\Sigma_i\not\vdash\tau,}$ let ${\Sigma_{i+1}=\Sigma_i,}$ unless ${\Sigma_i\cup\{\sigma_i\}\not\vdash\tau}$ either, in which case, let ${\Sigma_{i+1}=\Sigma_i\cup\{\sigma_i\}.}$

Now let ${\Sigma'=\bigcup_i\Sigma_i}$ and note that ${\Sigma'}$ satisfies the following properties:

${\Sigma'\not\vdash\tau,}$ by construction and compactness.
For any ${\sigma\in2^{<{\mathbb N}},}$ ${\sigma\in\Sigma'}$ iff ${\Sigma'\cup\{\sigma\}\not\vdash\tau.}$ The left-to-right implication is clear from (1). The other direction holds by construction: If ${\sigma=\sigma_i}$ and ${\Sigma'\cup\{\sigma\}\not\vdash\tau,}$ then certainly ${\Sigma_i\cup\{\sigma\}\not\vdash\tau,}$ and therefore ${\sigma\in\Sigma_{i+1}\subseteq\Sigma'.}$
In particular, ${\tau\notin\Sigma'.}$ It is actually ${\Phi=2^{<{\mathbb N}}\setminus\Sigma'}$ that interests us. In terms of ${\Phi,}$ property (3) says that ${\Phi\ne\emptyset.}$
${\Phi}$ is a tree.To see this, suppose that ${\sigma i\in\Phi,}$ where ${i\in2.}$ Then, by property (2), ${\Sigma'\cup\{\sigma i\}\vdash\tau.}$ But then, certainly, ${\Sigma'\cup\{\sigma\}\vdash\tau}$ so, by (2) again, ${\sigma\in\Phi.}$ This shows that ${\Phi}$ is closed under initial segments.
${\Phi}$ is actually a branch, i.e., ${[\Phi]}$ is a singleton.To see this, suppose that ${\sigma\in\Phi.}$ We need to show that there is a unique ${i\in 2}$ such that ${\sigma i\in\Phi.}$
Since ${\sigma\in\Phi,}$ then ${\Sigma'\cup\{\sigma\}\vdash\tau.}$ Suppose first that both ${\sigma 0}$ and ${\sigma 1}$ are in ${\Sigma'.}$ Then, by compression, ${\Sigma'\vdash\sigma,}$ and therefore ${\Sigma'\vdash\tau,}$ a contradiction.

Suppose now that neither ${\sigma 0}$ nor ${\sigma 1}$ is in ${\Sigma'.}$ Then ${\Sigma'\cup\{\sigma i\}\vdash\tau}$ for both ${i=0}$ and ${i=1.}$ It then follows, using Fact 3 from last lecture, that ${\Sigma'\vdash\tau,}$ again a contradiction. This gives the result.

Finally, let ${x}$ be the unique element of ${[\Phi].}$ Note that ${x}$ extends ${\tau,}$ since ${\tau\in\Phi.}$ Note also that ${x}$ extends no element of ${\Sigma,}$ since no element of ${\Sigma}$ is in ${\Phi,}$ and the initial segments of ${x}$ are precisely the elements of ${\Phi.}$ This proves that ${\Sigma\not\models\tau.}$ $\Box$

This is the reason why this formal system is called a tree system; both because of this argument, and because of the relation that it implies between this system and König’s lemma, as we will see below.

To illustrate the interplay resulting from the equivalence of the two relations ${\vdash}$ and ${\models,}$ consider the following two proofs:

Corollary 3 ${2^{\mathbb N}}$ is compact.

Proof: Given a covering of ${2^{\mathbb N}}$ by open sets, let ${\Sigma}$ be the collection of strings ${\sigma}$ such that the basic open set ${N_\sigma}$ is completely contained in one of the open sets in the covering.

Then

$\displaystyle 2^{\mathbb N}=N_{\perp}\subseteq\bigcup_{\sigma\in\Sigma}N_\sigma,$

and it follows that ${\Sigma\vdash{\perp}.}$ Therefore ${\Sigma_0\vdash{\perp}}$ for some finite subset ${\Sigma_0}$ of ${\Sigma,}$ so ${\Sigma_0\models{\perp},}$ and any finite collection of open sets in the covering that contain the sets ${N_\sigma}$ for ${\sigma\in \Sigma_0}$ constitutes a finite subcovering of ${2^{\mathbb N}.}$ $\Box$

It is not, of course, that the compactness of ${2^{\mathbb N}}$ is a deep result. But the trivial argument just given helps explain some of the difficulties we found previously, since our results supersede this topological theorem.

Corollary 4 König’s lemma holds for infinite subtrees of ${2^{<{\mathbb N}}}$ .

Proof: Given a tree ${T\subseteq2^{<{\mathbb N}},}$ suppose that ${[T]=\emptyset}$ and let ${\Sigma=2^{<{\mathbb N}}\setminus T.}$ Then ${\Sigma\models{\perp}}$ so, by completeness and Fact 5 from last lecture, there is a finite ${\Sigma_0\subset\Sigma}$ and an ${n}$ such that any ${\sigma}$ of length ${n}$ or larger extends an element of ${\Sigma_0.}$

Note now that ${\Sigma}$ is closed under extensions, since ${T}$ is a tree. It follows that ${\Sigma=2^{<{\mathbb N}}\setminus T}$ contains all strings of ${0}$ s and ${1}$ s, of length ${n}$ or larger. But then ${T\subseteq 2^{<n},}$ i.e., ${T}$ is finite. $\Box$

Typeset using LaTeX2WP. Here is a printable version of this post.

This entry was posted on Friday, September 4th, 2009 at 10:57 am and is filed under 502: Logic and set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
	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

A kind of library