We make certain notational conventions. These are referred to as CL (Computational Logic). The relation of interchangeability is introduced as the basic connection between logical formulas. This approach lends perspicuity to the results of sentential calculus. With its technical devices CL is able to rephrase logical theorems in rather succinct manner. Our exposition tries to steer a middle course between informality and strict rigor.

It is felt that the method of CL offers advantages for the teaching of logic. Proofs are algorithmic and resemble those of elementary algebra. All inferences are reversible and practically non-tentative.

Sign is a primitive term of CL. Its denning property is a capacity for entering into binary combination with other signs, or with itself, according to this convention:

x and y are signs if, and only if, (x y) is a sign. Bracketing is looked upon as an operation on signs in terms of which other operations are definable. The practice of some authors in classifying brackets under the heading of symbols, seems to us questionable; for unlike symbols or signs brackets are never used to denote anything. Brackets enter into the composition of signs, not to denote a grouping, but rather to exhibit it, in the manner of a diagram.

An unending list of letters, with or without subscripts,

serve to denote arbitrary signs. An arbitrary sign may or may not have other signs as parts. The numeral “2” is used as a constant. Bracketing abbreviation is as follows:

and so on. Outermost brackets will ordinarily be omitted. This kind of bracketing may be termed left-associative. For convenience, these bracketing conventions are crystallized into a rule.

In this note, we consider models of the theories of valued algebraically closed fields and convexly valued real closed fields, their reducts to the pure field or ordered field language respectively, and expansions of these by predicates which are definable in the valued field. We show that, in terms of definability, there is no structure properly between the pure (ordered) field and the valued field. Our results are analogous to several other definability results for reducts of algebraically closed and real closed fields; see [9], [10], [11] and [12]. Throughout this paper, definable will mean definable with parameters.

Theorem A. Let ℱ = (F, +, ×, V) be a valued, algebraically closed field, where V denotes the valuation ring. Let A be a subset ofFndefinable in ℱv. Then either A is definable in ℱ = (F, +, ×) or V is definable in.

Theorem B. Let ℛv = (R, <, +, ×, V) be a convexly valued real closed field, where V denotes the valuation ring. Let Abe a subset ofRndefinable in ℛv. Then either A is definable in ℛ = (R, <, +, ×) or V is definable in.

The proofs of Theorems A and B are quite similar. Both ℱv and ℛv admit quantifier elimination if we adjoin a definable binary predicate Div (interpreted by Div(x, y) if and only if v(x) ≤ v(y)). This is proved in [14] (extending [13]) in the algebraically closed case, and in [4] in the real closed case. We show by direct combinatorial arguments that if the valuation is not definable then the expanded structure is strongly minimal or o-minimal respectively. Then we call on known results about strongly minimal and o-minimal fields to show that the expansion is not proper.

We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C.

We show that it is relatively consistent with ZFC to have PCF structures of height δ, for all ordinals δ < ω3.

Among the results of this paper are the following:

1. Every Boolean (ultra)power is the union of an updirected elementary family of direct ultrapowers.

2. Under certain conditions, a finitely iterated Boolean ultrapower is isomorphic to a single Boolean ultrapower.

3. A ω-bounded filtral power is an elementary substructure of a filtral power.

4. Let be an elementary class closed under updirected unions (e.g., if is an amalgamation class); then is closed under finite products if and only if is closed under reduced products if and only if is a Horn class.

We introduce a notion of syntactical truth predicate (s.t.p.) for the second order arithmetic PA2. An s.t.p. is a set T of closed formulas such that:

(i) T(t = u) if and only if the closed first order terms t and u are convertible, i.e., have the same value in the standard interpretation

(ii) T(A → B) if and only if (T(A) ⇒ T(B))

(iii) T(∀xA) if and only if (T(A[x ← t]) for any closed first order term t)

(iv) T(∀X A) if and only if (T(A[X ← ∆]) for any closed set definition ∆ = {x ∣ D(x)}).

S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical) validity and have main model properties. In particular, their existence is equivalent to the existence of an ω-model of PA2, this fact being provable in PA2 with arithmetical comprehension only.

Kantorovich and Livenson [6] initiated the study of infinitary Boolean operations applied to the subsets of the Baire space and related spaces. It turns out that a number of interesting collections of subsets of the Baire space, such as the collection of Borel sets of a given type (e.g. the F σ sets) or the collection of analytic sets, can be expressed as the range of an ω-ary Boolean operation applied to all possible ω-sequences of clopen sets. (Such collections are called clopen-ω-Boolean.) More recently, the ranges of I-ary Boolean operations for uncountable I have been considered; specific questions include whether the collection of Borel sets, or the collection of sets at finite levels in the Borel hierarchy, is clopen-I-Boolean.

The main purpose of this paper is to give a characterization of those collections of subsets of the Baire space (or similar spaces) that are clopen-I-Boolean for some I. The Baire space version can be stated as follows: a collection of subsets of the Baire space is clopen-I-Boolean for some I iff it is nonempty and closed downward and σ-directed upward under Wadge reducibility, and in this case we may take I = ω 2. The basic method of proof is to use discrete subsets of spaces of the form K 2 to put a number of smaller clopen-I-Boolean classes together to form a large one. The final section of the paper gives converse results indicating that, at least in some cases, ω 2 cannot be replaced by a smaller index set.