Talk:Compactness theorem
From Wikipedia, the free encyclopedia
For instance, it follows that if something is true for any field of positive characteristic, it must also be true for fields of characteristic zero (so, for real, complex or rational numbers too).
- I moved this from the main page, since the statement is strictly untrue. For example, it is true for any field with positive characteristic that there exists a non-trivial finite subfield with the same characteristic, but this isn't true for fields of characteristic 0. I'm sure something similar and more accurate can be phrased; but I don't know enough to say it. Chas zzz brown
Well, the statement in question is not a sentence. You cannot express it by the first order predicate calculus formula. I have reverted with this clarification.
Actually, you are right, here is an example: there are x,y,z,t different from zero, s.t. x^2+y^2+z^2+t^2=0 - this holds true in every characteristic p, but not in rational numbers. This is a valid sentence. There is however always SOME field of characteristic zero for which the statement holds. (it is enough to have fields of arbitrary large characteristic) I have added corrections, the original statement actually goes the other way around and is called robertson principle, and the other statement is its contraposition.
What about confusion between the idea of compactness in analysis and compactness in logic? Shouldn't both versions of compactness be mentioned here?
Compactess in analysis is property that each cover contains a finite subcover - this is the origin of term in logic.
Added by Alberto Mura:
By Stone's theorem every Boolean algebra is isomorphic to a compact topological field U of sets of ultrafilters. This holds in particular for the Boolean algebra A of the sentences of a first-order theory T (called Lindenbaum-Tarski algebra of T), obtained by identifying every pair of sentences p and q such that |-p ↔ q via the partition induced by the equivalence relation |-p ↔ q. There is a one-to-one map f:P(A)-->U that maps every set C of elements of A to a closed set f(C) of ultrafilters such that if i ∈ T then f(∪Ci) = ∩ f(Ci));. Let M be a set of sentences of T and let be q a sentence of T such that M ||-q. Let V be the join of the elements of A that correspond in A to the elements of M, and let W = V ∪ {[-q]}.
Clearly, f(W) = 0 (i.e. f(W) equals the empty set of ultrafilters in A). Since the space of the ultrafilters of A is a compact Hausdorff space, there is a finite subset V' of V such that the f(V' ∪ {[-q]}) = 0. If so, there is a finite set F of elements of T, belonging to elements of V' (which are equivalence classes), such that F ||- q.
This proves the so-called compactness theorem. The above topological proof explains the use of the term "compactness" in logic. Bibliography:
Beth, E. W. - The Foundations of Mathematics, Amsterdam, 1968, 523-526.
Rasiowa H.-Sirkoski R. - The Mathematics of Metamathematics, Warszawa, 1968.
Sirkoski, R. - Boolean Algebras, Berlin, 1960.
Can't find Robertson's principle in this context. Is this rubbish? User:David Martland
Try http://www.media.mit.edu/physics/pedagogy/babbage/texts/rt.html if you dont believe
- Shouldn't it be Robinson (as in Abraham Robinson)? --Zundark 21:31 Nov 28, 2002 (UTC)
- As noted at the top of the referenced page:
-
- This is a transcription of relevant notes from the class 18.511 taught by Prof. Sacks in the Spring of 1998, organized and reinterpreted. Homework problems starting with problem 9 are solved in vitro. Notation is indecipherable.
- ...so there could very well be many typos. Chas zzz brown 22:25 Nov 28, 2002 (UTC)
Well, I found this Robertson on that site - I never heard about the name for the principle before, it seems it is really a misprint. But the statement is certainly true (it is a straightforward application, as fields of characteristic zero have axioms p<>0 for each p prime, and hence if a sentence is inconsistent with theory of fields of characteristic zero, there must be a finite subset of this set of axioms inconsistent with a statement so for every field of characteristic p greater than largest prime in that set it will be inconsistent too) - it is perhaps too simple to be some big principle, but it seems to be very illustrative for compactness theorem.
The phrase "if and only if any finite subset is whatever" is ambiguous: "any" could mean "any at all", i.e., at least one, or it could mean "every". I corrected the ambiguity by writing "if and only if every finite subset is whatever". The article also incorrectly said "consistent" instead of "satisfiable", and I corrected that. To say a set of sentences is "consistent", by definition means no contradiction can be proved from those sentences, and thus it relies on the notion of proof. From the finite nature of proofs, it follows instantly that if every finite subset is consistent, then so is the whole set; that is trivial. But the compactness theorem is not trivial. It speaks not of consistency, but of satisfiability, i.e., of the existence of models. Goedel's completeness theorem says that if S is a set of first-order sentences and T is a sentence that is true in every model in which all of the sentences in S are true, then T can be proved from S in a reasonable system of proof. "Reasonable" means that if any sentence R can be proved from S, then in every model in which every sentence in S is true, so is R (this is "soundness"), and that there is an algorithm for checking the validity of proofs. From the completeness theorem and the finitary nature of proofs, one can deduce the compactness theorem as a corollary. Since the compactness theorem does not mention proofs at all, one must then wonder whether it can be proved by other means, without mentioning provability of first-order sentences. One such proof uses ultraproducts. I highly recommend Boolos & Jeffrey's book Computability and Logic to anyone interested in these topics. -- Mike Hardy
