1
$\begingroup$

Let $\omega$ denote the set of non-negative integers and let $[\omega]^\omega$ be the collection of infinite subsets of $\omega$.

If $S\in [\omega]^\omega$ and $A\subseteq \omega$ we say that $A$ is well-balanced with respect to $S$ if $$\lim_{n\to\infty}\frac{|A\cap S\cap \{1,\ldots,n\}|}{|S\cap\{1,\ldots,n\}|+1} = 1/2.$$ Intuitively speaking, this means that $A$ contains "half of the members of $S$" (which also implies that $A$ is infinite.)

Question. Given ${\frak S}\subseteq [\omega]^\omega$ with $|{\frak S}| = \aleph_0$, is there $A\in[\omega]^\omega$ such that $A$ is well-balanced with respect to every member of ${\frak S}$?

$\endgroup$
  • $\begingroup$ If we take ${\frak S}$ to be the collection of infinite recursive sets of $\omega$, then any such $A$ would correspond to a bitstream that is computationally random. $\endgroup$ – Dominic van der Zypen Jan 7 at 10:42
  • 2
    $\begingroup$ $\liminf a_n=\limsup a_n=1/2$ can be abbreviated as $\lim a_n=1/2$. $\endgroup$ – GH from MO Jan 7 at 10:45
  • $\begingroup$ Oh right :-) Will simplify the post accordingly, thanks @GHfromMO $\endgroup$ – Dominic van der Zypen Jan 7 at 10:46
  • 5
    $\begingroup$ A random subset of $\omega$ (meaning that $n\in A$ iff the $n^{\text{th}}$ toss in an infinite sequence of fair coin tosses comes of heads) will do the job with probability $1$. $\endgroup$ – bof Jan 7 at 10:56
  • $\begingroup$ Isn't this sometimes called relative density (of the set $A$ with respect to the set $S$)? $\endgroup$ – Martin Sleziak Jan 7 at 10:57
6
$\begingroup$

By the strong law of large numbers, if $S$ is an infinite subset of $\omega$, a random subset of $\omega$ will be well-balanced with respect to $S$ with probability one.

By the countable additivity of Lebesgue measure, if $\mathfrak S$ is a countable collection of infinite subsets of $\omega$, a random subset of $\omega$ will be well-balanced with respect to every member of $\mathfrak S$ with probability one.

If Lebesgue measure is $\kappa$-additive (the union of fewer than $\kappa$ measure zero sets has measure zero) then the same holds for a collection $\mathfrak S$ of infinite subsets of $\omega$ with $|\mathfrak S|\lt\kappa$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.