2
$\begingroup$

Does the following function $f:\mathcal{P}(\mathbb{N})\rightarrow\{0,1\}$ exist :
$f(\mathbb{N})=1$,
$f(A\cup B)=f(A)+f(B)$ for $A\cap B=\emptyset$,
$f(A)=0$ for finite $A$

$\endgroup$
7
  • 4
    $\begingroup$ This is independent of ZF but follows from AC, and more commonly is known as a non-principal ultrafilter: en.wikipedia.org/wiki/Ultrafilter Anyway, this is not quite a research-level question (see the FAQ). $\endgroup$ Aug 19, 2011 at 21:04
  • 2
    $\begingroup$ Qiaochu, since your suggestion to close the question appears not to be being taken up (only one vote currently), I would encourage you or anyone simply to post an answer explaining in more detail the equivalence of such a function with a nonprincipal ultrafilter on $\mathbb{N}$. I personally find the question of fundamental significance. $\endgroup$ Aug 20, 2011 at 3:35
  • $\begingroup$ Joel: but does 2 exist? $\endgroup$
    – Yemon Choi
    Aug 21, 2011 at 4:59
  • $\begingroup$ Yes, 2={$\varnothing$,{$\varnothing$}}, and this is less than $5$. Are you objecting to my answer? I apologize if I have done something incorrect. $\endgroup$ Aug 21, 2011 at 5:25
  • $\begingroup$ Joel: oh, I'm not objecting, I was being facetious about the use of the word "exist", and the fact that we as mathematicians use it in senses perhaps not shared in other discourses. It was also a ham-fisted way to highlight the sensitivity of the question to a tacit assumption on certain foundations. $\endgroup$
    – Yemon Choi
    Aug 21, 2011 at 7:27

1 Answer 1

6
$\begingroup$

Since the suggestion to close the question has not been successful, allow me to offer an answer as a way of bringing the question to a conclusion.

Many mathematicians find the situation of the question, where one has a finitely additive measure on the natural numbers, to be both fascinating and disturbing.

Nevertheless, one may indeed construct such a function $f$ as you describe. If $\mu$ is any nonprincipal ultrafilter on $\mathbb{N}$, we may define that $f(A)=1$, if $A\in\mu$, and otherwise $f(A)=0$. Ultrafilters are often described as provided a sense of "largeness", and this conforms with the measure-theoretic sense of your question, since the sets in $\mu$ get measure $1$, and the other sets get measure $0$. The reason it works out for additivity is that disjoint sets are never both large, and so the requested $f(A)+f(B)$ always has the form $0+0$, $0+1$ or $1+0$. Specifically, the fact that $\mu$ is nonprincipal implies that finite sets get measure $0$; since $\mathbb{N}\in\mu$, we see that $f(\mathbb{N})=1$; and the additivity property follows from the fact any two sets in $\mu$ have a nonempty intersection, so if $A\cap B=\varnothing$, then at most one of them is in $\mu$.

But in fact, the existence of a function $f$ as you describe is exactly equivalent to a nonprincipal ultrafilter on $\mathbb{N}$, since for any such function $f$ the set of $A\subset\mathbb{N}$ with $f(A)=1$ must contain every set or its complement by the additivity property and contains no finite set by your other hypothesis. Ultimately, it is a nonprincipal ultrafilter on $\mathbb{N}$.

There is nothing special about $\mathbb{N}$ in the argument above, and we might consider nonprincipal ultrafilters on any set $X$, which are equivalent to the existence of a finitely-additive measure $f$ on $X$ as in your question, giving measure $1$ to $X$ and measure $0$ to any finite subset of $X$.

There are a variety of ways to prove that there is a nonprincipal ultrafilter on a set $X$.

  • One may first observe that the collection of co-finite subsets of $X$ forms a filter, often called the Frechet filter, and then by Zorn's lemma we may extend this to a maximal filter, which one then proves contains every set or its complement.

  • Instead, one may enumerate all subsets of $X$ in a well ordered sequence $X_\alpha$, and then decide at stage $\alpha$ of a transfinite recursion to add $X_\alpha$ to the filter being constructed, if this has infinite intersection with all the sets added so far, and otherwise adding the complement of $X_\alpha$. The result is a nonprincipal ultrafilter on $X$.

  • Another way to do it is by appealing to the compactness theorem of first-order logic. Write down the theory axiomatizing the desired properties of $f$ in the language consisting of a function symbol for $f$, plus constants $A$ for each $A\subset\mathbb{N}$ asserting that $f(A)$ is either $0$ or $1$, that additivity holds, that finite sets get measure $0$ and that $\mathbb{N}$ gets measure $1$. This theory is finitely consistent, and so by the compactness theorem it has a consistent completion, which provides an actual measure $f$, as desired.

  • In the case of $\mathbb{N}$, one could consider a nonstandard model of arithmetic $\mathbb{N}^\ast$, and fix a nonstandard infinite integer $N\in\mathbb{N}^\ast$. Now, define that $f(A)=1$, if $N\in A^\ast$, where $A^\ast$ is the nonstandard analogue of $A$, by the transfer principle, and otherwise $f(A)=0$. Thus, the measure $f$ is the trace on the standard model of the nonstandard measure concentrating on the point $N$. This is finitely additive, gives full measure to $\mathbb{N}$ and measure $0$ to finite sets, as desired.

  • In fact, every $f$ as you requested is exactly like the previous example, since if $\mu$ is the ultrafilter of $f$-measure one sets, then the nonstandard number $N=[id]_\mu$ in the ultrapower of $\mathbb{N}$ by $\mu$ has exactly the property that $f(A)=1$ when $N\in A^\ast$.

Finally, it should be mentioned that the proofs I have given above that there is a nonprincipal ultrafilter make essential use of the axiom of choice, and it is consistent with the ZF axioms without choice that there are no nonprincipal ultrafilters and hence no such functions $f$ as you requested. A more subtle fact is that the existence of ultrafilters extending any given filter is a strictly weaker principle than the axiom of choice, and is equivalent to the Boolean prime ideal theorem. Thus, one should not expect completely explicit constructions of examples of such functions $f$ as you have requested, although in the constructible universe $L$ one can find them within fairly low levels of the projective hierarchy of definability.

Lastly, let me mention that the existence of a measurable cardinal, one of the prominent large cardinal hypotheses, is exactly equivalent to asking whether there is a function $f$ defined on subsets of a set $X$ as you request, which moreover is countably additive, instead of merely finitely additive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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