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 .

     

Factorials and the finite sequences of sets

We write for the cardinality of the set of finite sequences of a set which is of cardinality . With the Axiom of Choice (), for every infinite cardinal where is the cardinality of the permutations on a set which is of cardinality . In this paper, we show that “ for every cardinal ”  is provable in and this is the best possible result in the absence of . Similar results are also obtained for : the cardinality of the set of finite sequences without repetition of a set which is of cardinality .     

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.     

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 .     

Fractional Kirchhoff problem with critical indefinite nonlinearity

We study the existence and multiplicity of positive solutions for a family of fractional Kirchhoff equations with critical nonlinearity of the form where is a smooth bounded domain, and . Here M is the Kirchhoff coefficient and is the fractional critical Sobolev exponent. The parameter λ is positive and the is a real valued continuous function which is allowed to change sign. By using a variational approach based on the idea of Nehari manifold technique, we combine effects of a sublinear and a superlinear term to prove our main results.     

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 maximum number of columns in supersaturated designs with

Cheng and Tang [Biometrika, 88 (2001), pp. 1169–1174] derived an upper bound on the maximum number of columns that can be accommodated in a two‐symbol supersaturated design (SSD) for a given number of rows () and a maximum in absolute value correlation between any two columns (). In particular, they proved that for (mod ) and . However, the only known SSD satisfying this upper bound is when . By utilizing a computer search, we prove that for , and . These results are obtained by proving the nonexistence of certain resolvable incomplete blocks designs. The combinatorial properties of the RIBDs are used to reduce the search space. Our results improve the lower bound for SSDs with rows and columns, for , and . Finally, we show that a skew‐type Hadamard matrix of order can be used to construct an SSD with rows and columns that proves . Hence, we establish for and for all (mod ) such that . Our result also implies that when is a prime power and (mod ). We conjecture that for all and (mod ), where is the maximum number of equiangular lines in with pairwise angle .     

Some properties of infinite factorials

With the Axiom of Choice , for any infinite cardinal but, without , we cannot conclude any relationship between and for an arbitrary infinite cardinal . In this paper, we give some properties of in the absence of and compare them to those of for an infinite cardinal . Among our results, we show that “ for any infinite cardinal and any natural number n” is provable in although “ for any infinite cardinal ” is not.     

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.     

Free sets for set‐mappings relative to a family of sets

Given a family of subsets of , we try to compute the least natural number n such that for every function there exists a bijection such that for all .     

On the honeymoon Oberwolfach problem

The honeymoon Oberwolfach problem HOP asks the following question. Given newlywed couples at a conference and round tables of sizes , is it possible to arrange the participants at these tables for meals so that each participant sits next to their spouse at every meal and sits next to every other participant exactly once? A solution to HOP is a decomposition of , the complete graph with additional copies of a fixed 1‐factor , into 2‐factors, each consisting of disjoint ‐alternating cycles of lengths . It is also equivalent to a semi‐uniform 1‐factorization of of type ; that is, a 1‐factorization such that for all , the 2‐factor consists of disjoint cycles of lengths . In this paper, we first introduce the honeymoon Oberwolfach problem and then present several results. Most notably, we completely solve the case with uniform cycle lengths, that is, HOP. In addition, we show that HOP has a solution in each of the following cases: ; is odd and ; as well as for all . We also show that HOP has a solution whenever is odd and the Oberwolfach problem with tables of sizes has a solution.     

Dimension of the space generated by Steiner systems

To every Steiner system with parameters on and blocks , we can assign its characteristic vector , which is a ‐vector whose entries are indexed by the ‐subsets of such that for each ‐subset of if and only if . In this paper, we show that the dimension of the vector space generated by all of the characteristic vectors of Steiner systems with parameters is , provided that and there is at least one such system.     

On the limit Sobolev regularity for Dirichlet and Neumann problems on Lipschitz domains

We construct a bounded C¹ domain Ω in for which the regularity for the Dirichlet and Neumann problems for the Laplacian cannot be improved, that is, there exists f in such that the solution of in Ω and either on or on is contained in but not in for any . An analogous result holds for Sobolev spaces with .     

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 .     

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.     

Counting restricted orientations of random graphs

We count orientations of avoiding certain classes of oriented graphs. In particular, we study , the number of orientations of the binomial random graph in which every copy of is transitive, and , the number of orientations of containing no strongly connected copy of . We give the correct order of growth of and up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota, and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.