# Given a complete lattice (A,⪯) Prove that

Given a complete lattice $$(A,\preceq)$$

$$\ \bullet \text{Prove: if}\ S,T \subset A, \text{then} \ \forall x \in S.\ \exists y\in T.x\preceq y \implies \bigvee S \preceq \bigvee T.$$ (1)

$$\ \bullet \text{Given a monoton function}$$ $$f: \mathbb{N} \times \mathbb{N}\rightarrow A \ \text{such that} \ \forall \ i,i',j,j'\in \mathbb{N}$$ $$i \le i' \wedge j \le j' \implies f(i,j)\preceq f(i',j').$$ Prove: $$\bigvee_{i,j\in \mathbb{N}\times \mathbb{N}} f(i,j)= \bigvee_{k\in \mathbb{N}} f(k,k)$$

1. The first point seems pretty obvious and follows (almost) from the definition of a complete lattice, we know that for any subsets $$S, T \subset A$$ there exists a supremum and infimum and form (1) it follows that $$\vee S \preceq \vee T.$$ Note: (its just an idea I'm not sure if its correct)
2. I'm not quite sure how to do the second part, I know that $$f$$ is monotone $$\implies f$$ is injective if I can prove $$|A|=|\mathbb{N}| \implies f$$ is surjective, the proof follows. But I don't know if $$f$$ is surjective so how can I be sure there isn't a bigger$$\ \vee f(k,k)$$
• 1 does need a small argument, give it! – Henno Brandsma Jun 9 '19 at 21:49
• constant maps are also monotone, so don't jump to conclusions... – Henno Brandsma Jun 9 '19 at 21:50
• You are right I didn't think of constant functions in this context, and your proof is quite sleek, thanks helped a lot – Nejc.Z Jun 10 '19 at 5:38

Suppose the condition $$\forall x \in S: \exists y \in T: x \preceq y$$ holds for $$S$$ and $$T$$. The completeness of the lattice ensures that $$\bigvee S$$ and $$\bigvee T$$ both exist in $$A$$.
If $$x\in S$$ then we have $$y \in T$$ with $$x \preceq y$$. Also $$y \preceq \bigvee T$$ as the latter is an upperbound for $$T$$. So for all $$x \in S$$ we know (by transitivity) that $$x \preceq \bigvee T$$, so $$\bigvee T$$ is an upperbound for $$S$$ and $$\bigvee S$$ is the smallest one of those, so by definition $$\bigvee S \preceq \bigvee T$$.
The second is a consequence: First, if $$(i,j) \in \Bbb N \times \Bbb N$$ then let $$k=\max(i,j)$$ and $$i \le k \land j \le k$$ is obvious. So $$f$$ being monotone tells us that $$f(i,j) \preceq f(k,k)$$.
This means that $$S=\{f(i,j): (i,j) \in \Bbb N \times \Bbb N\}$$ and $$T=\{f(k,k): k \in \Bbb N\}$$ satisfy the condition of 1. So $$\bigvee S \preceq \bigvee T$$ but as $$T \subseteq S$$ trivially, we also have $$\bigvee T \preceq \bigvee S$$ and hence equality (antisymmetry of $$\preceq$$), which is what was asked to prove.