Search

State machines are used in engineering many types of software-intensive systems. UML State Machines extend simple finite state machines with powerful constructs. Among the many extensions, there is one seemingly simple and innocent language construct that fundamentally changes state machines' reactive model of computation: doActivity behaviors. DoActivity behaviors describe behavior that is executed independently from the state machine once entered in a given state, typically modeling complex computation or communication as background tasks. However, the UML specification or textbooks are vague about how the doActivity behavior construct should be appropriately used. This lack of guidance is a severe issue as, when improperly used, doActivities can cause concurrent, non-deterministic bugs that are especially challenging to find and could ruin a seemingly correct software design. The Precise Semantics of UML State Machines (PSSM) specification introduced detailed operational semantics for state machines. To the best of our knowledge, there is no rigorous review yet of doActivity's semantics as specified in PSSM. We analyzed the semantics by collecting evidence from cross-checking the text of the specification, its semantic model and executable test cases, and the simulators supporting PSSM. We synthesized insights about subtle details and emergent behaviors relevant to tool developers and advanced modelers. We reported inconsistencies and missing clarifications in more than 20 issues to the standardization committee. Based on these insights, we studied 11 patterns for doActivities detailing the consequences of using a doActivity in a given situation and discussing countermeasures or alternative design choices. We hope that our analysis of the semantics and the patterns help vendors develop conformant simulators or verification tools and engineers design better state machine models.

We prove that the universal solenoid is the generic (in the sense of Baire category) connected compact metrizable abelian group. We also settle the dual problem in the sense of Pontryagin duality: $(\mathbb{Q},+)$, which is the dual of the universal solenoid, is the generic countably infinite torsion-free abelian group., Comment: 13 pages

We study generic properties of topological groups in the sense of Baire category. First we investigate countably infinite (discrete) groups. We extend a classical result of B. H. Neumann, H. Simmons and A. Macintyre on algebraically closed groups and the word problem. I. Goldbring, S. E. Kunnawalkam and Y. Lodha proved that every isomorphism class is meager among countably infinite (discrete) groups. In contrast, we show that there is a comeager isomorphism class among countably infinite (discrete) abelian groups. Then we turn to compact metrizable abelian groups. We use Pontryagin duality to show that there is a comeager isomorphism class among compact metrizable abelian groups. We discuss its connections to the countably infinite (discrete) case. Finally, we study compact metrizable groups. We prove that the generic compact metrizable group is neither connected nor totally disconnected; also it is neither torsion-free nor a torsion group., Comment: arXiv admin note: text overlap with arXiv:2110.15902

Countably infinite groups (with a fixed underlying set) constitute a Polish space $G$ with a suitable metric, hence the Baire category theorem holds in $G$. We study isomorphism invariant subsets of $G$, which we call group properties. We say that the generic countably infinite group is of property $P$ if $P$ is comeager in $G$. We prove that every group property with the Baire property is either meager or comeager. We show that there is a comeager elementary equivalence class in $G$ but every isomorphism class is meager. We prove that the generic group is algebraically closed, simple, not finitely generated and not locally finite. We show that in the subspace of Abelian groups the generic group is isomorphic to the unique countable, divisible torsion group that contains every finite Abelian group. We sketch the model-theoretic setting in which many of our results can be generalized. We briefly discuss a connection with infinite games., Comment: We have very recently become aware of the fact that another research group is working on very similar problems, see arXiv:2006.14048

We say that $E$ is a microset of the compact set $K\subset \mathbb{R}^d$ if there exist sequences $\lambda_n\geq 1$ and $u_n\in \mathbb{R}^d$ such that $(\lambda_n K + u_n ) \cap [0,1]^d$ converges to $E$ in the Hausdorff metric, and moreover, $E \cap (0, 1)^d \neq \emptyset$. The main result of the paper is that for a non-empty set $A\subset [0,d]$ there is a compact set $K\subset \mathbb{R}^d$ such that the set of Hausdorff dimensions attained by the microsets of $K$ equals $A$ if and only if $A$ is analytic and contains its infimum and supremum. This answers a question of Fraser, Howroyd, K\"aenm\"aki, and Yu. We show that for every compact set $K\subset \mathbb{R}^d$ and non-empty analytic set $A\subset [0,\dim_H K]$ there is a set $\mathcal{C}$ of compact subsets of $K$ which is compact in the Hausdorff metric and $\{\dim_H C: C\in \mathcal{C} \}=A$. The proof relies on the technique of stochastic co-dimension applied for a suitable coupling of fractal percolations with generation dependent retention probabilities. We also examine the analogous problems for packing and box dimensions., Comment: 21 pages, the proofs of Theorems 4.7 and 4.8 were improved, also some minor modifications

