I have this expression $(x \geq 1) \vee(x=0 \,\wedge\, y -z \geq 1)$ which I am solving over the nonnegative integers $x,y,z \in \mathbb{Z}_0^+$.
I suspect it is impossible to find a system of linear equalities which has the same solution set as my expression, but I'm having trouble proving this. Is it true? How do you prove this?
I know that the solution set to a system of linear inequalities must be convex --- that is, the segment between any two points in the solution set must consist entirely of solutions. I also know that the union of convex spaces is not, in general, convex. However, because we're dealing with integers, it seems at least sometimes possible to create a convex space that contains the integer points in the nonconvex union of convex spaces.
What I've tried so far is drawing a picture of the lattice of solutions. The entire ~octant beyond $x\geq 1$ is filled in, as is an upward-sloping half-plane $y-z \geq 1$ in $x=0$.
Intuitively, when I try to picture putting a supporting hyperplane straddling the $y-z \geq 1$ part and the $x \geq 1$ part, the slope doesn't work --- the distance between (0,a+1,a) and (1,0,a) keeps growing. But I don't know how to formalize this.
The broader context is I'm considering nonnegative integer solutions to (sort-of) linear inequalities $\sum_i \alpha_i x_i \leq -1$, where the coefficients are either $1,0,-1$ or $-\infty$. And trying to figure out in what cases there exists a system of linear inequalities whose solutions over the nonnegative integers are equivalent.
As a concrete case, in this question I'm considering $-\infty x - y + z \leq -1$, which is equivalent to the expression at the top of this page.
I define the solution to an equation involving negative infinites recursively by saying that the solution to $-\infty \cdot x_i + L(\vec{x}) \leq -1$ is the union of the solution to $x_i \geq 1$ and the solution to $L(\vec{x})\leq -1$; in the base case, there are no infinities.
