Effective Nonrecursiveness

Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1].     

Complexity properties of recursively enumerable sets andbsQ-completeness

The notions of boundedly strongly effectively speedable set and boundedly effectively speedable set are introduced. It is proved that the notions of boundedly strongly effectively speedable set, boundedly effectively speedable set, creative set, andbsQ-complete recursively enumerable set are equivalent. Translated fromMatematicheskie Zametki, Vol. 68, No. 4, pp. 554–559, October, 2000.     

Generalisations of disjunctive sequences

The present paper proposes a generalisation of the notion of disjunctive (or rich) sequence, that is, of an infinite sequence of letters having each finite sequence as a subword. Our aim is to give a reasonable notion of disjunctiveness relative to a given set of sequences F. We show that a definition like “every subword which occurs at infinitely many different positions in sequences in F has to occur infinitely often in the sequence” fulfils properties similar to the original unrelativised notion of disjunctiveness. Finally, we investigate our concept of generalised disjunctiveness in spaces of Cantor expansions of reals. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On balanced games with infinitely many players: Revisiting Schmeidler's result

We consider transferable utility cooperative games with infinitely many players and the core understood in the space of bounded additive set functions. We show that, if a game is bounded below, then its core is non-empty if and only if the game is balanced. This finding generalizes Schmeidler (1967) “On Balanced Games with Infinitely Many Players”, where the game is assumed to be non-negative. We also generalize Schmeidler's (1967) result to the case of restricted cooperation too.     

Computable Real-Valued Functions on Recursive Open and Closed Subsets of Euclidean Space

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.     

The Arithmetical Hierarchy of Real Numbers

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left (right) computable iff it is the supremum (infimum) of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable (multiple) sequences of rational numbers we introduce a non‐collapsing hierarchy {Σ_n, Π_n, Δ_n : n ∈ ℕ} of real numbers. We characterize the classes Σ₂, Π₂ and Δ₂ in various ways and give several interesting examples.     

Counting Lattice Paths with an Infinite Step Set and Special Access

We count lattice paths that remain in the first quadrant. A path can come from only finitely many lattice points, and if no further restrictions apply, can go to infinitely many others. By “further restrictions” we mean a boundary line above which the paths may have to stay. Access privilege to the boundary line itself is granted from certain lattice points in the form of a special access step set, which also may be infinite. Our approach to explicit solutions of such enumeration problems is via Sheffer polynomials and functionals, using results of the Umbral Calculus.     

Planar graphs producing no strongly almost trivial embedding

We present here infinitely many planar graphs which have no strongly almost trivial embeddings. Then we conclude that “strongly almost trivial” is more strict concept than “almost trivial.”. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 319–326, 2003     

Bridging the Gap Between the Dense and the Discrete: The Number Line and the “Rubber Line” Bridging Analogy

In two experiments we explored the instructional value of a cross‐domain mapping between “number” and “line” in secondary school students' understanding of density. The first experiment investigated the hypothesis that density would be more accessible to students in a geometrical context (infinitely many points on a straight line segment) compared to a numerical context (infinitely many numbers in an interval). The participants were 229 seventh to eleventh graders. The results supported this hypothesis but also showed that students' conceptions of the line segment were far from that of a dense array of points. We then designed a text-based intervention that attempted to build the notion of density in a geometrical context, making explicit reference to the number-to-points correspondence and using the “rubber line” bridging analogy (the line as an imaginary unbreakable rubber band) to convey the no-successor principle. The participants were 149 eighth and tenth graders. The text intervention improved student performance in tasks regarding the infinity of numbers in an interval; the “rubber line” bridging analogy further improved performance successfully conveying the idea that these numbers can never be found one immediately next to the other.     

Transformation of Quasiconvex Functions to Eliminate Local Minima

Quasiconvex functions present some difficulties in global optimization, because their graph contains “flat parts”; thus, a local minimum is not necessarily the global minimum. In this paper, we show that any lower semicontinuous quasiconvex function may be written as a composition of two functions, one of which is nondecreasing, and the other is quasiconvex with the property that every local minimum is global minimum. Thus, finding the global minimum of any lower semicontinuous quasiconvex function is equivalent to finding the minimum of a quasiconvex function, which has no local minima other than its global minimum. The construction of the decomposition is based on the notion of “adjusted sublevel set.” In particular, we study the structure of the class of sublevel sets, and the continuity properties of the sublevel set operator and its corresponding normal operator.     

Arrow's Theorem,Weglorz' Models and the Axiom of Choice

