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) $
  • $\begingroup$ 1 does need a small argument, give it! $\endgroup$ – Henno Brandsma Jun 9 '19 at 21:49
  • $\begingroup$ constant maps are also monotone, so don't jump to conclusions... $\endgroup$ – Henno Brandsma Jun 9 '19 at 21:50
  • $\begingroup$ You are right I didn't think of constant functions in this context, and your proof is quite sleek, thanks helped a lot $\endgroup$ – 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.

| cite | improve this answer | |

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.