How do I prove that every chain has an upper bound?

Question

Let $A$ be a non-empty set.

Let $X$ be the collection of bijections $f:U→V$ where $U,V$ are disjoint subsets of $A$.

Define the relation $≥$ as follows: $$(f:U→V) ≥ (f′:U′→V′) \text{ iff } U′⊆ U \text{ and }V′⊆ V f|_{U′}=f′$$

How do I prove that for every chain in $X$ there is an upper bound in $X$?

I think I mostly know how, but it's a matter of how to write it:

Let $C$ be a chain. Consider: union of all the functions in chain $C$. The union of the $U$'s is a subset of $A$, similarly the union of $T$'s in $C$ is also a subset of $A$. The Union of functions I assume is just the union of all the pairs, and since every function is bijective then the union will be bijective.

How do I concisely and elegantly write this proof?

A specific problem I have is how to represent the chain? should it be like this: $$C = \{f_\gamma:U_\gamma \to V_\gamma\ |\ \text{ for all }\gamma \in \Gamma\}$$

Answer 1

Let's write $X = \{f_\alpha: U_\alpha \to V_\alpha\}$ for notational purposes, and let $U = \bigcup_\alpha U_\alpha$, $V = \bigcup_\alpha V_\alpha$ and $f = \bigcup_\alpha f_\alpha$

There are a couple of things that need checking:

1. $f$ is still a function:

This is because $f_\alpha \leq f_\beta$ implies $f_\beta|_{U_\alpha} = f_\alpha$: that is, if $x \in U_\alpha \cap U_\beta$ then (since $X$ is a chain) we have either $f_\alpha \leq f_\beta$ or vice-versa, and so $f_\alpha(x) = f_\beta|_{U_\alpha}(x) = f_\beta(x)$.

2. $f$ is still injective:

Suppose $f(x) = f(y)$. Then we can find some $U_\alpha$ that contains both $x$ and $y$ (again since $X$ is a chain), and so we get $f_\alpha(x) = f_\alpha(y)$, so $x = y$.

3. $f$ is still surjective:

If $v \in V$ then have $v \in V_\alpha$, for some $\alpha$, and so there is some $x \in U_\alpha$ with $f(x) = f_\alpha(x) = v$.

4. $U$ and $V$ are still disjoint:

If $x \in U \cap V$ then $x \in U_\alpha$ and $x \in V_\beta$. Since $X$ is a chain we have $U_\alpha \subseteq U_\beta$ (or vice-versa) so wlog $x \in U_\beta \cap V_\beta$, which is a contradiction.

Your question about 'how to represent the chain' is just a matter of preference - I think the above notation is pretty clear, but I'm sure there are other ways you could write it. Note that some people consider a chain to be e.g. $f_0 \leq f_1 \leq f_2 \leq \ldots$ (especially in computer science), but normally the more general definition of 'a totally ordered subset of a poset' is used.