Search

Evolving recurrent neural networks represent a natural model of computation beyond the Turing limits. Here, we consider evolving recurrent neural networks working on infinite input streams. The expressive power of these networks is related to their attractor dynamics and is measured by the topological complexity of their underlying neural \(\omega \)-languages. In this context, the deterministic and non-deterministic evolving neural networks recognize the (boldface) topological classes of \(BC(\varvec{\mathrm {\Pi }}^0_2)\) and \(\varvec{\mathrm {\Sigma }}^1_1\) \(\omega \)-languages, respectively. These results can actually be significantly refined: the deterministic and nondeterministic evolving networks which employ \(\alpha \in 2^\omega \) as sole binary evolving weight recognize the (lightface) relativized topological classes of \(BC(\mathrm {\Pi }^0_2)(\alpha )\) and \(\mathrm {\Sigma }^1_1(\alpha )\) \(\omega \)-languages, respectively. As a consequence, a proper hierarchy of classes of evolving neural nets, based on the complexity of their underlying evolving weights, can be obtained. The hierarchy contains chains of length \(\omega _1\) as well as uncountable antichains.

Allow me to make a personal preliminary remark on how this article arose. Some time ago I got caught up in a dispute with a colleague, of whom I think very highly, that was conducted via e-mail and lasted two to three months. I believed that I was only stating something rather obvious and not at all original, but I was unable to convince my discussion partner.

FAUST $^{\mathsf 2}$ is a software tool that generates formal abstractions of possibly non-deterministic discrete-time Markov processes dtMP defined over uncountable continuous state spaces. A dtMP model is specified in MATLAB and abstracted as a finite-state Markov chain or a Markov decision process. The abstraction procedure runs in MATLAB and employs parallel computations and fast manipulations based on vector calculus, which allows scaling beyond state-of-the-art alternatives. The abstract model is formally put in relationship with the concrete dtMP via a user-defined maximum threshold on the approximation error introduced by the abstraction procedure. FAUST $^{\mathsf 2}$ allows exporting the abstract model to well-known probabilistic model checkers, such as PRISM or MRMC. Alternatively, it can handle internally the computation of PCTL properties e.g. safety or reach-avoid over the abstract model. FAUST $^{\mathsf 2}$ allows refining the outcomes of the verification procedures over the concrete dtMP in view of the quantified and tunable error, which depends on the dtMP dynamics and on the given formula. The toolbox is available at http://sourceforge.net/projects/faust2/

In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition refines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a longstanding open problem concerning the representation of memoryless continuous time by memoryfull continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems.

We show a correspondence between a predicative characterization of quantum states, we have recently introduced, and bi-logic, proposed by the Chilean psychoanalyst I. Matte Blanco. In bi-logic, the logic of the unconscious is characterized by "infinite" objects and by the "symmetric mode", without negation and logical consequence. In the quantum model it is possible to define a class of first order domains, called virtual singletons, that are uncountable, and that allow a generalization of the notion of duality, called symmetry. Symmetry makes negation and logical consequence collapse, in favour of different links between judgements, that are due to quantum correlations.

We demonstrate how polyhedral methods of mathematical programming can be developed for and applied to computing optimal solutions for large instances of a classical geometric optimization problem with an uncountable number of constraints and variables.

Smullyan is one of the great popular expositors of logic, as well as author of several books on puzzles and games. The probability version of Cantor’s proof is re-cast following Smullyan’s angle as a two-player game, further challenging readers who doubt the correctness of Cantor’s argument.