The lower dimension $\dim_L$ is the dual concept of the Assouad dimension. As it fails to be monotonic, Fraser and Yu introduced the modified lower dimension $\dim_{ML}$ by making the lower dimension monotonic with the simple formula $\dim_{ML} X=\sup\{\dim_L E: E\subset X\}$. As our first result we prove that the modified lower dimension is finitely stable in any metric space, answering a question of Fraser and Yu. We prove a new, simple characterization for the modified lower dimension. For a metric space $X$ let $\mathcal{K}(X)$ denote the metric space of the non-empty compact subsets of $X$ endowed with the Hausdorff metric. As an application of our characterization, we show that the map $\dim_{ML} \colon \mathcal{K}(X)\to [0,\infty]$ is Borel measurable. More precisely, it is of Baire class $2$, but in general not of Baire class $1$. This answers another question of Fraser and Yu. Finally, we prove that the modified lower dimension is not Borel measurable defined on the closed sets of $\ell^1$ endowed with the Effros Borel structure., Comment: 10 pages. A new paragraph added to the introduction

This report contains an analysis of the queries defined in the SIGMOD 2014 Programming Contest. We first describe the data set, then present the queries, providing graphical illustrations for them and pointing out their caveats. Our intention is to document our lessons learnt and simplify the work of those who will attempt to create a solution to this contest. We also demonstrate the influence of this contest by listing followup works which used these queries as inspiration to design better algorithms or to define interesting graph queries.

We consider a real-valued function $f$ defined on the set of infinite branches $X$ of a countably branching pruned tree $T$. The function $f$ is said to be a \textit{limsup function} if there is a function $u \colon T \to \mathbb{R}$ such that $f(x) = \limsup_{t \to \infty} u(x_{0},\dots,x_{t})$ for each $x \in X$. We study a game characterization of limsup functions, as well as a novel game characterization of functions of Baire class 1.

S. Banach pointed out that the graph of the generic (in the sense of Baire category) element of $\text{Homeo}([0,1])$ has length $2$. J. Mycielski asked if the measure theoretic dual holds, i.e., if the graph of all but Haar null many (in the sense of Christensen) elements of $\text{Homeo}([0,1])$ have length $2$. We answer this question in the affirmative. We call $f \in \text{Homeo}([0,1]^d)$ singular if it takes a suitable set of full measure to a nullset, and strongly singular if it is almost everywhere differentiable with singular derivative matrix. Since the graph of $f \in \text{Homeo}([0,1])$ has length $2$ iff $f$ is singular iff $f$ is strongly singular, the following results are the higher dimensional analogues of Banach's observation and our solution to Mycielski's problem. We show that for $d \ge 2$ the graph of the generic element of $\text{Homeo}([0,1]^d)$ has infinite $d$-dimensional Hausdorff measure, contrasting the above result of Banach. The measure theoretic dual remains open, but we show that the set of elements of $\text{Homeo}([0,1]^d)$ with infinite $d$-dimensional Hausdorff measure is not Haar null. We show that for $d \ge 2$ the generic element of $\text{Homeo}([0,1]^d)$ is singular but not strongly singular. We also show that for $d \ge 2$ almost every element of $\text{Homeo}([0,1]^d)$ is singular, but the set of strongly singular elements form a so called Haar ambivalent set (neither Haar null, nor co-Haar null). Finally, in order to clarify the situation, we investigate the various possible definitions of singularity for maps of several variables, and explore the connections between them., Comment: 31 pages. Final version with minor modifications

We answer a question of Banakh, Jab\l{}o\'nska and Jab\l{}o\'nski by showing that for $d\ge 2$ there exists a compact set $K \subseteq \mathbb{R}^d$ such that the projection of $K$ onto each hyperplane is of non-empty interior, but $K+K$ is nowhere dense. The proof relies on a random construction. A natural approach in the proofs is to construct such a $K$ in the unit cube with full projections, that is, such that the projections of $K$ agree with that of the unit cube. We investigate the generalization of these problems for projections onto various dimensional subspaces as well as for $\ell$-fold sumsets. We obtain numerous positive and negative results, but also leave open many interesting cases. We also show that in most cases if we have a specific example of such a compact set then actually the generic (in the sense of Baire category) compact set in a suitably chosen space is also an example. Finally, utilizing a computer-aided construction, we show that the compact set in the plane with full projections and nowhere dense sumset can be self-similar., Comment: 26 pages, 3 figures. Small modifications, final version

We show that every non-Haar-null analytic subset of $\mathbb{Z}^\omega$ contains a non-Haar-null closed subset. Moreover, we also prove that the codes of Haar-null analytic subsets, and, consequently, closed Haar-null sets in the Effros Borel space of $\mathbb{Z}^\omega$ form a $\mathbf{\Delta}^1_2$ set.

