free men
فريق العمـــــل *****
التوقيع : 
عدد الرسائل : 1500
الموقع : center d enfer
تاريخ التسجيل : 26/10/2009
وســــــــــام النشــــــــــــــاط : 6
 | |  Finite-Quantifier Languages | |
We have remarked that infinite-quantifier languages such as L(ω1,ω1) resemble second-order languages inasmuch as they allow quantification over infinite sets of individuals. The fact that this is not permitted in finite-quantifier languages suggests that these may be in certain respects closer to their first-order counterparts than might be evident at first sight. We shall see that this is indeed the case, notably in the case of L(ω1,ω).The language L(ω1,ω) occupies a special place among infinitary languages because—like first-order languages—it admits an effective deductive apparatus. In fact, let us add to the usual first-order axioms and rules of inference the new axiom scheme - اقتباس :
- [size=undefined]∧Φ → φ[/size]
for any countable set Φ ⊆ Form(ω1,ω) and any φ ∈ Φ, together with the new rule of inference - اقتباس :
| φ0, φ1, …, φn, … | | [size=undefined]∧[/size]n∈ω φn |
and allow deductions to be of countable length. Writing ⊢* for deducibility in this sense, we then have the - اقتباس :
- L(ω1,ω)-Completeness Theorem. For any σ ∈ Sent(ω1,ω), ⊨ σ ⇔ ⊢*σ
As an immediate corollary we infer that this deductive apparatus is adequate for deductions from countable sets of premises in L(ω1,ω). That is, with the obvious extension of notation, we have, for any countable set Δ ⊆ Sent(ω1,ω) - اقتباس :
- (2.1) Δ ⊨ σ ⇔ Δ⊢*σ
This completeness theorem can be proved by modifying the usual Henkin completeness proof for first-order logic, or by employing Boolean-algebraic methods. Similar arguments, applied to suitable further augmentations of the axioms and rules of inference, yield analogous completeness theorems for many other finite-quantifier languages.If just deductions of countable length are admitted, then no deductive apparatus for L(ω1,ω) can be set up which is adequate for deductions from arbitrary sets of premises, that is, for which (2.1) would hold for every set Δ ⊆ Sent(ω1,ω), regardless of cardinality. This follows from the simple observation that there is a first-order language L and an uncountable set Γ of L(ω1,ω)-sentences such that Γ has no model but every countable subset of Γ does. To see this, let L be the language of arithmetic augmented by ω1 new constant symbols {cξ : ξ < ω1} and let Γ be the set of L(ω1,ω)-sentences {σ} ∪ {cξ ≠ cη : ξ ≠ η}, where σ is the L(ω1,ω)-sentence characterizing the standard model of arithmetic. This example also shows that the compactness theorem fails for L(ω1,ω) and so also for any L(κ,λ) with κ ≥ ω1.Another result which holds in the first-order case but fails for L(κ,ω) with κ ≥ ω1 (and also forL(ω1,ω1), although this is more difficult to prove) is the prenex normal form theorem. A sentence is prenex if all its quantifiers appear at the front; we give an example of an L(ω1,ω)-sentence which is not equivalent to a conjunction of prenex sentences. Let L be the first-order language without extralogical symbols and let σ be the L(ω1,ω)-sentence which characterizes the class of finite sets. Suppose that σ were equivalent to a conjunction - اقتباس :
- [size=undefined]∧i∈I σi[/size]
of prenex L(ω1,ω)-sentences σi. Then each σi is of the form - اقتباس :
- Q1x1 … Qnxn φi(x1,…, xn),
where each Qk is ∀ or ∃ and φi is a (possibly infinitary) conjunction or disjunction of formulas of the form xk = xl or xk ≠ xl. Since each σi is a sentence, there are only finitely many variables in each φi, and it is easy to see that each φi is then equivalent to a first-order formula. Accordingly each σi may be taken to be a first-order sentence. Since σ is assumed to be equivalent to the conjunction of the σi, it follows that σ and the set Δ = {σi : i ∈ I} have the same models. But obviously σ, and hence also Δ, have models of all finite cardinalities; the compactness theorem for sets of first-order sentences now implies that Δ, and hence also σ, has an infinite model, contradicting the definition of σ.Turning to the Löwenheim-Skolem theorem, we find that the downward version has adequate generalizations to L(ω1,ω) (and, indeed, to all infinitary languages). In fact, one can show in much the same way as for sets of first-order sentences that if Δ ⊆ Sent(ω1,ω) has an infinite model of cardinality ≥ |Δ|, it has a model of cardinality the larger of ℵ0, |Δ|. In particular, any L(ω1,ω)-sentence with an infinite model has a countable model.On the other hand, the upward Löwenheim-Skolem theorem in its usual form fails for all infinitary languages. For example, the L(ω1,ω)-sentence characterizing the standard model of arithmetic has a model of cardinality ℵ0 but no models of any other cardinality. However, all is not lost here, as we shall see.We define the Hanf number h(L) of a language L to be the least cardinal κ such that, if an L-sentence has a model of cardinality κ, it has models of arbitrarily large cardinality. The existence of h(L) is readily established. For each L-sentence σ not possessing models of arbitrarily large cardinality let κ(σ) be the least cardinal κ such that σ does not have a model of cardinality κ. If λ is the supremum of all the κ(σ), then, if a sentence of L has a model of cardinality λ, it has models of arbitrarily large cardinality.Define the cardinals μ(α) recursively by - اقتباس :
| μ(0) | = | ℵ0 | | μ(α+1) | = | 2μ(α) | | μ(λ) | = | ∑α<λ μ(α), for limit λ. |
Then it can be shown that - اقتباس :
- h(L(ω1,ω)) = μ(ω1),
similar results holding for other finite-quantifier languages. The values of the Hanf numbers of infinite-quantifier languages such as L(ω1,ω1) are sensitive to the presence or otherwise of large cardinals, but must in any case greatly exceed that of L(ω1,ω).A result for L which generalizes to L(ω1,ω) but to no other infinitary language is the - اقتباس :
- Craig Interpolation Theorem: If σ,τ ∈ Sent(ω1,ω) are such that ⊨ σ → τ, then there is θ ∈Sent(ω1,ω) such that ⊨ σ → θ and ⊨ θ → τ, and each extralogical symbol occurring in θ occurs in both σ and τ.
The proof is a reasonably straightforward extension of the first-order case.Finally, we mention one further result which generalizes nicely to L(ω1,ω) but to no other infinitary language. It is well known that, if A is any finite L-structure with only finitely many relations, there is an L-sentence σ characterizing A up to isomorphism. For L(ω1,ω) we have the following generalization known as - اقتباس :
- Scott's Isomorphism Theorem. If A is a countable L-structure with only countably many relations, then there is an L(ω1,ω)-sentence whose class of countable models coincides with the class of L-structures isomorphic with A.
The restriction to countable structures is essential because countability cannot in general be expressed by an L(ω1,ω)-sentence.The language L(∞,ω) may also be counted as a finite-quantifier language. The concept of equivalence of structures with respect to this language is of especial significance: we call two (similar) structures A and B (∞,ω)-equivalent, written A ≡∞ω B, if the same sentences of L(∞,ω) hold in both A and B. This relation can, first of all, be characterized in terms of the notion of partial isomorphism. A partial isomorphism between A and B is a nonempty family P of maps such that:
- For each p ∈ P, dom(p) is a substructure of A, ran(p) is a substructure of B, and p is an isomorphism of its domain onto its range; and
- If p ∈ P, a ∈ A, b ∈ B, then there exist r, s ∈ P both extending p such that a ∈ dom(r), b ∈ ran(s) (“back and forth” property).
If a partial isomorphism exists between A and B, we say that A and B are partially isomorphic and write A [size=undefined]≅p B. We then have[/size] - اقتباس :
- Karp's Partial Isomorphism Theorem.
For any similar structures A, B, A ≡∞ω B ⇔ A [size=undefined]≅p B.[/size] There is also a version of Scott's isomorphism theorem for L(∞,ω), namely, - اقتباس :
- (2.2) Given any structure A, there is an L(∞,ω)-sentence σ such that, for all structures B, A[size=undefined]≅p B ⇔ B ⊨ σ.[/size]
Partial isomorphism and (∞,ω)-equivalence are related to the notion of Boolean isomorphism. To define this we need to introduce the idea of a Boolean-valued model of set theory. Given a complete Boolean algebra B, the universe V(B) of B-valued sets, also known as the B-extension of the universe V of sets, is obtained by first defining, recursively on α, - اقتباس :
- Vα(B) = {x: x is a function ∧ range(x) ⊆ B ∧ ∃ξ<α[domain(x) ⊆ Vξ(B)]}
and then setting - اقتباس :
- V(B) = {x: ∃α(x ∈ Vα(B))}.
Members of V(B) are called B-valued sets. It is now easily seen that a B-valued set is precisely aB-valued function with domain a set of B-valued sets. Now let L be the first-order language of set theory and let L(B) be the language obtained by adding to L a name for each element of V(B) (we shall use the same symbol for the element and its name). One can now construct a mapping [·](B)of the (sentences of the) language L(B) into B: for each sentence σ of L(B), the element [σ](B) of Bis the “Boolean truth value” of σ in V(B). This mapping [·](B) is defined so as to send all the theorems of Zermelo-Fraenkel set theory to the top element 1 of B, i.e., to “truth”; accordingly,V(B) may be thought of as a Boolean-valued model of set theory. In general, if [σ](B) = 1, we say that σ is valid in V(B), and write V(B) ⊨ σ.Now each x ∈ V has a canonical representative x in V(B), satisfying - اقتباس :
- x = y iff V(B) ⊨ x = y
x ∈ y iff V(B) ⊨ x ∈ y We say that two similar structures A, B are Boolean isomorphic, written A [size=undefined]≅b B, if, for some complete Boolean algebra B, we have V(B) ⊨ A [size=undefined]≅[/size] B, that is, if there is a Boolean extension of the universe of sets in which the canonical representatives of A and B are isomorphic with Boolean value 1. It can then be shown that:[/size] - اقتباس :
- (2.3) A ≡∞ω B ⇔ A [size=undefined]≅b B.[/size]
This result can be strengthened through category-theoretic formulation. For this we require the concept of a(n) (elementary) topos. To introduce this concept, we start with the familiary category of Set of sets and mappings. Set has the following key properties:
- There is a “terminal” object 1 such that, for any object X, there is a unique map X → 1 (for 1 we may take any one-element set, in particular, {0}).
- Any pair of objects X,Y has a Cartesian product X × Y.
- for any pair of objects one can form the “exponential” object YX of all maps from X → Y.
- There is a “truth-value” object Ω such that for each object X there is a natural correspondence between subobjects (subsets) of X and maps X → Ω. (For Ω we may take the set 2 = {0,1}; maps X → Ω are then characteristic functions on X.)
All four of these conditions can be formulated in category-theoretic language — a category satisfying them is called a topos. The category Set is a topos; so also are (i) the category Set(B) of Boolean-valued sets and mappings in any Boolean extension V(B) of the universe of sets; (ii) the category of sheaves of sets on a topological space; (iii) the category of all diagrams of maps of sets - اقتباس :
- X0 → X1 → X2 → …
The objects of each of these categories may be regarded as sets which are varying in some manner: in case (i) over a Boolean algebra; in case (ii) over a topological space; in case (iii) over (discrete) time. A topos may be conceived, then, as a universe of “variable” sets. The familiar category Set is the special limiting case of a topos in which the “variation” of the objects has been reduced to zero.Just as in set theory, “logical operators” can be defined on the truth-value object in any topos. These are maps ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω corresponding to the logical operations of negation, conjunction, disjunction and implication. With these operations, Ω becomes a Heyting algebra, thus embodying in general the laws not of classical but of intutionistic logic. In this sense intuitionistic logic is “internalized” in a topos: intuitionistic logic is the logic of variable sets. (Of course, classical logic is internalized in certain toposes, for instance Set and Set(B) for any complete Boolean algebra B.)Any topos may be conceived as possible “universe of discourse” in which mathematical assertions may be interpreted and mathematical constructions may be performed. Mathematical assertions are rendered interpretable in a topos E by expression within E's internal language — a type-theoretic version of the usual language of set theory. In a manner analogous to Boolean-valued validity, one can introduce an appropriate notion of validity in E of a sentence σ of its internal language. Again, we write E ⊨ σ for “σ is valid in E”.A topos E is said to be full if, for any set I, the I-fold copower[3] ∐I1 of its terminal object exists in E. ∐I1 may be thought of as the canonical representative in E of the set I; accordingly, we write it simply as I. (In V(B) this coincides with I as previously defined.) All the toposes mentioned above are full.Now let E be a full topos. If A = (A, R, …) is a structure, write A for (A, R, …). Two structures Aand B are said to be topos isomorphic, written A [size=undefined]≅t B, if, for some topos E defined over the category of sets, we have E ⊨ A [size=undefined]≅[/size] B. In other words two structures are topos isomorphic if their canonical representatives are isomorphic in the internal language of some topos. It can then be shown that[/size] - اقتباس :
- (2.4) A ≡∞ω B ⇔ A [size=undefined]≅t B.[/size]
Accordingly (∞,ω)-equivalence may be regarded as isomorphism in the extremely general context of universes of “v | |
|
اليوم في 1:40 pm من طرف