Rigid Unary Functions and the Axiom of Choice

We shall investigate certain statements concerning the rigidity of unary functions which have connections with (weak) forms of the axiom of choice.     

An exponential separation between the parity principle and the pigeonhole principle

The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. Ajtai (1990) previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with the pigeonhole principle as an axiom schema. His proof utilizes nonstandard model theory and is nonconstructive. We improve Ajtai's lower bound from barely superpolynomial to exponential and eliminate the nonstandard model theory.

Our lower bound is also related to the inherent complexity of particular search classes (see Papadimitriou, 1991). In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques (Beame et al., 1995).     

Non‐constructive Properties of the Real Numbers

We study the relationship between various properties of the real numbers and weak choice principles.     

Factors of Functions,AC and Recursive Analogues

We investigate certain statements about factors of unary functions (in particular,factors of permutations) which have connections with weak forms of the axiom of choice. We discuss more extensively the fine structure of Howard and Rubin's Form 314 (which concerns bireflectivity of permutations) from [4]. Some of our set‐theoretic results have also interesting recursive versions.     

NASH EQUILIBRIA WITHOUT CONTINUITY OF THE CHOICE RULES

The proposal in Alcantud and Alo′s-Ferrer [1], where players that express their tastes according to choice rules facing a competitive situation, is further exploited here. We prove that, under lack of continuity of the choice rules it is also possible to ensure the existence of equilibrium. We shall appeal to general situations that are fulfilled by well-established models, where players have non-transitive preferences of various types.     

Constructive Order Theory

We introduce the notion of constructive suprema and of constructively directed sets. The Axiom of Choice turns out to be equivalent to the postulate that every supremum is constructive, but also to the hypothesis that every directed set admits a function assigning to each finite subset an upper bound. The Axiom of Multiple Choice (which is known to be weaker than the full Axiom of Choice in set theory without foundation) implies a simple set‐theoretical induction principle (SIP), stating that any system of sets that is closed under unions of well‐ordered subsystems and contains all finite subsets of a given set must also contain that set itself. This is not provable without choice principles but equivalent to the statement that the existence of joins for constructively directed subsets of a poset follows from the existence of joins for nonempty well‐ordered subsets. Moreover, we establish the equivalence of SIP with several other fundamental statements concerning inductivity, compactness, algebraic closure systems, and the exchange between chains and directed sets.     

The rigid relation principle,a new weak choice principle

The rigid relation principle, introduced in this article, asserts that every set admits a rigid binary relation. This follows from the axiom of choice, because well‐orders are rigid, but we prove that it is neither equivalent to the axiom of choice nor provable in Zermelo‐Fraenkel set theory without the axiom of choice. Thus, it is a new weak choice principle. Nevertheless, the restriction of the principle to sets of reals (among other general instances) is provable without the axiom of choice.     

Weak choice principles

We consider several weak forms of the Axiom of Choice obtained debilitating some well known choice principles. Implication relations among them and independence results are established using, in some cases, permutation models or symmetric models. The relationship between Ramsey's Theorem and these choice principles is also explored, showing that, in this context, the known results are the best possible.

     

The Edgeworth-Pareto principle in terms of a fuzzy choice function

The Edgeworth-Pareto Principle, the simplest version of which has been known since the 19th century, is stated in general terms of a fuzzy choice function. The application of the principle is justified for a wide class of fuzzy multicriteria choice problems described by certain axioms of the rational behavior. These results bring the axiomatic substantiation of the Edgeworth-Pareto principle performed previously by the author to the most general form and make it possible to reveal the boundaries of that class of multicriteria choice problems for which the application of this principle is required. Based on scalarization methods as applied to multicriteria problems, upper bounds are derived for the unknown set of selected vectors.     

Regularization properties of the sequential discrepancy principle for Tikhonov regularization in Banach spaces

The stable solution of ill-posed non-linear operator equations in Banach space requires regularization. One important approach is based on Tikhonov regularization, in which case a one-parameter family of regularized solutions is obtained. It is crucial to choose the parameter appropriately. Here, a sequential variant of the discrepancy principle is analysed. In many cases, such parameter choice exhibits the feature, called regularization property below, that the chosen parameter tends to zero as the noise tends to zero, but slower than the noise level. Here, we shall show such regularization property under two natural assumptions. First, exact penalization must be excluded, and secondly, the discrepancy principle must stop after a finite number of iterations. We conclude this study with a discussion of some consequences for convergence rates obtained by the discrepancy principle under the validity of some kind of variational inequality, a recent tool for the analysis of inverse problems.     

Nonsmooth Characterizations of Asplund Spaces and Smooth Variational Principles

We show that the Asplund property of Banach spaces is not only sufficient but also a necessary condition for the fulfillment of some basic results in nonsmooth analysis involving Fréchet-like normals and subdifferentials as well as their sequential limits. In this way we obtain new characterizations of Asplund spaces within the framework of nonsmooth analysis. Then we study several versions of smooth variational principles in Asplund spaces, provide necessary and sufficient conditions for the validity of such principles, and establish their relationships with certain subdifferential properties of lower semicontinuous functions.     

Uncertainty principles for the continuous Hankel Wavelet transform

The aim of this paper is to prove Heisenberg-type uncertainty principles for the continuous Hankel wavelet transform. We also analyse the concentration of this transform on sets of finite measure. Benedicks-type uncertainty principle is given.     

