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.     

Classification of non‐well‐founded sets and an application

A complete list of Finsler, Scott and Boffa sets whose transitive closures contain 1, 2 and 3 elements is given. An algorithm for deciding the identity of hereditarily finite Scott sets is presented. Anti‐well‐founded (awf) sets, i. e., non‐well‐founded sets whose all maximal ∈‐paths are circular, are studied. For example they form transitive inner models of ZFC minus foundation and empty set, and they include uncountably many hereditarily finite awf sets. A complete list of Finsler and Boffa awf sets with 2 and 3 elements in their transitive closure is given. Next the existence of infinite descending ∈‐sequences in Aczel universes is shown. Finally a theorem of Ballard and Hrbá?ek concerning nonstandard Boffa universes of sets is considerably extended.     

Unions and the axiom of choice

We study statements about countable and well‐ordered unions and their relation to each other and to countable and well‐ordered forms of the axiom of choice. Using WO as an abbreviation for “well‐orderable”, here are two typical results: The assertion that every WO family of countable sets has a WO union does not imply that every countable family of WO sets has a WO union; the axiom of choice for WO families of WO sets does not imply that the countable union of countable sets is WO. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Kripke schema in metric topology

A form of Kripke's schema turns out to be equivalent to each of the following two statements from metric topology: every open subspace of a separable metric space is separable; every open subset of a separable metric space is a countable union of open balls. Thus Kripke's schema serves as a point of reference for classifying theorems of classical mathematics within Bishop‐style constructive reverse mathematics.     

Separations by Random Oracles and “Almost” Classes for Generalized Reducibilities

Let ≤_r and ≤_sbe two binary relations on 2^ℕ which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on 2^ℕ, which is obtained by choosing elements of 2^ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤_r‐cone of a randomly chosen set X, that is, the class of all sets A with A ≤_r X, differs from the lower ≤_s‐cone of X. By c osure under finite variation, the Kolmogorov 0‐1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤_r‐cone of A is either 0 or 1; let Almost_r be the class of sets for which the upper ≤_r‐cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2^ℕ which can be defined by a countable set of total continuous functionals on 2^ℕ in the same way as the usual resource‐bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource‐bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource‐bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations.     

On hereditarily small sets in ZF

We show in (the usual set theory without Choice) that for any set X, the collection of sets Y such that each element of the transitive closure of is strictly smaller in size than X (the collection of sets hereditarily smaller than X) is a set. This result has been shown by Jech in the case (where the collection under consideration is the set of hereditarily countable sets).     

Hereditarily strongly cwH and other separation axioms

We explore the relation between two general kinds of separation properties. The first kind, which includes the classical separation properties of regularity and normality, has to do with expanding two disjoint closed sets, or dense subsets of each, to disjoint open sets. The second kind has to do with expanding discrete collections of points, or full-cardinality subcollections thereof, to disjoint or discrete collections of open sets. The properties of being collectionwise Hausdorff (cwH), of being strongly cwH, and of being wD(ℵ₁), fall into the second category. We study the effect on other separation properties if these properties are assumed to hold hereditarily. In the case of scattered spaces, we show that (a) the hereditarily cwH ones are α-normal and (b) a regular one is hereditarily strongly cwH iff it is hereditarily cwH and hereditarily β-normal. Examples are given in ZFC of (1) hereditarily strongly cwH spaces which fail to be regular, including one that also fails to be α-normal; (2) hereditarily strongly cwH regular spaces which fail to be normal and even, in one case, to be β-normal; (3) hereditarily cwH spaces which fail to be α-normal. We characterize those regular spaces X such that X×(ω+1) is hereditarily strongly cwH and, as a corollary, obtain a consistent example of a locally compact, first countable, hereditarily strongly cwH, non-normal space. The ZFC-independence of several statements involving the hereditarily wD(ℵ₁) property is established. In particular, several purely topological statements involving this property are shown to be equivalent to b=ω₁.     

On spaces in which countably compact sets are closed, and hereditary properties

A space X is called C-closed if every countably compact subset of X is closed in X. We study the properties of C-closed spaces. Among other results, it is shown that countably compact C-closed spaces have countable tightness and under Martin's Axiom or 2^ω0<2^ω1, C-closed is equivalent to sequential for compact Hausdorff spaces. Furthermore, every hereditarily quasi-k Hausdorff space is Fréchet-Urysohn, which generalizes a theorem of Arhangel'sk in [4]. Also every hereditarily q-space is hereditarily of pointwise countable type and contains an open dense first countable subspace.     

Incomparable ω1‐like models of set theory

We show that the analogues of the embedding theorems of [3], proved for the countable models of set theory, do not hold when extended to the uncountable realm of ω₁‐like models of set theory. Specifically, under the ⋄ hypothesis and suitable consistency assumptions, we show that there is a family of many ω₁‐like models of , all with the same ordinals, that are pairwise incomparable under embeddability; there can be a transitive ω₁‐like model of that does not embed into its own constructible universe; and there can be an ω₁‐like model of whose structure of hereditarily finite sets is not universal for the ω₁‐like models of set theory.     

A characterization of distinguished Fréchet spaces