A subset $X$ of a Polish group $G$ is \emph{Haar null} if there exists a Borel probability measure $\mu$ and a Borel set $B$ containing $X$ such that $\mu(gBh)=0$ for every $g,h \in G$. A set $X$ is \emph{Haar meager} if there exists a compact metric space $K$, a continuous function $f : K \to G$ and a Borel set $B$ containing $X$ such that $f^{-1}(gBh)$ is meager in $K$ for every $g,h \in G$. We calculate (in $ZFC$) the four cardinal invariants ($\rm add$, $\rm cov$, $\rm non$, $\rm cof$) of these two $\sigma$-ideals for the simplest non-locally compact Polish group, namely in the case $G = \mathbb{Z}^\omega$. In fact, most results work for separable Banach spaces as well, and many results work for Polish groups admitting a two-sided invariant metric. This answers a question of the first named author and Z. Vidny\'anszky.

We give a complete description of the size of the conjugacy classes of the automorphism group of the random graph with respect to Christensen's Haar null ideal. It is shown that every non-Haar null class contains a translated copy of a nonempty portion of every compact set and that there are continuum many non-Haar null conjugacy classes. Our methods also yield a new proof of an old result of Truss., Comment: Most of this work previously appeared in the first version of the paper arXiv:1705.07593 which was split into 3 articles

In order to understand the structure of the "typical" element of an automorphism group, one has to study how large the conjugacy classes of the group are. For the case when typical is meant in the sense of Baire category, Truss proved that there is a co-meagre conjugacy class in Aut(Q, <), the automorphism group of the rational numbers. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. We give a complete description of the size of the conjugacy classes of Aut(Q, <) with respect to this notion. In particular, we show that there exist continuum many non-Haar null conjugacy classes, illustrating that the random behaviour is quite different from the typical one in the sense of Baire category., Comment: Most of this work previously appeared in the first version of the paper arXiv:1705.07593 which was split into 3 articles, including arXiv:1808.06121

Following Darji, we say that a Borel subset $B$ of an abelian Polish group $G$ is Haar meager if there is a compact metric space $K$ and a continuous function $f : K \to G$ such that the preimage of the translate, $f^{-1}(B+g)$ is meager in $K$ for every $g \in G$. The set $B$ is called strongly Haar meager if there is a compact set $C \subseteq G$ such that $(B+g) \cap C$ is meager in $C$ for every $g \in G$. The main open problem in this area is Darji's question asking whether these two notions are the same. Even though there have been several partial results suggesting a positive answer, in this paper we construct a counterexample. More specifically, we construct a $G_\delta$ set in $\mathbb{Z}^\omega$ that is Haar meager but not strongly Haar meager. We also show that no $F_\sigma$ counterexample exists, hence our result is optimal.

