Reductions on equivalence relations generated by universal sets

Let X, Y be Polish spaces, , . We say A is universal for Γ provided that each x‐section of A is in Γ and each element of Γ occurs as an x‐section of A. An equivalence relation generated by a set is denoted by , where . The following results are shown:

• (1) If A is a set universal for all nonempty closed subsets of Y, then is a equivalence relation and .
• (2) If A is a set universal for all countable subsets of Y, then is a equivalence relation, and
  • (i) and ;
  • (ii) if , then ;
  • (iii) if every set is Lebesgue measurable or has the Baire property, then .
  • (iv) for , if every set has the Baire property, and E is any equivalence relation, then .

     

Jump inversions of algebraic structures and Σ‐definability

It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump . We also show that this result does not hold for the limit ordinal . Moreover, we prove that there is no countable structure with the degree spectrum for .     

The first omitting cardinal for Magidority

An infinite cardinal λ is Magidor if and only if . It is known that if λ is Magidor then for some , and the first such α is denoted by . In this paper we try to understand some of the properties of . We prove that can be the successor of a supercompact cardinal, when λ is a Magidor cardinal. From this result we obtain the consistency of being a successor of a singular cardinal with uncountable cofinality.     

On the relative strengths of fragments of collection

Let be the basic set theory that consists of the axioms of extensionality, emptyset, pair, union, powerset, infinity, transitive containment, Δ₀‐separation and set foundation. This paper studies the relative strength of set theories obtained by adding fragments of the set‐theoretic collection scheme to . We focus on two common parameterisations of the collection: ‐collection, which is the usual collection scheme restricted to ‐formulae, and strong ‐collection, which is equivalent to ‐collection plus ‐separation. The main result of this paper shows that for all ,

1. proves that there exists a transitive model of Zermelo Set Theory plus ‐collection,
2. the theory is ‐conservative over the theory .

It is also shown that (2) holds for when the Axiom of Choice is included in the base theory. The final section indicates how the proofs of (1) and (2) can be modified to obtain analogues of these results for theories obtained by adding fragments of collection to a base theory (Kripke‐Platek Set Theory with Infinity plus ) that does not include the powerset axiom.     

The cofinality of the least Berkeley cardinal and the extent of dependent choice

This paper is concerned with the possible values of the cofinality of the least Berkeley cardinal. Berkeley cardinals are very large cardinal axioms incompatible with the Axiom of Choice, and the interest in the cofinality of the least Berkeley arises from a result in [1], showing it is connected with the failure of . In fact, by a theorem of Bagaria, Koellner and Woodin, if γ is the cofinality of the least Berkeley cardinal then γ‐ fails. We shall prove that this result is optimal for or . In particular, it will follow that the cofinality of the least Berkeley is independent of .     

A variant of Shelah's characterization of Strong Chang's Conjecture

Shelah considered a certain version of Strong Chang's Conjecture which we denote , and proved that it is equivalent to several statements, including the assertion that Namba forcing is semiproper. We introduce an apparently weaker version, denoted , and prove an analogous characterization of it. In particular, is equivalent to the assertion that the the Friedman‐Krueger poset is semiproper. This strengthens and sharpens results by Cox and sheds some light on problems posed by Usuba, Torres‐Perez and Wu.     

Neutrally expandable models of arithmetic

A subset of a model of is called neutral if it does not change the relation. A model with undefinable neutral classes is called neutrally expandable. We study the existence and non‐existence of neutral sets in various models of . We show that cofinal extensions of prime models are neutrally expandable, and ω₁‐like neutrally expandable models exist, while no recursively saturated model is neutrally expandable. We also show that neutrality is not a first‐order property. In the last section, we study a local version of neutral expandability.     

Indivisible sets and well‐founded orientations of the Rado graph

Every set can been thought of as a directed graph whose edge relation is ∈ . We show that many natural examples of directed graphs of this kind are indivisible: for every infinite κ, for every indecomposable λ, and every countable model of set theory. All of the countable digraphs we consider are orientations of the countable random graph. In this way we find indivisible well‐founded orientations of the random graph that are distinct up to isomorphism, and ?₁ that are distinct up to siblinghood.     

The prescribed Ricci curvature problem on three‐dimensional unimodular Lie groups

Let G be a three‐dimensional unimodular Lie group, and let T be a left‐invariant symmetric (0,2)‐tensor field on G. We provide the necessary and sufficient conditions on T for the existence of a pair consisting of a left‐invariant Riemannian metric g and a positive constant c such that , where is the Ricci curvature of g. We also discuss the uniqueness of such pairs and show that, in most cases, there exists at most one positive constant c such that is solvable for some left‐invariant Riemannian metric g.     

Models of : when two elements are necessarily order automorphic

We are interested in the question of how much the order of a non‐standard model of can determine the model. In particular, for a model M, we want to characterize the complete types of non‐standard elements such that the linear orders and are necessarily isomorphic. It is proved that this set includes the complete types such that if the pair realizes it (in M) then there is an element c such that for all standard n, , , , and . We prove that this is optimal, because if holds, then there is M of cardinality ?₁ for which we get equality. We also deal with how much the order in a model of may determine the addition.     

On the finite axiomatizability of

