Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Exercise 6.7 in chapter IV of Burris and Sankappanavar's A Course in Universal Algebra starts as follows:

Show that for $I$ countably infinite there is a subset $S$ of the set of functions from $I$ to $2$ which has cardinality equal to that of the continuum such that for $f \not= g$ with $f,g \in S$, $\{i \in I : f(i) = g(i)\}$ is finite.

I don't see how $S$ can have cardinality more than 2: let $f, g, h \in S$, with $f \not= g$ and $f \not= h$ and let $A = \{i \in I : f(i) = g(i)\}$ and $B = \{i \in I : f(i) = h(i)\}$. For $i$ in $I\backslash (A \cup B)$ we have $g(i) \not= f(i) \not= h(i)$, whence $g(i) = h(i)$, since $f(i), g(i), h(i) \in 2 = \{0, 1\}$. But $A$ and $B$ are finite, $I \backslash(A\cup B)$ is infinite. So $g(i) = h(i)$ holds for infinitely many $i$ and we must have $g = h$.

What have I missed? (A redefinition of 2, perhaps?)

I would also be grateful for a reference for what appears to be the goal of this exercise, namely to use an ultraproduct construction to obtain uncountable models from countable ones.

share|cite|improve this question
Since the main goal is to show that $|\,A^I / U\,| \geq 2^{\omega}$ whenever $U$ is a nonprincipal ultrafilter on a countably infinite set $I$ and $A$ is an infinite set, it would make sense to instead find a family $S$ of continuum-many functions $I \to A$ such that $\{ i \in I : f(i) = g(i) \}$ is finite for all distinct $f,g \in S$. – inactive... for now Aug 2 '12 at 11:12
Very likely they only want the sets $\{i \in I\,:\,f(i) = g(i) =1\}$ to be finite (at least from what @Arthur said). Such a family of functions is called almost disjoint. A number of nice arguments of the existence of such families is given in the second section of Geschke's notes on Almost disjoint and independent families. – t.b. Aug 2 '12 at 11:28
I am sure Arthur is right that the first part of the exercise should be about functions $I \rightarrow A$ not $I \rightarrow 2$ (since the second part then follows easily). With this correction, the claim follows easily from the first lemma in Geschke's notes. My thanks to Arthur and t.b. both. – Rob Arthan Aug 2 '12 at 12:05
Prof. Burris has corrected the exercise in the 2012 update to the book. – Rob Arthan Feb 28 '13 at 23:04

On the website of the book there is a newer version and - as the OP already pointed out in their comment the exercise is already corrected there (see page 150). It says:

Show that, for $I$ countably infinite and $A$ infinite, there is a subset $S$ of the set of functions from $I$ to $A$ which has cardinality equal to that of the continuum such that for $f\ne g$ with $f,g\in S$, $\{i\in I; f(i)=g(i)\}$ is finite. Conclude that $|A^I/U|\ge 2^\omega$ if $U$ is a nonprincipal ultrafilter over $I$.

The question basically boils down to finding such family for functions from an infinite countable set to an infinite countable set. (Since $A$ is infinite, it contains an infinite countable set.)$\newcommand{\N}{\mathbb{N}}\newcommand{\Q}{\mathbb{Q}}\newcommand{\R}{\mathbb{R}}$

So we can take $I=\N$ and $A$ can be an arbitrary infinite countable set.

For $A=\Q$ we can repeat basically the same trick as the trick which is used to show the existence of an almost disjoint family of cardinality $\mathfrak c$. See, for example, here or here.

For any real number $r\in\R$ we take any injective sequence $f_r \colon \N \to \Q$ of rational numbers, which converges to $r$. The system $\{f_r; r\in\R\}$ has the same cardinality as $r$. And for any $r\ne r'$ the set $\{i\in\N; f_r(i)=f_{r'}(i)\}$ is finite, since these two sequences have different limits.

A different approach, which only shows that there is uncountably many such functions.

Lemma: If $\{f_n; n\in\N\}$ is a sequence of functions from $\N$ to $\N$ then there is a function $f$ such that each set $A_n=\{i\in\N; f(i)=f_n(i)\}$ is finite.

Proof. We can define $$f(n)=\max\{f_i(j); i=0,\dots,n-1; j=0,\dots,n-1\}+1.$$ Then we have $\{i\in\N; f_n(i)=f(i)\}\subseteq\{0,1,\dots,n\}$. $\qquad\square$

Using the above fact and transfinite induction we can get a family of functions with cardinality $\aleph_1$, which has the required properties.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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