free men
فريق العمـــــل *****
التوقيع : 
عدد الرسائل : 1500
الموقع : center d enfer
تاريخ التسجيل : 26/10/2009
وســــــــــام النشــــــــــــــاط : 6
 | |  The Compactness Property | |
As we have seen, the compactness theorem in its usual form fails for all infinitary languages. Nevertheless, it is of some interest to determine whether infinitary languages satisfy some suitably modified version of the theorem. This so-called compactness problem turns out to have a natural connection with purely set-theoretic questions involving “large” cardinal numbers.We construct the following definition. Let κ be an infinite cardinal. A language L is said to be κ-compact (resp. weakly κ-compact) if whenever Δ is a set of L-sentences (resp. a set of L-sentences of cardinality ≤ κ) and each subset of Δ of cardinality < κ has a model, so does Δ. Notice that the usual compactness theorem for L is precisely the assertion that L is ω-compact. One reason for according significance to the κ-compactness property is the following. Call L κ-complete (resp. weakly κ-complete) if there is a deductive system P for L with deductions of length < κ such that, if Δ is a P-consistent[4] set of L-sentences (resp. such that |Δ| ≤ κ), then Δ has a model. Observe that such a P will be adequate for deductions from arbitrary sets of premises (of cardinality ≤ κ) in the sense of §2. It is easily seen that if L is κ-complete or weakly κ-complete, then L is κ-compact or weakly κ-compact. Thus, if we can show that a given language is not (weakly) κ-compact, then there can be no deductive system for it with deductions of length < κ adequate for deductions from arbitrary sets of premises (of cardinality ≤ κ).It turns out, in fact, that most languages L(κ,λ) fail to be even weakly κ-compact, and, for those that are, κ must be an exceedingly large cardinal. We shall need some definitions.An infinite cardinal κ is said to be weakly inaccessible if - اقتباس :
- (a) λ < κ → λ+ < κ, (where λ+ denotes the cardinal successor of λ), and
(b) | I | < κ and λi < κ (for all i ∈ I) ⇒ ∑i∈I λi < κ. If in addition - اقتباس :
- (c) λ < κ ⇒ 2λ < κ,
then κ is said to be (strongly)inaccessible. Since ℵ0 is inaccessible, it is normal practice to confine attention to those inaccessible, or weakly inaccessible, cardinals that exceed ℵ0. Accordingly, inaccessible or weakly inaccessible cardinals will always be taken to beuncountable. It is clear that such cardinals—if they exist—must be extremely large; and indeed the Gödel incompleteness theorem implies that the existence of even weakly inaccessible cardinals cannot be proved from the usual axioms of set theory.Let us call a cardinal κ compact (resp. weakly compact) if the language L(κ,κ) is κ-compact (resp. weakly κ-compact). Then we have the following results: - اقتباس :
- (3.1) ℵ0 is compact. This is, of course, just a succinct way of expressing the compactness theorem for first-order languages.
(3.2) κ is weakly compact ⇒ L(κ,ω) is weakly κ-compact ⇒ κ is weakly inaccessible. Accordingly, it is consistent (with the usual axioms of set theory) to assume that no languageL(κ,ω) with κ ≥ ω1 is weakly κ-compact, or, a fortiori, weakly κ-complete.
(3.3) Suppose κ is inaccessible. Then κ is weakly compact ⇔ L(κ,ω) is weakly κ-compact. Also, Also κ is weakly compact ⇒ there is a set of κ inaccessibles before κ. Thus a weakly compact inaccessible cardinal is exceedingly large; in particular it cannot be the first, second, …, nth, … inaccessible.
(3.4) κ is compact ⇒ κ is inaccessible. (But, by the result immediately above, the converse fails.) Let Constr stand for Gödel's axiom of constructibility; recall that Constr is consistent with the usual axioms of set theory. - اقتباس :
- (3.5) If Constr holds, then there are no compact cardinals.
(3.6) Assume Constr and let κ be inaccessible. Then κ is weakly compact ⇔ L(ω1,ω) is weakly κ-compact for all L.
(3.7) If Constr holds, then there are no cardinals κ for which L(ω1,ω) is compact. Accordingly, it is consistent with the usual axioms of set theory to suppose that there is no cardinal κ such that all languages L(ω1,ω) are κ-complete. This result is to be contrasted with the fact that all first-order languages are ω-complete. The import of these results is that the compactness theorem fails very badly for most languagesL(κ,λ) with κ ≥ ω1.Some historical remarks are in order here. In the 1930s mathematicians investigated various versions of the so-called measure problem for sets, a problem which arose in connection with the theory of Lebesgue measure on the continuum. In particular, the following very simple notion of measure was formulated. If X is a set, a (countably additive two-valued nontrivial) measure onX is a map μ on the power set PX to the set {0, 1} satisfying: - اقتباس :
- (a) μ(X) = 1,
(b) μ({x}) = μ(∅) = 0 for all x ∈X, and
(c) if A is any countable family of mutually disjoint subsets of X, then μ(∪A) = ∑{μ(Y) : Y ∈A}. Obviously, whether a given set supports such a measure depends only on its cardinality, so it is natural to define a cardinal κ to be measurable if all sets of cardinality κ support a measure of this sort. It was quickly realized that a measurable cardinal must be inaccessible, but the falsity of the converse was not established until the 1960s when Tarski showed that measurable cardinals are weakly compact and his student Hanf showed that the first, second, etc. inaccessibles are not weakly compact (cf. (3.3)). Although the conclusion that measurable cardinals must be monstrously large is now normally proved without making the detour through weak compactness and infinitary languages, the fact remains that these ideas were used to establish the result in the first instance.4. Incompleteness of Infinite-Quantifier LanguagesProbably the most important result about first-order languages is the Gödel completeness theorem which of course says that the set of all valid formulas of any first-order language L can be generated from a simple set of axioms by means of a few straightforward rules of inference. A major consequence of this theorem is that, if the formulas of L are coded as natural numbers in some constructive way, then the set of (codes of) valid sentences is recursively enumerable. Thus, the completeness of a first-order language implies that the set of its valid sentences isdefinable in a particularly simple way. It would accordingly seem reasonable, given an arbitrarylanguage L, to turn this implication around and suggest that, if the set of valid L-sentences is notdefinable in some simple fashion, then no meaningful completeness result can be established forL, or, as we shall say, that L is incomplete. In this section we are going to employ this suggestion in sketching a proof that “most” infinite quantifier languages are incomplete in this sense.Let us first introduce the formal notion of definability as follows. If L is a language, A an L-structure, and X a subset of the domain A of A, we say that X is definable in A by a formula φ(x, y1,…,yn) of L if there is a sequence a1,…,an of elements of A such that X is the subset of all elements x ∈ A for which φ(x, a1,…,an) holds in A.Now write Val(L) for the set of all the valid L-sentences, i.e., those that hold in every L-structure. In order to assign a meaning to the statement “Val(L) is definable”, we have to specify
- a structure C(L)—the coding structure for L;
- a particular one-one map—the coding map—of the set of formulas of L into the domain ofC(L).
Then, if we identify Val(L) with its image in C(L) under the coding map, we shall interpret the statement “Val(L) is definable” as the statement “Val(L), regarded as a subset of the domain ofC(L), is definable in C(L) by a formula of L.”For example, when L is the first-order language L of arithmetic, Gödel originally used as coding structure the standard model of arithmetic ℕ and as coding map the well-known function obtained from the prime factorization theorem for natural numbers. The recursive enumerability of Val(L) then means simply that the set of codes (“Gödel numbers”) of members of Val(L) is definable in ℕ by an L-formula of the form ∃yφ(x, y), where φ(x, y) is a recursive formula.Another, equivalent, coding structure for the first-order language of arithmetic is the structure[5]⟨H(ω), ∈ ⨡ H(ω)⟩ of hereditarily finite sets, where a set x is hereditarily finite if x, its members, its members of members, etc., are all finite. This coding structure takes account of the fact that first-order formulas are naturally regarded as finite sets.Turning now to the case in which L is an infinitary language L(κ,λ), what would be a suitable coding structure in this case? We remarked at the beginning that infinitary languages were suggested by the possibility of thinking of formulas as set-theoretical objects, so let us try to obtain our coding structure by thinking about what kind of set-theoretical objects we should take infinitary formulas to be. Given the fact that, for each φ∈Form(κ,λ), φ and its subformulas, subsubformulas, etc., are all of length < κ,[6] a moment's reflection reveals that formulas ofL(κ,λ) “correspond” to sets x hereditarily of cardinality < κ in the sense that x, its members, its members of members, etc., are all of cardinality < κ. The collection of all such sets is writtenH(κ). H(ω) is the collection of hereditarily finite sets introduced above, and H(ω1) that of allhereditarily countable sets.For simplicity let us suppose that the only extralogical symbol of the base language L is the binary predicate symbol ∈ (the discussion is easily extended to the case in which L contains additional extralogical symbols). Guided by the remarks above, as coding structure for L(κ,λ) we take the structure, - اقتباس :
- H(κ) =df ⟨H(κ), ∈ ⨡ H(κ)⟩.
Now we can define the coding map of Form(κ,λ) into H(κ). First, to each basic symbol s ofL(κ,λ) we assign a code object ⌈s⌉ ∈ H(κ) as follows. Let {vξ: ξ < κ} be an enumeration of the individual variables of L(κ,λ). - اقتباس :
| Symbol | Code Object | Notation | | ¬ | 1 | ⌈¬⌉ | | ∧ | 2 | ⌈∧⌉ | | [size=undefined]∧[/size] | 3 | ⌈[size=undefined]∧[/size]⌉ | | ∃ | 4 | ⌈∃⌉ | | ∈ | 5 | ⌈ ∈ ⌉ | | = | 6 | ⌈=⌉ | | vξ | ⟨0,ξ⟩ | ⌈vξ⌉ |
Then, to each φ ∈ Form(κ,λ) we assign the code object ⌈φ⌉ recursively as follows: - اقتباس :
- ⌈vξ = vη⌉ =df ⟨⌈vξ⌉, ⌈=⌉, ⌈vη⌉⟩,
⌈vξ ∈ vη⌉ =df ⟨⌈vξ⌉, ⌈∈⌉, ⌈vη⌉⟩; for φ, ψ ∈ Form(κ,λ), - اقتباس :
- ⌈φ ∧ ψ⌉ =df ⟨⌈φ⌉, ⌈∧⌉, ⌈ψ⌉⟩
⌈¬φ⌉ =df ⟨⌈¬⌉, ⌈φ⌉⟩
⌈∃Xφ⌉ =df ⟨⌈∃⌉, {⌈x⌉: x ∈ X}, ⌈φ⌉⟩; and finally if Φ ⊆ Form(κ,λ) with |Φ| < κ, - اقتباس :
- ⌈[size=undefined]∧Φ⌉ =df ⟨⌈[size=undefined]∧[/size]⌉, {⌈φ⌉: φ ∈ Φ}⟩.[/size]
The map φ ↦ ⌈φ⌉ from Form(κ,λ) into H(κ) is easily seen to be one-one and is the required coding map. Accordingly, we agree to identify Val(L(κ,λ)) with its image in H(κ) under this coding map.When is Val(L(κ,λ)) a definable subset of H(κ)? In order to answer this question we require the following definitions.An L-formula is called a Δ0-formula if it is equivalent to a formula in which all quantifiers are of the form ∀x∈y or ∃x∈y (i.e., ∀x(x∈y → …) or ∃x(x∈y ∧ …)). An L-formula is a Σ1-formula if it is equivalent to one which can be built up from atomic formulas and their negations using only the logical operators ∧, ∨, ∀x∈y, ∃x. A subset X of a set A is said to be Δ0 (resp. Σ1) on A if it is definable in the structure ⟨A, ∈ ⨡ A⟩ by a Δ0- (resp. Σ1-) formula of L.For example, if we identify the set of natural numbers with the set H(ω) of hereditarily finite sets in the usual way, then for each X ⊆ H(ω) we have: - اقتباس :
- X is Δ0 on H(ω) ⇔ X is recursive
X is Σ1 on H(ω) ⇔ X is recursively enumerable. Thus the notions of Δ0- and Σ1-set may be regarded as generalizations of the notions of recursiveand recursively enumerable set, respectively.The completeness theorem for L implies that Val(L) — regarded as a subset of H(ω) — is recursively enumerable, and hence Σ1 on H(ω). Similarly, the completeness theorem for L(ω1,ω) (see §2) implies that Val(L(ω1,ω)) — regarded as a subset of H(ω1) — is Σ1 on H(ω1). However, this pleasant state of affairs collapses completely as soon as L(ω1,ω1) is reached. For one can prove - اقتباس :
- Scott's Undefinability Theorem for L(ω1,ω1). Val(L(ω1,ω1)) is not definable in H(ω1)even by an L(ω1,ω1)-formula; hence a fortiori Val(L(ω1,ω1)) is not Σ1 on H(ω1).
This theorem is proved in much the same way as the well-known result that the set of (codes of) valid sentences of the second-order language of arithemetic L2 is not second-order definable in its coding structure ℕ. To get this latter result, one first observes that ℕ is characterized by a single L2-sentence, and then shows that, if the result were false, then “truth in ℕ” for L2-sentences would be definable by an L2-formula, thereby violating Tarski's theorem on the undefinability of truth.Accordingly, to prove Scott's undefinability theorem along the above lines, one needs to establish: - اقتباس :
- (4.1) Characterizability of the coding structure H(ω1) in L(ω1,ω1): there is an L(ω1,ω1)-sentence τ0 such that, for all L-structures A, A ⊨ τ0 ⇔ A [size=undefined]≅ H(ω1).
(4.2) Undefinability of truth for L(ω1,ω1)-sentences in the coding structure: there is noL(ω1,ω1)-formula φ(v0) such that, for all L(ω1, ω1)-sentences σ, H(ω1) ⊨ σ↔φ(⌈σ⌉).
(4.3) There is a term t(v0, v1) of L(ω1,ω1) such that, for each pair of sentences σ, τ ofL(ω1,ω1), H(ω1) ⊨ [t(⌈σ⌉,⌈τ⌉) = ⌈σ → τ⌉].[/size] (4.1) is proved by analyzing the set-theoretic definition of H(ω1) and showing that it can be “internally” formulated in L(ω1,ω1). (4.2) is established in much the same way as Tarski's theorem on the undefinability of truth for first- or second-order languages. (4.3) is obtained by formalizing the definition of the coding map σ ↦ ⌈σ⌉ in L(ω1,ω1).Armed with these facts, we can obtain Scott's undefinability theorem in the following way. Suppose it were false; then there would be an L(ω1,ω1)-formula θ(v0) such that, for all L(ω1,ω1)-sentences σ, - اقتباس :
- (4.4) H(ω1) ⊨ θ(⌈σ⌉) iff σ ∈ Val(L(ω1,ω1)).
Let τ0 be the sentence given in (4.1). Then we have, for all L(ω1,ω1)-sentences σ, - اقتباس :
- H(ω1) ⊨ σ iff (τ0 → σ) ∈ Val(L(ω1,ω1)),
so that, by (4.4), - اقتباس :
- H(ω1) ⊨ σ iff H(ω1) ⊨ θ(⌈τ0 → σ⌉).
If t is the term given in (4.3), it would follow that - اقتباس :
- H(ω1) ⊨ σ↔θ(t(⌈τ0⌉, ⌈σ⌉)).
Now write φ(v0) for the L(ω1,ω1)-formula θ(t(⌈τ0⌉, ⌈σ⌉)). Then - اقتباس :
- H(ω1) ⊨ σ↔φ(⌈σ⌉),
contradicting (4.2), and completing the proof.Thus Val(L(ω1,ω1)) is not definable even by an L(ω1,ω1)-formula, so a fortiori L(ω1,ω1) is incomplete. Similar arguments show that Scott's undefinability theorem continues to hold when ω1 is replaced by any successor cardinal κ+; accordingly the languages L(κ+,κ+) are all incomplete.[7] | |
|
أمس في 5:04 pm من طرف