The question of whether the bounded arithmetic theories and are equal is closely connected to the complexity question of whether is equal to . In this paper, we examine the still open question of whether the prenex version of , , is equal to . We give new dependent choice‐based axiomatizations of the ‐consequences of and . Our dependent choice axiomatizations give new normal forms for the ‐consequences of and . We use these axiomatizations to give an alternative proof of the finite axiomatizability of and to show new results such as is finitely axiomatized and that there is a finitely axiomatized theory, , containing and contained in . On the other hand, we show that our theory for splits into a natural infinite hierarchy of theories. We give a diagonalization result that stems from our attempts to separate the hierarchy for .     

A complete solution to existence of H designs

An H design is a triple , where is a set of points, a partition of into disjoint sets of size , and a set of ‐element transverses of , such that each ‐element transverse of is contained in exactly one of them. In 1990, Mills determined the existence of an H design with . In this paper, an efficient construction shows that an H exists for any integer with . Consequently, the necessary and sufficient conditions for the existence of an H design are , , and , with a definite exception .     

Algebraic numbers with elements of small height

In this paper, we study the field of algebraic numbers with a set of elements of small height treated as a predicate. We prove that such structures are not simple and have the independence property. A real algebraic integer is called a Salem number if α and are Galois conjugate and all other Galois conjugates of α lie on the unit circle. It is not known whether 1 is a limit point of Salem numbers. We relate the simplicity of a certain pair with Lehmer's conjecture and obtain a model‐theoretic characterization of Lehmer's conjecture for Salem numbers.     

Distinct partial sums in cyclic groups: polynomial method and constructive approaches

Let be an abelian group and consider a subset with . Given an ordering of the elements of , define its partial sums by and for . We consider the following conjecture of Alspach: for any cyclic group and any subset with , it is possible to find an ordering of the elements of such that no two of its partial sums and are equal for . We show that Alspach’s Conjecture holds for prime when and when . The former result is by direct construction, the latter is nonconstructive and uses the polynomial method. We also use the polynomial method to show that for prime a sequence of length having distinct partial sums exists in any subset of of size at least in all but at most a bounded number of cases.     

A note on the deductive strength of the Nielsen‐Schreier theorem

We show that the Boolean Prime Ideal Theorem () does not imply the Nielsen‐Schreier Theorem () in , thus strengthening the result of Kleppmann from “Nielsen‐Schreier and the Axiom of Choice” that the (strictly weaker than ) Ordering Principle () does not imply in . We also show that is false in Mostowski's Linearly Ordered Model of . The above two results also settle the corresponding open problems from Howard and Rubin's “Consequences of the Axiom of Choice”.     

Fractal graphs

The lexicographic sum of graphs is defined as follows. Let be a graph. With each associate a graph . The lexicographic sum of the graphs over is obtained from by substituting each by . Given distinct , we have all the possible edges in the lexicographic sum between and if , and none otherwise. When all the graphs are isomorphic to some graph , the lexicographic sum of the graphs over is called the lexicographic product of by and is denoted by . We say that a graph is fractal if there exists a graph , with at least two vertices, such that . There is a simple way to construct fractal graphs. Let be a graph with at least two vertices. The graph is defined on the set of functions from to as follows. Given distinct is an edge of if is an edge of , where is the smallest integer such that . The graph is fractal because . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of , which is itself fractal.     

The Tarski irredundant basis theorem and the finite soluble groups

Denote by and , respectively, the smallest and the largest cardinality of a minimal generating set of a finite group G. The Tarski irredundant basis theorem implies that for every k with there exist a minimal generating set , an index and in G such that is again a minimal generating set of G. In this case we say that is an immediate descendant of ω. There are several examples of minimal generating sets of cardinality smaller than which have no immediate descendant and so it appears an interesting problem to investigate under which conditions an immediate descendant exists. In this paper we discuss this problem in the case of finite soluble groups.     

High nonassociativity in order 8 and an associative index estimate

Let be a quasigroup. Put and assume that . Let and be the number of left and right translations of that are fixed point free. Put . Denote by the number of idempotents of . It is shown that . Call extremely nonassociative if . The paper reports what seems to be the first known example of such a quasigroup, with , , and . It also provides supporting theory for a search that verified for all quasigroups of order .     

There are eight‐element orthogonal exponentials on the spatial Sierpinski gasket

The self‐affine measure corresponding to an expanding matrix and the digit set in the space is supported on the spatial Sierpinski gasket, where are the standard basis of unit column vectors in and . In the case and , it is conjectured that the cardinality of orthogonal exponentials in the Hilbert space is at most “4”, where the number 4 is the best upper bound. That is, all the four‐element sets of orthogonal exponentials are maximal. This conjecture has been proved to be false by giving a class of the five‐element orthogonal exponentials in . In the present paper, we construct a class of the eight‐element orthogonal exponentials in the corresponding Hilbert space to disprove the conjecture. We also illustrate that the constructed sets of orthogonal exponentials are maximal.     

Bipartite spanning sub(di)graphs induced by 2-partitions

For a given -partition of the vertices of a (di)graph , we study properties of the spanning bipartite subdigraph of induced by those arcs/edges that have one end in each . We determine, for all pairs of nonnegative integers , the complexity of deciding whether has a 2-partition such that each vertex in (for ) has at least (out-)neighbours in . We prove that it is -complete to decide whether a digraph has a 2-partition such that each vertex in has an out-neighbour in and each vertex in has an in-neighbour in . The problem becomes polynomially solvable if we require to be strongly connected. We give a characterisation of the structure of -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes -complete even for strong digraphs. A further result is that it is -complete to decide whether a given digraph has a -partition such that is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.