2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • 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$ Commented May 9, 2019 at 22:56
  • $\begingroup$ Thanks, Noah. Changing the perspective really made my question trivial! $\endgroup$
    – Ruy
    Commented May 9, 2019 at 23:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .