32
$\begingroup$

The answer to this question must be known, but I do not know where to find it. It is related to the Ulam measures I believe.

Question. Is there a finitely additive measure defined on all subsets of positive integers $\mathbb{N}$, with values into $\{0,1\}$, (only two values) that is $$ \mu:2^{\mathbb{N}}\to \{0,1\} $$ such that $\mu(\{n\})=0$ for every $n\in\mathbb{N}$ and $\mu(\mathbb{N})=1$ ?

I believe such a result is needed in a proof of the co-area inequality that is stated in Coarea inequality, Eilenberg inequality. I am working with my student on some generalizations of that result so this is a research related question.

$\endgroup$
  • 40
    $\begingroup$ This is called non-principal ultrafilter (namely $\mu^{-1}(\{1\})$) $\endgroup$ – YCor Feb 18 at 20:52
  • 9
    $\begingroup$ I don't know (it's extensively documented anyway), but here's a proof (of its existence on any infinite set $X$): the set of ultrafilters is closed in the pointwise convergence topology, hence is compact, and its subset of principal ultrafilters (=Dirac measures) is an infinite discrete subset, hence is not compact and hence is a proper subset. Verifications are straightforward. $\endgroup$ – YCor Feb 18 at 21:31
  • 3
    $\begingroup$ An approach that functional analysts might like is to observe that $l^\infty/c_0$ is a C*-algebra. So let $\phi: l^\infty/c_0 \to \mathbb{C}$ be a unital *-homomorphism, and then define $\mu(S) = \phi(1_S + c_0)$. $\endgroup$ – Nik Weaver Feb 18 at 22:59
  • 4
    $\begingroup$ @DavidHandelman: A non-principal ultrafilter isn’t any kind of “complicated notion” — it’s just spelling out the details of what “maximal ideal” means in this special case (or rather, the dual conditions). $\endgroup$ – Peter LeFanu Lumsdaine Feb 19 at 17:07
  • 2
    $\begingroup$ @DavidHandelman: Sure, I wouldn’t quibble with describing ultrafilters as, say, less familiar. $\endgroup$ – Peter LeFanu Lumsdaine Feb 20 at 0:23
24
$\begingroup$

The answer is yes. I wrote a proof using YCor's comment.

Theorem. There a finitely additive measure defined on all subsets of positive integers $\mathbb{N}$, with values into $\{0,1\}$, (only two values) that is $$ \mu:2^{\mathbb{N}}\to \{0,1\} $$ such that $\mu(\{n\})=0$ for every $n\in\mathbb{N}$ and $\mu(\mathbb{N})=1$.

Proof. Let $$ \mathcal{F}_0=\{A\subset\mathbb{N}:\, \mathbb{N}\setminus A\ \ \text{is finite}.\} $$ $\mathcal{F}_0$ is a filter. By a filter we mean here a family $\mathcal{F}\subset 2^\mathbb{N}$ with the following properties

  1. $\mathbb{N}\in \mathcal{F}$,
  2. $\emptyset\not\in\mathcal{F}$,
  3. $A\in\mathcal{F}$, $A\subset B$ $\Rightarrow$ $B\in\mathcal{F}$,
  4. $A,B\in\mathcal{F}$ $\Rightarrow$ $A\cap B\in\mathcal{F}$.

Lemma. There is a family $\mathcal{F}\subset 2^{\mathbb{N}}$ such that $\mathcal{F}_0\subset\mathcal{F}$ and $\mathcal{F}$ has properties 1.-4. and also property

  1. $A\subset\mathbb{N}$ $\Rightarrow$ $A\in\mathcal{F}$ or $\mathbb{N}\setminus A\in\mathcal{F}$.

Remark. A family $\mathcal{F}\subset 2^\mathbb{N}$ satisfying properties 1.-5. is called an ultrafilter.

Proof. Filters containing $\mathcal{F}_0$ are ordered by the inclusion. The union of a chain of filters is a filter (this is obvious). Therefore by the Kuratowski-Zorn lemma there is a maximal filter $\mathcal{F}$ that contains $\mathcal{F}_0$. It remains to show that $\mathcal{F}$ satisfies property 5. (it has properties 1.-4. since it is a filter).

Suppose to the contrary that there is $A\subset\mathbb{N}$ such that $$ (*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A\not\in\mathcal{F} \quad \text{and} \quad \mathbb{N}\setminus A\not\in \mathcal{F}. $$ Define $$ \widetilde{\mathcal{F}}= \{ E\subset \mathbb{N}:\, \exists B\in\mathcal{F}\ \ A\cap B\subset E\}. $$ Note that $\mathcal{F}\subset\widetilde{\mathcal F}$, because for $B\in\mathcal{F}$, $A\cap B\subset B$ so $E=B\in\widetilde{\mathcal{F}}$. Also $\mathcal{F}\subsetneq\widetilde{F}$ is a propert subset, because $\mathbb{N}\in\mathcal{F}$, $A\cap\mathbb{N}\subset A$ so $A\in\widetilde{\mathcal F}$ by definition and hence $A\in\widetilde{\mathcal F}\setminus\mathcal{F}$.

It remains to prove that $\widetilde{\mathcal F}$ is a filter (has properties 1.-4.) to reach a contradiction with the maximality of $\mathcal{F}$.

Clearly $\widetilde{\mathcal F}$ has properties 1., 3., and 4. (by property 4. for $\mathcal{F}$).

It remains to prove property 2. Suppose to the contrary that $\emptyset\in \widetilde{\mathcal F}$. Then $A\cap B=\emptyset$ for some $B\in\mathcal{F}$. Then $B\subset\mathbb{N}\setminus A$ so $\mathbb{N}\setminus A\in\mathcal{F}$ by property 3. for $\mathcal{F}$ which contradicts $(*)$. The proof is complete. $\Box$

Now we define the finitely additive measure $$ \mu:2^{\mathbb{N}}\to \{0,1\} $$ such that $\mu(\{n\})=0$ for every $n\in\mathbb{N}$ and $\mu(\mathbb{N})=1$ as follows $$ \mu(A)= \begin{cases} 1 & \text{if $A\in \mathcal{F}$},\\ 0 & \text{if $A\not\in\mathcal{F}$}. \end{cases} $$ Finite-additivity of $\mu$ follows from the fact that no two subsets with measure $1$ can be disjoint.

Note: Countable additivity fails because $$ \mathbb{N} = \bigcup_{n=1}^\infty \{n\} \quad \text{but} \quad \mu(\mathbb{N}) \neq \sum_{n=1}^\infty \mu(\{n\}) \ . $$

$\Box$

$\endgroup$
  • 7
    $\begingroup$ This interpretation of ultrafilter was used by Kleiner and Leeb in “Rigidity of quasi-isometries ...” $\endgroup$ – Anton Petrunin Feb 19 at 2:59
22
$\begingroup$

Just about any form of the axiom of choice can be used to prove this. I like topology, so here's a proof using Tychonoff's theorem.

Consider the space $2^{2^\mathbb{N}}$ of all functions $2^{\mathbb{N}}\to\{0,1\}$ under the product topology. By Tychonoff's theorem this is compact, and it is easy to check from the definition of the product topology that the set $\mathcal{F}$ of all finitely-additive $\{0,1\}$-valued measures on $\mathbb{N}$ is closed in $2^{2^\mathbb{N}}$. Then the sequence of measures $\mu_k\in\mathcal{F}$ defined by $$ \mu_k(S) = \begin{cases}1 & \text{if }k\in S,\\ 0 & \text{if }k\notin S\end{cases} $$ must have a limit point $\mu\in\mathcal{F}$. Then $\mu(\mathbb{N})=1$ since $\mu_k(\mathbb{N})=1$ for all $k$, and $\mu(\{n\}) = 0$ for all $n\in\mathbb{N}$ since $\mu_k(\{n\})=0$ whenever $k>n$.

$\endgroup$
  • 2
    $\begingroup$ I like this proof! Here's a fun exercise to go with it: even though the closure of your sequence is compact, no subsequence of it converges! (This seems wrong at first, especially if you're accustomed to working with metric spaces -- but there's no contradiction here.) $\endgroup$ – Will Brian Feb 20 at 14:50
  • 2
    $\begingroup$ This is basically the detailed version of the 3-line proof I gave in a comment. $\endgroup$ – YCor Feb 21 at 13:28
  • $\begingroup$ @YCor Sorry, I hadn't noticed your comment, but you're right that it's the same proof as the one you suggest. $\endgroup$ – Jim Belk Feb 21 at 13:53
17
$\begingroup$

My comment seems to be buried so I'd like to repeat it here. There is a simple C*-algebra construction that answers the question. The quotient space $l^\infty/c_0$ is a unital commutative C*-algebra, so there is a $*$-isomorphism $\Phi: l^\infty/c_0 \cong C(X)$ for some compact Hausdorff space $X$. For any $x \in X$, define $\mu_x(S) = \Phi(1_S)(x)$.

Every such $\mu_x$ works. In fact, this establishes a 1-1 correspondence between the set of non-principal ultrafilters on $\mathbb{N}$ and the spectrum of $l^\infty/c_0$.

$\endgroup$
  • $\begingroup$ And $X$ is in fact the Stone-Čech remainder $\beta \mathbb{N} \setminus \mathbb{N}$, right? So there's another connection. $\endgroup$ – Nate Eldredge Feb 21 at 2:22
  • $\begingroup$ Right, the elements of $\beta\mathbb{N}\setminus\mathbb{N}$ correspond to free ultrafilters. $\endgroup$ – Nik Weaver Feb 21 at 2:36
  • $\begingroup$ @NikWeaver: What is $c_0$? $\endgroup$ – Bumblebee Feb 21 at 16:03
  • 2
    $\begingroup$ @Bumblebee: it is one of the standard sequence spaces. $\endgroup$ – Nik Weaver Feb 21 at 19:37
4
$\begingroup$

This can be proved without introducing ultrafilters by name, by doing "finitary measure theory" and using Zorn's lemma.

An algebra $A$ on a set $X$ is just a $\sigma$-algebra without the $\sigma$, i.e. $\newcommand{\powerset}{\mathcal{P}}A \subseteq \powerset(X)$ and is closed under finite unions and complements (and therefore all other Boolean operations).

Let $\newcommand{\N}{\mathbb{N}}F \subseteq \powerset(\N)$ be the set of finite sets and their complements (so-called cofinite sets). This is an algebra. Furthermore, we can define a 2-valued finitely-additive measure $\mu : F \rightarrow \{0,1\}$ to be $0$ on the finite sets and $1$ on the cofinite sets. The existence of the required 2-valued finitely-additive measure on $\powerset(\N)$ then follows from:

Proposition For any algebra $A \subseteq \powerset(X)$ and finitely-additive 2-valued measure $\mu : A \rightarrow \{0,1\}$, there exists a finitely-additive measure $\overline{\mu} : \powerset(X) \rightarrow \{0,1\}$ extending $\mu$.

Proof: Most of the difficulty is in believing that it's true. We use Zorn's lemma. The poset consists of pairs $(B,\nu)$ where $B \supseteq A$ is an algebra of sets, and $\nu : B \rightarrow \{0,1\}$ is a finitely-additive measure extending $\mu$. The order relation $(B_1,\nu_1) \leq (B_2,\nu_2)$ is defined to hold when $B_1 \subseteq B_2$ and $\nu_2$ extends $\nu_1$. Every chain in this poset has an upper bound - we just take the union of algebras (this is the step that fails for $\sigma$-algebras) and define the measure on the union in the obvious way.

Let $(B,\nu)$ be a maximal element in the poset. Suppose for a contradiction that $B \neq \powerset(X)$, so there is some $U \in \powerset(X) \setminus B$. We contradict the maximality of $B$ by extending $\nu$ to a larger algebra $B'$ including $U$. Define $B' = \{ (U \cap S_1) \cup (\lnot U \cap S_2) \mid S_1, S_2 \in B \}$. It is clear that $B \subseteq B'$ and $U \in B'$, and with a little Boolean reasoning we can prove that for all $S_1,S_2,T_1,T_2 \in B$: $$ ((U \cap S_1) \cup (\lnot U \cap S_2)) \cup ((U \cap T_1) \cup (\lnot U \cap T_2))\\ = (U \cap (S_1 \cup T_1)) \cup (\lnot U \cap (S_2 \cup T_2)) $$ and $$ \lnot ((U \cap S_1) \cup (\lnot U \cap S_2)) = (U \cap \lnot S_1) \cup (\lnot U \cap \lnot S_2) $$ This proves that $B'$ is an algebra.

Now, define $d \in \{0,1\}$ to be the "outer measure" of $U$, i.e. $d = 0$ if there exists $S \in B$ such that $U \subseteq S$ and $\nu(S) = 0$, otherwise $d = 1$. Without loss of generality we can take $d = 1$, because we can exchange the roles of $U$ and $\lnot U$. We define $\nu'((U \cap S_1) \cup (\lnot U \cap S_2)) = \nu(S_1)$. This is well-defined because if $(U \cap S_1) \cup (\lnot U \cap S_2) = (U \cap T_1) \cup (\lnot U \cap S_2)$, then $U \cap S_1 = U \cap S_2$, so $U \subseteq \lnot (S_1 \triangle S_2)$, so as $d = 1$, $\nu(\lnot (S_1 \triangle S_2)) = 1$, and therefore $\nu(S_1) = \nu(S_2)$. The identities we used to prove that $B'$ is an algebra can then be used to prove that $\nu'$ is finitely additive, and it follows directly from the definition that it extends $\nu$. So we successfully contradicted the maximality of $B$. $\square$


Of course, I actually think ultrafilters are a good thing to know about, both in topology and logic. There is also no metamathematical benefit in doing it this way - over ZF the existence of a non-principal ultrafilter on $\N$ and a finitely-additive 2-valued measure on $\powerset(\N)$ are equivalent. The above proof is based on something I came up with while reproving Stone duality in the case where the points of the Stone space are defined to be Boolean homomorphisms into $2$, rather than ultrafilters. The proposition above is a special case of the fact that complete Boolean algebras (such as $2$) are injective objects in the category of Boolean algebras.

$\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.