We examine the extent to which well orders satisfy the properties of local computability, which measure how effectively the finite suborders of the ordinal can be presented. Known results prove that all computable ordinals are perfectly locally computable, whereas \(\omega_1^\mathrm{CK}\) and larger countable ordinals are not. We show that perfect local computability also fails for uncountable ordinals, and that ordinals \(\alpha\geq \omega_1^\mathrm{CK}\) are θ-extensionally locally computable for all \(\theta \omega_1^\mathrm{CK}\), nor when \(\theta=\omega_1^\mathrm{CK}\leq\alpha

This chapter discusses the famous diagonal method of Georg Cantor to prove that the real numbers are uncountable. Two variants on the classic proof are presented, one involving probability.

This paper investigates some issues arising in categorical models of reversible logic and computation. Our claim is that the structural (coherence) isomorphisms of these categorical models, although generally overlooked, have decidedly non-trivial computational content. The theory of categorical coherence is based around reversible structural operations (canonical isomorphisms) that allow for transformations between related, but distinct, mathematical structures. A number of coherence theorems are commonly used to treat these transformations as though they are identity maps, from which point onwards they play no part in computational models. We simply wish to point out that doing so overlooks some significant computational content. We give a single example (taken from an uncountably infinite set of similar examples, and based on structures used in models of reversible logic and computation) of a category whose structural isomorphisms manipulate modulo classes of natural numbers. We demonstrate that the coherence properties that usually allow us to ignore these structural isomorphisms in fact correspond to countably infinite families of non-trivial identities in modular arithmetic. Further, proving the correctness of these equalities without recourse to the theory of categorical coherence appears to be a hard task.

As Grothendieck noticed in his letter to Faltings, a k-rational point in the boundary of a good compactification contributes a packet of sections, see Grothendieck ( Schneps, L., Lochak, P. (eds.), LMS Lecture Notes vol. 242, 1997), page 8, not necessarily accounted for by rational points of the variety. These sections will here be called cuspidal sections. In the general framework, cuspidal sections are best constructed by Deligne’s theory of tangential base points, see Deligne ( Mathematical Sciences Research Institute Publications, vol. 16, 1989). Cuspidal sections have been studied by Nakamura in the profinite setting (Nakamura, J. Reine Angew. Math. 405:117–130, 1990; J. Reine Angew. Math. 411:205–216, 1990; Math. Zeit. 206(4):617–622, 1991), while Esnault and Hai ( Adv. Math. 218(2):395–416, 2008) discussed the analogue in a tannakian setting.We will define packets of cuspidal sections and show in Proposition 250 that for hyperbolic curves over arithmetic base fields these packets are either empty or uncountable. Then we describe and extend Nakamura’s characterisation of cuspidal sections in terms of cyclotomically normalized pro-cyclic subgroups in order to cover the description foreseen by Grothendieck in his letter.We will also discuss the birational analogue of the section conjecture when smooth geometrically connected varieties are replaced by their function fields: by passing to the limit over all open subschemes, all sections in this birational setup are predicted to become cuspidal. For curves over finite extensions of \({\mathbb{Q}}_{p}\) the birational section conjecture holds by Koenigsmann’s Theorem, and we have even a 2-step nilpotent pro-p version due to Pop. Over an algebraic number field there are some partial results, see Theorem 265, and for curves over \(\mathbb{Q}\) we even have a full group theoretic description of all birationally liftable sections in Theorem 269 with respect to certain \({GL }_{2}\)-representations.For ease of exposition we will work in characteristic 0 only.

Omega-rule used by W. Buchholz to give an ordinal-free proof-theoretic analysis of \(\it \Pi^1_1\)-comprehension axiom has uncountable set of premises. We show how to make this set countable preserving the results and ideas of cut-elimination proof by Buchholz. The price is introduction of non-well founded derivation-like figures and use of continuous cut-elimination.

It follows from the results of Chapters 5, 6, 7 that the number of affine equivalence classes of closed (k, n-k)-spherical tube hypersurfaces in ℂ n+1, with n ≤ 2k, is finite in the cases: (a) k = n, (b) k = n - 1, and (c) k = n - 2 with n ≤ 6. The first result of this short chapter states that this number is infinite (in fact uncountable) in the following situations: (i) k = n - 2 with n ≥ 7, (ii) k = n - 3 with n ≥ 7, and (iii) k ≤ n - 4. The question about the number of affine equivalence classes in the only remaining case k = 3, n = 6 had been open since 1989 until it was resolved by Fels and Kaup in 2009. They gave an example of a family of (3, 3)-spherical tube hy- persurfaces in ℂ7 that contains uncountably many pairwise affinely non-equivalent elements. The original approach due to Fels and Kaup is explained in Chapter 9. In this chapter we present the Fels-Kaup family but deal with it by different methods. Namely, we give a direct proof of the sphericity of the hypersurfaces in the fam- ily and use the j-invariant to show that the family indeed contains an uncountable subfamily of pairwise affinely non-equivalent hypersurfaces.

In response to a 1997 problem of M. Vidyasagar, we state a necessary and sufficient condition for distribution-free PAC learnability of a concept class C under the family of all non-atomic (diffuse) measures on the domain Ω. Clearly, finiteness of the classical Vapnik-Chervonenkis dimension of C is a sufficient, but no longer necessary, condition. Besides, learnability of C under non-atomic measures does not imply the uniform Glivenko-Cantelli property with regard to non-atomic measures. Our learnability criterion is stated in terms of a combinatorial parameter VC(C mod ω1) which we call the VC dimension of C modulo countable sets. The new parameter is obtained by "thickening up" single points in the definition of VC dimension to uncountable "clusters". Equivalently, VC(C mod ω1) ≤ d if and only if every countable subclass of C has VC dimension ≤ d outside a countable subset of Ω. The new parameter can be also expressed as the classical VC dimension of C calculated on a suitable subset of a compactification of Ω. We do not make any measurability assumptions on C, assuming instead the validity of Martin's Axiom (MA).

We will develop a tight closure theory in characteristic zero which is different from the Hochster-Huneke approach discussed briefly in §5.6. In this chapter we treat the affine case, that is to say, we develop the theory for algebras of finite type over an uncountable algebraically closed field K of characteristic zero; the general local case will be discussed in Chapter 7. Recall that under the Continuum Hypothesis, any uncountable algebraically closed field K of characteristic zero is a Lefschetz field, that is to say an ultraproduct of fields of positive characteristic, by Theorem 2.4.3 and Remark 2.4.4. In particular, without any set-theoretic assumption, ℂ, the field of complex numbers, is a Lefschetz field. The idea now is to use the ultra-Frobenius, that is to say, the ultraproduct of the Frobenii (see Definition 2.4.21), in the same manner in the definition of tight closure as in positive characteristic. However, the ultra-Frobenius does not act on the affine algebra but rather on its ultra-hull, so that we have to introduce a more general setup. It is instructive to do this first in an axiomatic manner (§6.1) and then specialize to the situation at hand (§6.2). We briefly discuss a variant construction in §6.3, and conclude in §6.4 with another example how ultraproducts can be used to transfer constructions from positive to zero characteristic, to wit, the balanced big Cohen-Macaulay algebras of Hochster and Huneke.

The CTL * model-checking problem is thoroughly studied and is fully understood for finite and countable state spaces. Yet, in most models arising in the sciences and engineering the system's sate space is uncountable. Then, the standard computability and complexity theory is inapplicable but the semantics of CTL * has to be in some sense computable to allow for model-checking algorithms that are implementable on digital computers. To tackle this problem, we consider discrete-time continuous-space dynamic systems for which we study the computability of the standard semantics of CTL * and provide a variant thereof computable in the sense of Type-2 Theory of Effectivity.

In this paper we consider uncountable classes recognizable by ω-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language L from the class plus an ω-index a and outputs a sequence of ω-automata such that all but finitely many of these ω-automata accept the index α iff α is an index for L. It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin's tell-tale condition. For explanatory learning, such a result needs that a suitable indexing of the class is chosen. On the one hand, every class satisfying Angluin's tell-tale condition is vacillatory learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen. We also consider a notion of blind learning. On the one hand, a class is blind explanatory (vacillatory) learnable if and only if it satisfies Angluin's tell-tale condition and is countable; on the other hand, for behaviourally correct learning there is no difference between the blind and non-blind version. This work establishes a bridge between automata theory and inductive inference (learning theory).

The numerical results concerning the scaling properties of the disorder induced metal-insulator transition are reported. The critical exponents for the different universality classes are reviewed. Evidence is provided that sufficiently close to the critical point, one-parameter scaling holds for an uncountable set of scaling variables, the complete joined spectral distributions, for instance. In particular, the critical level statistics is independent of the size, depends on the dimensionality of the system, and on the symmetry class. Studies of the influence of the Coulomb repulsion on the localisation of few particles are briefly reported.

This paper is divided into two parts. The first part concerns several standard scenarios for how short-range spin glasses might behave at low temperature. Earlier theorems of the authors are reviewed, and some new results presented, including a proof that, in a thermodynamic system exhibiting infinitely many pure states and with the property (such as in replica-symmetrybreaking scenarios) that mixtures of these states manifest themselves in large finite volumes, there must be an uncountable infinity of states. In the second part of the paper, we offer some conjectures and speculations on possible unusual scenarios for the low-temperature phase of finite-range spin glasses in various dimensions. We include a discussion of the possibility of a phase transition without broken spin-flip symmetry, and provide an argument suggesting that in low dimensions such a possibility may occur. The argument is based on a new proof of Fortuin-Kasteleyn random cluster percolation at nonzero temperatures in dimensions as low as two. A second speculation considers the possibility, in analogy to certain phenomena in Anderson localization theory, of a much stronger type of chaotic temperature dependence than has previously been discussed: one in which the actual state space structure, and not just the correlations, vary chaotically with temperature.

We introduce the notion of a locally computable structure, a natural way of generalizing the notions of computable model theory to uncountable structures ${\mathcal{S}}$ by presenting the finitely generated substructures of $\S$ effectively. Our discussion emphasizes definitions and examples, but does prove two significant results. First, our notion of m-extensional local computability of ${\mathcal{S}}$ ensures that the Σ n -theory of ${\mathcal{S}}$ will be Σ n for all n≤ m+ 1. Second, our notion of perfect local computability is equivalent (for countable structures) to the classic definition of computable presentability.

In the BSS model of real number computations we prove a concrete and explicit semi-decidable language to be undecidable yet not reducible from (and thus strictly easier than) the real Halting Language. This solution to Post's Problem over the reals significantly differs from its classical, discrete variant where advanced diagonalization techniques are only known to yield the existence of such intermediate Turing degrees. Then we strengthen the above result and show as well the existence of an uncountable number of incomparable semi-decidable Turing degrees below the real Halting problem in the BSS model. Again, our proof will give concrete such problems representing these different degrees.

We consider copies and constructivizations of structures in admissible sets. In the first section we survey results about copies of countable structures in hereditary finite superstructures and definability (so called syntactical conditions of intrinsically computable properties) and state some conjectures about the uncountable case. The second section is devoted to constructivizations of uncountable structures in “simplest” uncountable admissible sets (more precisely, in hereditary finite superstructures over the models of c-simple theories). The third section contains some results on constructivizations of admissible sets within themselves.

Metric labelled transition systems are labelled transition systems whose states and actions form (pseudo)metric spaces. These systems can capture a large class of timed transition systems, including systems with uncountably many states and uncountable nondeterminism. In this paper a behavioural pseudometric is introduced for metric labelled transition systems. The behavioural distance between states, a nonnegative real number, captures the similarity of the behaviour of those states. The smaller the distance, the more alike the states are. In particular, the distance between states is 0 iff they are bisimilar. Three different characterisations of this pseudometric are given: a fixed point, a logical and a coinductive characterisation. These generalise the fixed point, logical and coinductive characterisations of bisimilarity.

Here we no longer assume Ω is countable. We assume given Ω and a σ-algebra A⊂(2Ω. (Ω, A) is called a measurable space. We want to construct probability measures on A. When Ω is finite or countable we have already seen this is simple to do. When Ω is uncountable, the same technique does not work; indeed, a “typical” probability P wih have P({ω|)=0 for all ω, and thus the family of all numbers P({ω|) for ω∈Ω does not characterize the probability P in general.

4.1 Projective spectra of linear spaces 4.2 Insertion: The completion functor 4.3 Projective spectra of locally convex spaces

This paper presents an approach to the use of rough integrals in signal analysis. For each set of sample sensor signal values, the average accuracy of set approximation is computed using a rough integral. In rough set theory, set approximation is carried out in non-empty, finite universes of objects. In this article, by contrast, set approximation is carried out inside non-empty, uncountable sets (universes) of points. This study is motivated by an interest in classifying sample values for various types of sensors. One result of this study has been the introduction of discrete integrals based on rough set theory. The rough integrals used in this article have practical implications, since these integrals serve as an aid in sensor reduction and in pattern recognition in analyzing segments of continuous signals. In the context of sensor reduction, rough integrals provide a basis for determining the relevance of sensors over a particular sampling period. In the context of pattern recognition, rough integrals can be useful in doing such things as classifying radar weather data, vehicular traffic patterns, robot navigation and waveforms of power system faults. A sample application of the rough integral in estimating the accuracy of set approximation of a sensor signal is given. The contribution of this article is an approach to measuring the relevance and accuracy of approximation of sample sensor signal values based on rough set methods.

We give a purely model-theoretic (denotational) characterization of the semantics of logic programs with negation allowed in clause bodies. In our semantics (the first of its kind) the meaning of a program is, as in the classical case, the unique minimum model in a program-independent ordering. We use an expanded truth domain that has an uncountable linearly ordered set of truth values between False (the minimum element) and True (the maximum), with a Zero element in the middle. The truth values below Zero are ordered like the countable ordinals. The values above Zero have exactly the reverse order. Negation is interpreted as reflection about Zero followed by a step towards Zero; the only truth value that remains unaffected by negation is Zero. We show that every program has a unique minimum model MP, and that this model can be constructed with a TP iteration which proceeds through the countable ordinals. Furthermore, collapsing the true and false values of the infinite-valued model MP to (the classical) True and False, gives a three-valued model identical to the well-founded one.

Classically, computability is introduced explicitly for functions f :⊆ (Σ*)n → Σ* on the set Σ* of finite words over an arbitrary finite alphabet Σ, for example by means of Turing machines. For computing functions on other sets M such as natural numbers, rational numbers or finite graphs, words are used as “code words” or “names” of elements of M. Under this view a machine transforms words to words without “understanding” the meaning given to them by the user. Equivalently, one can start with computable functions on the natural numbers instead of words and use numbers as “names”. Since the set Σ* of words over a finite alphabet is only countable, this method cannot be applied for introducing computability on uncountable sets M like the set ℝ of real numbers, the set of open subsets of ℝ or the set C[0; 1] of real continuous functions on the interval [0; 1].

Given an input sequence of data, a "rigid" pattern is a repeating sequence, possibly interspersed with "dont care" characters. In practice, the patterns or motifs of interest are the ones that also allow a variable number of gaps (or "dont care" characters): we call these the flexible motifs. The number of rigid motifs could potentially be exponential in the size of the input sequence and in the case where the input is a sequence of real numbers, there could be uncountably infinite number of motifs (assuming two real numbers are equal if they are within some δ > 0 of each other). It has been shown earlier that by suitably defining the notion of maximality and redundancy, there exists only a linear (or no more than 3n) number of irredundant motifs and a polynomial time algorithm to detect these irredundant motifs. Here we present a uniform framework that encompasses both rigid and flexible motifs with generalizations to sequence of sets and real numbers and show a somewhat surprising result that the number of irredundant flexible motifs still have a linear bound. However, the algorithm to detect them has a higher complexity than that of the rigid motifs.

This chapter presents an assessment procedure that is similar in spirit to those described in Chapter 10, but different in a key aspect: it is based on a finite Markov chain rather than on a Markov process with an uncountable set of Markov states. As a consequence, the procedure requires less storage and computation and can thus be implemented on a small machine.

The paper considers the problem of classifying countable-uncountable entities during the process of Knowledge Acquisition (KA) from texts. Since one of the main goals of KA is to identify types, means to distinguish new types, instances and individuals become particularly important. We review briefly related studies to show that the distinction countable-uncountable depends on the considered natural language, context usage and the domain; then countability is a perspective to look at a closed world since there is no universal general taxonomy. Finally we propose an internal ontological solution for mass objects which suits to a. project for generation of multilingual Natural Language (NL) explanations from Conceptual Graphs (CG).

Quasiperiodic tilings are those tilings in which finite patterns appear regularly in the plane. This property is a generalization of the periodicity; it was introduced for representing quasicrystals and it is also motivated by the study of quasiperiodic words. We prove that if a tile set can tile the plane, then it can tile the plane quasiperiodically — a surprising result that does not hold for periodicity. In order to compare the regularity of quasiperiodic tilings, we introduce and study a quasiperiodicity function and prove that it is bounded by x↦x+c if and only if the considered tiling is periodic. At last, we prove that if a tile set can be used to form a quasiperiodic tiling which is not periodic, then it can form an uncountable number of tilings.

In Section 1 we describe the fundamental notions of the theory of ordered sets and of order homomorphisms [order preserving mappings) between such sets. Sections 2 and 3 deal respectively with order homomorphisms on finite and countable ordered sets. In Section 4 we discuss various order separability conditions which lead to representations of orders on uncountable sets. In Section 5, with the help of material from Section 4, we apply Cantor’s two theorems on the existence of order homomorphisms. The final section, Section 6, introduces the link between orders and topologies.

This paper introduces the global limit set of a morphism language. This set is generated by a process called “reversed morphism” which is a systematic way to embed words in each other. If the morphism is recognizable, i.e. locally invertible, then the limit set is shown in bijection with a rational language. This allows us to deduce that the limit set can be uncountable, can be structured by a natural dynamics and can contain only strictly quasiperiodic words.

The global limit set has been introduced in a preceding work as a generalization of the way of generating infinite words by substitution systems, i.e. by iterating a morphism on a finite alphabet. We prove here that the boundary set (the “adherence set”) of a progressive substitution language is equal to its global limit set plus a simple set of words. This allows us to exhibit conditions to conclude that the full boundary is explicitly constructible, rationally codable and uncountable. The equivalence problem for boundaries is also shown decidable for iterated primitive morphisms.

We show that a Rabin recognizable set of trees is uncountable iff it is of the cardinality continuum iff it contains a non-regular tree. If a Rabin recognizable set L is countable, it can be represented as $$L = M\left[ {{{t_1 } \mathord{\left/{\vphantom {{t_1 } {x_1 , \ldots ,{{t_n } \mathord{\left/{\vphantom {{t_n } {x_n }}} \right.\kern-\nulldelimiterspace} {x_n }}}}} \right.\kern-\nulldelimiterspace} {x_1 , \ldots ,{{t_n } \mathord{\left/{\vphantom {{t_n } {x_n }}} \right.\kern-\nulldelimiterspace} {x_n }}}}} \right]$$ where M is a regular set of finite terms and t1, ..., t n are regular trees. We also design an algorithm which, given a Rabin automaton A, computes the cardinality of the set of trees recognized by A.

A definition of Continuity properly generalized from full to partial orders is presented. In addition to the continuity requirements of Dedekind (no gaps, no jumps) the definition includes requirements taken from physics and from engineering. All these requirements are fulfilled by the total order structure of real numbers, but at the cost of uncountably infinite cardinality. A central aspect of the proposed definition is that it admits models which are nowhere dense.

We construct a recursive class of trees having decidable theories in Lo(Q1). Furthermore this class is a dense class of trees. The methods which we use are similar to those of H. Lauchli and J.Leonhard [4]. From our construction the decidability of TR(X1), the theory of uncountable trees in Lo(Q1), follows as a corollary. This was first proved by H.Herre

Using topological concepts A. Blass [1] proved an uncountable version of Ramsey’s theorem. Here we prove a canonical version of this result.

We study the Sine-Gordon equation ϕtt - ϕzz + sinϕ = 0 subject to two classes of small perturbations: (1) spatially periodic perturbations on an infinite domain and (2) weak dissipation and temporally periodic perturbations on the boundary of a finite spatial domain. In the former case we prove the existence of a countable set of spatially periodic stationary solutions in addition to an uncountable set of non-periodic stationary solutions. In the latter case we prove that, if the excitation is sufficiently large compared with dissipation, a countable set of time-periodic motions of all periods as well as non periodic motions exist. All these stationary and periodic solutions are unstable (of saddle type) and are expected to coexist with stable solutions. However, in the global bifurcations leading to creation of the latter (time-dependent) solutions, infinite sets of asymptotically stable periodic orbits with arbitrarily long periods are expected to appear.

In [Sh3-6], Shelah attacked the problem of Morley's conjecture for countable first order theories. That is, he showed that if T is a countable first order theory then I(T, /\,) (= the number of non-isomorphic models of size /\,) is increasing for uncountable /\,. More specifically, he proved the main gap; i.e. if T is a countable complete first order theory then I(T, /\,) = 2" for A> or I(T, /\,) No for A> No. In [S14], Shelah showed that if T has DOP then I(T, A) = 2" for all A> and he showed the same for deep Tin [S14]. (See [HM] for a different exposition.) Moreover, in [ShS], he showed that the main gap holds for w-stable theories. Using [Sh5] as a prototype, one wants to show that if T is countable, superstable, shallow with N DOP then every model is primary and minimal over a suitably chosen independent w-tree of "small" submodels. Since the depth of a shallow superstable theory is less than Wl (see [L],) using the same techniques outlined in say [HM], we would obtain the main gap. However, there is no guarantee that there are primary models over independent w-trees of models. Hence, we need another dichotomy and we call it OTOP (definition 3.1). The negation is called NOTOP and has the consequence (1.5) that there are primary models over independent w-trees of models. In section 3, we see that OTOP leads to many models and in section 4, we outline the appropriate decomposition trees to handle the rest of the main gap. We will now outline the sections. Section 1 deals briefly with a general notion of projective partial order and proves some necessary facts concerning S;::TV. A more general approach can be found in [H]. As stated above, the important lemma 1.5 is proved and is due to Shelah. The definition of S;::e (1.9) is new and is different from the notions in [Sh6] and [Sf]. This definition of S;::e owes its existence to the one contained in [Sf] but here we prove 1.14 which is essential for the decomposition theorem in section 4. The lemmas involving S;::e are all new. However 1.15 is, of course, based on the three-model lemma from [Sh6]. The rest of section 1 is due to Shelah. Section 2 contains the definition of P-domination due to Harrington. All the lemmas contained in section 2 were known to Harrington and the notion was invented to remove the necessity of using -isolation from [Sh6]. Section 3 repeats the

1.2 Remark. It is easy to see that 1.1 implies that there is up to homotopy only one space B whose loop space is homotopy equivalent to the p-completion of S. To get such a strong uniqueness result it is definitely necessary to work one prime at a time: Rector [R] has produced an uncountable number of homotopically distinct spaces Y with loop space homotopy equivalent to S itself. Rector’s deloopings {Y } have the property that Yp ' (BS)p for all primes p. Theorem 1.1 implies that this condition is forced. Thus Rector’s classification

We prove that e.g. Open image in new window contradicting the common assumption that for singular strong limit λ, 2 λ have a bound only when X has uncountable cofinality. We prove a strengthening of the covering lemma, not using the fine structure theory (only some well known consequences, see Theorem 0.2). We prove it essentially in all cases in which the covering lemma holds.

If X is an uncountable Polish space, then the space BC(X) of bounded continuous functions on X is a factor of BC(I), where I denotes the set of irrational numbers. Etcheberry proved this by constructing a continuous surjection π: I→X that admits an averaging operator. Here, we provide an alternative technique for the construction of averaging operators that are even regular and also allow one to prove the first mentioned result.

One says that the sets x and y are equinumerous (in symbols, x ≈ y) if there is a 1 – 1 function mapping x on y. The notion of the cardinal |x| of x is obtained from equinumerosity by abstraction. The use of |x| does usually not require any special apparatus. E.g., when we say |x| — ℵ0 we mean to say that there is a 1 – 1 function mapping x on the set of all natural numbers; when we say |x| < |y| we mean that there are 1 – 1 functions mapping x into y, but none of them is onto y; etc. As is common in mathematics, one tends to pass from the abstract notion of cardinal numbers to real cardinal numbers, i.e., one wants to regard the cardinal numbers as objects of the mathematical system. This is where one encounters the problem of how to define the cardinal | x | of x as an object of set theory.