LOGIC IN THE TRACTATUS MAX WEISS Abstract. I present a reconstruction of the logical system of the Tractatus, which differs from classical logic in two ways. It includes an account of Wittgenstein's "form-series" device, which suffices to express some effectively generated countably infinite disjunctions. And its attendant notion of structure is relativized to the fixed underlying universe of what is named. There follow three results. First, the class of concepts definable in the system is closed under finitary induction. Second, if the universe of objects is countably infinite, then the property of being a tautology is Π11-complete. But third, it is only granted the assumption of countability that the class of tautologies is Σ1-definable in set theory. Wittgenstein famously urges that logical relationships must show themselves in the structure of signs. He also urges that the size of the universe cannot be prejudged. The results of this paper indicate that there is no single way in which logical relationships could be held to make themselves manifest in signs, which does not prejudge the number of objects. We have by now a quite systematic and rigorous grasp of the logical work of two of Wittgenstein's teachers, Frege and Russell. This is thanks in part to decades of flourishing scholarship, and thanks also to Frege and Russell themselves. In contrast, despite comparably voluminous commentary there is still no received understanding of anything describable as the logical system of the Tractatus (Wittgenstein, 1921). It is hard to resist the conclusion that the Tractatus did not, despite its professed program and its large reputation, offer any systematic alternative conception of the nature of logic. But the conclusion is mistaken. To the contrary, there is a system, or a class of similar systems, which can be understood to explicate the development of logic in the Tractatus. They differ rather sharply from those of Frege or Russell, as well as from classical firstor second-order logic. Nonetheless they can be exactly described and investigated metamathematically, for epistemological and metaphysical evaluation. In this paper, I will present one such system, and investigate some of its properties. These turn out to be of surprising and indeed independent interest. In seeking to understand what logic is supposed to be according to the early Wittgenstein, we may distinguish two kinds of evidence. First, there are the contours of his own construction, famously, for example, in the truth-functionality thesis and its enactment through iterated joint denial. Second, there are in the Tractatus apparent declarations of epistemological constraints on the nature of logic: some of these, for example, have been taken to suggest that according to Wittgenstein, logic must be decidable. I wish to separate these two strands. In the early decades of the 20th century, it was entirely possible for a proficient researcher to develop a computationally Thanks to Nate Ackerman, Roberta Ballarin, Juliet Floyd, Warren Goldfarb, Michael Kremer, Rehana Patel, John Schlipf, Sanford Shieh, Ori Simchen, and Kai Wehmeier. 1 2 MAX WEISS intractable system under the misapprehension of its decidability. Of course, it might be worthwhile to investigate systems which now can be seen to resonate with purported epistemological declarations of the Tractatus. The question still remains: what system, if any, did Wittgenstein in fact describe? The undecidability of logic being so deeply rooted in our own understanding, it is hard to take up in imagination the computational intuitions of researchers in the era which preceded its discovery. But in seeking to understand how someone tried to climb a mountain, we should study the climber's movements and the mountain's contours, not transpose the climber to a molehill. A large body of literature exhibits accelerating progress in our understanding of the development of logic in the Tractatus. Thanks especially to Geach (1981) and Soames (1983) and more recently Wehmeier (2004), (2008), (2009), and Rogers and Wehmeier (2012), it has become nearly received wisdom that Wittgenstein both intended and managed, if only haphazardly, to accommodate the expressive resources of first-order logic with equality. However, when the Tractatus was in preparation, first-order logic had not attracted much attention as an autonomous logical system. So it would be surprising to say the least to find that something like first-order logic, as it might be now understood, is the logic of the Tractatus. I want to explore two respects in which Wittgenstein's logic differs. They can each be understood to characterize a conception of logic which is a kind of intermediate between the logicisms of Frege and Russell on the one hand, and what became classical logic on the other. First, Wittgenstein's conception of logic differs from what became classical logic in regard to what is now understood as interpretation. Although the exact height of metalogical perspective reached by Frege or Russell has been a matter of some scholarly controversy, it seems nonetheless safe to deny that anything like the modern notion of first-order satisfiability or logical consequence plays a central role in their logical writings. Rather, for Frege and Russell, the notion of axiomatic derivability sets for logic a basic standard of rational organization, and thence also of logical correctness. But Wittgenstein denied such a role for proof. So it remains to be said just how the signs of a formalism could be subject to some standard of logical correctness by the lights of the Tractatus. Here, Wittgenstein propounds truth-conditional analyses of the notions of logical validity and of logical consequence. These analyses resemble the now classical reduction of consequence to the notions of truth-in-a-structure and class-of-all-structures. But while classically, a structure for a language may have as its domain any nonempty set, for Wittgenstein all structures relevant to the determination of validity have an underlying domain in common, the universal collection of all objects. It has been both claimed and denied, in commentary on Tarski (1936)-see Mancosu (2010) for a review-that this feature disrupts certain rudiments of model theory. But as we'll see, Wittgenstein's conception is yet further from the classical one, since like Russell he holds that each object has its own proper representative in a proposition. Second, Frege and Russell understood logic to include what we recognize as non-first-order resources. Frege's 1879 Begriffsschrift culminates with what, by Frege's lights, would be a purely logical analysis of the concept of the ancestral. Likewise, Russell's introduction of the axiom of reducibility was motivated in part by the desire to reduce to logic the principle of mathematical induction. First-order logic not having been isolated as an autonomous logical system, it is natural to LOGIC IN THE TRACTATUS 3 suppose that Wittgenstein inherited the expectation, regarding such non-first-order notions, that they were nonetheless logical. As Geach (1981), Potter (2009), and Ricketts (2012) among others have observed, he introduced a notion of "form-series" variable, which permits the expression, in finite space, of some countably infinite disjunctions. However, the literature contains no attempt at an exact reconstruction of the device. For example, although it's agreed that the disjuncts must be generated in some vaguely "effective" manner, it's not at all clear what this is supposed to mean. Moreover, the logical significance of the form-series device depends on the intelligibility of quantifying into the contexts it creates, but this in turn involves subtleties hitherto unaddressed in the secondary literature. I will construct a notion of formal series exactly. As an approximation from below, my assumption will be that it lies well within the system of constructions Wittgenstein did intend to admit. But then I will show that adding to first-order logic this approximation of the form-series device yields an expression of every concept definable by finitary induction. I'll also give some interpretive evidence to suggest that this was the point. So for present purposes, Wittgenstein's two main divergences from classical logic are these. The domain of every structure is one and the same collection of uniquely named objects. And, basic logical resources include the notion of iterated formal procedure. By making these divergences explicit, it becomes possible to give a mathematically definite characterization of the complexity of Wittgenstein's logical system. Let me quickly summarize the results to be established here; the technical notions are standard but will be defined in later sections. It has been widely recognized that Wittgenstein could respect a commitment to decidability of logic by presupposing that the domain of quantification is finite. This already implies that the complexity of logic depends on the cardinality of the domain; in §4 I'll evaluate the dependence precisely. I will show that if the domain is countably infinite, then the property of being a tautology in the logical system of the Tractatus is Π11-complete in a suitable analogue of the analytical hierarchy. But moreover, it is only granted the assumption of countability that the concept of tautology is Σ1 in the Levy hierarchy of formulas of set theory. Since, in any case, the notions of countableand of arbitrary-domain tautology are Π11 and Π ZF 1 a priori, these results are just about as strong as possible. When the form-series device is dropped from the system, then the notion of tautology returns to its familiar Σ1 position in the arithmetical hierarchy; however, the underlying notion of consequence remains just as intractable. There are several further respects in which logic as elaborated in the Tractatus may seem to differ from classical first-order logic. First, Wittgenstein takes as primitive not ordinary connectives like negation, disjunction or existential generalization, but rather a truth-functional operator N together with a variety of means of specifying the multiplicities of formulas to which it may be applied. Second, through a nonstandard interpretation of the objectual variables, Wittgenstein tries to eliminate the equality predicate. Third, the role of higher logical types in the Tractatus is a matter of some controversy. The first two of these features do not essentially alter the complexity-theoretic situation, but it considerably expedites the mathematics to abstract from them. On the other hand, the introduction of higher-order variables can only raise the complexity of the system. My primary aim is to establish lower bounds, so I could simply duck the controversy by introducing no higher types. 4 MAX WEISS Nonetheless, the complexity of, for example, the class of valid second-order formulas is far above the lower bounds established here (Väänänen, 2001). So, I argue on textual and systematic grounds that higher-order quantification does not figure centrally in Wittgenstein's account of the expressive resources of logic, and that impredicative quantification cannot figure at all. Thus, my contention will not just be that such-and-such are lower bounds, but moreover that significant strengthenings do not warrant comparable credence. A project to understand the purported nature of logic in the Tractatus encounters two kinds of difficulty. First, there are the well-known exegetical difficulties raised by the text itself. It is highly compressed, with its use of logical notation somehow both telegraphic and inconsistent. But a little reflection reveals technical subleties too, even within relatively uncontroversial features of the program. Of particular concern here will be the problem of implementing within quantificational logic Wittgenstein's proposal to compress some infinitary disjunctions into finite expressions. So in this paper, I will confine exegetical discussion to §1, with the aim there to justify interpretive hypotheses which underwrite the subsequent complexity-theoretic analysis. The point of the remainder of the paper is to give a mathematical explication of the hypotheses and then to investigate their consequences. I freely use notation and techniques which did not mature until after Wittgenstein's death. In outline, the rest of the paper runs as follows. §1 lays out some interpretive background. After briefly sketching the outlines of the Tractatus system, I introduce the two departures from classical logic under investigation, summarizing relevant literature and briefly sketching the importance of these eccentricities for the philosophical project of the Tractatus. §2 opens the mathematical developments. I begin by explicating Wittgenstein's notion of a structure as truth-possibility for elementary propositions, and show that it yields an embedding of the concept of truth in the concept of consequence. I then introduce an approximation of the form-series device, and propose an analysis of quantification into form-series contexts. Thanks to this analysis, it becomes possible to establish a foundational result, that the result of adding the form-series device to first-order logic does enjoy a decent form of extensionality. In §3, I turn to a question of the power of the form-series device, and show that as explicated here, it yields the effect of adding to first-order logic an operator for expressing finitary inductive definitions. At this point, the stage is set for the investigation of complexity. In §4 I present a detailed characterization of the complexity-theoretic effects of Wittgenstein's conception of structure and of his introduction of the form-series device, both separately and jointly: §4.1, §4.2, and §4.3 respectively treat the cases in which the underlying domain is supposed to be finite, or some fixed infinite cardinality, or considered in advance of any cardinality constraints at all. After sketching in §5 what I conjecture to be some philosophical significance for these results, the paper concludes in §6 with suggestions for future work. 1. Interpretive background In broad outline, Wittgenstein's conception of logical structure in the Tractatus is straightforward. The upshot is a collection of sentences, together with a relation on the collection which might be called "direct denial". The direct denial relation LOGIC IN THE TRACTATUS 5 distinguishes some sentences as atomic, namely those which directly deny no sentences. A nonatomic sentence is to be true if and only if each of the sentences it directly denies is not true. The relation of direct denial is supposed to secure that the truth or falsehood of each sentence be determined by the truth or falsehood of the sentences which are atomic. To this end, Wittgenstein prescribes that the collection of sentences and the relation of direct denial must together satisfy a certain structural condition, a so-called "general propositional form". Accordingly, atomic sentences may be regarded as having been given initially, and any other sentence must be presented as a joint denial of some sentences presented before it. As Geach (1981, 170) pointed out, the structural condition cannot be understood to require that anybody actually construct all sentences which precede a given sentence in the ordering, because in general, a sentence will have infinitely many antecedents. Rather, the condition purports to indicate when some finite manipulation of signs could secure for them a sense. The crux of the condition is that the relation of direct denial on the class of sentences be wellfounded. It is clear that if the relation of direct denial exhibited circularities, then it might not be intelligible as realizing a logical relationship of denial at all. For example, a sentence which appears to deny itself could be so understood only by taking it both to be both true and to be not true, which for early Wittgenstein would not be an understanding. But although Russell claimed to locate the origin of paradoxes in circularity, the mere exclusion of circularity does not suffice to secure the coherent interpretability of direct denial as denial: for example, it would still admit the construction of a sequence of sentences A0, A1, . . . each of whose terms is the direct denial of all its successors (see Yablo (1993)). In practice, Russell enforced the acyclicity of logical dependence by a metaphor of bottom-up construction in the ramified hierarchy of types; in imposing the stronger condition of wellfoundedness, this hierarchy is a clear conceptual antecedent of Wittgenstein's general propositional form. In neither Principia nor the Tractatus does the notion of wellfoundedness occur explicitly; so far as I know the concept is first explicitly formulated in Mirimanoff (1917). The existence of a wellfounded direct denial relation is supposed to give a condition on the construction of signs, according to which signs would be capable of expressing a sense. This means that wellfoundedness of direct denial should characterize the signs themselves, so that the relation can be determined from the mere signs without reference to their sense (cf. 3.33-3.331). To this end Wittgenstein prescribes that each nonatomic sentence have two parts. One part, which at 5.501 Wittgenstein calls a "bracket-expression", serves to present some possibly infinite multiplicity of other sentences. The other part is the famous operator N , which, attached to the bracket-expression, yields a sentence which directly denies precisely those sentences which the bracket-expression presents. Thus, to determine for any two sentences whether one directly denies the other, it should suffice to check whether the second is among the sentences presented by the bracket-expression of the first. It is clear that the complexity of logical dependence exhibited by the system will depend on the methods available for constructing bracket-expressions. Wittgenstein describes three methods at T5.501. The first method is simply to make a list of sentences outright; the resulting expression presents the sentences listed. Using joint denial on the lists, this obviously yields an analysis of negation and disjunction: the 6 MAX WEISS negation of a sentence is a sentence which directly denies just it, and the disjunction of two sentences is the negation of a direct denial of just those two. The second method is intended to yield an analysis of generalization over objects, and ultimately together with the first method to recover the expressive power of first-order logic with equality, at least under a certain "Russellian" construal. The third method goes rather farther, and was billed by Wittgenstein to yield at least a means of expressing the ancestral, or transitive closure, of expressible relations. In the rest of this section I will briefly sketch a somewhat anachronistic and oversimplified account of these two further methods which will suffice for the main purpose of this paper, which, again, is primarily analytical. 1.1. Objectual generality. Wittgenstein's account of quantification is rather sparse, mentioning only the N -operator, its application to finite lists, and its application to the collections of terms of bracket expressions constructed by a second method. According to T5.501, this second method consists in "giving a function fx , whose values for all values of x are the propositions to be described." Suppose, then, that some bracket expression presents the values of fx . Then, the result of attaching the sign of joint-denial to the bracket expression amounts, in some sense, to the same as the ostensibly Principian formula ∼ Ex .fx . Wittgenstein seems to intend this mysterious "function" fx to be something like a propositional function in the sense of Principia. However, it would appear to be only in the 3.31s that there appears anything approaching an explanation: "if we turn a constituent of a proposition into a variable, there is a class of propositions which are values of the resulting variable proposition" (3.315). Very roughly speaking, the second method might now be summarized as follows. The result of turning a constituent of a proposition into a variable is supposed to determine a propositional function; then an existential generalization is to be analyzed as the negation of the direct denial of the totality of the function's values. 1.1.1. The grammar of quantification. The abstractness of this account has abetted some controversy. In particular, Fogelin (1976) argued that since Wittgenstein does not mention any device for indicating the scope of the generalization, therefore he cannot distinguish between, say, the negation of the joint denial of the values of a function, and the joint denial of their negations. However, Soames (1983, 583ff) responded that Wittgenstein does not in his brief remarks purport to analyze quantification by supplying a notational system with definite syntax. Rather, the proposal purports merely to schematize the construction of one truth-condition from others. Thus, Fogelin's argument can be taken to show, unsurprisingly, that any particular instance of Wittgenstein's constructional schema must include a device for the identification of those subformulas whose semantic role is to present the totality of values of a propositional function. Geach and Soames conclude the debate by observing that the schema for construction of truth-conditions is satisfied by a notation tricked out with Principia-like scope indicators. Such a notation can be understood as an "intended model" of the schematic description. Thus, for example, within the model one might distinguish elements NNxfx and NxNfx as respectively truth-conditionally equivalent to the disjunction and conjunction of the collection of values of fx . Henceforth, I will simply work in such an intended model. In fact, I will assume that the model includes an image of a classical syntax of quantificational logic, in a signature which contains at least a few individual LOGIC IN THE TRACTATUS 7 constants and at least a few monadic and dyadic predicate letters. This assumption can actually be weakened in some philosophically interesting respects, but I will not explore the possibility here. We can now similarly explicate the notion of propositional function. Recall that a procedure of turning a constituent of a proposition into a variable is supposed to determine a function, which given some argument, returns a proposition. Without reference to any particular model of syntax, it is not at all clear just what could be meant by "constituent" (Bestandteil), let alone by turning one into a variable. But having assumed a classical syntax, then propositions may be identified with closed formulas. The notion of constituent may then be taken to include at least the individual constants which occur in the formula. Wittgenstein's construction by way of propositional variables and the N -operator establishes an interesting asymmetry between disjunctive and conjunctive truthoperations. The signs ∨ or ∃ of a disjunctive truth-operation can be disabbreviated trivially as NN . In contrast, conjunctive expressions can be disabbreviated only in the context of their occurrence with propositional variables. Fogelin has therefore correctly noted that in Wittgenstein's framework, the admissibility of conjunctive truth-operations entails nontrivial constraints on the class of propositional variables. Suppose, for example, that we simply added to first-order logic a one-off propositional variable whose range were the totality of elementary propositions. Given only the system's other resources, the disjunction but not the conjunction of its values could be expressed. Now about the system developed in §2, it does hold that conjunctions can be taken wherever disjunctions can, but must be proven (see Proposition 7 of §3.1). 1.1.2. Higher-order logic? One might wonder if the notion of constituent might not best be understood to include other syntactically related items as well, for example complex expressions constructible from a proposition by abstraction. Michael Potter, for example, writes: Take some sign expressing a proposition and single out part of the sign. Now keep this part fixed and let the rest of the sign vary. All the propositions that can be obtained by varying the sign in this way form a class. The variable used to pick out this class is called a propositional function, but Wittgenstein invariably refers to it simply as a function. (Potter, 2009, 269) Although Potter cites only 5.501 in the vicinity of this proposal, its strongest support may come from 3.315. According to the proposal, it is not a singled-out "part" which is initially allowed to vary, but rather "the rest" of a proposition. Potter does not actually say that the rest is a part at all, nor does he explicitly link his use of the term "part" directly to any usage in the text. But, since Wittgenstein only says that parts can be varied (or really: "turned into variables"), therefore Potter's gloss appears to presume that for any part of a proposition, the "rest" of the proposition besides it is also a part. However, in general, it is not the case that for any part of a given proposition, the rest of the proposition is a simple or elemental part. Thus, Potter would appear to understand the usage of Bestandteil to include parts or aspects of propositions which are other than simple parts. Both Ogden-Ramsey (Wittgenstein, 1922) and Pears-McGuiness (Wittgenstein, 1961) translate Bestandteil not as "part" but as "constituent". As with Bestandteil, 8 MAX WEISS one might say that a thing which has constituents is somehow formed by them in a naturally privileged way. For example, molecules are constituted by atoms. In contrast, a mere "part" of something can be understood as a result of projection or abstraction, as with the northern hemisphere of the earth. So, one might say that something which has constituents is already "articulated" in terms of them, for they are simple or elemental in contrast to it; on the other hand a decomposition into mere parts or segments in general requires choosing one path rather than another. Moreover, one might say that something depends on its constituents, but its mere parts-like the top half of the earth-conversely depend on it (Fine, 2010, 586). The heuristic metaphysics of Russell's ramified hierarchy of propositions provides an historically apposite example. Russell motivates the construction of the ramified hierarchy along an ordering of metaphysical dependence, if only as a convenient fiction. The ordering begins with the constitution of the universe by various objects and relations (Whitehead and Russell, 1913, 45); these objects and relations are the constituents of the earliest propositions (57ff). In contrast, a proposition can be seen to fall in the range of various propositional functions, these functions being obtained from the proposition by the abstraction, or "turning into variables" of constituents. Since propositional functions follow their values in the order of dependence, therefore propositional functions are not constituents of their values. This motivates the requirement in Russell that a propositional function cannot take itself as argument: the function depends on its values, the argument of the function which yields a value is a constituent of that value, and the value depends on its constituents. There are a couple of reasons to suppose that at 3.315 and elsewhere, by Bestandteil Wittgenstein doesn't just mean part, but part which is simple or elemental. The first is circumstantial. Wittgenstein himself accepted the rendering by OgdenRamsey of Bestandteil as "constituent". As I've just sketched, a usage of the latter term was already established by Russell in the exposition of the ramified theory of types. And in claiming at 3.333 that "the sign for a function already contains the prototype of its argument", Wittgenstein borrows a plank of that theory. The second reason is internal. Wittgenstein identifies what he refers to as Bestandteile with those expressions whose meaning is chosen, or determined by arbitrary convention. Thus, at 3.315 he says what might be turned into a variable are "those signs whose meaning is arbitrarily determined" (jene Zeichen, deren Bedeutung willkürlich bestimmt wurde), and indeed so determined "by arbitrary convention" (willkürlich Übereinkunft). In contrast, the meaning of expressions which are not Bestandteile is determined not by arbitrary convention but by their structure, given the choice of meanings for the Bestandteile. Thus, at 4.024 he says that to understand a sentence it suffices to understand its Bestandteile. And at 4.025 he remarks, heuristically, that in translation only the propositional-or perhaps here sentential-constituents (Satzbestandteile) are translated; presumably Satzbestandteil is supposed to pick out the sort of thing that is listed in a dictionary, and so is intended, without modification by any adjective like "simple", to evoke a contrast with expressions composed of several words. Now, at 4.025 Wittgenstein does mention Bindewörter-translated "conjunctions"-among the Satzbestandteile which are translated. But, this is because 4.025 really presents an heuristic analogy of the dependence on convention of propositions with the dependence on convention of unanalyzed sentences of English or German. Ultimately, there is only one essential respect in which the identity of a proposition must depend on a conventional LOGIC IN THE TRACTATUS 9 choice of meanings, and this is the assignment of meanings to names. Thus, at 4.5, Wittgenstein proposes to give a general description of symbols, such that everything satisfying the description can express a sense given only a suitable choice of meanings of names. And this matters philosophically, because it's by boiling down the choice of meaning to the choice of meanings of names that Wittgenstein works out what's announced as his "fundamental thought", that logical constants are not representatives (4.023). So, Bestandteile are the parts of a proposition whose meaning is chosen, or immediately fixed by convention. And the parts of a proposition whose meaning is chosen are precisely the names, i.e., the simple propositional constituents. But, at 3.315 Wittgenstein describes propositional functions as the results of turning into variables not mere parts, i.e., Teile, but Bestandteile, or constituents. Hence, the sort of thing which yields a propositional function upon being turned into a variable is a name. Now, it's true that some kind of higher-type quantification appears to be mentioned twice in the Tractatus (3.333 and 5.5261). The two mentions can both be glossed with multi-sorted first-order quantification, which entails no increase in logical complexity (Henkin, 1950). Still, Wittgenstein does leave room for some kind of higher-order generality. For, at 5.501, Wittgenstein introduces his three ways of presenting propositional multiplicities without clearly suggesting that the ways are exhaustive. In particular, predicative higher-order generality might be introduced through some fourth or fifth method of presentation of propositional multiplicities. However, the range of any such higher-order generality would be constrained by the requirement of wellfoundedness of logical evaluation. To see this, consider, for example, "Napoleon has all the properties of a great general." This sentence can be seen as predicating something, say B, of Napoleon; let's call the sentence B[n]. Now, further suppose that B[n] generalizes over everything predicable of Napoleon. Then, the truth-value of B[n] would be determined as the joint denial of each negation of a sentence C[X]→ X[n], for X anything predicable of Napoleon. So B itself falls in the range of X, and the determination of the truth-value of B[n] would depend on that very determination. In other words: the conception of generality as depending for its truth-value on those of its instances rules out higher-order quantification which is impredicative. So, while Wittgenstein's remarks do leave room for some kind of "higher-order" quantification, this would have to be interpreted predicatively. Precisely what expressive power Wittgenstein might've sought from such supplementations of the three stated methods of construction remains, to my knowledge, an open question in the literature. In sum, a cursory examination of the text suggests that the notion of turning a constituent into a variable is reasonably interpreted on the syntactical model of propositions as replacing a constant term a with a variable term x. Just as propositions become closed formulas, propositional functions are canonically explicated here as formulas containing at least one free variable. 1.1.3. Identity. This syntactical model of propositional functions suggests a natural account of their courses of values. We might identify the application of a propositional function with the instantiation of a formula. So the totality of values of a propositional function would become the class of closed instances of a formula, and an existential generalization becomes the disjunction of the elements of such a class. 10 MAX WEISS However, the reality is not quite so simple. As Hintikka (1956) and Wehmeier (op. cit.) have shown, Wittgenstein introduced a reinterpretation of the bound variable, which helps to sustain a contention that the equality predicate is dispensable. This reinterpretation, which I'll call the "sharp" as opposed to the "natural" reading, amounts to requiring that a bound variable omit from its range those objects which are mentioned in its scope. Thus, the result of replacing a free variable with an appropriately sorted constant in a formula is a value of the function if and only if the constant does not already occur in the formula. Or equivalently, a proposition is a value of a propositional function if and only if that function is the result of turning some constant into a variable in the proposition. This amendation yields a sharp divergence from classical first-order semantics. Hintikka and Wehmeier have shown, in a sense to be made precise, that every truth-condition of a formula of first-order logic with equality under the natural interpretation is the truth-condition of a formula of first-order logic without equality under the sharp interpretation. The translation of a naturally into a sharply read formula requires just two changes. Each existential quantification is disjoined with its omitted instances. And, each predication of equality is replaced with either a tautology or a contradiction containing the same constants and free variables, according as the two arguments of the predication, as linguistic expressions, are the same or distinct. The Hintikka-Wehmeier result certainly helps to justify Wittgenstein's claim that the equality predicate is dispensable. But the justification is not obviously complete, for as Rogers and Wehmeier (2012, 547) point out, the result has a seemingly important qualification: the sharp reading affords an equality-free rephrasing of truth-conditions only when the class of all structures is restricted to those in which no distinct constants codenote. So, the translations eliminate the equality predicate only if there is no nontrivial distinction to be drawn between structures according as they do or do not assign the same denotation to a given term. In response to this apparent difficulty, Rogers and Wehmeier (2012, 546) cite Wittgenstein's remark (5.526) that "the world can be completely described by means of completely generalized propositions". But this remark could be used to show that there don't need to be any simple predications of equality only by being taken to show that there don't need to be any elementary propositions. It's more likely that at 5.526 means just that there are some completely generalized propositions such that their truth leaves no further question how the world is. It doesn't follow that generalities could be susceptible to truth and falsehood independently of their instances. For example, waxing psychologistic Wittgenstein says "the understanding of general propositions depends palpably on that of the elementary propositions" (4.411). It's unlikely that 5.526 is an offhand remark that the truth-functionality thesis is optional. Rather, the purported elimination of the equality predicate would appear to require some independent justification for the claim that simple predications of equality do not distinguish between structures. Wittgenstein's position regarding the equality predicate cannot be just that the equality predicate is, like disjunction, not primitive, for its purported uses are not all accommodated. But nor does Wittgenstein hold that the conventions governing the sign underwrite no symbols at all; one might express by their means a proposition to the effect that there are at least two authors of Principia Mathematica. The position is rather that the conventions do not suit the logicosyntactic role of a predicate. LOGIC IN THE TRACTATUS 11 Specifically, the basic function of an equality predicate would have to be, completed with some other occurrences of terms, to yield a proposition which is true iff those terms denote the same object. But, claims Wittgenstein, there is no such function: what would fulfill such a purported function must be either nonsensical or empty (5.5303). I suggest that the situation should be understood like this. Wittgenstein derived his notion of proposition from early Russell, for whom at the end of analysis each object has only one representative, which is that very object. Then for anything at all, there is only one true proposition to the effect that it is the same as a given object, namely the proposition that the thing is the same as itself. And as Russell remarked: "when any term is given, the assertion of its identity with itself, though true, is perfectly futile" (Russell, 1903, 65). Famously, he proceeded in "On Denoting" (1905) to explain the value of apparent statements of identity on the ground that they aren't identities after all. The hypothesis that each object has one and only one representative reduces the truth or falsehood of simple predications of equality to their own mere identity as propositions, making it plausible that they draw no genuine distinctions between structures. Now, the Russellian conception of propositions also makes it intelligible to suppose that "the specification of all true elementary propositions describes the world completely" (4.26), even if there are no elementary predications of equality. For example, if it is given that there are just two elementary propositions, that Lisa and Lucy are cats on the mat, then since the propositions themselves contain cats, the specification that both are true determines that there are two cats on the mat. If, on the other hand, the propositions instead contained proxies not in one-one correspondence with the objects, then knowing the truth-values of elementary propositions would leave open the question of how crowded the mat is. For Wittgenstein maintains that two objects might have all their properties in common (5.5302). But as is well known, Wittgenstein did pull away from the Russellian conception. On the one hand he maintained that the proposition must by itself determine how things must stand if it is true. Furthermore, he supposed that this could be the case only if the way constituents stand to each other in the proposition were the same as the way that objects are thereby said to stand. Yet if the constituents of the proposition just are what is mentioned, it follows that every proposition is true. In the Tractatus, Russellian objectual propositional constituents must therefore give way to proxies. Surely there is no initial plausibility to the suggestion that each object has one and only one representative, though things do not self-represent. But Wittgenstein fully imbibed the doctrine that the world is completely determined by the truth and falsehood of elementary propositions. So even as objects do not represent themselves, propositions retain a role in Wittgenstein's logical thinking which requires that each object has one and only one representative. Or as Russell himself put it: "there will be one word and no more for every simple object" (Russell, 1918, 198). In summary, then, a simple predication of equality could distinguish between structures only if it has both possibilities of truth and falsehood. But it can't have both possibilities, if denotation essentially puts names and objects in one-one correspondence. Yet only if names and objects are in one-one correspondence could a proposition be a truth-function of elementary propositions. On pain of 12 MAX WEISS breaking the truth-functionality thesis, Wittgenstein must hold in the Tractatus that there is no room for the equality predicate to distinguish nontrivially between structures. In this way, the proviso on the Hintikka-Wehmeier result is discharged. In the context of the Wittgenstein's other commitments, these authors have indeed justified Wittgenstein's claim to have recovered what could count as the genuine expressive contribution of the equality predicate. 1.1.4. The Russellian constraint and the fixed-domain conception. On the strength of the arguments of Geach, early Soames, and Wehmeier, we can conclude that Wittgenstein manages to accommodate the basic notions of first-order logic. But as we've seen, the accommodation induces four eccentricities. First, Wittgenstein rejects the equality predicate. Second, he recaptures some lost expressiveness by stipulating that a variable omits from its range what is mentioned in its scope. Third, he maintains that no further first-order expressiveness remains uncaptured, by stipulating that no two constants codenote. Finally, the analysis of quantified propositions as truth-functions requires that every element of the domain is denoted by a constant. The point of this paper is to develop a complexity-theoretic analysis of Wittgenstein's logical system. From this point of view, the work of earlier interpreters licenses abstraction from the first two eccentricities. For the translations of Hintikka and Wehmeier establish that the consequence relations determined by the sharp and natural semantics of first-order formulas are mutually Turing-reducible. It is not straightforward to extend these translations to the outer reaches of Wittgenstein's system; but enough will be clear for present purposes. The second pair of eccentricities reflects Wittgenstein's conception of the relationship between names and the universe, which differs in two fundamental respects from the classical model-theoretic treatment of the relationship between constants and the domain of a structure. The argument that the equality predicate is dispensable requires that simple statements of equality draw no nontrivial distinctions in the class of all structures, and hence that there is no structure in which distinct constants codenote. The proposal to analyze an existentially generalized proposition as the disjunction of the values of a propositional function is extensionally adequate only to structures in which each element of the domain is denoted by a constant. Together these requirements are equivalent to what I'll call a "Russellian" constraint on structures, that the denotation relation be a one-one correspondence between the class of names and the domain. The reason for the terminology is simply that the constraint is canonically satisfied by a structure such that every element of its domain is the one and only name of itself. Of course, the terminology isn't intended to convey any characterization of Russell himself. Rather, it's intended to mark Russell's deep effect on Wittgenstein. We've seen that the Russellian constraint is well-rooted in the Tractatus, namely in the doctrine that a proposition is a truth-function of elementary propositions. To say that a proposition is a truth-function of some others is to say that, logically, its truth-value is a function of theirs, so that any maximal consistent choice of elementary propositions and their negations entails either the proposition or its negation. But this claim has counterexamples if distinct constants codenote, and has counterexamples if not all elements of a domain must be denoted by constants. Hence the truth-functionality thesis evidently presupposes the Russellian constraint. LOGIC IN THE TRACTATUS 13 It might be wondered whether the truth-functionality thesis somehow obfuscates the very notion of a quantifier. Doesn't it just turn a universal generalization into a "big conjunction"? However, the truth-functionality thesis follows from the Russellian constraint. And the Russellian constraint is only a restriction on the class of all structures. Hence, the truth-functionality thesis cannot by itself entail any substantive change in the theory of truth-conditions. It modifies only the universe of relata to which that theory might be applied, namely the universe of structures. So, the truth-functionality thesis does not affect the meaning of quantifiers, if the meaning of quantifiers depends only on their role in fixing truth-conditions. On the other hand, the truth-functionality thesis does modify the notion of consequence, which Wittgenstein seems to give a protomodel-theoretic analysis (5.12). Say that an elementary truth-possibility is a maximal consistent set of elementary propositions and negations thereof, and that the truth-grounds of a proposition are the elementary truth-possibilities which entail it. Then a proposition is a consequence of some others iff all their common truth-grounds are truth-grounds of it. By the Russellian constraint, every truth-ground common to all instances of a universal generalization is a truth-ground of the generalization. So the generalization is a logical consequence of the class of its instances. Thus, the truth-functionality thesis does modify the meaning of quantifiers if their meaning is taken to depend essentially on their role in constituting the consequence relation. However, a defender of the Russellian constraint might respond that the role of subsentential expressions in constituting the consequence relation is exhausted by their contribution to truthconditions. Thus, the charge that truth-functionality obfuscates the quantifiers depends on a controvertible philosophical presumption. Wittgenstein's analysis of the consequence relation resembles that of Tarski (1936). The similarity is not just that both analyses generalize over something like logically possible distributions of truth and falsehood. For Tarski seems furthermore to have defined the consequence relation under a "fixed-domain" conception of structure, according to which they all have the same domain in common (Bays, 2001). The fixed-domain conception and the Russellian constraint are closely related, for they both require that the domains of all structures have the same cardinality. However, the fixed-domain conception of structure is not as strong. For it implies neither that every object be denoted by a constant, nor that no constants codenote. The two conceptions differ significantly in their effects on the complexity of logic. As with Russellian consequence, the complexity of fixed-domain consequence depends on whether the domain is infinite. In case the domain is finite, the fixeddomain and Russellian notions pretty much coincide. But suppose that the domain D is infinite, and consider the corresponding notion of fixed-domain consequence for a countable signature. Let I be the set of formulas to the effect that there are at least n objects for each n. Since D is infinite, A must be a fixed-domain consequence of T if A is a classical consequence of T ∪ I. Conversely, suppose that some classical structure satisfies T ∪ I but not A. Since the signature is countable and D is infinite, the Lowenheim-Skolem theorems imply that some structure with domain D satisfies T but not A. Therefore, if the signature is countable, then the fixed-domain consequences of T are precisely the classical consequences of T ∪ I. So fixed-domain consequence is recursively enumerable on any infinite domain. In contrast, we'll see in §2.2 and §4.3 that Russellian consequence permits categorical axiomatizations of rich countable structures. On no infinite domain is Russellian consequence even 14 MAX WEISS arithmetically definable, at least if the signature contains a dyadic predicate. Finally, it should be noted that a fixed-domain theorist can follow normal mathematical practice in taking uncountable structures to have a countable signature. So the fixed-domain theorist can generally avoid difficulties associated with uncountable signatures. 1.2. Formal generality. We have now considered two of the three methods of presenting propositional multiplicities which Wittgenstein sketches at 5.501. I've indicated how they can together be understood to yield something like the expressive resources of first-order logic, but also argued that this understanding must inflect the underlying proto-model-theoretic analyses of validity and consequence. Let's now turn to the third method, which Wittgenstein describes as "giving a formal law" according to which the presented sentences are constructed. The sentences so presented constitute the terms of what he calls a "form-series". Series which are ordered by internal relations I call formal series. The series of numbers is ordered not by an external relation, but by an internal relation. Similarly the series of propositions aRb, ( Ex) : aRx . xRb, ( Ex, y) :aRx . xRy . yRb, etc. (4.1252) The general term of the formal series a,O'a,O'O'a, . . . I write like so: "Ja, x,O'xK". This expression in brackets is a variable. The first term of the bracket expression is the beginning of a formal series, the second the form of an arbitrary term x of the series, and the third the form of that term of the series which immediately follows x. (5.2522) As Geach (1981, 171) observed, Wittgenstein here announces an intention, by means of a so-called formal series, to construct an expression of the ancestral. Frege's analysis of the ancestral required second-order quantification, indeed impredicatively. In contrast, Wittgenstein begins with the natural idea of constructing the countably infinite disjunction of all propositions to the effect that b is connected to a by R through this or that number of steps. However, he then proposes a notation-the third kind of bracket-expression-by means of which a series of disjuncts would be presented in finite space. The ancestral would be expressed by the negation of the joint denial of the sentences which the bracket expression presents. So, the form-series variable extends first-order logic to include the simulated presence of some countably infinite disjunctions. Clearly, not every countably infinite set of formulas will correspond to some such simulated disjunction, for the disjuncts must be generated by means of what Wittgenstein calls an "operation". In turn, an operation should return some sentence B when applied to a sentence A only in virtue of some "internal relation" which B bears to A. Sundholm (1992, 61) points out that the apostrophe in Wittgenstein's notation O'a apparently borrows from the description in Principia of the object to which a bears the relation O. Thus, the question what counts as an operation reduces to the question which relations are "internal". Wittgenstein's handling of technical matters is not widely celebrated for its precision. But the remarks about quantifiers borrow some clarity from Russell and Frege. And of course quantifiers became a standard part of the logical education of philosophers. On the other hand, the origins of the concept of operation are obscure, and corresponding extensions of quantificational logic never got much traction. LOGIC IN THE TRACTATUS 15 What is widely acknowledged is that the form-series device is supposed to yield an analysis of the ancestral in terms of an idea of iterated operation. There are few published attempts to propose any general comprehension principles for operations to do the job. Geach (1981, 170) suggests "the notation [aRb, aSb, aR/Sb] gives us the series of propositions aRb, aR/Rb, aR/(R/R)b etc. ad inf.. . . ." Here, an expression like aR/Rb is presumably supposed to abbreviate an ordinary first-order formula. However, the disabbreviation for nonelementarily expressed relations is left obscure; and the proposal makes the concept of operation seem tailored to a particular one of what are presumably various possible uses. In a similar vein, Potter (2009, 272) writes: "the formal series [of 4.1252] is expressed by the variable [ aRb, aχb, (∃x) :aRx . xχb ]". The grounds of this declaration aren't made explicit: it's not clear why, for example, the third term of the series of indicated propositions shouldn't be something like (∃x) :aRx . (∃x) :xRx . xRb. The notation proposed by Potter appears to indicate what's intended only granted an understanding of what the whole thing is supposed to mean. So the proposal runs afoul of Wittgenstein's complaint about Russell, that "he had to mention the meaning of signs when establishing the rules for them" (3.331). Of course, Wittgenstein himself never established those rules clearly. But as I've urged, the question whether anything could realize the conception of logic in the Tractatus can't be answered without going beyond what Wittgenstein actually did. For better or for worse, the job is ours to make something clear. There has also been disagreement about what should count as an operation and what shouldn't. For example, Sullivan (2004) contends that no internal relation distinguishes nontrivially between names, or-though this terminology is neither Sullivan's nor Wittgenstein's-that internal relations are "permutation-invariant" (see also Sundholm, 1992, 69). In contrast, Ricketts (2012) conjectures that form-series disjunctions might serve to simulate predicative higher-order existential generalization. Textual issues aside, the proposal would require enumerating the class of formulas A[a], A[b], . . . for all names a, b, . . ., by means of logically insignificant features like spelling. However, it is reasonable to assume that the class of operations should be closed under composition. But then supposing O to enumerate the names as in Ricketts' proposal, the result of composing O once with itself would enumerate, as it were, "every other name". It may then so happen to turn out that in the actual world, the thereby enumerated names would denote just those objects which are spacetime points interior to Russell's left hand. In another language, differing only in what would seem to be a logically insignificant manner, the probability would be zero that Russell's left hand is definable, but his nose might be definable instead. Ricketts' proposal implies that languages which differ over logically insignificant features are not intertranslatable. Textual evidence suggests that Wittgenstein does countenance a formal enumeration of names in the Notebooks (e.g., 23.11.16d). But such suggestions largely disappear in the Tractatus. Disagreements about the precise extent of the concept of operation may need to be resolved on systematic grounds, which I leave to further work. In this paper's formal development, I will adopt a fairly strict policy: operations will be invariant under permutations of all names except those which occur as parameters in the operator-sign. The key mathematical results depend only on operations which are fully permutation invariant. 16 MAX WEISS 1.2.1. Motivations for form-series. Textual evidence suggests that two motives drove Wittgenstein to supplement the logic of objectual generality and truth-functions with formal series. Wittgenstein seems to have postulated quite early the presence of some propositional structure which shares the necessities inherent in a fact. The postulation gets expressed in a remark, at 4.023, that thanks to some "logical scaffolding", a person can "see" how things must be if a proposition is true. An example from the Notebooks of this sort of visibility might be the following: For example, perhaps we assert of a patch in our visual field that it is to the right of a line, and we assume that every patch in our visual field is infinitely complex. Then if we say that a point in that patch is to the right of the line, this proposition follows from the previous one, and if there are infinitely many points in the patch then infinitely many propositions of different content follow LOGICALLY from that first one. And this of itself shews that the proposition itself was as a matter of fact infinitely complex. That is, not the propositional sign by itself, but it together with its syntactical application.(Wittgenstein, 1979, 18.6.15g) A year earlier, Wittgenstein had identified a similar complexity in the fact that a chair is brown, and sketched a formal series of propositions which would reproduce it (1979, 19.9.14, pp. 5 and 134). The second motivation for the form-series device stems from problem of giving the general propositional form. Although the problem is mentioned already in the 1914 notes of Moore (1979, 113) it is not until April 1916 that there appears a sketch of Wittgenstein's eventual approach: "suppose that all simple propositions were given me: then it can simply be asked what propositions I can construct from them. And these are all propositions and this is how they given" (16.4.16; cf. T4.51). So, the notion of form-series here finds a second use, in an account of the way in which propositions are constructed by elementary propositions through repeated application of a formal procedure. As Avron (2003) argues, this technical task provides a natural motivation for adding to first-order logic a device to express the ancestral. Goldfarb (2012) speculates that it was a conviction that logic must comprehend the grounds of people's understanding of logic, and particularly the underpinnings of recognition of formulas and proofs, which sustained in Wittgenstein the view that induction is logical. The two roles of formal series in the pre-Tractatus manuscripts lead to two roles in the Tractatus. On the one hand, T4.1252, T5.252 and T5.501 invoke and explain an "immanent" use of formal series in articulating the structure of facts; paradigmatic of such use is the expression of the ancestral. On the other hand, a "transcendent" use at T6 purportedly fulfills the promise of 4.51 to say how all propositions can be constructed from certain simple ones. Sundholm (1992, 66) remarks of the transcendent use that it is at least superficially more complicated than the immanent one: it acts on a higher-order relation which takes as one argument not a single item but a potentially infinite multiplicity. In consequence, the use of a form-series variable to specify the totality of propositions flirts with impredicativity (Sundholm, 1992, 70). Why couldn't that variable be used to specify the basis of a truth-operation? Here it may help to note a textual detail. The Prototractatus (Wittgenstein, 1971) antecedent of the explanation in the T5.252s addresses not the simpler, immanently LOGIC IN THE TRACTATUS 17 admitted form but the higher-order form instead. So, in deriving the Tractatus from this earlier draft, Wittgenstein restricted his explanation of formal series to the immanent use. This clearly deliberate reversal suggests that Wittgenstein eventually decided to admit only the lower-level form under constructional procedures described at T6 by a use of the higher-level form. The separation of "immanent" and "transcendent" form-series variables introduces a couple of potential responses to the problem about impredicativity raised by Sundholm. First, it might be proposed that there is some fixed type to which all meaningful uses of the form-series device must conform, while allowing that the expression at T6 does not conform to that type. To this proposal, it might be objected that once a system of propositional construction has become surveyable by means of a definite, though higher-level form-series variable, the higher-level expression should itself become susceptible to significant use in a yet broader collection of sentences. On this second proposal, any characterization of a system of propositions would yield eo ipso a further method of propositional construction, which the whole would still transcend. In that case, the general form of the truthfunction given at T6 would be understood as in some sense open-ended (cf. Floyd, 2001). A difficulty for this proposal is that Wittgenstein repeatedly attempts to justify the postulation of a general propositional form precisely on the grounds that every possible form of a proposition must be foreseeable (4.5c; see also Wittgenstein (1979, 21.11.16)). Developing the open-endedness proposal would require clarifying Wittgenstein's notion of foreseeability. 1.2.2. Toward an explication. Luckily, the goals of this paper do not extend to explicating the general propositional form in detail. But the above gloss would license one helpful assumption, that the form-series method mentioned at 5.501 isn't intended to handle the apparently more complicated induction of T6. Rather, following the 5.2522s, we might naturally consider only form-series variables constructed from unary operations. However, even the notion of unary operation is of course still unclear, and no purportedly exhaustive reconstruction could be uncontroversial. For several reasons I will take a minimalist approach to the positing of operations. First, the goal of the paper is to establish lower bounds on the complexity of the system, not upper bounds. Second, it is nice to see how much can be got from how little. Third, details of implementation do not just take care of themselves, but become complicated quickly (see §2.3, particularly Lemma 4). The minimal analysis of operation I propose to investigate is roughly this. An operation is presented by a schematic letter together with a formula; the presented operation returns the result of substituting the operand for the letter in the presenting formula. A bit more concretely, suppose that ξ 7→ Ω(ξ) is a procedure which, applied to a formula, returns another formula. Then in something like Wittgenstein's notation, JA, ξ,Ω(ξ)K would signify the series of formulas A,Ω(A),Ω(Ω(A)) . . . . 18 MAX WEISS Now, consider a first-order formula B which is ordinary except in that someplace where an atomic formula might have occurred, there occurs instead a schematic letter p. This can be supposed to determine, with respect to p, a function (1) ξ 7→ B[p/ξ] which, applied to the formula A, returns the result B[p/A] of replacing each occurrence of p in B with A. In turn, the notation (2) JA, ξ,B[p/ξ]K can be understood to signify the series of formulas A,B[p/A], B[p/B[p/A]], . . . . Of course, there are many other reasonable notions of operation besides those of the form of (1). But I'll consider just these. This justifies a notational economy: instead of (2) I'll just write JA, p,BK. As we'll see in §3, this ostensibly weak reconstruction suffices to express all notions which can be defined by induction, including in particular the ancestral. There will actually be various ways of doing it, but they'll all have in common that they contain only finitely many variables. Thus, it's clear that they don't express the ancestral in quite the way that Wittgenstein envisaged at 4.1252. And more generally, it is certainly not the case that every formal procedure hazarded by Wittgenstein has the form A 7→ B[p/A]. Conversely, however, it is plausible that everything of that form should count as a formal procedure. On the present reconstruction, the form-series device does not simulate the occurrence of infinitely many variables in a formula. The form-series Wittgenstein gives at 4.1252 to express the ancestral does use infinitely many variables, though of course inessentially. One might take this to license essential uses too. A familiar concept which might then become expressible is the quantifier "there are infinitely many". The interpretive grounds for such a strengthened line of reconstruction should be supplemented with some systematic considerations. Wittgenstein does say that number is a "formal" concept (4.1272); perhaps then "there are infinitely many" ought to be a logically definable. However, by Wittgenstein's lights a concept's being formal doesn't imply that it's definable at all. For example, identity is supposed to be a formal concept but is not definable (see §1.1.3). Although the logicality of an infinity quantifier doesn't seem to be precluded by the text, the quantifier is not logically definable by induction, yet induction handles all the envisaged applications of the form-series device for which there is textual evidence. 1.2.3. Programmatic background. Let me conclude this section by sketching some interpretive context for the two logical eccentricities to be investigated in this paper- the restriction to Russellian structures and the addition of the form-series device. In the preface to the book Wittgenstein promises to solve philosophical problems by clarifying the nature of logic. A superficial survey indicates that the centrally organizing task of the book is to give a general propositional form, a purported common nature of whatever can be said or thought. It is not clear at first blush how such a task could itself complete the understanding of logic which is needed for the solution to philosophical problems. In the Tractatus, the purported general propositional form gets presented twice. At first, Wittgenstein keeps it short: LOGIC IN THE TRACTATUS 19 [. . . ] The general propositional form is: es verhält sich so und so. (4.5c) It's not at all clear how this could be a philosophical cure-all. In fact there is more to consider: A proposition constructs a world with the help of a logical scaffolding, so that one can actually see from the proposition how everything stands logically if it is true. (T4.023e) Such scaffolding may be supposed to constitute the sort of logic whose misunderstanding is the purported source of philosophical problems. If that's right, the solution to philosophical problems might be seen to require attention to the nature of those manipulations of signs through which signs come to have sense: that is, to lay out the pieces of scaffolding clearly. Wittgenstein announces such a consideration of details at T5, which leads at T6 to a refinement of the general propositional form: A proposition is a truth-function of elementary propositions. (T5) The general form of the truth-function is [p, ξ,N '(ξ)]. That is the general form of the proposition. (T6) So, Wittgenstein's promised solution to philosophical problems would appear to depend, at least in part, on the progress from T4.5 to T6. In particular, the progress is supposed to clarify just how it could be of necessity that if some propositions are true, then some other propositions are true as well. Accordingly, possibilities reappear as distributions of truth-value over propositions. And a fundamental problem of logic becomes to clarify how the structure of propositions constrains what distributions of truth and falsehood are possible for them. As we'll see, the program leads to a realization of logic whose complexity turns on the number of objects that exist. In particular, if the number of objects might be uncountably infinite, then the complexity of the resulting notion of tautology seems to rule out any reasonable sense in which, after all, logical validity or logical consequence could be a mere matter of propositional structure. Under the assumption that validity and consequence can depend only on propositional structure, the significance of the main results of this paper can be stated as follows: it is only if the universe is countable that the conception of logic in the Tractatus might be coherent. 2. Framework We've now seen that Wittgenstein's conception of logic differs from the classical understanding of first-order logic in at least the following two ways. First, the notion of structure is subjected to a Russellian constraint, so that the elements of its domain are in one-one correspondence with the constants of its signature. Second, the logical vocabulary contains a device for the expression in finite space of countably infinite disjunctions. In this section, I'll assemble a framework for studying those features. After sketching in §2.1 a suitable variant L of first-order logic, I'll show in §2.2 that the Russellian constraint yields an interpretation of some familiar slogans from the Tractatus. In §2.3, I'll show that L can be extended to a system LF which implements an analysis of Wittgenstein's form-series device. But first some common background. A signature S consists, for all k, of a set of k-place predicates and a set of k-place function symbols. I will say that a signature R is Russellian provided that R contains 20 MAX WEISS at least one predicate and at least one function symbol, but no function symbol of arity greater than zero. Function symbols of arity zero are also known as constants. A structure M for S consists of a nonempty set, its domain D, plus a mapping which takes k-place function symbols and k-place predicates to k-ary functions and k-ary relations on D. Let R be a Russellian signature. I will say that a structure M for R is Russellian, or is a D-structure, if it meets the following further conditions: • every constant of R is its own image under M, and • every element of D is the image of a constant. The convention that constants denote themselves is purely for notational convenience, and all subsequent results will extend transparently to the general situation in the Tractatus where denotation is any bijection between the constants and the domain. Finally, a logic maps a signature to the collection of classes of its structures. Typically the mapping is determined in two steps. First a syntax generates from the signature a class of formulas. Then a semantics associates with a formula the class of structures in which it is true. Let's now see how this works for L and LF. 2.1. The system L. As indicated in §1.1, the system of the Tractatus can be understood as including a variant of first-order logic. I'll refer to this variant as L. Let me begin by rehearsing its mostly familiar construction. Given a Russellian signature, first-order logic determines a language like this. There is a set of individual variables x, y, . . . , x0, y0, . . ., which, given the function symbols of S, determines the class of terms of the language. Second, the class of L-formulas is given by an induction with just these clauses: • R~t is a formula if R is a k-ary predicate and ~t is a list of terms of length k • t = u is a formula if t, u are terms • ¬A, (A ∨B), and ∃xA are formulas whenever A,B are formulas and x is a variable. I will refer to formulas so generated as the proper formulas of L. It will be useful to have extended L with a category of schematic letters, p, q, r, p1, . . ., adding the inductive clause • every schematic letter is a formula. Improper formulas will not be assigned semantic values directly. Rather, they support the implementation of the form-series device in LF (see §2.3). Just to fix notation, here are some fairly standard niceties. Free, bound, and binding occurrences of a variable should be taken in the usual way. I'll write A[x/t] for the result of replacing each free occurrence of x in A with the term t, unless this replacement introduces new bound occurrences. Vectors over terms for expressions indicate finite sequences of expressions of the indicated type. Then A[~x/~t] signifies the result of simultaneously substituting each element of the sequence ~t for the corresponding element of the sequence ~x, relettering variables bound in A where necessary. Finally, A[~a] abbreviates A[~x/~a] where ~x is the canonically ordered sequence of all variables occurring free in A. The definition of truth for L is straightforward. I will specialize for the notion of Russellian structure the approach of Shoenfield (1967). Let R be a Russellian signature with D its class of constants, and let M be a D-structure for R. Now suppose that A is a proper closed formula of L. The atomic, equality, and truthfunctional cases are handled as usual. But suppose that A is ∃xB. In this case we stipulate that LOGIC IN THE TRACTATUS 21 • M |= ∃xB iff M |= B[a] for some a in D. 2.2. Effects of the Russellian constraint. The specialization to Russellian structures has deep effects on the notions of validity and consequence, which are nonetheless defined in a familiar-looking way. Definition 1. Let R be a Russellian signature with domain D. A proper closed formula A over the signature R is D-valid if M |= A for all D-structures M for R. Likewise, A is a D-consequence of the set X of proper closed formulas, or X ⇒D A, provided that there is no D-structure M for R such that M 6|= A while M |= B for all B in X. With the notion of D-consequence in hand, we can begin to interpret some basic slogans of the Tractatus. According to 4.26, "the world" is supposed to be completely described by specifying which elementary propositions are true and which false. Say that the diagram ∆(M) of a structure consists of the atomic sentences true in M, plus the negations of the atomic sentences false in M. The remark of 4.26 now becomes that a structure is axiomatized up to identity by its diagram. Proposition 1. Let M and M′ be D-structures. If M′ |= ∆(M), then M′ = M. Proof. Since M and M′ are both D-structures, they have the same domain. So suppose R is an R-predicate. Then (~a) ∈ RM iff R~a ∈ ∆(M), and R~a ∈ ∆(M) iff (~a) ∈ RM′ .  Note that if the notion of D-structure is relaxed so as to require only that denotation of constants be a bijection, then diagrams axiomatize structures only up to isomorphism. Subsequent results don't depend on this difference. When every structure is axiomatized by its diagram, consequence becomes a generalization of truth. Or in other words, truth is what follows from a diagram. Proposition 2. Let M be a D-structure. Then M |= A iff ∆(M)⇒D A. Proof. Since M |= ∆(M), therefore ∆(M) 6⇒D A if M 6|= A. Conversely, suppose M |= A. By Proposition 1, if M′ |= ∆(M), then M′ = M, so M′ |= A. Hence ∆(M)⇒D A.  Proposition 2 records a radical departure from the classical concept of consequence: for Wittgenstein, the concept of consequence embeds the concept of truth. See Martin-Löf (1996) for discussion of this approach. Of course, it is the left-to-right direction of Proposition 2 which does not hold for the classical or fixed-domain consequence relations. Another slogan of the Tractatus is that a proposition is a "truth-function" of elementary propositions. In the present framework, this slogan becomes that each sentence or its negation is a Russellian consequence of the diagram of a structure. Proposition 3. ∆(M)⇒D A iff ∆(M) 6⇒D ¬A. Proof. Of course M |= A iff M 6|= ¬A. But by Proposition 2, ∆(M) ⇒D A iff M |= A, and M 6|= ¬A iff ∆(M) 6⇒D ¬A.  Consider, for example, the concept of arithmetical truth. Let R be a Russellian signature with a couple of three-place predicates, while the set D of constants of R is countably infinite. Now, let N be a D-structure for R which is isomorphic to the structure of the natural numbers under the ternary relations of sum and product. 22 MAX WEISS Proposition 4. Under the D-consequence relation, the set ∆(N) axiomatizes N up to identity. Thus, the set of arithmetical truths is decidable relative to the set of D-consequences of ∆(N). Proof. Immediate from Propositions 1 and 2.  Of course, there's nothing special about the structure N in this context; Proposition 4 holds for any structure whatsoever. 2.3. The system LF. In §1.2, I argued that Wittgenstein envisions logic also to include a method of expressing some countably infinite disjunctions, though in finite space. Let's now develop an extension LF of L, which implements this idea. The goal is to become able to express a disjunction whose disjuncts are the results of applying repeatedly some finitely presented "operation". We will pursue the proposal of §1.2.2, to consider only operations of substituting the operand for a schematic letter in a formula. 2.3.1. LF-syntax. The rules for building formulas of LF are precisely those of L, plus just one more: • ∨ JA, p,BK is an LF-formula provided that A is an LF-formula and B is an L-formula. Let's call the indicated occurrence of p a binding occurrence of p; its scope will be said to be the formula B. An occurrence of p is bound iff it falls in the scope of a binding occurrence of p. I'll say that a formula of LF is proper iff it contains no free occurrence of a schematic letter. Note that an improper formula B may be a subformula of a proper formula iff B is actually a formula of L. Improper formulas which don't belong to L remain only for theoretical convenience. It will be just the proper closed formulas which receive a truth-value in a structure. 2.3.2. LF-operations. A formula ∨ JA, p,BK is to become understood as a disjunction. Its terms are to be the results of repeatedly applying the operation presented by p,B to the initial formula A. The pair p,B presents the operation which substitutes the operand for each occurrence of p in B. To spell this out, let's fix some notation. Definition 2. (i) The formula B[p/A] is the result of substituting A for every free occurrence of p in B. (ii) If C = ∨ JA, p,BK, then write C0 = A and Ci+1 = B[p/Ci]. Regarding clause (i), note that operator-signs contain no bound schematic letters, so the qualifier "free" isn't necessary for intepreting form-series formulas. But it will be useful to have the more general concept of substitution on hand throughout. The clause (ii) begins to spell out how form-series disjunctions present a series of disjuncts. I will sometimes write JA, p,BKk for ( ∨ JA, p,BK)k. An alternative characterization of iterated substitution will become useful shortly, in proving the fundamental Lemma 4. Write [p/B]k for k successive applications of the substitution [p/B]. Lemma 1. Let ∨ JA, p,BK be a formula of LF. Then JA, p,BKk = p[p/B]k[p/A]. LOGIC IN THE TRACTATUS 23 Proof. Let's use induction on k. The result is clear for k = 0. So suppose it to hold for k. Then JA, p,BKk+1 = B[p/JA, p,BKk] = B[p/p[p/B]k[p/A]] = B[p/p[p/B]k][p/A] = B[p/B]k[p/A] = p[p/B]k+1[p/A].  Before proceeding to the semantics, let's consider a nontrivial application of the form-series device. Let R be a dyadic predicate. The ancestral of the relation expressed by R can be expressed by an infinite disjunction of a series of formulas like Rxy ∃z0(Rxz0 ∧Rz0y) ∃z1(∃z0(Rxz0 ∧Rz0z1) ∧Rz1y) ∃z2(∃z1(∃z0(Rxz0 ∧Rz0z1) ∧Rz1z2) ∧Rz2y) ... These formulas altogether contain infinitely many variables z0, z1, . . ., and so they can't be generated merely by an operation of the sort postulated here. But, each quantifier ∃zk+2 doesn't bind any variable in the scope of ∃zk. So the indices should be recyclable by some trick or other. For example, write A0, A1, . . . for the first, second, . . . terms of the series Rxy ∃z(Rxz ∧Rzy) ∃z(∃y(Rxy ∧Ryz) ∧Rzy) ∃z(∃y(∃z(Rxz ∧Rzy) ∧Ryz) ∧Rzy) ... Let B = ∃z(∃y(p ∧Ryz) ∧Rzy). Then A2k = p[p/B] k[p/A0], and A2k+1 = p[p/B] k[p/A1] for all k < ω. So by Lemma 1, the disjuncts Ai of an expression of an ancestral are precisely the 'disjuncts' of(∨ JA0, p, BK ) ∨ (∨ JA1, p, BK ) . Of course, I have not yet said what it is for a formula of LF to express something. Let's fix that. 2.3.3. LF-semantics. Developing a semantics for LF will take a little more effort. To construct a definition of truth it is tempting simply to extend the classical definition directly, evaluating bound variables by assignment or instantiation. Unfortunately, this does not work. The reason is that, roughly speaking, we would like form-series 24 MAX WEISS formulas to behave like countably infinite disjunctions-but that's not what they are. To see the difficulty, note that the substitution of terms does not commute with the expansion of form-series formulas into their infinitary counterparts. Consider, for example, a formula A = ∨ JFx, p,∃x(Gx ∧ p)K. Applying directly the usual notion of substitution of terms would yield A[x/a] = ∨ JFa, p,∃x(Gx ∧ p)K, and so, for example, A[x/a]1 = ∃x(Gx ∧ Fa). On the other hand, A1 = ∃x(Gx ∧ Fx), and so A1[x/a] = ∃x(Gx ∧ Fx). Of course, quantification doesn't quite require the good behavior of substitution, but here the mischief is deeper: the introduction of form-series into first-order logic disrupts the expected notion of free occurrence of a variable. To solve this problem, let's play a trick: run two stages of evaluation. First expand form-series variables into the formal series they present, and only then evaluate the quantifiers. Formulas of LF thus get expanded into an infinitary extension of first-order logic LF. This results by adding, to the formation rules of L, the clause • ∨ k<ω Ak is a formula if each Ak is a formula, and to the evaluation rules of L the corresponding clause • M |= ∨ k<ω Ak iff M |= Ak for some k < ω. As with L, I'll say that a formula of LF is proper if it contains no schematic letters. We want to define recursively a mapping * * * which expands a formula of LF into some corresponding formula of LF. To justify the recursion we need a further idea. Definition 3. The level of a formula A of LF is the pair (iA, jA), where • iA = 0, if A is atomic or schematic; iA = iB + 1 if A = ∨ JB, p, CK, and otherwise iA is the maximum of the iB for all immediate subformulas B of A; • jA = 0 if A is atomic or schematic, and otherwise jA = k + 1, where k is the maximum of the jB for B an immediate subformula of A. The level of A is lower than the level of B iff either iA < iB or iA = iB and jA < jB. The ordering of levels is clearly wellfounded. Unlike ordinary syntactical complexity, it fulfils the following useful condition. Lemma 2. Suppose that C = ∨ JA, p,BK is a formula of LF. Then Ck has lower level than C. Proof. The result is clear since iCk ≤ iC0 and iC0 < iC .  Lemma 2 now justifies the desired analysis of form-series expansion. Definition 4. The form-series expansion of a formula A is the LF-formula A =  ∨ k<ω A k, if A is ∨ JB, p, CK ∃xB, if A is ∃xB B ∨ C, if A is B ∨ C ¬B, if A is ¬B A, if A is atomic or schematic. In ordinary quantificational logic, a formula is truth-evaluable if closed. That is not the case in LF, because a formula with no free variables may still contain an LOGIC IN THE TRACTATUS 25 unbound schematic letter. But a proper closed formula is one that contains neither free variables nor unbound schematic letters. The following somewhat tedious lemma guarantees that proper closed formulas expand into proper closed formulas of LF. Lemma 3. Suppose that A is a merely proper formula of LF. Then A is a proper formula of LF whose free variables are among those of A. Proof. We argue by induction on the level of A. Only two cases are nontrivial. First suppose that A is ∃xB. By induction hypothesis, B is a proper formula of LF whose free variables are among those of B. Then A = ∃xB is a proper formula of LF, whose free variables are among those of A. Now suppose A = ∨ JB, p,CK. By Definition 4, A = ∨ k<ω A k. Clearly B = A0 must be proper if A is, and the free variables of B are among those of A. Suppose now that Ak is proper and that its free variables are among those of A. Then Ak+1 = C[p/Ak]. The free variables of C must be among those of A. And since A is proper, a schematic letter q can occur free in C only if q = p. Hence Ak+1 is proper, and its free variables are among those of A. Since each Ai has lower level than A, it follows by outer induction hypothesis that each A i , and hence A itself, is a proper formula of LF whose free variables are among those of A.  After that bit of ground-clearing we can extend the definition of truth to LF. Definition 5. Let A be a proper closed formula of LF. Then M |= A iff M |= A. 2.3.4. Extensionality. A primary goal of this paper is to determine the expressiveness of LF. We have just seen a definition of truth which does not proceed by syntactical complexity. So it is not at all obvious that LF can be given a robust semantics. I'll now show, however, that LF is extensional. Toward this end, let me first record a basic lemma, that the expansion of a form-series formula into its infinitary counterpart commutes with substitution of formulas. Lemma 4. Suppose that A is proper, and that B[p/A] is a formula of LF. Then B[p/A] = B[p/A]. Let's now use the lemma to derive the promised extensionality. Then I'll prove the lemma to conclude the section. Proposition 5. Suppose that C[p/A], C[p/B] are proper formulas of LF, and that A and B are proper. If M |= ∀~u(A↔ B) then M |= C[p/A]↔ C[p/B]. Proof. By the definition of |= and * * *, the condition M |= ∀~u(A↔ B) implies M |= ∀~u(A↔ B). By the extensionality of infinitary logic it follows that M |= C[p/A]↔ C[p/B]. So by Lemma 4, M |= C[p/A]↔ C[p/B]. The result now follows by the definition of |=.  26 MAX WEISS Lemma 4 owes its relatively straightforward proof to the parsimonious implementation of formal series in LF. Proof of Lemma 4. The goal is to prove that B[p/A] = B[p/A], under the assumption that A is proper. We argue by induction on the level of B. It suffices to handle the only nontrivial situation, where B = ∨ JC, q,DK. Let's distinguish cases according to whether or not p = q. First suppose that p = q. It is clear that p[p/D]k[p/C[p/A]] = p[p/D]k[p/C][p/A]. By Lemma 1 together with Definitions 2 and 4, it follows that B[p/A] = ∨ JC, p,DK[p/A] = ∨ JC[p/A], p,DK = ∨ k<ω p[p/D]k[p/C[p/A]] = ∨ k<ω p[p/D]k[p/C][p/A] = ∨ k<ω Bk[p/A].(3) On the other hand, suppose that p 6= q. Using By Lemma 1 together with Definitions 2 and 4 again, B[p/A] = ∨ JC, q,DK[p/A] = ∨ JC[p/A], q,D[p/A]K = ∨ k<ω q[q/D[p/A]]k[q/C[p/A]](4) Let's now argue by induction on k that q[q/D[p/A]]k[q/C[p/A]] = q[q/D]k[q/C][p/A].(5) The case of k = 0 is trivial. So assume (5) to hold for k ≥ 0. Using p 6= q and the propriety of A, straightforward considerations about substitution imply that q[q/D[p/A]]k+1[q/C][p/A] = q[q/D[p/A]][q/D]k[q/C[p/A]] = q[q/D][p/A][q/D]k[q/C][p/A] = q[q/D]k+1[q/C][p/A].(6) This proves (5). But (5) together with (4) imply by Lemma 1 that B[p/A] = ∨ k<ω q[q/D]k[q/C][p/A] = ∨ k<ω Bk[p/A](7) holds in the case that p 6= q as well as in the case that p = q. However, Bk has lower level than B. So the outer induction hypothesis applies: Bk[p/A] = Bk[p/A].(8) From (3), (7), and (8), we obtain the desired conclusion B[p/A] = ∨ k<ω Bk[p/A] = ∨ k<ω Bk [p/A] = B[p/A].  LOGIC IN THE TRACTATUS 27 3. Expressiveness We've now got a reconstruction LF of Wittgenstein's logical system. Let's see what it can do. In §3.1, I'll begin by developing the semantics a bit further, spelling out what it is for formulas to define relations and operators. I'll then show that LF has some further nice properties: one result settles an issue about definability of infinitary conjunctions, and another gives a semantic characterization of form-series formulas. In §3.2, I'll apply that semantic machinery to show that LF is capable of expressing finitary inductive definitions; we'll see in particular that the form-series device yields a categorical analysis of arithmetic. Finally, in §3.3 I'll sketch the rather diffuse system of relationships, in point of expressiveness, between LF and other extensions of first-order logic. 3.1. Definability of relations and operators. Recall that by Proposition 5 of §2.3, the system LF enjoys a strong form of extensionality: in any reasonable situation, a subformula can be exchanged with any of its logical equivalents without change of truth-value. Exploiting extensionality everywhere, we can now complete the task of wrangling the unruly syntactical manipulations into a denotational semantics. This will sharpen later talk of expressiveness, for example in the treatment of induction in §3.2. By Lemma 3, a formula which is closed and proper has a truth-value. So such formulas have truth-values as suitable semantic values. What about other formulas? Regarding those which are proper but not closed, we can follow an approach which is typical to first-order logic. Take an n-ary relation over a domain D to be a set of n-tuples of elements of D. As a limiting case, assume that there is exactly one 0-tuple ∅. Now, suppose that A is any proper formula containing exactly k ≥ 0 free variables. Then the formula A defines over M a k-ary relation |A|M over D as follows: |A|M = {(a1, . . . , ak) : M |= A[a1, . . . , ak]}. This stipulation subsumes the treatment of closed formulas, once the truth-values are identified with the zeroary relations {∅} and ∅ (Krivine, 1998, 63). To interpret form-series expressions, we also need to make some sense of improper formulas. Here it is easiest to proceed indirectly. Say that a operator on D is a function from j-ary relations on D to k-ary relations on D; let's call the pair j, k its type. Now, let M be a structure. Where R,S . . . are predicates not in the signature of M, let M, X, Y, . . . be the result of expanding M to interpret R as X, S as Y , and so on. As with the treatment of satisfaction, the notation M, X, Y, . . . tacitly assumes a lexicographic ordering of the predicates interpreted. Suppose that A is a formula in the signature of an expansion M, X of M to R. Then A defines through R over M the operator |A|R:M : X 7→ |A|M,X . The type of A is j, k, with j the arity of R, and k the arity of |A|M,X . I will say that an operator is Lor LF-definable if some formula of L, or of LF, defines Γ. For example, the formula ∃yRx1 * * *xky defines through R the operator of type k + 1, k such that |∃yR~xy|R:M(X) = {(~a) : M, X |= ∃yR~xy[~a]} = {(~a) : (~a, b) ∈ X for some b ∈ D}. 28 MAX WEISS We can now give a method of interpreting improper formulas. It will only be needed here to interpret an improper formula B with at most one free letter, say p. Suppose that R is not in the signature of M. The above stipulations imply that the formula B[p/R~x] defines through R over M the operator |B[p/R~x]|R:M : X 7→ |B[p/R~x]|M,X . In this way, an improper formula B is interpreted relative to a substitution of some R~x for p. The type of the defined operator is j, k where j is the length of ~x, and k is the number of variables free in B[p/R~x]. Clearly, the choice of ~x affects the type of the operator defined. In form-series contexts, normal uses will involve an operator of type j, j for some j. The following lemma will clarify the semantics of LF's form-series device. Lemma 5. Suppose that B[p/C] is a proper LF-formula, that C is proper, and that the variables free in C are precisely ~x. Then |B[p/C]|M = |B[p/R~x]|R:M(|C|M). Proof. Immediate from extensionality plus the notion of defined operator.  Before applying Lemma 5 to interpret formal series, we just need to smooth out one wrinkle. Say that a form-series expression JA, p,BK is normal if the variables free in each JA, p,BKk are precisely the variables free in A. It suffices to interpret normal expressions: ∨ JA, p,BK is equivalent to A ∨ ∨ JB[p/A], p, BK, and the latter is normal. At last, we interpret a normal form-series disjunction as the union of results of applying a L-defined operator zero or more times to a defined relation. Proposition 6. Suppose that JA, p,BK is normal and proper, and that the variables free in A are ~x. Then∣∣∣∨JA, p,BK∣∣∣ = ⋃ k<ω ( |B[p/R~x]|R:M )k (|A|M) . Proof. Lemma 5 implies for all k that∣∣JA, p,BKk+1∣∣ = |B[p/R~x]|R:M (∣∣JA, p,BKk∣∣) from which the claim is immediate by induction and the definition of truth.  We can now take care of a puzzle which has been left hanging for a while. Recall that in building up LF, form-series disjunctions were adopted as primitive. But what about conjunctions? As noted in §1.1.1, an adequate reconstruction of Wittgenstein's system ought to predict the question is not trivial. Note that by Proposition 6, it is reasonable to understand a formula C to express the conjunction of JA, p,BK provided that |C|M = ⋂ k<ω ( |B[p/R~x]|R:M )k (|A|M) for all M. We now have the following. Proposition 7. Suppose that JA, p,BK is normal and proper. Then ¬ ∨ J¬A, p,¬B[p/¬p]K expresses the conjunction of JA, p,BK. LOGIC IN THE TRACTATUS 29 Proof. Suppose that Γ = |B[p/R~x]|R:M. Let's write X for the complement of X relative to the domain of M. Let Γ be defined by Γ(X) = Γ ( X ) . Applying Lemma 5 twice, |¬B[p/¬R~x]|R:M(X) = |B[p/R~x]|M,X = Γ(X). By Proposition 6, it follows that∣∣∣¬∨J¬A, p,¬B[p/¬p]K∣∣∣ = ⋃ k<ω Γk ( X ) . It therefore suffices to show that⋃ k<ω Γk ( X ) = ⋂ k<ω Γk(X). To this end, let's argue by induction on k that Γk ( X ) = Γk(X). The claim is trivial for k = 0. So suppose it to hold for k. Then Γk+1 ( X ) = Γ ( Γk ( X )) = Γ ( Γk (X) ) = Γ (Γk (X)) = Γk+1(X).  Before pressing further, let's get a routine syntactical lemma out of the way. In §2.3, I sketched a method of expressing the ancestral of a relation, which relies on a trick for recycling bound variables. The following lemma generalizes that trick. Note that it relies on the presence of an equality predicate. I've found this to be the main obstacle to interpreting LF under Wehmeier's 2004 semantics of variables. Lemma 6. Each formula A of LF is equivalent to a formula of the form A′[p/R~x] such that R does not occur in A′, for any predicate R. Proof. Let A be a formula of LF. Then there are some sequences ~t1, . . . ,~tk of terms such that A has the form A′[p1/R~t1] * * * [pk/R~tk], where R does not occur in A′. Let R~x~ti be the formula ∃~x(ti,1 = x1 ∧ * * * ∧ ti,n = xn ∧R~x), where x1, . . . , xn = ~x and ti,1, . . . , ti,n = ~ti. Then, R~x~ti is logically equivalent to R~ti. So by Proposition 5, the formula A is equivalent to A′[p1/R~x~t1] * * * [pk/R~x~tk].  3.2. Induction. Let's now turn to the main goal of this section: to clarify the relationship between form-series disjunctions and finitary inductive definitions. The essential idea, attributed by Barwise (1977) to Arthur Rubin, is that a finitary inductive definition can be regarded as a countably infinite disjunction which contains only finitely many variables. I'll aim to show that every finitary inductive definition can be expressed by a form-series disjunction. To this end, we need first to spell out what is a finitary inductive definition and what it is for a logic to express one. Consider some examples. (A) the empty set is hereditarily finite; every finite set of hereditarily finite sets is hereditarily finite. (B) the empty set is hereditarily countable; every countable set of hereditarily countable sets is hereditarily countable. Each of these clauses can be used to specify the totality of results of repeatedly applying a rule to some initially given objects. The rule determines an operation, Γ, which takes a class X and returns the class Γ(X) of all results of once applying the rule to any of its elements. The rule is applied again to X ∪ Γ(X), and so on. Write 30 MAX WEISS Γ∪ : X 7→ X ∪Γ(X). Then the inductively specified totality should certainly include all elements of the classes X,Γ∪(X),Γ∪(Γ∪(X)), . . ., each class being obtained by some finite number of applications of Γ. Consider the union of all those classes. Does it contain every result of applying the rule to its elements? Say that the induction is finitary if this is so. Thus, example (A) is finitary but (B) is not. Now for some notation. Let I0Γ = Γ(∅), let I α+1 Γ = I α Γ ∪Γ(I α Γ), and for λ a limit ordinal let IλΓ = ⋃ α<λ I α Γ. If α is the least ordinal such that I α+1 Γ = I α Γ, then write IΓ = I α Γ. Induction transforms the operator Γ into the class IΓ. So the induction determined by Γ is finitary if IΓ = I ω Γ . The notation just introduced assumes induction always to take the empty class as a "base case". Of course this implies no loss of generality. Let ΓX(∅) = X and ΓX(Y ) = Γ(Y ) otherwise. I'll sometimes write I α Γ(X) for I α ΓX . Proposition 8. Suppose that Γ is L-definable. Then IωΓ is LF-definable. And so is the operator X 7→ IωΓ(X). Proof. Write Γ = |A|R:M, where the variables free in A are ~x. Also suppose that A = A′[p/R~x], with R not in A′. Clearly, |(p ∨A′)[p/R~x]|R:M = Γ∪. So using Proposition 6, ∣∣∣∨J⊥, p, p ∨A′K∣∣∣M = ⋃ k<ω I kΓ = I ω Γ , where ⊥ is any unsatisfiable L-formula. For the second part, take the defining formula to be ∨ JR~x, p, p ∨A′K.  As a first application of Proposition 8, let's reconsider the ancestral. Suppose that X is a two-place relation. Following (1903, 210), let's write X1 = X, and write Xk+1 for the class of all (a, b) such that (a, c) ∈ Xk and (c, b) ∈ X for some c. The ancestral can now be interpreted as an operator Γ∗ : X 7→ ⋃ 0<k<ωX k. Proposition 9. In the logic LF, the ancestral operator is definable. Proof. Let A be the formula Rxy ∨ ∃z(Rxz ∧ Rzy). Then |A|R:M : ⋃k i=1X i 7→⋃2k i=1X i. So Iω|A|R:M(X) = ⋃ k<ωX k = Γ∗(X). By Proposition 8, it follows that there is a formula, call it Ancestral , such that |Ancestral |R:M = Γ∗.  Toward a second example, let's develop an analysis of arithmetical concepts within LF. For Wittgenstein unlike for Frege and Russell, this will not be a matter of specifying relations between distinctively numerical objects. Rather, arithmetical concepts are techniques for reporting factual relationships (see Tractatus 6.2ff). Accordingly, let's now build a method of arithmetical reporting. Let X be an ordinary two-place relation on D. Then X can be understood to determine counterparts of arbitary arithmetical relations. For example, consider the one-place arithmetical relation which holds just of the natural number k. To this there will correspond a two-place relation on D which holds of just those a, b ∈ D such that (a, b) ∈ Xk. Similarly, if ρ is the arithmetical relation which holds of just those j, k, l such that l = j+k, then the choice of X determines as corresponding to ρ the four-place relation on D which holds of just those a, b, c, d such that (a, b) ∈ Xj , (a, c) ∈ Xk, and (a, d) ∈ Xj+k. Now since numbers are not objects, arithmetical relations are not relations on objects. Therefore no particular choice of material relation X belongs in the analysis LOGIC IN THE TRACTATUS 31 of arithmetic. Instead, an arbitrary k-place arithmetical relation ρ will be analyzed as an operator Γρ of type 2, k + 1: Γρ(X) = {(a, b1, . . . , bk) : (a,b1) ∈ Xn1 , . . . , (a, bk) ∈ Xnk for some (n1, . . . , nk) ∈ ρ}.(9) Specifically, addition and multiplication determine operators Γ+ and Γ× of type 2, 4. Proposition 10. The addition and multiplication operators are LF-definable. Proof. In the case of addition, the idea is to show how to build a minimal four-place relation between initial object, left and right summands, and sum, so that (i) any initial object has itself as a sum of itself with itself and (ii) any successor of a sum of left and right summands is a sum both of the left summand with the successor of the right, and of the right summand with the successor of the left. Let R,S be twoand four-place predicates not in the signature of M. For the base case, let A be the formula w = x = y = z. For the induction step, let B be the formula ∃y∃z(Swxyz ∧Ryy1 ∧Rzz1). Then |B|S:M,X : Y 7→ {(a, b, c1, d1) : (a, b, c, d) ∈ Y for some c, d with (c, c1) ∈ X and (d, d1) ∈ X}. Now similarly, let C be an L-formula which describes the effect of at once taking successor in the left summand and the sum. Then Iω|B∨C|S:M,X (|A| M) = Γ+(X). By Proposition 8, it follows that in the signature of an expansion of M to R, there is a formula Plus such that |PlusR:M| = Γ+. Let's now turn to multiplication. In handling the successor steps, the strategy will be to refer to addition by passing the buck to the base case. More precisely, I'll prove the definability of an operator Γ+× of type 2, 7 such that Γ+× : X 7→ {(a, b, c, d, e, f, g) : (a, b, c, d) ∈ Γ+(X) ∧ (a, e, f, g) ∈ Γ×(X)}. For the base case let A be an LF-formula, in the signature of an expansion of M to a new dyadic predicate R, such that |A|M,X = {(a, b, c, d, a, a, a) : (a, b, c, d) ∈ |Plus|M,X}. Now let S be a new seven-place predicate. Then there is a first-order formula B in the signature of an expansion of M to R,S such that |B|S:M,X : Y 7→ {(a, b, c, d, e, f1, g1) : (a,b, c, d, e, f, g) ∈ Y for some f, g with (f, f1) ∈ X and (a, g, e, g1, a, a, a) ∈ Y }. Similarly, let C be a formula which specifies the effect of taking successor in the left multiplicand rather than in the right. Then Iω|B∨C|S:M,X (|A| M) = Γ+×(X). By Proposition 8 there is, in the signature of an expansion of M to R, a formula PlusTimes such that |PlusTimes|R:M = Γ+×. Existentially generalizing out the three addition placeholders of PlusTimes gives a formula Times such that |Times|R:M = Γ×, as desired.  32 MAX WEISS Proposition 11. If ρ is an arithmetically definable relation on the natural numbers, then Γρ is an LF-definable operator. Proof. It suffices to show that for any arithmetically definable relation ρ, there is an operator Γρ satisfying (9) above. We argue by induction on the complexity of formulas in a language of arithmetic with signature 0,′ ,+,×, where ′,+,× are treated as relations. The proof is trivial. Let WeakAncestral be the formula x = y ∨ Ancestral . Let φ? be the image of φ under the translation • 0(x) 7→ x = w; ′(x, y) 7→ Rxy; +(x, y, z) 7→ Plus[w, x, y, z]; ×(x, y, z) 7→ Times[w, x, y, z]; • x = y 7→ x = y; ¬φ 7→ ¬φ?; φ∨ψ 7→ φ?∨ψ?; ∃xφ 7→ ∃x(WeakAncestral [w, x]∧ φ?). Now define Aφ to be the formula WeakAncestral [w, x1]∧. . .∧WeakAncestral [w, xk]∧ φ?, where x1, . . . , xk are the variables free in φ. If φ defines ρ over a standard model of arithmetic, then ∣∣Aφ∣∣R:M = Γρ.  From a given relation X, the addition and multiplication operators determine relations which look only as much like addition and multiplication as X looks like successor. For example, if X looks like the successor relation on the hours of a clock, then the corresponding addition and multiplication relations look like those of arithmetic modulo twelve. However, in the odd event that ω itself happens to be lying around somewhere, then that can certainly be reported. The proposal that Wittgenstein's form-series operator ought to yield a categorical axiomatization of arithmetic is due to Goldfarb (2012). Proposition 12. Suppose that the domain of M is infinite, and that M contains a dyadic predicate. There is a single formula A of LF such that M |= A iff M contains a corresponding copy of the natural numbers under the successor relation. Moreover, if M |= A, then any counterpart of an arithmetically definable relation is definable on M. Proof. Immediate from Propositions 9 and 11.  After that foray into applications, let's return to the general theory. The operator of an inductive definition is often specified by reference to a previously inductively defined concept: in this way, for example, the usual definition of multiplication invokes the concept of addition. But the syntax of LF does not allow operatorsigns to contain form-series expressions. So it might be wondered whether this technique can always be simulated in LF. In the proof of Proposition 10, we saw that multiplication can be defined from addition by folding the concept of addition into a second-order parameter of the base case. Let me conclude this section by sketching a result to the effect that the method is general. Any LF-defined relations can be treated like primitives of the underlying structure. Proposition 13. Suppose that Γ is L-definable over M, Y1, . . . , Yn and that Y1, . . . , Yn are LF-definable over M. Then IωΓ is LF-definable over M. Proof. By hypothesis, there is an L-formula A such that |A|R:M,Y1,...,Yk = Γ; and there are LF-formulas B1, . . . , Bn with |Bi|M = Yi for each of the Bi. We may assume A to have the form A′[p/R~x, q1/S1~y1, . . . , qn/Sñyn], where A ′ is an L-formula containing none of R,S1, . . . , Sn. Indeed, suppose that the free variables of A are LOGIC IN THE TRACTATUS 33 precisely ~x, and that the free variables of each Bi are ~yi, with the ~yi distinct from all ~x and from all ~yj with j 6= i. For any relations V,W , write V ×W for set of all (~a,~b) with (~a) ∈ V and (~b) ∈W . And write ΠiVi for V1 × V2 × * * * . Now it would be nice to define in L an operator satisfying (10) IkΓ×ΠiYi 7→ I k+1 Γ ×ΠiYi for all k. Sadly, such an operator will not in general exist unless IkΓ and each of the Yi = |B|M are nonempty. So, the construction must be split into cases. Note that IωΓ = I ω Γ∪ . So we can assume that Γ = Γ∪. We can at once get a trivial case out of the way, namely where Γ(∅) = ∅. For in this case, IωΓ = ∅, and so |⊥|M = IωΓ . To motivate the handling of the other cases, let's first work the end of the proof. Let e be a selection e1, . . . , em of numbers from 1, . . . , n. For every such e, we'll aim to have constructed a formula De such that if it is precisely Be1 , . . . , Bem amongst B1, . . . , Bn which have nonempty extension, then |De|M = IωΓ. Now let Ee be a formula which says that it is precisely the Be1 , . . . , Bem with nonempty extension. Take Ce to be the formula Ee → De. For the trivial case, we can choose C0 to be the formula ¬∃~xA′[p/⊥, q1/B1, . . . , qn/Bn]→ ⊥. Finally, let C be the conjunction of C0 with each of the 2 n formulas Ce. The construction of the De will then give the desired result that |C|M = IωΓ . It remains to build each formula De, under the hypothesis that Γ(∅) and precisely Ye1 , . . . , Yem are nonempty. Write ~ye for ~ye1 , . . . , ~yem . Let Te be a new predicate whose arity is the length of ~x, ~ye. Now for 0 ≤ j ≤ n, let Ge,j =  ∃~yeTe~x~ye, if j = 0; ∃~x~ye1 * * * ~yei−1~yei+1* * * ~yemTe~x~ye, if j = ei ⊥, otherwise. Then |Ge,0|M,ΠiYei = Γ(∅), and |Ge,j |M,ΠiYei = Yj if 1 ≤ j ≤ n. Let Fe be the formula A ′[p/Ge,0, q1/Ge,1, . . . , qn/Ge,n]∧Ge,e1 ∧* * *∧Ge,em . Then Fe defines over M an approximation of the operator (10), so that (11) Iω|Fe|Te:M : Γ(∅)×ΠiYei 7→ I ω Γ ×ΠiYei . Since Fe is a formula of L, we can apply the induction of Proposition 8 to define the operator mentioned in (11). Using A′ and the Bi, it is also clear that Γ(∅)×ΠiYei is LF-definable over M. So, the relation IωΓ ×ΠiYei is itself definable over M. Existentially generalizing out the ~ye yields the formula De desired for the case in question, namely such that |De|M = IωΓ .  3.3. Comparisons. Let's now zoom way out, and compare LF with some other extensions of first-order logic. First, it is obvious from the double-bar semantics that LF is a subsystem of the infinitary logic Lω1ω which results by adding to first-order logic countably infinite disjunctions. However, even L∞ω has no wellfoundedness quantifier (Lopez-Escobar, 1966). Indeed, LF is a subsystem of the fragment Lωω1ω in which no formula contains infinitely many variables (Barwise, 1977); and Lωω1ω lacks a quantifier "there are infinitely many". The system LF is also related to some subsystems of second-order logic. For example, the Π11 fragment of second-order logic (Π11SOL, as defined in Heck (2011)) expresses finitary inductive definitions, 34 MAX WEISS so it is at least as expressive as LF. But it also has an infinity quantifier, so it is strictly more expressive. The situation is different with monadic second-order logic (MSOL), which a priori expresses finitary inductive definitions only of monadic properties. And indeed, since the monadic second-order theory of the successor relation is decidable (Büchi, 1960), it follows that unlike LF, monadic second-order logic cannot define both addition and multiplication from successor. Conversely, the monadic fragment, like the Π11 fragment, does have a wellfoundedness quantifier. Thus monadic second-order logic and LF are incomparable. Strictly weaker than all of these systems is the result LA of adding an ancestral operator to first-order logic. In sum, we have Proposition 14. Write X → Y to mean that logic Y is strictly more expressive than logic X. Then Lω1ω Π 1 1SOL MSOL Lωω1ω OO LQ∞ cc :: LQwf dd :: LF ii OO LA. jj OO 4. Definability One way to characterize the consequence relation in first-order logic is through a universal generalization over structures. Since a structure consists of a maybe infinite collection of objects plus some relations on the collection, this analysis makes the consequence relation look unmanageable: to verify that the relation obtains, it looks as though we'd have to run through an infinity of in general infinite structures and determine that each is not a countermodel. However, first-order logic admits a complete notion of proof: accordingly, whenever some formula is a first-order consequence of some others, some finite pattern of formulas gives an effective witness. So, it turns out to suffice instead to enumerate the finite patterns of formulas until a proof appears. This collapse in the complexity of the consequence relation is a fairly special property of first-order logic. Slight enrichments of the logic tend to complicate the consequence relation and outrun any system of finite witnesses. In this section, we turn to the problem of characterizing the complexity-theoretic effects of the Russellian semantics and of the form-series device. On the one hand, the Russellian constraint winnows the class of countermodels, so that the answers to old questions may change. On the other hand, the form-series device introduces new formulas, hence raising more questions. In §4.1, I'll develop an appropriate framework for measuring the complexity of metalogical concepts of LF. In §4.2 and §4.3, I'll respectively consider the cases in which the domain has been chosen to be some fixed finite or infinite collection. Finally, §4.4 will address the complexity of D-validity and D-consequence considered prior to a choice of D. LOGIC IN THE TRACTATUS 35 4.1. Measuring definitions. Let's start with a simple framework for measuring the complexity of logical notions, which we can then apply to the notions of D-validity and D-consequence for L and LF. A standard measure of logical complexity derives from the theory of computable functions on the natural numbers. Its application to logic depends on the technique of arithmetization, according to which formulas are "coded" as natural numbers. In the present context, arithmetization is somewhat annoying, since it prejudges nontrivial interpretive questions. First, it applies only if the signature is countable. Since a Russellian signature includes the domain of its Russellian structures, this excludes structures with uncountable domains. Second, arithmetization yields the definability of, e.g., the class of names coded by the even integers. This leads to troubles of the sort indicated in §1.2. Sundholm (1992, 71) recommends an approach to this problem derived from Barwise (1975, 78ff): code syntactical constructions not arithmetically but settheoretically, treating logical vocabulary as pure sets, and the terms of the signature as urelements. In a little more detail, suppose S is a structure. Let HF(|S|) be the class of hereditarily finite sets over the domain |S| of S; thus the elements of HF(|S|) are generated, given the elements of |S| initially, by repeatedly forming all finite sets of what's obtained already. This determines a first-order structure HF(S) whose domain is HF(|S|), together with the natural membership relation on HF(|S|), the property of belonging to the domain |S| of urelements, and each of the relations and functions baked into S itself. I will write HF and HF for HF(∅) and HF(∅) respectively. We'll be specially concerned with HF(S) for S not any old structure, but a Russellian signature considered as a structure. The class HF(S) will be regarded as the universe of possible syntactical constructions from the initially given assortment of nonlogical vocabulary. For simplicity of coding, I will just identify the signature with its collection D of names. This implies no serious loss of generality. For one thing, a signature with countably many predicates can be interpreted as a signature with at most one predicate of each arity: take the jth predicate of arity k to be the predicate whose arity is the numerical code of the pair j, k. But second, a language with at most one predicate of each arity can take an atomic formula to be simply a sequence of terms, so doesn't need predicates. We will therefore work over HF(D), where the underlying structure D is a bare class of urelements. Logical vocabulary should be coded by pure sets. Atomic formulas are coded in HF(D) as finite sequences of variables and of elements of D. Nonatomic formulas result from atomic formulas through this or that finitary set-theoretic construction. The structure HF(D) is of course itself a structure for a first-order language whose two nonlogical predicates are those of membership and urelementhood, or ∈ and D. The complexity of a class on HF(D) can now be measured by the logical complexity of the simplest formulas which define it. I'll just sketch the portion of the framework we'll need; the details can be found in Barwise (1975). A formula is ∆0 if it is built up from atomic formulas by negation, disjunction, and bounded existential quantification ∃x ∈ y . . .. A formula is Σ1 (or Π1) if it's the result of prefixing a ∆0 formula with a sequence of existential (universal) quantifiers; also the result of prefixing a Πn (or Σn) formula with a string of existential (universal) quantifiers is said to be Σn+1 (Πn+1). Now the complexity of a subclass of HF(D) is given by the complexity of the simplest formula which defines it. A class is said to be ∆n if it is both Σn and Πn. 36 MAX WEISS The definability-theoretic characterization of complexity of classes of hereditarily finite sets generalizes naturally the recursion-theoretic measures of complexity on the natural numbers. Note that each natural number is uniquely represented as a sum of powers of two, and so it can be taken to code the set of whatever is coded by the powers (Ackermann, 1937). This gives a bijection between the naturals and HF. It's now straightforward to verify that a set of integers is recursive iff it is it is ∆1 on HF (Barwise, 1975, 47ff), likewise for r.e. and Σ1, and so on. As Kirby (2009) argues, HF can therefore be seen as a natural home of finitary constructions. Moreover, the extension of HF to HF(D) preserves the alignment of definabilitytheoretic and computability-theoretic classifications. In particular, the introduction of D does not affect first-order definability-theoretic complexity of pure classes. Proposition 15. Suppose X ⊆ HF. Then X is Σn on HF iff X is Σn on HF(D). Proof. In one direction, note that the class HF is Σ1 on HF(D). So if φ is a Σn definition of X on HF, then the relativization of φ to HF is a Σn definition of X on HF(D). Conversely, the downward Löwenheim-Skolem theorem implies that HF(D) has a countable elementary substructure HF(D)′. Let D′ be the least subclass of D such that each element of the domain of HF(D)′ belongs to HF(D′). Each element of HF(D′) is definable on HF(D) by a first-order formula with parameters in D′. So in fact, HF(D)′ = HF(D′). So any HF(D) has a countable elementary substructure HF(D′). We may therefore assume that D is countable. Let p be a bijection from D onto the class of pure sets of the form (0, a). Define f : HF(D) → HF so that f(a) = p(a) for a ∈ D, and otherwise f(a) = (1, {f(b) : b ∈ a}). Let HF(D)∗ = {f(a) : a ∈ HF(D)}; let D∗ = {p(a) : a ∈ D}, and let a ∈∗ b iff b = (1, c) for some c such that f(a) ∈ c. Then f is an isomorphism of HF(D) onto (HF(D)∗,D∗,∈∗), while D∗,∈∗ are Σ1 on HF. Now, suppose that φ is a Σn definition of X on HF(D). Let φ∗ be the relativization to HF(D)∗ of the result of replacing ∈ and D in φ with the definitions of ∈∗ and D∗. Then φ∗ is a Σn definition of X ∗ on HF(D). Moreover, the restriction of f to HF is Σ1 on HF. Therefore, φ∗[f(x)] is a Σn definition of X on HF.  4.2. The finite case. Let's now apply this framework to analyze the metatheory of L and LF. The first couple of results should be reassuring. Proposition 16. Suppose D is finite. Then D-validity for LF is ∆1 on HF(D), and D-consequence for L is Σ1. Proof. Consider the infinitary expansion A of a formula A. Let B be an unquantified infinitary formula which results by successively replacing each existentially quantified subformula of A with the finite disjunction of its D-instances. Now consider an infinite disjunctive subformula C of B; suppose by induction that all subformulas of C are finitary. Then C has the form ∨ (D,E[p/D], E[p/E[p/d]], . . .), where D and E are constructed from some k atomic formulas by negation and finite disjunction, though E itself may also contain p. By extensionality, Proposition 5, C must be equivalent to the disjunction of its first 22 k disjuncts, and we can just drop the rest. Let A↓ be the formula, constructed from atomic sentences by negation and finite disjunction, which results by eliminating from B in this way each of its infinitary subformulas. Clearly there is a Σ1-definable function on HF(D) associating A↓ to A. But validity for finitary formulas is ∆1. LOGIC IN THE TRACTATUS 37 If D is finite, then D-consequence is compact. So, A is an D-consequence of X iff there's a conjunction B of elements of X such that B → A is valid; this can be expressed as a Σ1 formula on HF(D).  Let's now drop the assumption that D is finite. The second reassuring result is that, if we drop form-series from the logic, and consider only the notion of D-validity, then this is no more complicated than usual. Proposition 17. D-validity for L is Σ1 on HF(D), for all D. Proof. It suffices to consider the case where D is infinite. Let I be a collection of L-formulas to the effect that "there is at least one thing, there are at least two things, . . . ". For A a formula of L, Let TA be an L-formula a 6= b ∧ a 6= c ∧ . . . to the effect that no two names in A denote the same thing. We now argue that A is D-valid iff A is a classical consequence of I ∪ TA. In one direction, suppose that A is not D-valid, so that M 6|= A for some D-structure M. Clearly M |= TA since A is a D-structure, and M |= I since D is infinite. Hence A is not a classical consequence of I ∪ TA. Conversely, suppose that there's a classical structure M such that M |= I ∪ TA but M 6|= A, where the signature of M consists just of the nonlogical vocabulary of A. Since M |= TA, it follows by the Lowenheim-Skolem theorems that M is elementarily equivalent to a structure M′ whose domain is D. Since M′ |= I, therefore M′ is isomorphic to an M′′ such that aM ′′ = a for each constant a which occurs in A. In turn, M′′ may be expanded to an D-structure M′′′ such that M′′′ 6|= A. The completeness theorem for first-order logic implies that A is a classical consequence of I ∪ TA iff there is a proof of A from I ∪ TA. Formally, however, the property "being a proof of A from I ∪ TA" is ∆1 on HF(D), so that "having a proof from T ∪ IA" is Σ1. From the previous paragraph, it follows that the collection of D-valid formulas is Σ1 on HF(D).  So, D-validity is never more complicated than classical validity. Does this also hold for D-consequence? By the compactness theorem, classical consequence is no more complicated than classical validity. But if D is infinite, then D-consequence is clearly not compact. For example, a universal generalization is a D-consequence of the set of its instances, but not of any finite subset. In other words, the complexity of the D-consequence relation remains to be determined. 4.3. Countability and categoricity. Let's now fix the domain to be infinite. What, then, is the complexity of D-validity and of D-consequence for LF in this case? Recall, from §2.2 and §3.2, that the Russellian constraint and the form-series device each lead to categorical axiomatizations of the standard model of arithmetic. I'll now show that LF categorically axiomatizes another infinite structure as well: HF(D) itself. This leads to an amusing application of Tarski's theorem, which shows that validity is not first-order definable on HF(D). After establishing the definability of satisfaction relative to truth, we then conclude that in fact LF-validity is Π11-complete. Finally I'll show that L-consequence is Π 1 1-complete as well. Let M be a relational structure without constants. Now, say that M is Daxiomatized up to isomorphism by some formulas X iff the formulas X are true in some D-structure, and if by an addition of constants, M can be expanded to a structure which is isomorphic to every D-structure satisfying X. 38 MAX WEISS Proposition 18. Suppose D is infinite. Then HF(D) is D-axiomatizable up to isomorphism by a single formula of LF. Proof. We want to find a formula Z such that M |= Z iff M is isomorphic to HF(D), for all D-structures M. Write D and E for a monadic and dyadic predicate of L; these can serve, inside L or LF, as counterparts of the predicates "x is an urelement" and "x belongs to y". Note that HF(D) can be seen as the smallest set which contains the empty set and all urelements, and which is closed under the procedure x, y 7→ x ∪ {y} of adjoining y to x. This suggests that the class of D-structures which are isomorphic to HF(D) can be defined by a single formula of LF. Using the predicate E for the counterpart of membership, it's straightforward to express the graph of the corresponding procedure of adjunction: Adj = ∀w(Ewz ↔ Ewx ∨ w = y). Let F be a new monadic predicate. Let ClAdj = ∃x∃y(Fx ∧ Fy ∧Adj) and let Γ = |ClAdj|F :M. Let M0 = |¬∃yExy|M. By Proposition 8, let Z ′ be a formula in the one free variable x such that |Z ′|M = IωΓ(M0). And let Z1 = ∀xZ ′. Thus, Z1 is true in just those M where everything results from things without elementsM by repeated adjunctionM. Furthermore, let Z2 = ∀x∀y∃!zAdj[x, y, z]) Z3 = ∃!x(¬Dx ∧ ∀y¬Eyx) Z4 = ∀x(Dx→ ∀y¬Eyx) Z5 = ∀x∃y(Dy ∧ ¬Eyx). And finally let Z = Z1 ∧ Z2 ∧ Z3 ∧ Z4 ∧ Z5. It remains to show that M |= Z iff M is isomorphic to HF(D). In one direction, it is clear that any D-structure isomorphic to HF(D) satisfies Z. Conversely, suppose that M |= Z. We want to construct an isomorphism from M onto HF(D). Since M is a D-structure, its domain is just D. By Z3 and Z4, the class M0 consists of the stuff in D M plus exactly one thing ∅M not in DM. Conditions Z1 and Z2 ensure that the cardinality of D differs by at most א0 from the cardinality of DM. Moreover if D is countable, then Z5 together with Z2 ensures that D M is infinite and therefore also countable. So in any case, there is a bijection f from DM onto D. For a ∈ M0, let h(a) = ∅ if a = ∅M, and otherwise let h(a) = f(a). A couple of quick observations before extending h from M0 to all of D. First: it is routine to show by induction on k that if a ∈ IkΓ(M0), then every EM-chain descending from a has length at most k. Since D = IωΓ(M0), therefore E M is wellfounded. Second: the truth of Z2 implies that adjunction M is functional; write a # b for the c such that M |= Adj[a, b, c]. By Z1, each c ∈ D−M0 can be written in the form c = a # b for some a, b. Now Z2 says that there is exactly one thing whose elementsM are b together with the elementsM of a. So, c is determined by its elementsM. But c was arbitrary. So no two setsM have the same elementsM. LOGIC IN THE TRACTATUS 39 For a ∈ D−M0, we may now define h(a) = {h(b) : EMba}. Let's argue that h is an isomorphism of M onto HF(D). Suppose s ∈ HF(D). Clearly if s = ∅ or s ∈ D, then s is in the range of h. Otherwise s = {s1, . . . , sk}; by induction on rank we may assume each si = h(ai) for some ai, and so s = h(∅M # a1 # * * * # ak) where # associates to the left. Conversely, suppose that h(a) = h(b) but a 6= b. Without loss of generality, we can assume there's a c such that EMca but not EMcb while h(c) ∈ h(b), so that h(c) = h(d) for some d 6= c, contradicting the wellfoundedness of EM. Since h is a bijection, we must therefore also have that h(b) ∈ h(a) iff EMba.  We're exploring the complexity of concepts of the metatheory of L and LF. So far it has been enough simply to identify formulas of these object-languages with elements of a certain convenient structure, namely HF(D). At this point we'll need to begin making explicit reference to expressions of the formal metatheory. Indeed, it will also be useful to think of L as containing copies of the first-order expressions of the metalanguage. To keep things clear, I will in the rest of this subsection never any longer use unadorned logical notation to refer to expressions of L or LF. using unadorned logical notation. Whereas ∃,¬,∨, (, ), x, y, . . . ,∈,D . . ., etc., now refer to expressions of the metalanguage, only ∃, ¬, ∨, (, ), ẋ, ẏ, . . . , Ė, Ḋ . . . now refer to corresponding expressions of L, which are understood as elements of HF(D). Where φ is a formula of the metalanguage, its L-copy is φ: for example if φ is ∃x(x ∈ y → x ∈ z), then φ is ∃ẋ(Ėẋẏ→ẋ∈ż). We'll also consider second-order quantification in the metalanguage; the coding scheme must then be extended correspondingly. I'll continue to use uppercase italic letters informally to range over those elements of HF(D) which code formulas of L or of LF. Finally, the notions of D-validity and D-consequence have obvious counterparts as relations on codes of Land LF-formulas; I'll refer to these counterparts as ValidL, ImpliesL, ValidLF and ImpliesLF. With Proposition 18, we saw that the structure HF(D) can be D-axiomatized up to isomorphism by a single formula of LF. This implies that the concept of first-order truth-in-HF(D) is embedded in the concept of LF-validity. Proposition 19. Suppose that D is infinite. Then, there is a first-order formula θ in the signature of HF(D), with one extra monadic predicate V, such that HF(D),ValidLF |= θ[φ]↔ φ for all first-order formulas φ in the signature of HF(D). Proof. Let Z be the categorical LF-axiom for HF(D), which is given by the proof of Lemma 18. Let ζ be a formula of the metalanguage such that HF(D) |= ζ[x/a, y/b] iff a is an LF-formula A and b is Z→A. Let θ be the formula ∃y(ζ ∧ V y). Given that D is infinite, HF(D) is isomorphic to an HF(D)-coded D-structure. Using this fact, it is routine to verify that θ satisfies the claim of the lemma.  We are clearly in the vicinity of Tarski's theorem, which has the following corollary. Lemma 7. Suppose that θ is a first-order formula in the signature of HF(D) together with a single new predicate R, such that HF(D), X |= θ[φ]↔ φ. for every first-order formula φ in the signature of HF(D). Then X is not first-order definable on HF(D). 40 MAX WEISS Proof. Suppose to the contrary that X were first-order definable, say by a formula ψ whose free variables are just ~x. Let θ′ be the result of everywhere replacing R~x with ψ. Then HF(D) |= θ′[φ]↔ φ for all φ, and this contradicts Tarski's theorem.  Proposition 20. Suppose that D is infinite. Then the class of D-valid LF-formulas is not first-order definable on HF(D). Proof. Immediate from Proposition 19 and Lemma 7.  In fact, something stronger is true. A formula is said to be (explicitly) Π11 if it is the result of prefixing a first-order formula with a string of universal second-order quantifiers. The official definitions of D-validity and of D-consequence have the form "for all D-structures. . . ". Moreover, a D-structure is determined by its diagram. And under the coding of L-formulas with elements of HF(D), a diagram is just a class on HF(D). So the official definitions of D-validity and D-consequence are naturally expressed over HF(D) with Π11 formulas. Can this rendering be simplified? A class P is said to be Π11-complete over some structure if for every Π 1 1 formula φ, there's a first-order formula ψ such that φ[~a] ↔ ψ[P,~a] holds for all ~a in the domain. Thus, P is Π11-complete if every class definable by a second-order universal generalization of a first-order formula is first-order definable relative to P . Note that since HF(D) permits coding finite sequences of classes as classes of finite sequences, it is enough to consider the case of a single universal second-order quantifier. I'll now show that for formulas of LF, the concept of D-validity is Π11-complete. To this end, I'll show that in HF(D), the concept of satisfaction can be reduced to the concept of truth, and then show that the concept of truth for Π11 formulas is first-order definable relative to D-validity. Reducing satisfaction to truth is somewhat like trying to replace de re mental states with de dicto ones (except perhaps in being easier). As is well known, each element of HF has a parameter-free first-order definition, so in that case, the satisfaction of a formula by an element can be reduced to truth using something like Russell's theory of descriptions. This is not so for elements of HF(D), since the urelements are indiscernible. But for present purposes, a notion weaker than that of definition will suffice. Say that sets a, b are isomorphic if they are identical modulo swapping of urelements. Now let's say that a formula describes a if it is satisfied precisely by the sets isomorphic to a. The crucial fact about descriptions will be this: that no objects satisfying the same description differ over any parameter-free formula. As I'll verify below, every element of HF(D) is first-order describable. Indeed, a "canonical" description of a can be generated from a in a simple uniform manner. This means that lying within HF(D), there is a definable "road back" from each object to a bunch of codes of its canonical descriptions. Lemma 8. There's a formula δ in the signature of HF(D), such that (i) if HF(D) |= δ[a, b] then b codes a canonical description of a, and (ii) HF(D) |= ∀x∃yδ[x, y]. Proof. Let's begin by associating to each element a of HF(D) a formula γa without parameters which canonically describes it. First, write ν for a one-one association of variables νa, νb, . . . for some finitely many elements a, b, . . . of HF(D). Now, let's construct a formula βa,ν which says of the objects assigned to its free variables that LOGIC IN THE TRACTATUS 41 they're arranged as the elements of the transitive closure of a: βa,ν = { Dνa if a ∈ D, and ∀y ( y ∈ νa ↔ ∨ b∈a y = νb ) ∧ ∧ b∈a βb,ν , otherwise . Conjoin βa,ν with each formula νb 6= νc such that b, c are distinct urelements in the transitive closure of a. Finally, let γa,ν be the result of existentially generalizing this with respect to each variable νb such that b 6= a. Then HF(D) |= γa,ν [b] iff b is isomorphic to a, and so γa,ν describes a. Clearly the construction of γa,ν from a can be first-order definably replicated inside of HF(D). The formula γa,ν is given relative to the choice ν of variables for sets. To wash this out, we'll now take as defined, by induction on rank, the relation that holds between a and b iff b = γa,ν for some ν. It remains only to conjoin the requirement that the one free variable of γa,ν is ẋ. The result is a first-order formula δ in the signature of HF(D) such that HF(D) |= δ[a, b] iff b = γa,ν for some ν such that νa = ẋ. Then δ satisfies if HF(D) |= δ[a, b], then there's a φ such that b = φ and φ describes a, for all a, b. Thus, δ defines the graph of a function which takes an element of HF(D) to a nonempty class of codes of its canonical descriptions. Since every element of HF(D) has a canonical description, therefore also HF(D) |= ∀x∃yδ[x, y].  The definable describability of each element of HF(D) now yields the desired reduction of Π11 satisfaction. The reduction is more general, but I'll just state the relevant case. Let TrueΠ11 be the class of codes of Π 1 1 formulas which are true in HF(D). Lemma 9. There's a first-order formula θ such that HF(D) |= φ[a] iff HF(D),TrueΠ11 |= θ[a, φ](12) for all a and all Π11 formulas φ in the signature of HF(D). Proof. Let δ be the formula provided by Lemma 8, and let T be the predicate interpreted by TrueΠ11 . We can assume that the free variable of φ is x. Let's work out how to say that ∃ẋ(φ∧γa) belongs to TrueΠ11 for some description γa of a. Let η be the formula ∃w(Tw ∧ w = ∃ẋ(y∧z) ). Then HF(D),TrueΠ11 |= η[b, c] iff b and c are codes of Π11 formulas such that ∃ẋ(b∧c) is in TrueΠ11 . Let θ be the formula ∃z(δ[x, z] ∧ η). Noting that any metalinguistic formula φ is parameter-free, it is routine to verify that (12) holds of θ.  Proposition 21. If D is infinite, then TrueΠ11 is first-order definable relative to ValidLF. Proof. Let θ be the formula V(Z→x) where V is a predicate not in the signature of HF(D), and Z is the LF-formula of Proposition 18 which categorically axiomatizes HF(D). Suppose φ is a first-order formula in the free second-order variables ~X. 42 MAX WEISS Then HF(D) |= ∀ ~Xφ iff HF(D), ~P |= φ for all subclasses ~P of HF(D) iff M, ~P |= φ for all D-structures M ' HF(D) and all ~P ⊆ D iff HF(D),ValidLF |= θ[φ].  Proposition 22. If D is infinite, then the class of D-valid formulas of LF is Π11-complete on HF(D). Proof. Immediate from Lemma 9 and Proposition 21.  Note that a priori, the definition of D-consequence is Π11, since quantification over structures is essentially just second-order quantification over HF(D). So, Proposition 22 is as strong as possible. It shows that if the underlying universe is infinite, then there cannot be a notion of proof whose completeness would, as in the case of first-order logic, secure any reduction in the complexity of class of valid formulas. The fact which underlies this is that if the universe is infinite, then LF can itself characterize HF(D) up to isomorphism. Needless to say, a concept of proof need not serve only to situate validity or consequence in the complexity-theoretic universe. For example, the existence of a sound and complete proof procedure might be held to supply its correlative notion of consequence with some sort of an explanation or analysis. From that point of view, the limitive results of this section don't rule out philosophical importance for some sound and complete notion of proof for LF. Under the assumption that D is countable, the languages L and LF can be translated into countably infinite truth-functional logic. And so they do have a complete notion of proof (Lopez-Escobar, 1965). Unlike the notion of proof for classical logic, this cannot show the consequence relation to be any simpler than what's given by its a priori specification. Nonetheless, it might be claimed to demonstrate that the corresponding consequence relation is uniformly realized through infinitary symbolic patterns, and, therefore, still appropriately grounded in propositional structure. The philosophical development and evaluation of this proposal is a difficult problem, which must be left to further work. Let's conclude this subsection by evaluating the complexity-theoretic significance of the restriction to countable Russellian structures independently of the form-series device. We saw in §2.2 that under D-consequence, every structure is categorically axiomatized by its diagram. Consequently, a counterpart of Proposition 22 holds for the notion of D-consequence over L-formulas. The counterpart is somewhat weaker, because infinite diagrams are not in general definable over HF(D). So within HF(D), the concept of D-consequence yields the concept of truth-in-HF(D) only relative to an enumeration of D. The proof mimics that of Proposition 22. Let (HF(D),D,∈, f) be the result of adding to HF(D) a mapping f of ω onto D. Proposition 23. Suppose that D is countably infinite. ImpliesL is Π 1 1-complete on (HF(D),D,∈, f). Proof. By Lemma 9, TrueΠ11 is Π 1 1-complete on HF(D). Since HF(D) contains a first-order definable copy of (HF(D),D,∈, f), therefore TrueΠ11 must also be Π11-complete on (HF(D),D,∈, f). So it suffices to show that TrueΠ11 is first-order definable on (HF(D),D,∈, f, ImpliesL). LOGIC IN THE TRACTATUS 43 Suppose that MHF(D) is a D-structure isomorphic to HF(D) itself. Let ∆(MHF(D)) = the diagram of MHF(D). From Proposition 1 it follows that M |= ∆(MHF(D)) iff M = MHF(D). So there's a first-order formula θ such that HF(D), ImpliesL,∆(MHF(D)) |= θ[φ] iff HF(D) |= φ for all Π11 formulas φ . But there is an M, isomorphic to HF(D), whose diagram is first-order definable on (HF(D),D,∈, f). So, the class TrueΠ11 is first-order definable on (HF(D),D,∈, f, ImpliesL), as desired.  4.4. Uncountability and nonabsoluteness. So far, we've been investigating the complexity of concepts of the metatheory of L and LF relative to this or that fixed choice of D. If the universe must be finite, then the notion of tautology is in any case decidable. If the universe is fixed as some infinite set D, then the notion of LF-tautology is Π11-complete on HF(D). However, from an epistemological point of view it is not clear that the most significant measure of complexity presumes a determination of D. For as we'll see in §5, Wittgenstein appears to demand, in some sense, that the size of the universe not be prejudged. So, I want now to investigate what can be said about the complexity of D-validity as a relation between LF-formulas and arbitrary choices of D, and analogously for D-consequence with sets of L-formulas. As we've seen, the concept of being D-valid formula of LF can be expressed by a formula using second-order quantification over HF(D). The definition can also be phrased as a formula which uses a single first-order universal quantification ranging over the power set of HF(D). Can that universal quantifier be replaced with an existential one? By Proposition 22, the existential quantifier couldn't just range over HF(D), but we might hope to find some infinitary notion of "proof", or more broadly of "pattern", to witness the concept of D-validity for LF. Could such a complete, if perhaps quite profligate, notion of proof be established on the basis of the axioms of set theory? As before, it's natural to avoid assuming that D has been coded as some pure set. Here, let's adapt ZFC to handle D as a collection of urelements. Add to the language of set theory a primitive predicate D which corresponds to the property of belonging to the class D of urelements. Add an axiom to the effect that nothing in D has an element, and replace the usual axiom of extensionality with an axiom that things outside of D are the same if they have the same elements. It simplifies matters to assume that the elements of D form a set, although the result established here can be extended to the case in which the assumption is dropped. In the resulting set theory ZFCU, the theory of logics L and LF easily results by formalizing the construction which earlier took place in HF(D). In particular, the assumption that D forms a set means that the definition of validity and consequence become expressible by universal, first-order generalization over subsets of D. It is clear that the Russellian constraint on the class of all structures implies that the consequence relation discriminates between domains of different cardinality. For example, it certainly discriminates between domains of different finite cardinality. As we'll now see, the Russellian constraint also implies that the consequence relation effects transfinite discriminations as well. 44 MAX WEISS Proposition 24. (i) There is an LF-formula Uncountable such that Uncountable is D-valid iff D is uncountable. (ii) For any subset s of D, there is a set Ontos of L-formulas such that Ontos is D-satisfiable iff s has the same cardinality as D. Proof. (i) Call a binary relation successorlike if it stands to D as the successor relation stands to the finite ordinals. Let Uncountable be an LF-formula which says that R is not successorlike. Clearly Uncountable works as desired. (ii) Suppose that D is infinite, and let s be a subset of D. For some monadic predicate F , let Fs be the collection of all formulas Fa for a ∈ s, together with all formulas ¬Fa for a 6∈ s. And, for some dyadic predicate R, let B be an L-formula to the effect that R maps the F s onto D. Let Ontos = Fs ∪ {B}. Then Ontos is D-satisfiable iff there is a surjection from s onto D.  However, the following lemma shows that the condition of uncountability of the class of urelements cannot be expressed by a Σ1 formula. Lemma 10. There is no Σ1 formula θ such that ZFCU ` D א0 ↔ θ. Proof. Assume to the contrary that θ is a Σ1 formula such that ZFCU ` D א0 ↔ θ. Let V(x) formalize "the class of all sets with urelements drawn from x". For any formula φ, write φV(x) for the relativization of φ to V(x). And let Tc(x) formalize "the transitive closure of x". Clearly, ZFCU proves that any surjection from ω to a set m belongs to the class of all sets with urelements drawn from Tc(m). So, (13) ZFCU ` m 4 א0 → (D 4 א0)V(Tc(m)). Since D ≤ א0 and θ are Σ1, therefore D 4 א0 → ¬θ is Π1. Moreover, V(Tc(m)) is transitive. But, Π1 formulas are downward absolute for transitive classes (Jech, 2003, 185). So from ZFCU ` D א0 ↔ θ, it follows that (14) ZFCU ` (D 4 א0)V(Tc(m)) → ¬θV(Tc(m)). And (13) and (14) together imply (15) ZFCU ` m 4 א0 → ¬θV(Tc(m)). On the other hand, we assumed that ZFCU ` D א0 → θ. Write φm for the relativization of φ to m. Using the axiom of choice, a version of the reflection theorem implies that if ZFCU + φ ` θ then ZFCU + φ ` ∃m(m 4 א0 ∧m is transitive∧ θm)) (Jech, 2003, 165ff). So by the deduction theorem, (16) ZFCU ` D א0 → ∃m(m 4 א0 ∧m is transitive ∧ θm). We also assumed that θ is Σ1, so that θ is upward absolute for transitive classes. Consequently, (16) implies (17) ZFCU ` D א0 → ∃m(m 4 א0 ∧ θV(Tc(m)). From (15) and (17), it follows that (18) ZFCU ` D א0 → ⊥. But ZFCU + D א0 is consistent relative to ZF. So (18) contradicts the consistency of ZF.  LOGIC IN THE TRACTATUS 45 We can now put the pieces together, establishing the last technical result of this paper. Let ValidLF formalize in ZFCU the property of being a D-tautology; and let ImpliesL formalize the relation of D-consequence which holds between a set of formulas and a formula. Say that a formula is Σ1-definable in ZFCU if it is provably equivalent to a Σ1 formula. Then Proposition 25. Neither ValidLF nor ImpliesL is Σ1-definable in ZFCU. Proof. First suppose that φ is a Σ1 formula such that (19) ZFCU ` φ↔ ValidLF. Let ξ be a Σ1 term for the (coded) LF-formula Uncountable of Proposition 24. Clearly, it is provable in ZFCU that Uncountable is a tautology iff D is uncountable: (20) ZFCU ` ValidLF[ξ]↔ D א0. So by (19) and (20) there would be a Σ1 equivalent of D א0, and this contradicts Lemma 10. Similarly, suppose that ψ is a Σ1 formula such that (21) ZFCU ` ψ ↔ ImpliesL. The proof of Proposition 24 (ii) gives a method of constructing, from any subset s of D, a set Ontos of formulas which is D-satisfiable iff s has the same cardinality as D. When formalized in ZFCU, this construction yields a Σ1 term ζ in the free variable x such that (22) ZFCU ` ∀x(ImpliesL[ζ, ⊥]↔ x ≺ D) where ⊥ is a Σ1 term for the code of an L-contradiction. By (21) and (22) it follows that (23) ZFCU ` ∃x(א0 4 x ∧ ψ[ζ, ⊥])↔ א0 ≺ D. But the left side of (23) is Σ1, again contradicting Lemma 10.  By itself, Russellian constraint broadens but does not significantly complicate the class of validities. However, on classical semantics, it's compactness which ensures that if validity is witnessed by finite proofs, then so is consequence. And D-consequence is not compact, because for example a universal generalization is a D-consequence of the class of its instances. So D-consequence might turn out to be more complicated than validity. And indeed, the effects are as strong as possible: D-consequence permits no simplification of the analysis of consequence through universal generalization over structures. On the other hand, in the case of D countably infinite, the form-series device makes the concept of validity already that bad regardless of the Russellian constraint. But, the form-series device also has the effect of concentrating, into the notion of validity, the complications of the consequence relation which follow from the Russellian constraint. This implies, in the general case, that the concept of tautology, or of logically valid formula, is not even Σ1 definable in set theory. So in the general case, it is not just that we cannot replace the search through the collection of structures on some infinite domain with an enumeration of finite proofs. Rather, validity cannot in general be witnessed by any system of mathematical constructions which are identifiable by properties intrinsic to the constructions themselves. It depends essentially on the extrinsic matter of which bijections happen to exist in the mathematical universe. 46 MAX WEISS 5. Conclusion Let me now summarize the results of the previous sections, and then sketch an implication which I take to be of philosophical significance. We've seen that logic as Wittgenstein conceives it in the Tractatus differs from classical logic in two ways. The presence of the form-series device contributes to LF the capacity to express induction, and therefore allows categorical finite axiomatization of rich countable structures. Wittgenstein also relativizes the notion of structure to some fixed domain D of what has a unique name. This doesn't, by itself, significantly complicate the notion of validity. But it breaks the compactness theorem: indeed, the D-consequence relation embeds the concept of truth. When the two departures from classical logic are combined, then we obtain the notion of D-validity for LF-formulas. And this notion turns out to depend on the distinction between D countable and uncountable. I want now to consider the significance, for the Tractatus, of distinctions in the cardinality of domain. In the Tractatus, the question of the number of existing objects has a problematic status. Specifically, Wittgenstein distinguishes in the 5.55s between logic and its "application". The application of logic supposedly "decides what elementary propositions there are" (5.557a). At the same time, "logic and its application must not overlap" (5.557e), because logic "cannot anticipate" what lies in its application (5.557b). Now, the totality of objects, and the totality of elementary propositions, are alike in that each constitutes, or makes manifest, some limit to "empirical reality" (5.5561). So, the size of the universe would appear to belong to the "application" of logic, rather than to logic itself; and so it could not be anticipated by logic alone (see also 5.55b, together with 5.551a). It would seem obvious that Wittgenstein wants to maintain that relations of consequence, contradictoriness, and so on do belong to logic (6.1ff). For example, it might be supposed to belong to logic that the disjunction of some proposition with its negation is a tautology. Among what belongs to logic, then, Wittgenstein would include the consequence relation, but exclude the size of the universe. From what became the classical understanding of the consequence relation, this pair of constraints seems quite natural. Indeed, the classical understanding would exclude the size of the universe from logic: no proposition "there are at least n F s" classically entails the proposition "everything is F", yet nor is any proposition "there are at least n things" a logical truth. But as we've seen, Wittgenstein restricts the class of all structures to those with some common underlying domain. So from the Tractatus point of view, if the number of objects is finite, then the consequence relation would evince this; likewise it could be seen that the number of objects isn't any particular finite n. Wittgenstein maintains that if infinitely many objects exist, then this fact would show up in the extent of the consequence relation. Thus, if consequence belongs to logic, then something that would make itself felt in logic is the size of the universe. We've now reached something of an antinomy. It's natural to understand 5.557 as denying that logic might by itself anticipate the number of objects. But as we've just seen, logic would anticipate the number of objects if the consequence relation belonged to logic. I'm inclined to conclude that for the early Wittgenstein, the consequence relation does not belong to logic without qualification. Instead, the consequence relation emerges in the application of logic. It is in the application of logic, for example, that LOGIC IN THE TRACTATUS 47 "formal-logical properties of language and the world" would get shown through the fact that a given proposition of logic is a tautology: "the fact that a tautology is yielded by this particular way of connecting its constituents characterizes the logic of its constituents" (6.12b). The consequence relation belongs to logic only once logic is taken together with its application. One thing that is fairly clear, though, is that applying logic was not a job Wittgenstein undertook in the Tractatus itself: he gives only an illustrative example at 6.3751. So, he cannot coherently have intended the consequence relation itself to be revealed in the Tractatus. The question then arises: in what respect could that book have been intended to illuminate logic? As I suggested toward the end of §1.2.3, Wittgenstein's promised solution to philosophical problems appears to depend on the evolution of the general propositional form: it begins with the gnomic "this is how things are" at 4.5, but becomes the "general form of the truth-function" at 6. Specifically, philosophical progress would, in any particular case, involve rewriting propositions in such a way that their logical interrelations would be made manifest in the resulting propositional signs. For example, rewriting "the mug reflects white light" as a conjunction one of whose conjuncts is "the mug reflects red light" would make manifest that the former entails the latter. Wittgenstein's rather attenuated conception of philosophical progress would seem to turn on the conviction that analysis is possible: that the totality of propositions can be rewritten in such a way that all modal interdependence between propositions would be made manifest merely in the signs for them. Thus it would become clear that "the only necessity that exists is logical necessity" (6.37). This conception of philosophical progress plainly requires some independent standard for a logical relationship's being made manifest. Suppose people recognize some propositions p and q to be such that p entails q, and suppose some purported analysis to rewrite them in the signs A and B. The adequacy of such an analysis would be determined at least partly by whether the entailment of q by p is shown in the new signs A,B. Without such a standard, the adequacy of the purported analysis would be indeterminate. But what is it, exactly, for something to be made manifest, or shown? It is unlikely that Wittgenstein could have meant by this anything like "made evident" in an epistemic sense. He wrote that "it is remarkable that so exact a thinker as Frege should have appealed to the degree of self-evidence as the criterion of a logical proposition" (6.1271). The assimilation of epistemology to psychology tells against evidentness as a criterion for logical consequence. Moreover, the number of objects that exist is supposed to be shown (Wittgenstein, 1979, 19.8.19): but the epistemic status of the question of the number of objects is, to say the least, obscure. Let's say that a feature of symbols is symbolically realized if it supervenes purely on what makes anything into those symbols. I propose that Wittgenstein took something's being shown to require that it be symbolically realized. The philosophical purpose of the evolution of a general form of the proposition at 4.5 into a general form of the truth-function at 6 can then be understood at least in part as responding to the demand for a univocal account of the symbolic realization of logical consequence. Wittgenstein deigns to no concerted application of logic himself. So, if he had achieved his goal in the general form of the truth-function, then the symbolic realization of consequence would have to have been identified independently of the 48 MAX WEISS application of logic. It is tempting to conclude that this could be achieved. For example, the contradictoriness of any proposition with its negation would be so fixed, no matter what the proposition's ultimate analysis reveals it to be. Another example of something fixed by Wittgenstein's purported logical achievement would be this: that ∀xA would follow from A[a], A[b], . . . under the condition that A[a], A[b], . . . are all the instances of ∀xA. More generally, as I understand it, the Tractatus presents an attempt to show how the entirety of the consequence relation might be fixed, conditional on any determination of the totality of objects. Having proposed an account of the symbolic realization of logical consequence, Wittgenstein then could declaim a priori that logic, in its application, makes manifest "formal-logical properties of language and the world" (6.12). The propositions show the logical form of reality. They exhibit it. (4.121e-g) Thus a proposition fa shows that in its sense the object a occurs, two propositions fa and ga that they are both about the same object. If two propositions contradict one another, this is shown by their structure; similarly if one follows from another, etc. (4.1211) Within this sketch of Wittgenstein's logical aims in the Tractatus, the complexitytheoretic analyses of §4 assume a new significance. Compatibly with those analyses, is there some way in which mere propositional structure could be taken to make manifest the D-validity of all D-valid formulas, no matter the size of D? Wittgenstein suggested that axiomatic proofs represent progress toward this goal: Whether a proposition belongs to logic can be calculated by calculating the logical properties of the symbol. And this we do when we prove a logical proposition. For without troubling ourselves about a sense and a meaning, we form the logical propositions out of others by mere symbolic rules (6.126a,b). We've seen that if the number of objects is infinite, then it is completely out of the question that some notion of finite proof could suffice to demonstrate the validity of all valid formulas. But Wittgenstein himself couldn't have rested content with axiomatic proof, because he held that validity, or tautologousness, is only a limiting case of the broader phenomenon of logical consequence. If the truth of one proposition follows from the truth of others, this expresses itself in relations in which the forms of these propositions stand to one another, and we do not need to put them in these relations first by connecting them with one another in a proposition; for these relations are internal, and exist as soon as, and by the very fact that, the propositions exist. (5.131) Toward an account of the consequence relation Wittgenstein gives only this seemingly proto-Tarskian sketch: If the truth-grounds which are common to a number of propositions are all also truth-grounds of some one proposition, we say that the truth of this proposition follows from the truth of those propositions. (5.12) Unfortunately, this apparent analysis falls under a remark that "truth-functions can be arranged in series" (5.1a). So it looks to be lodged in a notational proposal which LOGIC IN THE TRACTATUS 49 is at best incomplete. The proposal is that some propositions can be written as tables of agreement and disagreement with the distributions of truth-value over elementary propositions (4.442). Surely, Wittgenstein couldn't say that all propositions can be so written, for a priori the number of elementary propositions might be infinite. The details of the construction of a general form of the truth-function through iterations of joint denial are evidently driven by a demand that propositions can be written down even if they have infinite logical ancestry. So, the truth-tabular symbolism does make some logical consequence manifest. But like a proof system for first-order logic, it is only partial. The question then remains: is there some very loose, even wildly profligate, notion of symbolic pattern, which could serve to make manifest all instances of the D-consequence relation, or even the D-validity of all D-valid formulas, no matter the size of D? The results of §4.4 suggest that the answer to this question is no. We may suppose the relevant "pattern" to be exemplifiable by sets at any level of the cumulative hierarchy, and require only that exemplification of the pattern by a set be discernible by a first-order formula whose quantifiers are restricted to the set's transitive closure. No first-order formula could, in this way, univocally discern a pattern which would be adequate to Wittgenstein's notion of consequence, not without prejudging the number of objects. At least, that's the drift of Proposition 25. The underlying problem is that Wittgenstein's concept of consequence detects the difference between countable and uncountable domains: by Proposition 24, there is even a single LF-formula which is valid iff the domain is uncountable. Whether some set is countable doesn't depend only on its internal structure, but on the extrinsic matter of which functions happen to exist in the mathematical universe. The sensitivity of consequence to distinctions in the transfinite suggests that there is no reasonable notion of symbolic pattern whose exemplifications could serve to realize all instances of the consequence relation-at least not without some a priori constraint on the number of objects. Thus, the reason Wittgenstein's concept of consequence cannot in general be realized in some univocally specified kind of symbolic pattern is that so conceived, consequence depends on distinctions of transfinite cardinality. It might be wondered whether this sensitivity to the transfinite could be trimmed away without great loss. But its origins were already recorded way back in Proposition 2: that Wittgenstein's concept of consequence embeds the concept of truth. In turn, the embedding of truth in consequence is immediate from the book's core thesis, that a proposition is a truth-function of elementary propositions. So the results are deeply rooted. To conclude, Wittgenstein's early conception of philosophical progress requires some independent standard for a logical relationship's being made manifest in signs. The evolution of the general form of a proposition into the general form of a truth-function looks like a gesture toward such a standard. Yet that attempt proceeds without any concerted application of logic, and hence avowedly without prejudice to the size of the universe. The results of this paper suggest, however, that without prejudging the number of objects, no single concept of manifestation could be adequate to Wittgenstein's concept of consequence. 6. Further work 1. formal procedures. The implementation in LF of the form-series device does not accommodate everything Wittgenstein might have accepted as a formal procedure. 50 MAX WEISS For example, LF does not allow operator-signs to contain form-series expressions; nor does it accommodate many-place or multigrade operations. Could a richer operation-scheme maintain a tractable semantics but yield a more expressive logic? I have also not attempted in this paper to clarify the interaction between the form-series device and the interpretation of objectual variables which is developed by Wehmeier (2004). The example of §2.3 gives an expression of the ancestral under the exclusive interpretation. But Wehmeier's translation schemes do not extend straightforwardly to LF, and I do not know how to avoid the use of equality in proving the adequacy of LF to finitary induction (see Lemma 6 and Propositions 8 and 13). 2. the bar notation. Wittgenstein introduces a bar notation, which is said to convert a propositional variable ξ into an expression ξ of the plurality of its values (see especially 5.501). In §2.3, we saw that form-series contexts complicate the interpretation of free variables; I handled the problem somewhat brutally by dividing semantic evaluation into two stages. A more interesting approach is to introduce Wittgenstein's bar notation into the object-language. In a propositional sign, each enclosed propositional variable would have a bar written somewhere above it, with the priority of the expansions indicated by the vertical order of the bars. It is tempting to speculate that Wittgenstein's use of a bar, rather than an "inline" device, represents an attempt to escape the parse tree in some such way as we've seen 5.501 to require. 3. philosophy of arithmetic. In this paper, I've argued that the form-series device permits definitions by induction on ordinary dyadic relations, like adjacency or temporal priority. Any such ordinary relation thereby generates material analogues of the system of finite ordinals, together with addition, multiplication, and indeed all arithmetically definable relations. Within this account, ordinal concepts are generated by an operation of taking the relative product of a relation with itself. So understood, "a number is an exponent of an operation" (6.021). Frascolla (1997) offers another perspective on 6.021, developing an operational interpretation of the equational fragment of Peano arithmetic; he concludes that the interpretation cannot be extended to quantified arithmetical formulas. Can the two appearances of arithmetic be somehow understood as complementary? 4. a presumption of countability? Some commentators do already appear to find Wittgenstein to be committed in the Tractatus to the domain's countability (Ricketts, 2012). As I've already noted, there exist complete notions of "proof" for countably infinite truth-functional logic. The N -operator lends itself to elegant proof-theoretic analysis, particularly through a transfinite generalization of "bilateral" proof systems (Smiley 1996 and Rumfitt 2006). Could some such notion be relevantly found to underwrite a realization of logical consequence by symbolic patterns? And can a presumption of countability be squared with Wittgenstein's insistence that the number of names not be prejudged? References Ackermann, W. (1937). Die widerspruchsfreiheit der allgemeinen mengenlehre. Mathematische Annalen, 114:305–315. Avron, A. (2003). Transitive closure and the mechanization of mathematics. In Thirty Years of Automating Mathematics, pages 149–171. Kluwer Academic Publishers. Barwise, J. (1975). Admissible Sets and Structures. Springer-Verlag, Berlin. LOGIC IN THE TRACTATUS 51 Barwise, J. (1977). On Moschovakis closure ordinals. Journal of Symbolic Logic, 42(2):292–296. Bays, T. (2001). On Tarski on models. Journal of Symbolic Logic, 66(4):1701–1726. Büchi, J. (1960). On a decision method in restricted second-order arithmetic. In International Congress for Logic, Methodology and Philosophy of Science, pages 1–11. Fine, K. (2010). Towards a theory of part. Journal of Philosophy, 107(11):559–589. Floyd, J. (2001). Number and ascriptions of number in Wittgenstein's Tractatus. In Floyd, J. and Shieh, S., editors, Future Pasts. Harvard University Press, Cambridge, MA. Fogelin, R. (1976). Wittgenstein. Routledge and Kegan Paul. Frascolla, P. (1997). The "Tractatus" system of arithmetic. Synthese, 112(3):353– 378. Frege, G. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Louis Nebert, Halle. Geach, P. (1981). Wittgenstein's operator N . Analysis, 41(4):178–81. Goldfarb, W. (2012). Wittgenstein against logicism. Unpublished. Heck, R. (2011). A logic for Frege's theorem. In Frege's Theorem. Oxford University Press, New York. Henkin, L. (1950). Completeness in the theory of types. Journal of Symbolic Logic, 15(2):81–91. Hintikka, J. (1956). Identity, variables, and impredicative definitions. Journal of Symbolic Logic, 21(3):225–245. Jech, T. (2003). Set Theory. Springer, third edition. Kirby, L. (2009). Finitary set theory. Notre Dame Journal of Formal Logic, 50(3):227–244. Krivine, J.-L. (1998). Théorie des Ensembles. Cassini, Paris. Lopez-Escobar, E. G. K. (1965). An interpolation theorem for denumerably long formulas. Fundamenta Mathematicae, LVII:253–272. Lopez-Escobar, E. G. K. (1966). On defining well-orderings. Fundamenta Mathematicae, 59(1):13–21. Mancosu, P. (2010). Fixedversus variable-domain interpretations of Tarski's account of logical consequence. Philosophy Compass, 5(9):745–759. Martin-Löf, P. (1996). On the meanings of the logical constants and the justifications of the logical laws. Nordic Journal of Formal Logic, 1(1):11–60. Mirimanoff, D. (1917). Les antinomies des Russell et de Burali-Forti et le problème fondamentale de la théorie des ensembles. L'Enseignment Mathématique, 19. Potter, M. (2009). The logic of the Tractatus. In Gabbay, D. M. and Woods, J., editors, From Russell to Church, volume 5 of Handbook of the History of Logic. Elsevier. Ricketts, T. (2012). Logical segmentation and generality in Wittgenstein's Tractatus. In Potter, M. and Sullivan, P., editors, Wittgenstein's Tractatus: History and Interpretation. Oxford University Press. Rogers, B. and Wehmeier, K. (2012). Tractarian first-order logic: identity and the N -operator. Review of Symbolic Logic, 5(4):538–573. Rumfitt, I. (2006). 'Yes' and 'no'. Mind, 109(436):781–824. Russell, B. (1903). The Principles of Mathematics. Allen and Unwin, London. Russell, B. (1905). On denoting. Mind, 14(56):479–493. 52 MAX WEISS Russell, B. (1918). The philosophy of logical atomism. In Marsh, R. C., editor, Logic and Knowledge. Allen and Unwin. Shoenfield, J. (1967). Mathematical Logic. A K Peters, Natick, MA. Smiley, T. (1996). Rejection. Analysis, 56:1–9. Soames, S. (1983). Generality, truth-functions, and expressive capacity in the Tractatus. Philosophical Review, 92(4):573–589. Sullivan, P. (2004). The general form of the proposition is a variable. Mind, 113(449):43–56. Sundholm, G. (1992). The general form of the operation in Wittgenstein's Tractatus. Grazer Philosophische Studien, 42:57–76. Tarski, A. (1936). O pojeciu wynikania logicznego. Przeglad Filozoficzny, 39:58–68. Väänänen, J. (2001). Second order logic and foundations of mathematics. Bulletin of Symbolic Logic, 7(4). Wehmeier, K. (2004). Wittgensteinian predicate logic. Notre Dame Journal of Formal Logic, 45:1–11. Wehmeier, K. (2008). Wittgensteinian tableaux, identity, and codenotation. Erkenntnis, 69(3):363–376. Wehmeier, K. (2009). On Ramsey's 'silly delusion' regarding Tractatus 5.53. In Primiero, G. and Rahman, S., editors, Acts of Knowledge History, Philosophy and Logic. College Publications. Whitehead, A. N. and Russell, B. (1910-1913). Principia Mathematica. Cambridge University Press. Wittgenstein, L. (1921). Logische-philosophische abhandlung. Annalen der Naturphilosophie, XIV:168–198. Wittgenstein, L. (1922). Tractatus Logico-Philosophicus. Kegan Paul. Wittgenstein, L. (1961). Tractatus Logico-Philosophicus. Routledge & Kegan Paul. Wittgenstein, L. (1971). Prototractatus. Routledge & Kegan Paul, London. Wittgenstein, L. (1979). Notebooks 1914-1916. Blackwell, Oxford. Yablo, S. (1993). Paradox without self-reference. Analysis, 53(4):252–252. Boston University, Boston, MA, 02215 USA E-mail address: max@whythis.net URL: http://whythis.net