5 - Semilinear Sets

Question 1

SLS closure properties

Answer 1

linear functions
iteration
vector addition
intersection/union/complement

obs:
LINEAR (not semi) sets are not closed under any of the Boolean operations

Question 2

SLS union/intersection closure proof

Answer 2

union: by definition
intersection: proove linear sets closure, then:
M ∩ (M1 ∪ M2) = (M ∩ M1) ∪ (M ∩ M2)

Question 3

SLS equivalence?

Answer 3

Ginsburg & spanier 64.66

A set is Presburger-definable iff its Semi-linear