Linear Arithmetic - why calling it linear?

Question

This might sound like a stupid question, but I could not figure out, why Linear Arithmetic is called linear.

Linear Arithmetic often comes in play when talking about SMT Solving. For example, in this PDF linear arithmetic is defined as formulas using $=$, $\leq$, $<$ within the atoms. Somethink like 3*x_1 + 2*x_2 ≤ 5*x_3 is a linear arithmetic formula.

Because of which property is this arithmetic called linear?

This arithmetic preserves the linearity of the atoms. https://en.wikipedia.org/wiki/Linearity — vadim123, Jul 03 '13 at 14:03

score 5 · Answer 1 · answered Jul 03 '13 at 14:01

5

It seems that linear in that document is related to linear programming, which is optimization with linear constraints.

answered Jul 03 '13 at 14:01

lhf

216,483

Yes, a point made explicit in Sec. 5.1.1 of the PDF, Solvers for Linear Arithmetic. Apparently the term linear arithmetic is being used to pose (first order polynomial) constraints, whose satisfiability then constitute decision problems. – hardmath Jul 03 '13 at 14:10

score 0 · Answer 2 · answered Jul 03 '13 at 14:07

0

A function $F(x)$ is linear when $F(ax+by)=aF(x)+bF(y)$. This means that solutions to $F(x)=0$ are linear spaces and solutions to $F(x)\le 0$ are half spaces. The point, here, is that all your formulas are constructed to be linear.

answered Jul 03 '13 at 14:07

Emanuele Paolini

21,447

It seems more apt to construe "linear" as referring to first-order polynomials, rather than to linearity of a function on a vector space. Affine functions, in particular, are allowed in this linear arithmetic. – hardmath Jul 03 '13 at 14:12
Well, but why first order polynomials are called linear, after all? – Emanuele Paolini Jul 03 '13 at 14:13

Linear Arithmetic - why calling it linear?

2 Answers2

Linked