We prove in this paper that every semilinear set is a finite union of disjoint linear sets, using elementary combinatorial-topological lemmas.
This paper gives a positive answer to an open problem proposed by Seymour Ginsburg in his book ([2], p. 195).
Let N denote the nonnegative integers and R denote the real numbers. For each integer n ~ 1 let R" ----R β’ "" β’ R and N" = N β’ ". β’ N (n times). A linear set L(c; Pl ,..., Pr) is a subset {x ] x = c + Y'~=I kip~ for nonnegative integers k~, i = 1,..., r} of N n, where c, Pl ..... Pr are elements of N". We call c the constant and Pl ..... Pr the periods of the linear set. In particular we denote by L(c) a linear set whose periods are all zero vectors (i.e. consisting of single element c) and regard as r = 0. A subset of N" is called semilinear if it is a finite union of linear sets. Let L(c; Pl .... , p~) C N" be a linear set. We say that the linear set is of s-dimension, if the periods Pa ,--., Pr span a s-dimensional vector space in R n, and that the linear set is fundamental if s :-r. (i.e. Pl .... , Pr are linearly independent in R"). In this paper the empty set is regarded also as a (--l)-dimensional fundamental linear set. By Lemma A. 1. a ([2] p. 212), every linear set is a finite union of fundamental linear sets.
In fact, we prove the following: THEOREM I. Let A ~-L(c; Pa ..... p,~) and B = L(d; ql ..... qt) be two fundamental linear sets. Then A --B is a finite union of disjoint fundamental linear sets of dimension ~s. THEOREM 2. Every semilinear set is a finite union of disjoint fundamental linear sets.
* The author is grateful to the refree who pointed out that the result was obtained independently and perhaps at an earlier date by Eilenberg and Schutzenberger ([1]), but that the present method of proof differs from theirs.