In order to understand the structure of the `typical' element of an automorphism group, one has to study how large the conjugacy classes of the group are. When typical is meant in the sense of Baire category, a complete description of the size of the conjugacy classes has been given by Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. When typical means random, that is, almost every with respect to this notion of Haar null sets, the behavior of the automorphisms is entirely different from the Baire category case. In this paper, we generalize the theorems of Dougherty and Mycielski about $S_\infty$ to arbitrary automorphism groups of countable structures isolating a new model theoretic property, the Cofinal Strong Amalgamation Property. As an application we show that a large class of automorphism groups can be decomposed into the union of a meager and a Haar null set.

In order to understand the structure of the "typical" element of a homeomorphism group, one has to study how large the conjugacy classes of the group are. When typical means generic in the sense of Baire category, this is well understood, see e.g. the works of Glasner and Weiss, and Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. When typical means random, that is, almost every with respect to this notion of Haar null sets, the behaviour of the homeomorphisms is entirely different from the generic case. For $\text{Homeo}^+([0,1])$ we describe the non-Haar null conjugacy classes and also show that their union is co-Haar null, for $\text{Homeo}^+(\mathbb{S}^1)$ we describe the non-Haar null conjugacy classes, and for $\mathcal{U}(\ell^2)$ we show that, apart from the classes of the multishifts, all conjugacy classes are Haar null. As an application we affirmatively answer the question whether these groups can be written as the union of a meagre and a Haar null set.

We survey results about Haar null subsets of (not necessarily locally compact) Polish groups. The aim of this paper is to collect the fundamental properties of the various possible definitions of Haar null sets, and also to review the techniques that may enable the reader to prove results in this area. We also present several recently introduced ideas, including the notion of Haar meager sets, which are closely analogous to Haar null sets. We prove some results in a more general setting than that of the papers where they were originally proved and prove some results for Haar meager sets which were already known for Haar null sets.

Let $(G,\cdot)$ be a Polish group. We say that a set $X \subset G$ is Haar null if there exists a universally measurable set $U \supset X$ and a Borel probability measure $\mu$ such that for every $g, h \in G$ we have $\mu(gUh)=0$. We call a set $X$ naively Haar null if there exists a Borel probability measure $\mu$ such that for every $g, h \in G$ we have $\mu(gXh)=0$. Generalizing a result of Elekes and Stepr\=ans, which answers the first part of Problem FC from Fremlin's list, we prove that in every abelian Polish group there exists a naively Haar null set that is not Haar null.

J. Zapletal asked if all the forcing notions considered in his monograph are homogeneous. Specifically, he asked if the forcing consisting of Borel sets of $\sigma$-finite 2-dimensional Hausdorff measure in $\mathbb{R}^3$ (ordered under inclusion) is homogeneous. We give a partial negative answer to both questions by showing that this $\sigma$-ideal is not homogeneous. Let $\mathcal{N}^1_2$ be the $\sigma$-ideal of sets in the plane of 1-dimensional Hausdorff measure zero. D. H. Fremlin determined the position of the cardinal invariants of this $\sigma$-ideal in the Cicho\'n Diagram. This required proving numerous inequalities, and in all but three cases it was known that the inequalities can be strict in certain models. For one of the remaining ones Fremlin posed this as an open question in his monograph. We answer this by showing that consistently $\mathrm{cov}(\mathcal{N}^1_2) > \mathrm{cov}(\mathcal{N})$, where $\mathcal{N}$ is the usual Lebesgue null ideal. We also prove that the remaining two inequalities can be strict. Moreover, we fit the cardinal invariants of the $\sigma$-ideal of sets of $\sigma$-finite Hausdorff measure into the diagram. P. Humke and M. Laczkovich raised the following question. Is it consistent that there is an ordering of the reals in which all proper initial segments are Lebesgue null but for every ordering of the reals there is a proper initial segment that is not null with respect to the $1/2$-dimensional Hausdorff measure? We determine the values of the cardinal invariants of the Cicho\'n Diagram as well as the invariants of the nullsets of Hausdorff measures in the first model mentioned in the previous paragraph, and as an application we answer this question of Humke and Laczkovich affirmatively.

In the 1970s M. Laczkovich posed the following problem: Let $\mathcal{B}_1(X)$ denote the set of Baire class $1$ functions defined on an uncountable Polish space $X$ equipped with the pointwise ordering. \[\text{Characterize the order types of the linearly ordered subsets of $\mathcal{B}_1(X)$.} \]The main result of the present paper is a complete solution to this problem. We prove that a linear order is isomorphic to a linearly ordered family of Baire class $1$ functions iff it is isomorphic to a subset of the following linear order that we call $([0,1]^{<\omega_1}_{\searrow 0},<_{altlex})$, where $[0,1]^{<\omega_1}_{\searrow 0}$ is the set of strictly decreasing transfinite sequences of reals in $[0, 1]$ with last element $0$, and $<_{altlex}$, the so called \emph{alternating lexicographical ordering}, is defined as follows: if $(x_\alpha)_{\alpha\leq \xi}, (x'_\alpha)_{\alpha\leq \xi'} \in [0,1]^{<\omega_1}_{\searrow 0}$, and $\delta$ is the minimal ordinal where the two sequences differ then we say that \[ (x_\alpha)_{\alpha\leq \xi} <_{altlex} (x'_\alpha)_{\alpha\leq \xi'} \iff (\delta \text{ is even and } x_{\delta}x'_{\delta}). \] Using this characterization we easily reprove all the known results and answer all the known open questions of the topic.

The notions of shyness and prevalence generalize the property of being zero and full Haar measure to arbitrary (not necessarily locally compact) Polish groups. The main goal of the paper is to answer the following question: What can we say about the Hausdorff and packing dimension of the fibers of prevalent continuous maps? Let $K$ be an uncountable compact metric space. We prove that the prevalent $f\in C(K,\mathbb{R}^d)$ has many fibers with almost maximal Hausdorff dimension. This generalizes a theorem of Dougherty and yields that the prevalent $f\in C(K,\mathbb{R}^d)$ has graph of maximal Hausdorff dimension, generalizing a result of Bayart and Heurteaux. We obtain similar results for the packing dimension. We show that for the prevalent $f\in C([0,1]^m,\mathbb{R}^d)$ the set of $y\in f([0,1]^m)$ for which $\dim_H f^{-1}(y)=m$ contains a dense open set having full measure with respect to the occupation measure $\lambda^m \circ f^{-1}$, where $\dim_H$ and $\lambda^m$ denote the Hausdorff dimension and the $m$-dimensional Lebesgue measure, respectively. We also prove an analogous result when $[0,1]^m$ is replaced by any self-similar set satisfying the open set condition. We cannot replace the occupation measure with Lebesgue measure in the above statement: We show that the functions $f\in C[0,1]$ for which positively many level sets are singletons form a non-shy set in $C[0,1]$. In order to do so, we generalize a theorem of Antunovi\'c, Burdzy, Peres and Ruscher. As a complementary result we prove that the functions $f\in C[0,1]$ for which $\dim_H f^{-1}(y)=1$ for all $y\in (\min f,\max f)$ form a non-shy set in $C[0,1]$. We also prove sharper results in which large Hausdorff dimension is replaced by positive measure with respect to generalized Hausdorff measures, which answers a problem of Fraser and Hyde., Comment: 42 pages

In 1990 Kechris and Louveau developed the theory of three very natural ranks on the Baire class $1$ functions. A rank is a function assigning countable ordinals to certain objects, typically measuring their complexity. We extend this theory to the case of Baire class $\xi$ functions, and generalize most of the results from the Baire class 1 case. We also show that their assumption of the compactness of the underlying space can be eliminated. As an application, we solve a problem concerning the so called solvability cardinals of systems of difference equations, arising from the theory of geometric decompositions. We also show that certain other very natural generalizations of the ranks of Kechris and Louveau surprisingly turn out to be bounded in $\omega_1$. Finally, we prove a general result showing that all ranks satisfying some natural properties coincide for bounded functions.

We consider decompositions of the real line into pairwise disjoint Borel pieces so that each piece is closed under addition. How many pieces can there be? We prove among others that the number of pieces is either at most 3 or uncountable, and we show that it is undecidable in $ZFC$ and even in the theory $ZFC + \mathfrak{c} = \omega_2$ if the number of pieces can be uncountable but less than the continuum. We also investigate various versions: what happens if we drop the Borelness requirement, if we replace addition by multiplication, if the pieces are subgroups, if we partition $(0,\infty)$, and so on.

Let $G$ be an abelian Polish group, e.g. a separable Banach space. A subset $X \subset G$ is called Haar null (in the sense of Christensen) if there exists a Borel set $B \supset X$ and a Borel probability measure $\mu$ on $G$ such that $\mu(B+g)=0$ for every $g \in G$. The term shy is also commonly used for Haar null, and co-Haar null sets are often called prevalent. Answering an old question of Mycielski we show that if $G$ is not locally compact then there exists a Borel Haar null set that is not contained in any $G_\delta$ Haar null set. We also show that $G_\delta$ can be replaced by any other class of the Borel hierarchy, which implies that the additivity of the $\sigma$-ideal of Haar null sets is $\omega_1$. The definition of a generalised Haar null set is obtained by replacing the Borelness of $B$ in the above definition by universal measurability. We give an example of a generalised Haar null set that is not Haar null, more precisely we construct a coanalytic generalised Haar null set without a Borel Haar null hull. This solves Problem GP from Fremlin's problem list. Actually, all our results readily generalise to all Polish groups that admit a two-sided invariant metric., Comment: 10 pages

A set $\mathcal{A}\subset C[0,1]$ is \emph{shy} or \emph{Haar null } (in the sense of Christensen) if there exists a Borel set $\mathcal{B}\subset C[0,1]$ and a Borel probability measure $\mu$ on $C[0,1]$ such that $\mathcal{A}\subset \mathcal{B}$ and $\mu\left(\mathcal{B}+f\right) = 0$ for all $f \in C[0,1]$. The complement of a shy set is called a \emph{prevalent} set. We say that a set is \emph{Haar ambivalent} if it is neither shy nor prevalent. The main goal of the paper is to answer the following question: What can we say about the topological properties of the level sets of the prevalent/non-shy many $f\in C[0,1]$? The classical Bruckner--Garg Theorem characterizes the level sets of the generic (in the sense of Baire category) $f\in C[0,1]$ from the topological point of view. We prove that the functions $f\in C[0,1]$ for which the same characterization holds form a Haar ambivalent set. In an earlier paper we proved that the functions $f\in C[0,1]$ for which positively many level sets with respect to the Lebesgue measure $\lambda$ are singletons form a non-shy set in $C[0,1]$. The above result yields that this set is actually Haar ambivalent. Now we prove that the functions $f\in C[0,1]$ for which positively many level sets with respect to the occupation measure $\lambda\circ f^{-1}$ are not perfect form a Haar ambivalent set in $C[0,1]$. We show that for the prevalent $f\in C[0,1]$ for the generic $y\in f([0,1])$ the level set $f^{-1}(y)$ is perfect. Finally, we answer a question of Darji and White by showing that the set of functions $f \in C[0,1]$ for which there exists a perfect $P_f\subset [0,1]$ such that $f'(x) = \infty$ for all $x \in P_f$ is Haar ambivalent., Comment: 12 pages

More than 80 years ago Kolmogorov asked the following question. Let $E\subseteq \mathbb{R}^{2}$ be a measurable set with $\lambda^{2}(E)<\infty$, where $\lambda^2$ denotes the two-dimensional Lebesgue measure. Does there exist for every $\varepsilon>0$ a contraction $f\colon E\to \mathbb{R}^{2}$ such that $\lambda^{2}(f(E))\geq \lambda^{2}(E)-\varepsilon$ and $f(E)$ is a polygon? We answer this question in the negative by constructing a bounded, simply connected open counterexample. Our construction can easily be modified to yield the analogous result in higher dimensions., Comment: 5 pages

A subset $X$ of a Polish group $G$ is called \emph{Haar null} if there exists a Borel set $B \supset X$ and Borel probability measure $\mu$ on $G$ such that $\mu(gBh)=0$ for every $g,h \in G$. We prove that there exists a set $X \subset \mathbb{R}$ that is not Lebesgue null and a Borel probability measure $\mu$ such that $\mu(X + t) = 0$ for every $t \in \mathbb{R}$. This answers a question from David Fremlin's problem list by showing that one cannot simplify the definition of a Haar null set by leaving out the Borel set $B$. (The answer was already known assuming the Continuum Hypothesis.) This result motivates the following Baire category analogue. It is consistent with $ZFC$ that there exist an abelian Polish group $G$ and a Cantor set $C \subset G$ such that for every non-meagre set $X \subset G$ there exists a $t \in G$ such that $C \cap (X + t)$ is relatively non-meagre in $C$. This essentially generalises results of Bartoszy\'nski and Burke-Miller.

Let us say that an element of a given family $\A$ of subsets of $\R^d$ can be reconstructed using $n$ test sets if there exist $T_1,...,T_n \subset \R^d$ such that whenever $A,B\in \A$ and the Lebesgue measures of $A \cap T_i$ and $B \cap T_i$ agree for each $i=1,...,n$ then $A=B$. Our goal will be to find the least such $n$. We prove that if $\A$ consists of the translates of a fixed reasonably nice subset of $\R^d$ then this minimum is $n=d$. In order to obtain this result we reconstruct a translate of a fixed function using $d$ test sets as well, and also prove that under rather mild conditions the measure function $f_{K,\theta} (r) = \la^{d-1} (K \cap \{x \in \RR^d : = r\})$ of the sections of $K$ is absolutely continuous for almost every direction $\theta$. These proofs are based on techniques of harmonic analysis. We also show that if $\A$ consists of the magnified copies $rE+t$ $(r\ge 1, t\in\R^d)$ of a fixed reasonably nice set $E\subset \R^d$, where $d\ge 2$, then $d+1$ test sets reconstruct an element of $\A$. This fails in $\R$: we prove that an interval, and even an interval of length at least 1 cannot be reconstructed using 2 test sets. Finally, using randomly constructed test sets, we prove that an element of a reasonably nice $k$-dimensional family of geometric objects can be reconstructed using $2k+1$ test sets. A example from algebraic topology shows that $2k+1$ is sharp in general.

R.D.Mauldin asked if every translation invariant $\sigma$-finite Borel measure on $\RR^d$ is a constant multiple of Lebesgue measure. The aim of this paper is to show that the answer is "yes and no", since surprisingly the answer depends on what we mean by Borel measure and by constant. We present Mauldin's proof of what he called a folklore result, stating that if the measure is only defined for Borel sets then the answer is affirmative. Then we show that if the measure is defined on a $\sigma$-algebra \emph{containing} the Borel sets then the answer is negative. However, if we allow the multiplicative constant to be infinity, then the answer is affirmative in this case as well. Moreover, our construction also shows that an isometry invariant $\sigma$-finite Borel measure (in the wider sense) on $\RR^d$ can be non-$\sigma$-finite when we restrict it to the Borel sets.

We show that the Continuum Hypothesis implies that for every $0

We give an affirmative answer to a question of K. Ciesielski by showing that the composition $f\circ g$ of two derivatives $f,g:[0,1]\to[0,1]$ always has a fixed point. Using Maximoff's Theorem we obtain that the composition of two $[0,1]\to[0,1]$ Darboux Baire-1 functions must also have a fixed point.

Gruenhage asked if it was possible to cover the real line by less than continuum many translates of a compact nullset. Under the Continuum Hypothesis the answer is obviously negative. Elekes and Stepr\=ans gave an affirmative answer by showing that if $C_{EK}$ is the well known compact nullset considered first by Erd\H os and Kakutani then $\RR$ can be covered by $\cof(\iN)$ many translates of $C_{EK}$. As this set has no analogue in more general groups, it was posed as an open question whether such a result holds for uncountable locally compact Polish groups. In this paper we give an affirmative answer in the abelian case. More precisely, we show that if $G$ is a nondiscrete locally compact abelian group in which every open subgroup is of index at most $\cof(\iN)$ then there exists a compact set $C$ of Haar measure zero such that $G$ can be covered by $\cof(\iN)$ many translates of $C$. This result, which is optimal in a sense, covers the cases of uncountable compact abelian groups and of nondiscrete separable locally compact abelian groups. We use Pontryagin's duality theory to reduce the problem to three special cases; the circle group, countable products of finite discrete abelian groups, and the groups of $p$-adic integers, and then we solve the problem on these three groups separately. In addition, using representation theory, we reduce the nonabelian case to the classes of Lie groups and profinite groups, and we also settle the problem for Lie groups. We remark that M.~Ab\'ert recently gave an affirmative answer for profinite groups.

We show that the existence of measurable envelopes of all subsets of $\RR^n$ with respect to the $d$-dimensional Hausdorff measure $(0

We answer a question of Darji and Keleti by proving that there exists a compact set $C_0\subset\RR$ of measure zero such that for every perfect set $P\subset\RR$ there exists $x\in\RR$ such that $(C_0+x)\cap P$ is uncountable. Using this $C_0$ we answer a question of Gruenhage by showing that it is consistent with $ZFC$ (as it follows e.g. from $\textrm{cof}(\iN)<2^\omega$) that less than $2^\omega$ many translates of a compact set of measure zero can cover $\RR$.

We show that the set of Liouville numbers is either null or non-$\sigma$-finite with respect to every translation invariant Borel measure on $\RR$, in particular, with respect to every Hausdorff measure $\iH^g$ with gauge function $g$. This answers a question of D. Mauldin. We also show that some other simply defined Borel sets like non-normal or some Besicovitch-Eggleston numbers, as well as all Borel subgroups of $\RR$ that are not $F_\sigma$ possess the above property. We prove that, apart from some trivial cases, the Borel class, Hausdorff or packing dimension of a Borel set with no such measure on it can be arbitrary.

Following Laczkovich we consider the partially ordered set $\iB_1(\RR)$ of Baire class 1 functions endowed with the pointwise order, and investigate the order types of the linearly ordered subsets. Answering a question of Komj\'ath and Kunen we show (in $ZFC$) that special Aronszajn lines are embeddable into $\iB_1(\RR)$. We also show that under Martin's Axiom a linearly ordered set $\mathbb{L}$ with $|\mathbb{L}|<2^\omega$ is embeddable into $\iB_1(\RR)$ iff $\mathbb{L}$ does not contain a copy of $\omega_1$ or $\omega_1^*$. We present a $ZFC$-example of a linear order of size $2^\omega$ showing that this characterisation is not valid for orders of size continuum. These results are obtained using the notion of a compact-special tree; that is, a tree that is embeddable into the class of compact subsets of the reals partially ordered under reverse inclusion. We investigate how this notion is related to the well-known notion of an $\RR$-special tree and also to some other notions of specialness.

The set of continuous or Baire class 1 functions defined on a metric space $X$ is endowed with the natural pointwise partial order. We investigate how the possible lengths of well-ordered monotone sequences (with respect to this order) depend on the space $X$.

We consider the set of Baire 1 functions endowed with the pointwise partial ordering and investigate the structure of the linearly ordered subsets.

We show that if the gradient of $f:\RR^2\rightarrow\RR$ exists everywhere and is nowhere zero, then in a neighbourhood of each of its points the level set $\{x\in\RR^2:f(x)=c\}$ is homeomorphic either to an open interval or to the union of finitely many open segments passing through a point. The second case holds only at the points of a discrete set. We also investigate the global structure of the level sets.

A function $f:\RR^n \to \RR$ is called \emph{vertically rigid} if $graph(cf)$ is isometric to $graph (f)$ for all $c \neq 0$. We settled Jankovi\'c's conjecture in a separate paper by showing that a continuous function $f:\RR \to \RR$ is vertically rigid if and only if it is of the form $a+bx$ or $a+be^{kx}$ ($a,b,k \in \RR$). Now we prove that a continuous function $f:\RR^2 \to \RR$ is vertically rigid if and only if after a suitable rotation around the z-axis $f(x,y)$ is of the form $a + bx + dy$, $a + s(y)e^{kx}$ or $a + be^{kx} + dy$ ($a,b,d,k \in \RR$, $k \neq 0$, $s : \RR \to \RR$ continuous). The problem remains open in higher dimensions.

A function $f:\RR \to \RR$ is called \emph{vertically rigid} if $graph(cf)$ is isometric to $graph (f)$ for all $c \neq 0$. We prove Jankovi\'c's conjecture by showing that a continuous function is vertically rigid if and only if it is of the form $a+bx$ or $a+be^{kx}$ ($a,b,k \in \RR$). We answer a question of Cain, Clark and Rose by showing that there exists a Borel measurable vertically rigid function which is not of the above form. We discuss the Lebesgue and Baire measurable case, consider functions bounded on some interval and functions with at least one point of continuity. We also introduce horizontally rigid functions, and show that a certain structure theorem can be proved without assuming any regularity.

Cain, Clark and Rose defined a function $f\colon \RR^n \to \RR$ to be \emph{vertically rigid} if $\graph(cf)$ is isometric to $\graph (f)$ for every $c \neq 0$. It is \emph{horizontally rigid} if $\graph(f(c \vec{x}))$ is isometric to $\graph (f)$ for every $c \neq 0$ (see \cite{CCR}). In an earlier paper the authors of the present paper settled Jankovi\'c's conjecture by showing that a continuous function of one variable is vertically rigid if and only if it is of the form $a+bx$ or $a+be^{kx}$ ($a,b,k \in \RR$). Later they proved that a continuous function of two variables is vertically rigid if and only if after a suitable rotation around the z-axis it is of the form $a + bx + dy$, $a + s(y)e^{kx}$ or $a + be^{kx} + dy$ ($a,b,d,k \in \RR$, $k \neq 0$, $s : \RR \to \RR$ continuous). The problem remained open in higher dimensions. The characterization in the case of horizontal rigidity is surprisingly simpler. C. Richter proved that a continuous function of one variable is horizontally rigid if and only if it is of the form $a+bx$ ($a,b\in \RR$). The goal of the present paper is to prove that a continuous function of two variables is horizontally rigid if and only if it is of the form $a + bx + dy$ ($a,b,d \in \RR$). This problem also remains open in higher dimensions. The main new ingredient of the present paper is the use of functional equations.

A \emph{hull} of $A \subset [0,1]$ is a set $H$ containing $A$ such that $\lambda^*(H)=\lambda^*(A)$. We investigate all four versions of the following problem. Does there exist a monotone (wrt. inclusion) map that assigns a Borel/$G_\delta$ hull to every negligible/measurable subset of $[0,1]$? Three versions turn out to be independent of ZFC (the usual Zermelo-Fraenkel axioms with the Axiom of Choice), while in the fourth case we only prove that the nonexistence of a monotone $G_\delta$ hull operation for all measurable sets is consistent. It remains open whether existence here is also consistent. We also answer a question of Z. Gyenes and D. P\'alv\"olgyi which asks if monotone hulls can be defined for every chain (wrt. inclusion) of measurable sets. We also comment on the problem of hulls of all subsets of $[0,1]$.

Let $\R^\R$ denote the set of real valued functions defined on the real line. A map $D: \R^\R \to \R^\R$ is a {\it difference operator}, if there are real numbers $a_i, b_i \ (i=1,..., n)$ such that $(Df)(x)=\sum_{i=1}^n a_i f(x+b_i)$ for every $f\in \R^\R $ and $x\in \R$. A {\it system of difference equations} is a set of equations $S={D_i f=g_i : i\in I}$, where $I$ is an arbitrary set of indices, $D_i$ is a difference operator and $g_i$ is a given function for every $i\in I$, and $f$ is the unknown function. One can prove that a system $S$ is solvable if and only if every finite subsystem of $S$ is solvable. However, if we look for solutions belonging to a given class of functions, then the analogous statement fails. For example, there exists a system $S$ such that every finite subsystem of $S$ has a solution which is a trigonometric polynomial, but $S$ has no such solution. This phenomenon motivates the following definition. Let ${\cal F}$ be a class of functions. The {\it solvability cardinal} $\solc (\iF)$ of ${\cal F}$ is the smallest cardinal $\kappa$ such that whenever $S$ is a system of difference equations and each subsystem of $S$ of cardinality less than $\kappa$ has a solution in ${\cal F}$, then $S$ itselfhas a solution in ${\cal F}$. In this paper we determine the solvability cardinals of most function classes that occur in analysis. As it turns out, the behaviour of $\solc ({\cal F})$ is rather erratic. For example, $\solc (\text{polynomials})=3$ but $\solc (\text{trigonometric polynomials})=\omega_1$, $\solc ({f: f\ \text{is continuous}}) = \omega_1$ but $\solc ({f: f\ \text{is Darboux}}) =(2^\omega)^+$, and $\solc (\R^\R)=\omega$. We consistently determine the solvability cardinals of the classes of Borel, Lebesgue and Baire measurable functions, and give some partial answers for the Baire class 1 and Baire class $\alpha$ functions.