Let $X$ be the first uncountable ordinal. In other words $X$ is an uncountable set equipped with a well-ordering relation "$\leq $" such that, for every $x$ in $X$, the set $$ \{y\in X:\ y\leq x\} $$ is countable. Let $$ T=\{(x, y)\in X\times X:\ y\leq x \}, $$ so that $T$ consist of everything below the diagonal in $X\times X$.

Let us agree to call a subset $G\subseteq T$ a graph, provided $$ \big ((x,y_1)\in G\big ) \ \wedge\ \big ((x,y_2)\in G\big ) \ \Rightarrow \ y_1=y_2. $$ Clearly these are precisely the graphs of $X$-valued functions $f$ defined on subsets of $X$, such that $f(x)\leq x$, for every $x$.

Question: Is it possible to write $T$ as the union of a countable family of graphs?


There's a more general result here:

Suppose $\mathcal{A}=(A_i)_{i\in I}$ is a collection of countable nonempty sets. Then the set $$[\mathcal{A}]=\{(a,i): a\in A_i\}$$ is the union of countably many graphs of functions.

When phrased this way it's much easier to think about. Simply fix surjections $b_i:\omega\rightarrow A_i$, and for $k\in\omega$ let $$f_k:I\rightarrow\bigcup\mathcal{A}:i\mapsto b_i(k).$$ Then the union of the graphs of the $f_k$s is exactly $[\mathcal{A}]$.

(Put another way, $f_k(i)=b_i(k)$ - basically, you have $I$-many "columns" of size $\le\omega$, and you view the whole grid as $\omega$-many "rows" of size $I$.)

Of course, we use the axiom of choice when we pick the $b_i$s, and in the absence of choice can fail (and in particular the special case of your question can fail without choice). But that's a side point.

  • 5
    $\begingroup$ Your definition $f_k(i)=b_i(k)$ reminds me that Attila Máté once told a class in combinatorial set theory that the main technique of that subject is interchanging the subscript and the argument. $\endgroup$ – Andreas Blass May 9 at 22:56
  • $\begingroup$ Thanks, Noah. Changing the perspective really made my question trivial! $\endgroup$ – Ruy May 9 at 23:25

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.