Does conjunction of linear inequalities implies the summation of them

Question

Let A and B represent two linear inequalities:

$A : a_1 x_1 + ... + a_n x_n \geq k_1$

$B : b_1 x_1 + ... + b_n x_n \geq k_2$

If A and B is unsatisfiable (does not have solution), does the following hold in general (the conjunction of two inequalities implies the summation of them )? If so, I am looking for a formal proof?

$A \land B \implies A + B$

$_1_1+...+_n_n \geq1 \;\; \land \;\; _1_1+..._n_n\geq _2 \implies _1_1+...+_n_n + _1_1+..._n_n \geq _1+_2 $

and then I would like to generalize the above theorem to summation of several inequalities.

My attempt: My intuition is that if A and B be unsatisfiable, there is a matrix of Farkas coefficient C such that the weighted sum of A + B would be zero, and leads to -1 > 0 contradiction. Since A and B are unsatisfiable, the conjunction would be false. Therefore $\bot \implies \bot$ which is a correct statement.

My question is how to generalise this proof for a system of linear inequalities $A : \bigwedge \Sigma_{i=1}^{n} a_i x_i\leq k_i \;\; \wedge \;\; \bigwedge \Sigma_{i=1}^{n} b_i y_i\leq l_i $

and

$B: \bigwedge \Sigma_{j=1}^{n} a_j x_j\leq w_j \;\; \wedge \;\; \bigwedge \Sigma_{j=1}^{n} b_j y_j\leq z_j $

Answer 1

This does not hold in general. Consider $A: x > 2$ and $B: x > 4$. Then $A+B: 2x > 6$ which is equivalent to $x > 3$. This cannot be written as some suitable combination of $A$ and $B$.

Answer 2

It's still false, even with the unsatisfiability assumption.

Consider the inequalities \begin{align} -2x &> 2 \\ x & > 3 \end{align} Their sum is $$ -x > 5 $$ i.e., $x < -5$. But $x < -5$ does not imply that $x > 3$.

Answer 3

Solution to third version of problem:

Write $\mathbf{a}\cdot \mathbf{x}$ for $a_1x_1+\cdots+a_nx_n$. Then each inequality is of the type $\mathbf{a}\cdot \mathbf{x}\ge k$. If you have a bunch of them, then you get for example \begin{align*} \mathbf{a}\cdot \mathbf{x}\ge k_1\\ \mathbf{b}\cdot \mathbf{x}\ge k_2\\ \ldots\\ \mathbf{g}\cdot \mathbf{x}\ge k_7 \end{align*}

Now from algebra, $(\mathbf{a}+\mathbf{b})\cdot \mathbf{x}=\mathbf{a}\cdot \mathbf{x}+\mathbf{b}\cdot \mathbf{x}$.

Proof \begin{align*}(a_1+b_1)x_1+(a_2+b_2)x_2+\cdots&=a_1x_1+b_1x_1+a_2x_2+b_2x_2+\cdots\\ &=(a_1x_1+a_2x_2+\cdots)+(b_1x_1+b_2x_2+\cdots),\end{align*}

So if $\mathbf{a}\cdot \mathbf{x}\ge k_1$ and $\mathbf{b}\cdot \mathbf{x}\ge k_2$ then $(\mathbf{a}+\mathbf{b})\cdot \mathbf{x}\ge k_1+k_2$.

Hence one can show your statement to be true by induction. For this, I'm going to use $\mathbf{a}_1,\mathbf{a}_2,\ldots$ for each collection of parameters instead of $\mathbf{a},\mathbf{b},\ldots$; they are not to be confused with the previous real number parameters $a_1,a_2,\ldots$. It is true for $n=1$ (and $n=2$ by the above), so if it is true for $n$ inequalities $\mathbf{a}_1\cdot\mathbf{x}\ge k_1,\ldots,\mathbf{a}_n\cdot\mathbf{x}\ge k_n$, and you're given $n+1$ inequalities, then

\begin{align*}(\mathbf{a}_1+\mathbf{a}_2+\cdots+\mathbf{a}_n+\mathbf{a}_{n+1})\cdot x&=(\mathbf{a}_1+\cdots+\mathbf{a}_n)\cdot x+\mathbf{a}_{n+1}\cdot x\\ &\ge(k_1+\cdots+k_n)+k_{n+1}\\ &=k_1+\cdots+k_{n+1} \end{align*}

Answer 4

I don't see how the linear combination part is relevant. $A \geq k_1, B \geq k_2 \rightarrow A+B \geq k_1+k_2$ regardless of where $A$ and $B$ come from. This can be seem by

$$A \geq k_2$$ $$A-k_1 \geq 0$$ $$B+(A-k_1)\geq B \geq k_2$$ $$B+A \geq k_1+k_2$$