I've been learning about non-principal ultrafilters with the overall aim of understanding the ultrapower construction of the Hyperreals.

Couple of things I'm confused on:

Firstly the Ultrafilter Lemma: I'm confused how taking the union of cofinite sets and utilising zorn's lemma shows the filter is non-principal. I think I'm viewing cofinite sets incorrectly... If $q$ is a cofinite subset on the Natural numbers then how can it contain any subset other than the entire set of natural numbers? If it did contain anything else surley the filter would then contain finite sets?

Second: I know to construct Hyperreals we use an equivalence relation, what does it mean for an equivalence relation to be modulo an Ultrafilter; I've only ever seen modulo integers.

Given a free ultrafilter $U$ on $\mathbb{N}$ and real-valued sequences a,b define the relation $=_U$ by $a=_U b$ if $\{j\in\ \mathbb{N}: a_j= b_j\}$ belongs to $U$ in this set what is the purpose of j? Is it simple for labelling the sequences? If so then why does it have to be part of the natural numbers?

Sorry for the long post!

  • $\begingroup$ Thinking about it a bit more I think I've come up with the answer to part three. j is just the labelling subscript, so the set is essentially the "agreement set" i.e. what terms in the real-valued sequences agree? $\endgroup$
    – user253919
    Jul 13, 2015 at 19:35
  • $\begingroup$ Yes, that’s correct. Two sequences are equivalent if they agree on a ‘large’ set, i.e., one that’s in the ultrafilter. I don’t quite understand your question about cofinite sets. $\{n\in\Bbb N:n>3\}$ is a cofinite subset of $\Bbb N$ that is clearly not all of $\Bbb N$, since it’s missing $0,1,2$, and $3$. $\endgroup$ Jul 13, 2015 at 19:41
  • $\begingroup$ Brian, Do you know what it means to be modulo on an ultrafilter then? I initally thought it was like standard modulo arithmetic, but that doesn't make sense? You can't have any remainder in an infnite set... Regarding the cofinite sets I think your example has cleared up my misunderstanding. I was thinking it was taking the union of the complement part {0,1,2,3} in your example, but it isn't! $\endgroup$
    – user253919
    Jul 13, 2015 at 20:17
  • $\begingroup$ When we say, for instance, that two sequences are equal modulo an ultrafilter $\mathscr{U}$, we simply mean that the set of indices on which they agree belongs to $\mathscr{U}$. $\endgroup$ Jul 13, 2015 at 20:29

1 Answer 1


In Part A we try to deal with your question about cofinite sets. In Part B we deal with the more interesting problem of trying to get to grips with the ultrapower.

Part A: We are proving the existence of a non-principal ultrafilter on the the set $\mathbb{N}$ of natural numbers. The same idea works for producing a non-principal ultrafilter on any infinite index set $I$.

Recall that a subset $A$ is a cofinite subset of $\mathbb{N}$ if the complement of $A$ (in $\mathbb{N}$) is finite. For example, the set $A$ of all integers $\gt 100$ is a cofinite subset of $\mathbb{N}$. The set of odd natural numbers is not a cofinite subset of $\mathbb{N}$, since its complement is infinite. A cofinite subsets of $\mathbb{N}$ is really really large, almost all of $\mathbb{N}$, with finitely many exceptions.

The set of cofinite subsets of $\mathbb{N}$ is a filter. To show this, it is enough to show that (i) The empty set is not cofinite; (ii) If $A$ is cofinite, and $A\subset B$, then $B$ is cofinite and (iii) the intersection of any two cofinite subsets of $\mathbb{N}$ is cofinite. These facts are not hard to verify.

By using Zorn's Lemma, we can show that any filter, and in particular the filter $F$ of cofinite subsets of $\mathbb{N}$, can be extended to an ultrafilter. Any ultrafilter $U$ on $\mathbb{N}$ that extends $F$ must be non-principal. For suppose to the contrary that $U$ has the singleton $\{k\}$ as one of its elements. The complement of $\{k\}$ is cofinite, so is in $F$, and therefore in $U$, contradicting the fact that $U$ is an extension of $F$.

Part B: I like to think of an ultrafilter $U$ on $\mathbb{N}$ as a special kind of "measure" $\mu$ defined on all subsets of $\mathbb{N}$. If $A\in U$, then $\mu(A)=1$ and if $A\not\in U$, then $\mu(A)=0$.

Note that the measure $\mu$ is in general only finitely additive, not countably additive. Sets in the ultrafilter are thought of as "large" and their complements are thought of as tiny, negligible.

Let $M$ be an $L$-structure, and let $U$ be an ultrafilter on $\mathbb{N}$, which we would rather call $I$. We want to define what we mean by the $L$-structure $M^I/U$. For now we will only describe the underlying set of the structure $M^I/U$. If you need detail about the $L$-structure, that is, the interpretation of the non-logical symbols of $L$, I can supply it.

Let $|M|$ be the underlying set of $M$. (In your question, $|M|$ is the set of reals.) Then $M^I$ is the set of all functions from the natural numbers $I$ to $|M|$. So $|M|^I$ can be thought of as the set of all infinite sequences $m_0.m_1,m_2,\dots$ of elements of $|M|$.

Call two such sequences equivalent if they are equal "almost everywhere" with respect to the measure $\mu$ induced by the ultrafilter $U$. Mpre technically, we say that the sequences $m_0,m_1,m_2,\dots$ and $m_0',m_1',m_2',\dots$ are equivalent if the set of all $i$ such that $m_i=m_i'$ is a set in the ultrafilter (a "large" set).

Verification that this is indeed an equivalence relation is not hard. For transitivity we will be using the fact that the intersection of two sets in the ultrafilter is in the ultrafilter, that the intersection of two sets of measure $1$ has measure $1$. Now we define the set $|M|^I/U$ as the collection of equivalence classes.

There is (sort of) a connection with arithmetic modulo $m$. There, any two numbers that differ by a multiple of $m$ are thought of as "the same." In the ultrapower, any two sequences that differ only on a set of measure $0$ are thought of as the same. If we go to the language of ideals, we find that in fact the constructions use structurally very similar algebraic concepts, the concept of a quotient structure.

If you have further questions please leave a comment.

  • $\begingroup$ Andre, thanks for such a detailed response. Just to clarify my understanding on the cofinite set, in your example the complement of A would be the integers from 1 to 100? What would the complement of {k} be? I don't know why I'm struggling with this part -.-. Regarding part B I understand parts of it, but think it's getting out of my depth (i'm an undergraduate). $\endgroup$
    – user253919
    Jul 13, 2015 at 21:13
  • $\begingroup$ Depends on whether you think $0$ is a natural number (I do). So the complement of $A$ would be the integers from $0$ to $100$, or $1$ to $100$. The complement of $\{17\}$ is the set of all natural numbers other than $17$. As to quotient structures, one meets them typically (North America) in second year third year. $\endgroup$ Jul 13, 2015 at 21:35
  • $\begingroup$ yeah I figured that bit after. Thanks. I think I'll use Brad's info for the Part B for now and have a look into these quotient structures and then come back and re-read your post (I haven't taken too much group theory); it wasn't offered to much at my university :/. Thanks for the help! $\endgroup$
    – user253919
    Jul 13, 2015 at 21:40
  • $\begingroup$ You are welcome. After a while, work with ultrapowers is pretty intuitive. The only thing that remains (irremediably) somewhat mysterious is the concept of a non-principal ultrafilter, since the Axiom of Choice is necessary even to prove existence, $\endgroup$ Jul 13, 2015 at 22:03

You must log in to answer this question.