WPC 2B/P Z#|x10cpiCourier 10cpiCourier 10cpi BoldCourier 17cpiX@IBM 4019 LaserPrinterIB401LAS.PRSXx  @89,,,,0L}X@2 2!4XU'@Courier 10cpiCourier 10cpi Bold2xxx@&Xx  @89X@2xxxsXx  `w9Xp&FFF!uF  @89@er]] [/S] [/B] [/L] ] [drive:][path][filename] Specifies drive,2 2  3'3'Standard3'3'Standard9 LaserPrinter@    4AN APPLICATION OF LOGIC TO COMBINATORIAL GEOMETRY: HOW MANY TETRAHEDRA ARE EQUIDECOMPOSABLE WITH A CUBE? 0 Vladik Kreinovich, Olga Kosheleva  CComputer Science Department, The University of Texas at El Paso, < El Paso TX 79968 USA &ABSTRACT It is known (Rapp, 1985) that elementary geometry with anadditional quantifier "there exist uncountably many" is decidable.We show that this decidability helps in solving the followingproblem from combinatorial geometry: does there exist anuncountable family of pairwise noncongruent tetrahedra that arenequidecomposable with a cube?  2  DEFINITION 1. By an elementary geometry , following [Tarski1951], [Seidenberg 1954], we mean the following theory: thevariables x, y, z, ... run over real numbers; terms are constructedfrom variables by using addition and multiplication; elementaryformulas are of the type t=t' or t>t' or t 2 ("implies"), ~ ("not"), and quantifiers (Ax) and (Ex). The wellknown result of Tarski is that elementary geometry isdecidable [Tarski 1951].  2  DEFINITION 2. By an elementary geometry with an additional 2 quantifier "there exist uncountably many" we mean a theory with thesame elementary formulas, in which a formula is obtained fromelementary ones by adding the logical, connectives, quantifiers or 2T$ the expression (Q1a1...an)P, where P is an arbitrary formula and a1, 2% ..., an is an arbitrary finite set of variables. The semantics of this expression is "there exist uncountably'0*((  2 many vectors (a1,...,an) for which the formula P is true". It is known that this theory is decidable [Rapp 1985]. APPLICATION. One of the remaining open problems connected withHilbert's Third Problem (on polyhedra) [Hilbert 1902] is as follows[Boltianskii 1978]. In a plane, every triangle (and moreover, every 2 polygon) is equidecomposable with some square in the sense thatthey can be both decomposed into the same finite number of pairwise congruent polygonal pieces. In 3dimensional space, only forsome tetrahedra it was known that they are equidecomposable with acube [Hill 1896]. Solving a problem posed by Hilbert, Dehn proved[Dehn 1900] that there exist tetrahedra that are notequidecomposable with any cube. So, a natural problem arises: whattetrahedra are equidecomposable with a cube? Surprisingly, since[Hill 1896] only finitely many new tetrahedra with this propertywere found [Goldberg 1974, Boltianskii 1978]. So, Boltianskii asksa question: Do there exist an uncountable family of pairwise noncongruenttetrahedra, other than Hill's tetrahedra and equidecomposable witha cube? The abovementioned decidability algorithm can give a partialanswer to this question.  2L  DEFINITION 3. We say that polyhedra P and Q are n 2x equidecomposable iff they can be both decomposed into finitely manypairwise congruent polytopes in such a way that a total number ofall the vertices of all these polytopes does not exceed n. COMMENT. Two polytopes are equidecomposable iff they are nequidecomposable for some n. If for every n there exist no morethan countably many noncongruent tetrahedra that are nequidecomposable with a cube, then the total number of tetrahedrathat are equidecomposable with a cube is also countable (as a'0*(( countable union of countable sets). Therefore, the existence of anuncountable family of pairwise noncongruent tetrahedra that areequidecomposable with a cube is equivalent to the fact that forsome n there exists an uncountable family of pairwise noncongruent tetrahedra that are nequidecomposable with a cube. Inview of that Boltianskii's question can be reformulated as follows: Do there exist an n and an uncountable family of pairwise noncongruent tetrahedra, that are different from Hill's tetrahedra,and nequidecomposable with a cube?  2  THEOREM. There exists an algorithm that for every n checkswhether there exist an uncountable family of pairwise noncongruent tetrahedra, that are different from Hill's tetrahedra and 2h nequidecomposable with a cube. PROOF. Let's fix a coordinate system. Then a tetrahedron isdescribed by the coordinates of its 4 vertices, i.e., by 12(finitely many) real numbers. Let's denote these 12 numbers by a 2D 12dimensional vector x . The coordinates of the vertices of thepolytopes that form a decomposition are also real numbers (no morethan 3n of them, because there are no more than n vertices).Congruence can be expressed as equality of all the distances,which, in its turn, is equivalent to equality of their squares. So,it is expressible by an elementary formula of elementary geometry. 2L The fact D( x ) that a given tetrahedron x is nequidecomposable witha cube means that there exists a decompositions of the tetrahedronand a decomposition of some cube that are pairwise congruent. 2 Therefore D( x ) is constructed from elementary formulas by applyingquantifiers, hence it is also a formula of elementary geometry. Hill's tetrahedra are also described by algebraic formulas, so 2T$ the fact that a tetrahedron, described by its coordinates vector x ,is not congruent to any of these tetrahedra, is also a formula ofelementary geometry. We want to apply the decidability algorithm for elementary'0*(( geometry with a quantifier "there exists uncountably many". Themain obstacle to its direct application is the phrase "pairwisenoncongruent" that is not directly expressible in this language. 2 Therefore, we want to restrict ourselves to some class C0 of"representatives" of congruence classes, i.e., to a such class oftetrahedra that every tetrahedron is congruent to one and only onetetrahedron from this class. In order to describe these representatives, let's do thefollowing. If all 6 edges of the tetrahedron are of different 2 length, then we can take the longest one e1. The edge e1 has twovertices; for each of them, we can compute the maximum value of all 2 the edges, different from e1, that end in this vertex. Let's choose 2 the vertex v for which this maximum e2 is greater. Then, we canmove the tetrahedron in such a way that v coincides with O; then, 2h we can rotate it so that after the rotation, e1 lies on the axisOX, and then rotate additionally so that the edge that has the 2 length e2 lies in the plane OXY. This procedure shows that we canrestrict ourselves to the tetrahedra for which the first vertex isO=(0,0,0), the second lies in OX (i.e., its second and thirdcoordinates are 0), the third vertex is in OXY (i.e., its thirdcoordinate is 0), and the lengths of the edges satisfy thecorresponding inequalities (i.e., the edge that is on OX is thelongest, etc). Inequality between lengths can be expressed asinequality between their squares, i.e., as an inequality betweenpolynomials of variables). Let's denote the set of all suchtetrahedra by C. One can easily see that for the case of tetrahedra withdifferent edge lengths, this definition gives the desired class ofrepresentations: every tetrahedron with different edge lengths iscongruent to one of the tetrahedra from C, and tetrahedra from Care not congruent to each other. In case some edges are equal it iseasy to propose likewise representations. A union of these sets of 2% representations is the desired class C0. Now the question whether there exist an uncountable family ofpairwise noncongruent tetrahedra with some property, is'0*(( equivalent to the following question: do there exist uncountably 2, many tetrahedra from C0 with this property. The class C0 isdescribed by a formula from elementary geometry, the property "tobe nequidecomposable with a cube, and to be not congruent to aHill's tetrahedron" can be also expressed in this theory, so we canapply the decidability algorithm for elementary geometry with an 2 additional quantifier Q1. Q.E.D. COMMENT. The main result of this paper were announced in[Kosheleva Kreinovich 1989] and [Kreinovich Kosheleva 1990]; forother algorithmic aspects of Hilbert's Third Problem see [Kosheleva1980]. ACKNOWLEDGEMENTS. The authors are greatly thankful to AlexandrD. Alexandrov (Leningrad), Vladimir G. Boltianskii (Moscow) andPatrick Suppes (Stanford) for valuable discussions, and to theanonymous referee for important suggestions. This work waspartially supported by an NSF grant No. CDA9015006. REFERENCES Boltianskii, Vladimir G. Hilbert's Third Problem, V. H. Winston& Sons, Washington, D.C., 1978. Dehn, M. Ueber raumgleiche Polyeder, Nachr. Acad. Wiss.Gottingen Math.Phys. Kl., 1900, pp. 345354. Goldberg, M. New rectifiable tetrahedra, Elem. Math., 1974, Vol.29, pp. 8589. Hilbert, David. Mathematical Problems, lecture delivered beforethe International Congress of Mathematics in Paris in 1900,translated in Bull. Amer. Math, Soc., 1902, Vol. 8, pp. 437479. Hill, M.J.M. Determination of the volumes of certain species oftetrahedra without employment of the method of limits, Proc. LondonMath. Soc., 1896, Vol. 27, pp. 3953. Kosheleva, Olga M. Axiomatization of volume in elementarygeometry, Siberian Mathematical Journal, 1980, Vol. 21, No. 1, pp.7885.'0*((Ԍ Kosheleva, Olga M.; Kreinovich, Vladik. Algorithmic problems ofcombinatorial geometry. Center for New Informational Technology"Informatika", Technical Report, Leningrad, 1989 (in Russian). Kreinovich, Vladik; Kosheleva, Olga M. Elementary geometry withan additional quantifier "there exists uncountably many" isdecidable. The University of Texas at El Paso, Computer ScienceDepartment, Technical Report UTEPCS9023, August 1990. Rapp, Andreas. The ordered field of real numbers and logics withMalitz quantifiers, The Journal of Symbolic Logic, 1985, Vol. 50,No. 2, pp. 380389. Seidenberg, A. A new decision method for elementary algebra,Annals of Math., 1954, Vol. 60, pp. 365374. Tarski, A. A decision method for elementary algebra andgeometry, 2nd ed., Berkeley and Los Angeles, 1951, 63 pp.