Algebraic manipulation of universal quantifier

Question

I apologize in advance if my title is not super descriptive, I'm not exactly sure if "algebraic" is the correct term.

Let's say I have two sequences, $A$ and $B$, where $A_i$ is the $i$th element, 1 indexed. $n$ is the size of $A$, and $m$ is the size of $B$

If I have the following statement about these sequences:

$$\forall_{i,j} ((1 \leq i \leq n \wedge 1 \leq j \leq n \wedge i<j) \implies A_i \leq A_j) \wedge \forall_{i,j} ((1 \leq i \leq m \wedge 1 \leq j \leq m \wedge i<j) \implies B_i \leq B_j) \wedge \forall_{i,j}((1 \leq i \leq n \wedge 1 \leq j \leq m) \implies A_i < B_j)$$

Essentially saying that "A and B are sorted nondecreasing, and all elements of A are $\leq$ all elements of B", I know that the following statement must be true of $C = AB$ ($C$ is the concatenation of these two sequences):

$$\forall_{i,j} ((1 \leq i \leq n+m \wedge 1 \leq j \leq n+m \wedge i<j) \implies C_i \leq C_j)$$

I know this to be true of course based on intuition, but how do I manipulate the first statement in a way to reflect the second? The farthest I got was extracting $A_n < B_1$ and trying figure out how to use that to my advantage. I'm sure there is a way to do this somewhat how we can with De Morgan's laws to predicate logic, but I am having trouble finding a resource.

Answer 1

I don't know why you write general quantifier three times in your innitial statement (instead of just one at the beginning). You could also write the statement as formal statement much

But anyways, your innitial statement says: Let $A=(A_i)_{1\leq i\leq n}$, $B=(B_i)_{1\leq i\leq m}$ be finite (no stricly) increasing sequences, such that for any natural $1\leq i\leq n$ and $1\leq j\leq m$ we got $A_i<B_j$.

You want to prove essentialy that for any $1\leq k,t\leq m+n$, $k\leq t$ and sequence $C=(A_1,..., A_n,B_1,...,B_m), the $C$ is increasing.

To prove that take any $k,t,k\le t$ as above. And consider scenarios.

1. $k,t\leq n$: then both $C_k,C_t=A_k,A_t$ so $C_k\leq C_t$ (same with $k,t>n$
2. $k<n<t$: then $C_k=A_k,C_t=B_t$ so $C_k\le C_t$ (As $A_k\le B_t$ for any appropriate indices $k,t$).

This is any possible scenarios and hence we proved our theorem.