Leon Gumański
Yüklə 0,58 Mb.
|
- Bu səhifədəki naviqasiya:
- References
DEFINITION 5.8. .
DEFINITION 5.9. where for some d and g : d+g = pi+s.
Let us visualize graphically the relation of the tableau T+ to T, supposing that n=2, k=i+4 and
REMARK 5.4. Note that in all tableaux to which the subtableau We intend to show that if the sets With this aim in view let us proceed now to proving a lemma in which: CONVENTION 5.1. The signs “ LEMMA 5.2. For every i Claim 1. The set Claim 2. The set PROOF. Claim 1. According to definition 5.7. the sets Now, proving by induction on s, let be s=1. In this case the set 1. When in certain places in the elements of 2. If a y–variable occurs in certain places in the second member v of a closing pair such that For s>1 the proof is analogous. Claim 2. The proof is analogous to the proof of Claim 1. Replace Lemma 5.2. shows that if the set Next, in the light of Assumption 5.2 that the number k is the minimum length coefficient of proof P, it is easy to notice that there must be in P such a tableau T in which there are no superfluous stages (transformations) and the closing pair appears only at the last stage k. In fact there must exist at least n tableaux of this type in the proof P because the set LEMMA 5.3. A certain tableau T in the proof P has the following features: (I). The set (II). For every i PROOF. As the existence of at least n tableaux having the feature (I) evidently follows from Assumption 5.2, let us consider an arbitrarily chosen tableau T of this type and then – proving indirectly – let us assume that for a certain i We now proceed to the next lemma which exposes one more characteristic feature of tableau T. LEMMA 5.4. The tableau T, that Lemma 5.3 speaks about, apart from the features (I) and (II) may also have the following property: (III). There is at most one number i such that:
PROOF. Let  be a set of degree f<m. Then in any case the following disjunction must be true:
A1. Either the set When the first disjunct of A1 is true, two cases may take place: 1° The set 2° The set In case 1° two situations can be taken into consideration: First – when the sets The second situation may occur when an atomic expression u, absent in the set Now consider the case 2°. The set We have shown so far that if the first disjunct of A1 is true, then in any case which does not lead to contradiction the set Suppose in turn that the second disjunct of A1 is true, i. e. the set This is not to deny, however, that when LEMMA 5.5. The minimum length coefficient k of the proof P can be estimated: k<2. PROOF. As can be seen from Lemma 5.3 and Lemma 5.4, there are such tableaux in the proof P in which a closing pair appears only at stage k and starting from stage 2 new kinds (i. e. absent at previous stages) of sets of atomic expressions of degree hm occur at every stage – except one stage at most. Thence the number k may be at most by one greater than the number (k +1) of all kinds of nonempty sets of a degree not higher than m of atomic expressions which it is possible to construct of the predicate variables being present in the expression t and of m different y–variables. The number can be estimated in every case. Namely, it is possible to make mi atomic expressions of one i–ary (i–adic, i–place) predicate variable and m different y–variables (we apply the formula for permutations of m variables taken i at a time with repetitions). As in the sets that we are considering each of expressions can be preceded by the sign plus, we have to distinguish 2mi expressions with one i–ary predicate variable. Now suppose that there are at most r–ary predicate variables in the expression t and pi is the number of distinct i–ary (ir) predicate variables present in t. Hence, of all the predicate variables that are found in t and of m different y–variables it is possible to build 
different atomic expressions. Let U be the set of all these expressions. There are 2–1 nonempty subsets of U. Note that every set of degree hm that can be met in the tableau T of the proof P is of the same kind as a certain subset of U. However, some subsets of U – although not identical – are of the same kind (e. g. if the binary variable “f” occurs in t and m=3, then there are six sets of the same kind as {fy1y2,+fy2y1}). It follows that  <2–1, but as we have already stated k+1, hence k<2.
THEOREM 5.3. The first–order functional calculus is decidable. PROOF. If the prefix of t consists only of universal or only of existential quantifiers, then according to Theorem 5.1 and Theorem 5.2 provability of t can be checked up by means of one–stage tableau–construction. In case the prefix of t consists of universal as well as of existential quantifiers, it is sufficient to inspect, using the method described in section 4, whether there is a (2–1)–stage proof of t. When such a proof cannot be constructed, then in the light of Lemma 5.5 this is an evidence that t is unprovable.
The author is indebted to Prof. Michiel van Lambalgen (Amsterdam) for his suggestions concerning the structure of a former version of this paper. References [1] W. Ackermann: Solvable Cases of the Decision Problem. North–Holland Publ. Co., Amsterdam 1954. [2] E. W. Beth: Formal Methods. An Introduction to Symbolic Logic and to the Study of Effective Operations in Arithmetic and Logic. Synthese Library, D. Reidel, Dordrecht 1962. [3] D. Hilbert, W. Ackermann: Grundzüge der theoretischen Logik. Vierte Auflage, Springer, Berlin–Göttingen–Heidelberg 1959. [4] L. Kalmár, J. Surányi: On the Reduction of the Decision Problem. Third paper, Pepis Prefix, A Single Binary Predicate. “The Journal of Symbolic Logic” 1950, Vol. XV, p. 161. [5] H. Leblanc, W. A. Wisdom: Deductive Logic. Sec. Edit. Allyn and Bacon Inc., Boston–London–Sydney–Toronto 1976. [6] L. Gumański: On Decidability of the First–Order Functional Calculus. 7th International Congress of Logic, Methodology and Philosophy of Science, Salzburg 1983, Vol. 1 Abstracts of Section 1. [7] L. Gumański: Entscheidbarkeit des engeren Pradikatenkalküls. Untersuchungen zur Logik und Methodologie, Bd 3, Karl–Marx–Universität Leipzig, 1986. [8] L. Gumański: Wprowadzenie w logikę współczesną (Introduction to Contemporary Logic), in Polish, PWN, Warszawa 1990. [9] L. Gumański: Remarks on Cantor’s Diagonal Method and Some Related Topics, [in:] Types of Logical Systems and Problem of Truth, Bulgarian Academy of Science, Sofia 1988. Also in the present edition, see next page.
(Sympozjum Bułgarsko–Polskie, Sofia 23–27 IX 1985) I. In my paper [8] delivered before the 7th International Congress of Logic, Methodology and Philosophy of Science in Salzburg I presented a decision procedure for the functional calculus of first order. This result contradicts the well–known Church's theorem and so the problem arises what an error has been committed in the proof of the theorem. A careful perusal and strenuous analysis have shown that the matter is more serious than it might seem at first. Alonzo Church has namely applied in [2] the so–called diagonal method5 sometimes declared to be „one of the strongest and most famous methods in modern mathematics”6. The method was introduced by Cantor for the first time in 1874. There has been some disagreement among scientists concerning the correctness of the method. Objections have been raised not only by mathematicians7. However, some celebrities have decidedly refuted them therefore the method has been generally accepted for a long time and brought into practice especially in set theory and in the realm of foundations of mathematics. The aim of the present paper is to demonstrate that despite its distinguished credentials the method is unreliable and all the purported proofs in which it is employed – though not necessarily their theses – ought to be doomed to oblivion. It might be well to start with a brief habitual description of the method. We may put it as follows: One takes into consideration an arbitrarily chosen denumerable subset S of a certain infinite set F of sequences and enumerates one way or another the elements of S, let us say E = <s1, s2, ..., si, ...> where si = <ei1, ei2, ..., eii, ...>. By this means one obtains a sequence of sequences. Then a definition of a „new” sequence d = < d1, d2, ..., di, ... > belonging to the set F is introduced. The definition is so constructed that it ought to be plain that d is different from each si, because di is unlike eii, for every positive integer i. Such a result is usually achieved due to an appropriate function f indicated in the definition of d. Hereafter sequences defined like d will be called ‘diagonal’. It is exactly the definition of a diagonal sequence applied in proofs, which constitutes the gist of the method at issue. The purpose of proofs of this kind is to show that the denumerable subset S is a proper subset of the set F (in symbols S F). I Example I. Let F be the set of all decimal representations (expansions) of real numbers x in the interval 0 < x 1 and let S be any denumerable subset of F. Each decimal fraction of S has the form of a sequence: 0.e1e2e3… We arrange the decimals of S in a sequence E = < s1, s2, …, si, …> choosing a mapping between S and the set N of all positive integers. The resulting sequence of sequences may be depicted as follows:
. .
. . . .
si: 0.ei1ei2ei3…eii... . .
. . . .
di = 1 if eii ≠ 1, di = 2 if eii = 1. It is claimed that d is a fraction different from all the decimals of S because the ith digit (after the decimal point) in the ith decimal of S is eii while the ith digit in d is di ≠ eii. On the other hand d is an infinite decimal fraction between 0 and 1, hence it belongs to F. Example II. Let F be the set of all functions of one variable and S be its denumerable subset that contains only functions assigned by the formulae <A1, A2, …, Ai, …> of a formal system AR of arithmetic according to the following rule (for each natural number n):
where Ai(n) is the result of substituting the name of the number n for all occurrences of free variables in Ai. Hence we have a sequence E of functions <f1, f2, ..., fi, ...>. We identify fi with the sequence of successive values of fi : <ei1, ei2, ..., eik, ...> where eik = fi(k). Then we define a function h belonging to F: h(n) = 1 if fn(n) = 0, h(n) = 0 in other cases. The diagonal sequence d is the sequence <d1, d2, ..., di, ...> where di = h(i). In other words d is the sequence of successive values of the function h. It is asserted that the function h, identified with d, though belongs to F does not belong to the sequence E, for otherwise it would be fk(k) = 1 iff fk(k) = 0, for a natural number k. It should be noted that the diagonal method may and has been applied both in direct and indirect proofs. So we consider it advisable to discuss the two cases separately. Moreover, in our considerations we shall confine ourselves at first to proofs constructed on the grounds of naive preaxiomatic set theory and only after that we shall turn to analogous proofs based on axiomatic version of the theory. IIa. Indirect tactics is the most common form encountered in proofs in which the diagonal method is adopted. W. K. Essler states accordingly that the definition of a diagonal sequence may always serve to deduce an absurdity8 It is important a point to realize and to keep in mind that in indirect proofs no more than one assumption is allowable, namely the negation of the thesis to be proved. Only theorems chosen from the theory on which the proof is founded may occur as other premisses of the reasoning. A definition can be incorporated solely on condition that the existence of the object defined follows from premisses already recognized in the proof. However, the fact of the matter is that the existence of the diagonal sequence d is, as a rule, not a logical consequence of premisses in indirect proofs based on non–axiomatic set theory. The statement of existence, usually overlooked or suppressed, makes actually the second assumption of the proof. For that reason the final conclusion should run in the form of disjunction: either the thesis is true or d does not exist. The contradiction obtained in the proof does not allow to decide which of the two disjuncts is veracious or which premiss is responsible for the contradiction. A. A. Fraenkel, one of the most prominent originators and propagators of modern set theory, at an early stage of his activity must have felt that something was wrong with indirect proofs applying the diagonal method. Most likely therefore he wrote as follows in [5] about Cantor’s proof of non–denumerability of the continuum: “Surely anybody who becomes acquainted with this proof for the first time, with all his admiration for the simple and significant fundamental idea (called diagonal procedure) will not be able to suppress a painful feeling … which though does not belie the compelling power of the fundamental idea, nevertheless smells something insidious or at least unfair in the arrangement of its conclusions”9. IIb. Fraenkel believed that most doubts would disappear if the direct form of proof was chosen. Let us then turn to that kind of proofs. In this case, as well as in the previous one, it is maintained that the diagonal sequence d is different from each sequence si of the subset S. What makes us think so? Authors do not say much about it. They probably treat the point intuitively as obvious. And so for instance if d, si are decimal fractions, as in our Example I, it is usually just stated that the ith digit of si is eii while the ith digit of d is di ≠ eii 10. The first impression that this explanation is satisfactory turns out, on closer inspection, to be misleading. There is a gap concealed behind the innocent–sounding words. To convince ourselves of this let us first make a query again: How do we know that di ≠ eii? The right answer may seem to read: we know this from the definition of d. But that is not at all the case. The definition only requires that eii should be transformed into a different member di, for each number i. However, this requirement can merely be fulfilled on certain conditions. In order to compare eii with di or to decide if it is possible to convert eii into di one must know more about the subset S. Otherwise there is no certainty that the comparison or the conversion can be performed. I am going to show it at once. When using the diagonal method in proofs one must not specify either the subset S or the enumeration E (although S or E may be characterized in a general way as in Example II), because otherwise an objection may be raised that a diagonal sequence can be constructed for the given S and E, however an open problem remains whether it is possible to form a diagonal sequence for other subsets of F and other enumerations as well. That is why, in order to preserve generality it is usually just stated that S and E are freely chosen but fixed within the proof. If so, it cannot be excluded a priori that S fulfils the condition S = F. The exclusion of the condition is inadmissible for the following reason: From the assumption S F it follows immediately: ( We have to consider both disjuncts of (+) and must not reject any one of them without serious grounds. Now, supposing S = F it should be clear that d S, because d F is admitted. Then it follows at once from d S that d = sk for some positive integer k. In other words, the defined sequence d belongs to the enumeration E=<s1, s2, ..., si, ...> of S. Nevertheless, in this case it is obvious that d does not exist, for it is impossible to convert ekk into dk in such a way that dk becomes different from ekk (as the definition of d requires) and remains identical with ekk at the same time (because d = sk). In sum, the requirement of the definition cannot be met and the relation f (by means of which d has been defined) is not a genuine function, as no single value exists for the argument k. Or to put it another way, if we assume S = F, then ‘d’ does not denote any existing object, because from the assumption combined with the definition of d a contradiction follows (ekk dk and ekk = dk ). In short, if S = F, d does not exist. Hence by contraposition we have: if d exist, then S F. In other words S F (or S F which follows) is a necessary condition of existence of the diagonal sequence d. There are even more necessary conditions of existence of d, as we shall show in a moment. O And now let us add another remark. Against the background of the statement that S and E are freely chosen, it cannot be a priori excluded that the enumeration E fulfills the condition eik = dk for every k < i. In this instance the diagonal sequence d is up to ith member identical with si+1 for every positive integer i. So in our Example I the sequence E may have the form:
. .
. . . .
s11: 0.2111111111123… s12: 0.2111111111223… . .
. . . .
si: 0.211……….1211…eii… si+1: 0.211……….1211…diei+1i+1… . .
. . . .
It can be easily seen that < d1, d2, ..., dk> = <ei1, ei2, ..., eik> for every i and k < i. Now consider a principle, let us call it P, to the effect that if for every i and k < i: < d1, d2, ..., dk> = <ei1, ei2, ..., eik>, then there exist, in infinity, such a member of E which is identical with d. The principle P may seem quite plausible, especially when one notes a certain similarity to many thesis already acknowledged in mathematics (like 1 = 0.999…). Suppose we accept the principle P. Then we fall into contradiction immediately: d is different from all the members of E (let us take it for a moment that this can be shown convincingly) and d is identical with one of them. Hence d does not exist. This argument is to give evidence once more of the fact that existence of a diagonal sequence is not absolute, it depends not only on some necessary conditions, such as S F or D S, but also on certain accepted or rejected principles. O For all that reasons we must consider the existence of diagonal sequences as highly uncertain and their definitions as inadmissible, at least as long as it is not demonstrated that the defined diagonal sequence exists. Consequently, if such a demonstration has not been given, we must recognize any proof (even a direct one) that employs the diagonal method to be fallacious. As a matter of fact the demonstration is lacking in proofs which are not based on axiomatic set theory. III. There are a number of points here which need explaining or disentangling at this stage in order to forestall some expected objections. So let us break off our main considerations for a while. First of all it seems apposite to focus our attention on the correctness of definitions. Until 20th century the problem was not dealt with by logicians and mathematicians as scrupulously as it was deserving. Cantor, like most of his contemporaries, appears not to realize that a mere act of defining does not warrant existence of an intended object. In particular he surely believed that each diagonal sequence was an actual entity which became known due to its definition. Neither was he aware that definitions might cause contradictions. The antinomies of set theory, which were discovered about the turn of 20th century, were a real shock for him and for other scientists as well. Several remedies were offered, most of them artificial, devised ad hoc. However, as H. Poincaré rightly advised, we ought to learn a lesson from the discovery of antinomies. In the first place it is worthy of notice that all the paradoxes of logic and set theory either immediately derive from or can be shown to depend on definitions. Such a phenomenon cannot be accidental. This observation gives us a heuristic indication where we should search for means suitable for removal of antinomies. It is definitions that must be responsible for each paradox in question. So it seems reasonable to demand that they should fulfill certain conditions. Yet it would be hard to draw up a full specification of all indispensable conditions because correctness of various kinds of definitions depends on diverse factors. None the less, it is now generally agreed that each object defined correctly must exist11. On the other hand, different views have been advanced and defended with regard to the problem what the word ‘existence’ means in relation to mathematical and logical objects. This is not the right place or time for a discussion of the problem but we may take it for granted that non–contradictoriness is a necessary, if not also sufficient, condition for the existence of abstract entities of this sort. That is why we have said above that the sequence d does not exist when d = sk, for then dk is both identical with and different from ekk. What is more, in that case the definition of the diagonal sequence d must be regarded as incorrect. It can be easily anticipated that many persons would object. Why should we recognize as incorrect for instance the definition of the sequence d in Example II? The function h requires only to replace 0 by 1 or conversely 1 by 0. This can be always done”, they could say. However, in reality the operation is feasible unless and until some additional requirements interfere. It is a regrettable mistake to think that any definition which turns out to be correct under certain circumstances retains its correctness independently of conditions. The meaning of the term defined and existence of the object denoted by the term depend on the framework into which the definition has been incorporated.12 Taken separately (as an inscription) the definition is not univocal or rather void of meaning. When confining ourselves to functions we can state that in order to define a function f (by means of an equivalence) first of all one must fix precisely its domain and counterdomain13. This is usually done by the context (explanations or premises, or theory, deductive system, framework) which constitutes the background against which the definition of f is presented. Any essential modification of the context may result in a change or annihilation of the function. Thus for instance the function of being a square root of a number defined by the equivalence: (++) in case the domain is qualified as the set of natural numbers, differs from the function defined by means of the same equivalence when the domain is restricted to positive even numbers. None the less in both cases the definition (++) is correct. However, if we extend the domain over the set of all real numbers, the definition (++) loses its correctness because the necessary condition to the effect that for each argument there exists only one value is violated (hence the relation is no more a function)14 and moreover it is possible to infer contradictions from this definition combined with some theorems of the theory of real numbers. Consequently, the object (function) so defined does not exist on the ground of this theory. In general we have a negative criterion: if a definition added to a consistent set of sentences (premises, theory, framework) entails a contradiction, the object defined does not exist and the definition is faulty. Still, it might be well to lay emphasis once more on the fact that the same definition may be faultless when joined to another set of sentences. It should be worth while making the observation by way of digression that in the light of the just mentioned criterion the problem of antinomies appears in a new shape. An antinomy is not a mysterious logical puzzle, nor is a threat to the very foundation of logic. It is simply a quite innocuous proof in which the derived absurdity demonstrates that against the background constituted by a set of accepted premises (or theory) the defined object does not exist and the applied definition is inadmissible. IV. Now let us return to the main drift of our consideration. We have ascertained that the existence of diagonal sequences is doubtful, questionable. Nevertheless the creators of axiomatic set theory took a different view and declared themselves for the existence of the sequences. Why did they make such an option? This is a question for the history and sociology of science. It seems that not only cognitive but also emotional and even aesthetic motives have played an important part. If they had made another option, they would probably have obtained a much simpler set theory, without various kinds of infinity. In any case, the Zermelo axiomatization and all its subsequent modifications were devised in order to protect the Cantor’s theory from antinomies on the one hand and to preserve at least some of the so–called impredicative definitions on the other15. With a view to ensuring existence for objects defined by means of impredicative definitions, among them for diagonal sequences, Zermelo introduced the axiom of separation which states that for any set X and any definite condition C there is a subset Y of X containing all and only those elements of X for which the condition C holds good. It has been in dispute how to understand ‘definite conditions’. Diverse proposals have been advanced. At any rate all the offered solutions have tended to vindicate and to retain, in spite of Poincaré’s strong criticism, those impradicative definitions which are indispensable for the construction of Cantor´s set theory. It must be admitted that owing to this shift many proofs grounded on axiomatic set theory and carried out according to the diagonal method have been acknowledged to be formally correct since the existence of the diagonal sequence is secured axiomatically. But are they convincing? The answer must be in the negative. A proof is convincing if and only if all its basic premises are recognized as true and all its consequences follow from the premises. However, in the proofs in question one of the fundamental premises is the just mentioned axiom of separation (called sometimes ‘axiom of subset’ or ‘definitional axiom’). This axiom raises grave objection. All sentential functions with a free variable different from ‘Y’ are, in practice, treated as definite conditions. It is assumed that each element of any given set X should either fulfil the condition C or not (in the exclusive sense of the conjunction ‘or’). If no element of X fulfils C, the separated (defined) subset Y of X exists but is empty. Otherwise Y is not empty. And so, with respect to the given set X, the condition C may belong to one of two classes according as it separates from X an empty or non–empty subset. Still the sentential functions under consideration ought to be devided with regard to X not only into two but at least into four classes. For there may also be such sentential functions (conditions) that some elements of X neither satisfy nor violate (do not satisfy) them, e. g. because the theory we are taking advantage of is weakly incomplete and within its framework satisfaction of C cannot be proved or disproved for some elements of X. In this instance the subset Y is undetermined and it is impossible to state its existence or non–existence. Besides, the discovery of antinomies has brought to light the fact that some sentential functions (conditions) can be satisfied and not satisfied at the same time by an element of X since both things are provable. It should be plain that under these circumstances the subset Y does not exist, i. e. the condition C separates no subset from X. To this last class belong the sentential functions which occur as definiens in impredicative definitions. Yet the axiom of separation is so applied as if the third and the fourth class of sentential functions were neglected. As a matter of fact the axiom does not lead to contradiction within set theory, for other axioms are so adjusted that not every set X can be accepted as existing. Very comprehensive sets cannot be introduced. Owing to these favourable special circumstances the dangers which are inherent in the axiom are avoided or rather they do not manifest themselves. At all events the axiom of separation taken as such in seclusion cannot be viewed as obvious or well–founded. It is unsafe, untrustworthy. That is why the axiom is unfit for justifying the previously mentioned option made by the originators of axiomatic set theory. The assumption that the diagonal sequence d exists is arbitrary. Its acceptance is nothing but a result of a decision, of a subjective preference. Now, existence of real objects as well as of abstract, theoretical ones does not depend on decision, on human will. In particular it is not sufficient to decide that diagonal sequences should exist. For all these reasons we must consider all proofs constructed according to the diagonal method and based on axiomatic set theory as not convincing, as mere samples of logical deduction grounded on arbitrary assumptions. The method does not make a reliable instrument for scientific investigations. V. And now to conclude we may return to our point of departure. As I have already alluded A. Church in his proof that the functional calculus of first order is undecidable has made use of the diagonal method. And that is his mistake. The calculus has its own objective properties independent of our will. It is decidable as I managed to demonstrate in my paper [8]. No arbitrary decisions, no assumptions, no axioms can help it. References[1] E. W. Beth: The Foundations of Mathematics. Amsterdam 1959. [2] A. Church: An Unsolvable Problem of Elementary Number Theory. “American Journal of Mathematics” 1936, Vol. 58. [3] A. Church: A Note on the Entscheidungsproblem. “The Journal of Symbolic Logic” 1936, Vol. 1, No 1. [4] W. K. Essler: Aufzählbarkeit und Cantorsches Diagonalverfahren. Untersuchungen zu Grundfragen der Logik. München 1964. [5] A. A. Fraenkel: Zehn Vorlesungen über die Grundlegung der Mengenlehre. Leipzig, Berlin 1927. [6] A. A. Fraenkel: Zum Diagonalverfahren Cantors. „Fundamenta Mathematicae” 1935, Vol. XXV. [7] A. A. Fraenkel: Abstract Set Theory. Sec. Ed., Amsterdam 1961. [8] L. Gumański: On Decidability of the First Order Functional Calculus. 7th International Congress of Logic, Methodology and Philosophy of Science, Salzburg 1983, Vol.1 Abstracts of Section 1. [9] S. C. Kleene: Introduction to Metamathematics. Amsterdam, Groningen 1959. [10] A. Mostowski: Logika matematyczna. Warszawa, Wrocław 1948. [11] P. Suppes: Introduction to Logic. Princeton, New Jersey 1957. 1 Free individual variables may be bound by universal quantifiers placed in front of the expression. How sentential variables can be equivalently eliminated cf. e. g. [1] p. 17. 2 Instead of Beth’s tableaux any other system can be applied with regressive proofs, e. g. Smullyan’s analytic trees or the deductive systems SI presented in [8]. 3 The rule F(Ea) is often formulated without restrictions relative to the variable b (even in the original Beth’s texts). But such formulations are too broad and consequently can be misleading for they allow to introduce “new” variable at each application of the rule. However, some logicians have already realized that a procedure of this kind is usually pointless and suitable restrictions should be imposed on the variable b. Cf. e. g. [3] p. 78 rule (d) or [5] p. 188 routine D. 4 Cf. the condition concerning the variable b in rule F(a). 5 Cf. the demonstration of Theorem XVIII on p. 360. 6 Cf. A. A. Fraenkel [7] p. 54. 7 Cf. A. A. Fraenkel [6]. 8 Cf. W. K. Essler [4] p. 33. 9 Cf. A. A. Fraenkel [5] p. 10. 10 Even authors who construct their proof adopting axiomatic set theory act similarily. Cf. e. g. Fraenkel [7] p. 53, Kleene [9] p. 7. 11 For instance A. Mostowski in his textbook [10] p. 249 wrote: ”one may use a symbol denoting an object, no matter which (of an arbitrary logical type) only if we know that the object exists”. 12 Cf. E. W. Beth [1] p.363f. 13 Cf. P. Suppes [11] p. 231. 14 Cf. P. Suppes [11] p.158. 15 Cf. E. W. Beth [1] especially §§ 120, 121, 150. Yüklə 0,58 Mb. Dostları ilə paylaş:
|
is on the first (from above) branch of 
. The raising segments relate to the first branch, the sinking segments to the second branch. The tableau T+ is marked with the dashed line and T with the continuous line.
belongs any changes of substitutions by F(Ea) performed in the subsequent subtableaux do not cause changes in other tableau of the proof P (i. e. in tableaux to which 
are of the same kind up to degree m, then it is possible to obtain at stage i+s (for every s) in the tableau T all such kinds of sets of degree hm which occur in T+ one stage futher (i. e. at stage i+s+1).
/Sub”, “
/ Sub” denote such sets that come into being at stage i+s in place of 
is up to degree m of the same kind as the set 
, then there are such admissible substitutions Sub (by F(Ea)) that for every s such that i+s
/Sub is up to degree m of the same kind as the set 
.
/Sub is up to degree m of the same kind as the set 
.
are on the same branch g, hence ji+s=fi+s+1 and by Observation 2.2 the sets have the same structure.
. That is why it is possible to choose at stage i+1 such admissible substitutions Sub by virtue of F(Ea) that the set 
/Sub is up to degree m of the same kind as 
. It is sufficient to follow two rules for Sub:
the y–variables are different (identical) choose for Sub from y–variables admissible by F(Ea) different (identical) variables for analogous places. There is enough y–variables to choose from because one needs for Sub at most m1 different y–variables (see Assumption 5.1) and there are at least m different variables in 
and the first member of the pair belongs to 
, then choose for Sub the y–variable which occurs in analogous places in an atomic expression 
of the same kind as v but such that 
. The expression 
by the antecedent of the lemma.
,
by 
respectively.
is contained. In particular if the set 
includes a two–stage closing pair of which the first member belongs to 
and the second member to 
, then it is possible to obtain at stage k–1 a closing pair of which the first member is in 
and the second in 
/Sub. Similarily, when the set 
.
and no subset 
of degree h is of a kind different from the subsets of degree h included in 
and thus a closing pair could be obtained at stage k–1.
t will probably not do to say as much as that to explain what for us will count as the diagonal method. That is why we shall illustrate the method by two paradigm examples.
+) S = F or S F.
n the other hand, if we assume the second disjunct of (+): S F, no evidence of existence of a diagonal sequence can be deduced. On the contrary, it turns out that such a sequence may not exist. For instance, in the light of the fact that S is freely chosen, even if S F it is not unlikely that S contains the set D of all the sequences built of the same members of which d should be constructed, i. e. D S. However, in this case d S too for d D. Consider by way of illustration our Example I. If S contains all the sequences (decimal representations 0.ei1, ei2, ..., eik, ...) built at most of the digits 1, 2, then d must be one of these sequences, since d should also be constructed of the digits 1,2 only. But when d S, we can continue our reasoning in the same way as in the case S = F and demonstrate that D S is one more necessary condition of existence of d.
1: 0.123456789012…
n the other hand, we cannot indicate any sufficient condition of existence of diagonal sequences except perhaps such general ones as e.g.: no contradiction follows from the definition of the diagonal sequence added to the given non contradictory framework. But conditions of this kind give no criterion and may by called in question if one stipulates more than mere non–contradictoriness for the existence of abstract objects.