Bierstedt and Bonet proved in 1988 that if a metrizable locally convex space E satisfies the Heinrich's density condition, then every bounded set in the strong dual (E ′, β (E ′, E)) of E is metrizable; consequently E is distinguished, i.e. (E ′, β (E ′, E)) is quasibarrelled. However there are examples of distinguished Fréchet spaces whose strong dual contains nonmetrizable bounded sets. We prove that a metrizable locally convex space E is distinguished iff every bounded set in the strong dual (E ′, β (E ′, E)) has countable tightness, i.e. for every bounded set A in (E ′, β (E ′, E)) and every x in the closure of A there exists a countable subset B of A whose closure contains x. This extends also a classical result of Grothendieck. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

When a compact (countably compact) set is closed. II

We obtain (a) necessary and sufficient conditions and (b) sufficient conditions for a compact (countably compact) set to be closed in products (sequential products) and subspaces (sequential subspaces) of normal spaces. As a consequence of these, sufficient conditions are obtained for (i) the closedness of arbitrary (countable) union of closed sets and (ii) the equality of the union of the closures and the closure of the union of arbitrary (countable) families of sets in these spaces. It is also shown that these results do not hold for quotients of even T ₄,-spaces.     

The Strengths of Some Violations of Covering

We consider two models V₁, V₂ of ZFC such that V₁ ⊆ V₂, the cofinality functions of V₁ and of V₂ coincide, V₁ and V₂ have that same hereditarily countable sets, and there is some uncountable set in V₂ that is not covered by any set in V₁ of the same cardinality. We show that under these assumptions there is an inner model of V₂ with a measurable cardinal κ of Mitchell order κ⁺⁺. This technical result allows us to show that changing cardinal characteristics without changing cofinalities or ω‐sequences (which was done for some characteristics in [13]) has consistency strength at least Mitchell order κ⁺⁺. From this we get that the changing of cardinal characteristics without changing cardinals or ω‐sequences has consistency strength Mitchell order ω₁, even in the case of characteristics that do not stem from a transitive relation. Hence the known forcing constructions for such a change have lowest possible consistency strength. We consider some stronger violations of covering which have appeared as intermediate steps in forcing constructions.     

The wi‐club filter on 𝒫κ λ

We develop the theory of C_{κ, λ}ⁱ, a strongly normal filter over ??_κ λ for Mahlo κ. We prove a minimality result, showing that any strongly normal filter containing {x ∈ ??_κ λ: |x | = |x ∩ κ | and |x | is inaccessible} also contains C_{κ, λ}ⁱ. We also show that functions can be used to obtain a basis for C_{κ, λ}ⁱ (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs

A graph G is 1‐Hamilton‐connected if G?x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X?E⁺(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012     

Finite 2‐Distance Transitive Graphs

A noncomplete graph Γ is said to be (G, 2)‐distance transitive if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set of Γ, and for any vertex u of Γ, the stabilizer is transitive on the sets of vertices at distances 1 and 2 from u. This article investigates the family of (G, 2)‐distance transitive graphs that are not (G, 2)‐arc transitive. Our main result is the classification of such graphs of valency not greater than 5. We also prove several results about (G, 2)‐distance transitive, but not (G, 2)‐arc transitive graphs of girth 4.     

Destructibility of stationary subsets of Pκλ

For a regular cardinal κ with κ ^<κ = κ and κ ≤ λ , we construct generically (forcing by a < κ‐closed κ ⁺‐c. c. p. o.‐set ℙ₀) a subset S of {x ∈ P _κ λ : x ∩ κ is a singular ordinal} such that S is stationary in a strong sense (F ^IA_κ λ ‐stationary in our terminology) but the stationarity of S can be destroyed by a κ ⁺‐c. c. forcing ℙ* (in V ^ℙ) which does not add any new element of P _κ λ . Actually ℙ* can be chosen so that ℙ* is κ‐strategically closed. However we show that such ℙ* itself cannot be κ‐strategically closed or even <κ‐strategically closed if κ is inaccessible. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Containment for c, s, t operators on a binary relation

The operators c, s and t are complement, symmetric and transitive closure of a binary relation. If u and v denote finite sequences of these operators then we define u v iff for every binary relation . We find the distinct representative and containment between these sequences. The asymmetric operator is not one of these. There are 54 representatives for binary relations, 20 for transitive relations, and 10 for symmetric relations. There are 26 component types of a binary relation, 10 for transitive relations, and 6 for symmetric relations. There are 16 connected types of a binary relation, 8 for transitive relations, and 4 for symmetric relations. We study well founded relations. Total relations may not be contractible but well founded ones are. The complement of (a Hasse diagram of) a non-empty partial order of arbitrary cardinality is contractible. Ordered sets are naturally homotopy equivalent to partially ordered sets. There are 10 relations which can have arbitrary polyhedral homotopy type and 42 are either contractible or the homotopy type of a wedge of n-spheres. The homotopy type of two relations is not determined.     

When a Compact (Countably Compact) set is Closed

We give necessary and sufficient conditions for a compact (countably compact) set to be closed in S ₂ (Fréchet, S ₂) and in normal (Fréchet, normal) spaces. Sufficient conditions are obtained for (i) the closedness of arbitrary (countable) union of closed sets and (ii) the equality of the union of the closures and the closure of the union of arbitrary (countable) families of sets, in such spaces. Countable compactness of the closure of a countably compact set in Fréchet, S ₂-spaces, and related results are also obtained.     

On effective σ‐boundedness and σ‐compactness

We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $\Delta ^{1}_{1}$ equivalence relations $\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$, any $\Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $\Delta ^{1}_{1}$ sets and lightface $\Delta ^{1}_{1}$ equivalence classes of the relations $\mathrel {\mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $\mathrel {\mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $\Sigma ^{1}_{2}$ sets A are obtained.