7
$\begingroup$

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.

  • 2
    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$.2012-08-02
  • 1
    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](http://www.hcm.uni-bonn.de/fileadmin/geschke/papers/IndependentFamilies_03.pdf).2012-08-02
  • 0
    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.2012-08-02
  • 1
    Prof. Burris has corrected the exercise in the 2012 update to the book.2013-02-28

1 Answers 1