Applying Weglorz' mode s of set theory without the axiom of choice, we investigate Arrow‐type social we fare functions for infinite societies with restricted coalition algebras. We show that there is a reasonable, nondictatorial social welfare function satisfying “finite discrimination”, if and only if in Weglorz' mode there is a free ultrafilter on a set representing the individuals.     

Design of solids for antigravity motion illusion

This paper presents a method for designing solid shapes containing slopes where orientation appears opposite to the actual orientation when observed from a unique vantage viewpoint. The resulting solids generate a new type of visual illusion, which we call “impossible motion”, in which balls placed on the slopes appear to roll uphill thereby defying the law of gravity. This is possible because a single retinal image lacks depth information and human visual perception tries to interpret images as the most familiar shape even though there are infinitely many possible interpretations. We specify the set of all possible solids represented by a single picture as the solution set of a system of equations and inequalities, and then relax the constraints in such a way that the antigravity slopes can be reconstructed. We present this design procedure with examples.     

Weakly precomplete computably enumerable equivalence relations

Using computable reducibility ? on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers , that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ₃‐complete, whereas the index set of the weakly precomplete ceers is Π₃‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ₃‐complete.     

Markets with countably infinitely many traders

In this paper we will show how to construct, in a canonical way, a continuous economy in the sense of R. J. Aumann [1]. This construction is based on W. Hildenbrand's [3] definition of “pure competition” for an exchange economy with countably infinitely many participants.     

Interpolation by universal,hypercyclic functions

In the present article we study an interpolation problem for classes of analytic functions, in a systematic manner. More precisely, we provide sufficient conditions so that proper and “big”, in the Baire category sense, subclasses of analytic functions have an interpolation property at an infinite set of points. We then apply our main theorems to several classes of universal, hypercyclic functions.     

An inexact approach to solving linear semi-infinite programming problems

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed     

Rang des matrices Hermitiennes semi-définies positives indéfiniment divisibles

In this paper we study n × n Hermitian semidefinite positive matrices which are infinitely divisible in a sense that we define in Sec. 1. We establish (Theorem 2.2) a stability property for the rank of the “Hadamard power matrices” of such a matrix.     

Advertising Response Functions and Media Planning

In the first part of this paper the definition and use of advertising response functions are examined critically. It is shown that advertising response functions cannot be regarded as models of the advertising process whose parameters are known, that only a small section of the complex functions often postulated is relevant to media planning, that measures of advertising impacts or exposures are relative rather than absolute, and consequently that the “response function” only shows a notional relationship between advertising response and exposure, which normally needs to be calibrated to the advertising appropriation.In the second part a media planning system which utilizes a “control parameter” rather than a “response function” is described. The main feature of the “control parameter” is that it adapts itself so that an appropriate relationship between response and exposure is used, whatever the appropriation. Other features of the system are described.     

Data Visualization With Multidimensional Scaling

We discuss methodology for multidimensional scaling (MDS) and its implementation in two software systems, GGvis and XGvis. MDS is a visualization technique for proximity data, that is, data in the form of N × N dissimilarity matrices. MDS constructs maps (“configurations,” “embeddings”) in IR^k by interpreting the dissimilarities as distances. Two frequent sources of dissimilarities are high-dimensional data and graphs. When the dissimilarities are distances between high-dimensional objects, MDS acts as a (often nonlinear) dimension-reduction technique. When the dissimilarities are shortest-path distances in a graph, MDS acts as a graph layout technique. MDS has found recent attention in machine learning motivated by image databases (“Isomap”). MDS is also of interest in view of the popularity of “kernelizing” approaches inspired by Support Vector Machines (SVMs; “kernel PCA”).

This article discusses the following general topics: (1) the stability and multiplicity of MDS solutions; (2) the analysis of structure within and between subsets of objects with missing value schemes in dissimilarity matrices; (3) gradient descent for optimizing general MDS loss functions (“Strain” and “Stress”); (4) a unification of classical (Strain-based) and distance (Stress-based) MDS.

Particular topics include the following: (1) blending of automatic optimization with interactive displacement of configuration points to assist in the search for global optima; (2) forming groups of objects with interactive brushing to create patterned missing values in MDS loss functions; (3) optimizing MDS loss functions for large numbers of objects relative to a small set of anchor points (“external unfolding”); and (4) a non-metric version of classical MDS.

We show applications to the mapping of computer usage data, to the dimension reduction of marketing segmentation data, to the layout of mathematical graphs and social networks, and finally to the spatial reconstruction of molecules.