A few remarks on divergent sequences: Rates of divergence

We continue investigation of certain classes of sequences of positive real numbers which are important in asymptotic analysis of divergent processes. Among others, we define the notion of quotient speed, give representation results for some kinds of sequences and improve several our earlier results concerning selection principles and games.     

The usefulness of Bayesian optimal designs for discrete choice experiments

Recently, the use of Bayesian optimal designs for discrete choice experiments, also called stated choice experiments or conjoint choice experiments, has gained much attention, stimulating the development of Bayesian choice design algorithms. Characteristic for the Bayesian design strategy is that it incorporates the available information about people's preferences for various product attributes in the choice design. This is in contrast with the linear design methodology, which is also used in discrete choice design and which depends for any claims of optimality on the unrealistic assumption that people have no preference for any of the attribute levels. Although linear design principles have often been used to construct discrete choice experiments, we show using an extensive case study that the resulting utility‐neutral optimal designs are not competitive with Bayesian optimal designs for estimation purposes. Copyright © 2011 John Wiley & Sons, Ltd.     

Sticks and clubs

We study combinatorial principles known as stick and club. Several variants of these principles and cardinal invariants connected to them are also considered. We introduce a new kind of side by-side product of partial orderings which we call pseudo-product. Using such products, we give several generic extensions where some of these principles hold together with ¬CH and Martin's axiom for countable p.o.-sets. An iterative version of the pseudo-product is used under an inaccessible cardinal to show the consistency of the club principle for every stationary subset of limits of ω₁ together with ¬CH and Martin's axiom for countable p.o.-sets.     

Heuristic Parameter Choice Rules for Tikhonov Regularization with Weakly Bounded Noise

We study the choice of the regularization parameter for linear ill-posed problems in the presence of noise that is possibly unbounded but only finite in a weaker norm, and when the noise-level is unknown. For this task, we analyze several heuristic parameter choice rules, such as the quasi-optimality, heuristic discrepancy, and Hanke-Raus rules and adapt the latter two to the weakly bounded noise case. We prove convergence and convergence rates under certain noise conditions. Moreover, we analyze and provide conditions for the convergence of the parameter choice by the generalized cross-validation and predictive mean-square error rules.     

Minimal representation of insurance prices

This paper prices insurance contracts by employing law invariant, coherent risk measures from mathematical finance. We demonstrate that the corresponding premium principle enjoys a minimal representation. Uniqueness–in a sense specified in the paper–of this premium principle is derived from this initial result. The representations are derived from a result by Kusuoka, which is usually given for nonatomic probability spaces. We extend this setting to premium principles for spaces with atoms, as this is of particular importance for insurance.Further, stochastic order relations are employed to identify the minimal representation. It is shown that the premium principles in the minimal representation are extremal with respect to the order relations. The tools are finally employed to explicitly provide the minimal representation for premium principles, which are important in actuarial practice.     

The strong maximum principle revisited

In this paper we first present the classical maximum principle due to E. Hopf, together with an extended commentary and discussion of Hopf's paper. We emphasize the comparison technique invented by Hopf to prove this principle, which has since become a main mathematical tool for the study of second order elliptic partial differential equations and has generated an enormous number of important applications. While Hopf's principle is generally understood to apply to linear equations, it is in fact also crucial in nonlinear theories, such as those under consideration here.In particular, we shall treat and discuss recent generalizations of the strong maximum principle, and also the compact support principle, for the case of singular quasilinear elliptic differential inequalities, under generally weak assumptions on the quasilinear operators and the nonlinearities involved. Our principal interest is in necessary and sufficient conditions for the validity of both principles; in exposing and simplifying earlier proofs of corresponding results; and in extending the conclusions to wider classes of singular operators than previously considered.The results have unexpected ramifications for other problems, as will develop from the exposition, e.g.

(i)

two point boundary value problems for singular quasilinear ordinary differential equations (Sections 3 and 4);

(ii)

the exterior Dirichlet boundary value problem (Section 5);

(iii)

the existence of dead cores and compact support solutions, i.e. dead cores at infinity (Section 7);

(iv)

Euler-Lagrange inequalities on a Riemannian manifold (Section 9);

(v)

comparison and uniqueness theorems for solutions of singular quasilinear differential inequalities (Section 10).

The case of p-regular elliptic inequalities is briefly considered in Section 11.     

Elimination of Skolem functions for monotone formulas in analysis

In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems -qf , where (GA is a hierarchy of (weak) subsystems of arithmetic in all finite types (introduced in [14]), AC-qf is the schema of quantifier-free choice in all types and is a set of certain analytical principles which e.g. includes the binary K?nig's lemma. We apply this method to show that the arithmetical closures of single instances of -comprehension and -choice contribute to the growth of extractable bounds from proofs relative to only by a primitive recursive functional in the sense of Kleene. In subsequent papers these results are widely generalized and the method is used to determine the arithmetical content of single sequences of instances of the Bolzano-Weierstra? principle for bounded sequences in , the Ascoli-lemma and others. February 14, 1996     

Matrix identities and the pigeonhole principle

We show that short bounded-depth Frege proofs of matrix identities, such as PQ=IQP=I (over the field of two elements), imply short bounded-depth Frege proofs of the pigeonhole principle. Since the latter principle is known to require exponential-size bounded-depth Frege proofs, it follows that the propositional version of the matrix principle also requires bounded-depth Frege proofs of exponential size.