149:. This complexity is optimal, as there are examples where the output has a double exponential number of connected components. This algorithm is therefore fundamental, and it is widely used in
304:
702:
236:
566:
459:
507:, the projection of an algebraic set may be non-algebraic. Thus the existence of real algebraic sets with non-algebraic projections does not rely on the fact that the
868:
414:
algebraic sets. For these sets the theorem fails, i.e. projections of algebraic sets need not be algebraic. As a simple example consider the
142:
831:
797:
742:
173:
of sets defined by a finite number of polynomial equations and inequalities, that is by a finite number of statements of the form
863:
150:
788:. Translations of Mathematical Monographs. Vol. 88. Translated from the Russian by Smilka Zdravkovska. Providence, RI:
649:
and points. The final condition for such a collection to be an o-minimal structure is that the projection map on the first
789:
115:
40:-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities. The
765:
247:
576:
575:-axis is the half-line [0, ∞), a semialgebraic set that cannot be obtained from algebraic sets by (finite)
179:
134:
33:
146:
646:
53:
512:
111:
596:
508:
61:
29:
722:
170:
130:
126:
92:
65:
49:
734:
532:
428:
827:
793:
781:
757:
738:
162:
138:
119:
819:
803:
769:
488:≠ 0. This is a semialgebraic set, but it is not an algebraic set as the algebraic sets in
807:
773:
110:) is equivalent to a similar formula without quantifiers. An important consequence is the
815:
727:
580:
504:
406:
If we only define sets using polynomial equations and not inequalities then we define
857:
620: ≥ 1 such that we can take finite unions and complements of the subsets in
407:
45:
44:—also known as the Tarski–Seidenberg projection property—is named after
847:
57:
17:
310:
497:
415:
464:
This is a perfectly good algebraic set, but projecting it down by sending (
519:
41:
764:. London Mathematical Society Lecture Note Series. Vol. 248.
680:. The Tarski–Seidenberg theorem tells us that this holds if
64:
constructed from polynomial equations and inequalities by
703:
Decidability of first-order theories of the real numbers
145:, which allows quantifier elimination over the reals in
374:). Then the Tarski–Seidenberg theorem states that if
535:
431:
250:
182:
137:
that is too high for using the method on a computer.
726:
560:
453:
298:
230:
591:This result confirmed that semialgebraic sets in
28: + 1)-dimensional space defined by
299:{\displaystyle q(x_{1},\ldots ,x_{n})>0\,}
8:
820:"Real Algebraic Tools in Stochastic Games"
231:{\displaystyle p(x_{1},\ldots ,x_{n})=0\,}
540:
534:
450:
430:
295:
280:
261:
249:
227:
212:
193:
181:
714:
503:This example shows also that, over the
762:Tame topology and o-minimal structures
484:produces the set of points satisfying
826:. Dordrecht: Kluwer. pp. 57–75.
7:
689:is the set of semialgebraic sets in
603:. These are collections of subsets
526:, which is defined by the equation
143:cylindrical algebraic decomposition
14:
824:Stochastic Games and Applications
629:and the result will still be in
151:computational algebraic geometry
133:, the resulting algorithm has a
733:. New York: Springer. pp.
869:Theorems in algebraic geometry
320:. We define a projection map
286:
254:
218:
186:
1:
790:American Mathematical Society
595:form what is now known as an
645:are simply finite unions of
394:) is a semialgebraic set in
141:introduced the algorithm of
638:, moreover the elements of
402:Failure with algebraic sets
36:can be projected down onto
885:
766:Cambridge University Press
561:{\displaystyle y^{2}-x=0.}
378:is a semialgebraic set in
848:Tarski–Seidenberg theorem
454:{\displaystyle xy-1=0.\,}
22:Tarski–Seidenberg theorem
571:Its projection onto the
422:defined by the equation
135:computational complexity
864:Real algebraic geometry
518:Another example is the
511:of real numbers is not
147:double exponential time
587:Relation to structures
562:
455:
300:
232:
125:Although the original
54:quantifier elimination
24:states that a set in (
782:Khovanskii, Askold G.
661:must send subsets in
563:
500:and the finite sets.
456:
386: ≥ 1, then
301:
233:
60:, that is that every
56:is possible over the
533:
513:algebraically closed
429:
332:by sending a point (
248:
180:
30:polynomial equations
729:Algorithmic Algebra
723:Mishra, Bhubaneswar
597:o-minimal structure
328: →
129:of the theorem was
66:logical connectives
558:
451:
296:
228:
120:real-closed fields
52:. It implies that
50:Abraham Seidenberg
850:at PlanetMath.org
758:van den Dries, L.
653:coordinates from
163:semialgebraic set
139:George E. Collins
876:
837:
811:
777:
749:
748:
732:
719:
567:
565:
564:
559:
545:
544:
460:
458:
457:
452:
305:
303:
302:
297:
285:
284:
266:
265:
237:
235:
234:
229:
217:
216:
198:
197:
105:
97:
86:
78:
70:
884:
883:
879:
878:
877:
875:
874:
873:
854:
853:
844:
834:
816:Neyman, Abraham
814:
800:
780:
756:
753:
752:
745:
721:
720:
716:
711:
699:
688:
679:
670:
644:
637:
628:
611:
589:
581:set complements
536:
531:
530:
505:complex numbers
427:
426:
404:
373:
364:
357:
347:
338:
276:
257:
246:
245:
208:
189:
178:
177:
159:
103:
95:
84:
76:
68:
12:
11:
5:
882:
880:
872:
871:
866:
856:
855:
852:
851:
843:
842:External links
840:
839:
838:
832:
812:
798:
778:
751:
750:
743:
713:
712:
710:
707:
706:
705:
698:
695:
684:
675:
671:to subsets in
665:
642:
633:
624:
607:
588:
585:
579:, unions, and
569:
568:
557:
554:
551:
548:
543:
539:
462:
461:
449:
446:
443:
440:
437:
434:
408:algebraic sets
403:
400:
369:
362:
352:
343:
336:
307:
306:
294:
291:
288:
283:
279:
275:
272:
269:
264:
260:
256:
253:
239:
238:
226:
223:
220:
215:
211:
207:
204:
201:
196:
192:
188:
185:
158:
155:
13:
10:
9:
6:
4:
3:
2:
881:
870:
867:
865:
862:
861:
859:
849:
846:
845:
841:
835:
833:1-4020-1492-9
829:
825:
821:
817:
813:
809:
805:
801:
799:0-8218-4547-0
795:
791:
787:
783:
779:
775:
771:
767:
763:
759:
755:
754:
746:
744:0-387-94090-1
740:
736:
731:
730:
724:
718:
715:
708:
704:
701:
700:
696:
694:
692:
687:
683:
678:
674:
668:
664:
660:
656:
652:
648:
641:
636:
632:
627:
623:
619:
615:
610:
606:
602:
598:
594:
586:
584:
582:
578:
577:intersections
574:
555:
552:
549:
546:
541:
537:
529:
528:
527:
525:
521:
516:
514:
510:
506:
501:
499:
495:
491:
487:
483:
479:
475:
471:
467:
447:
444:
441:
438:
435:
432:
425:
424:
423:
421:
417:
413:
409:
401:
399:
397:
393:
389:
385:
381:
377:
372:
368:
361:
355:
351:
346:
342:
335:
331:
327:
323:
319:
315:
312:
292:
289:
281:
277:
273:
270:
267:
262:
258:
251:
244:
243:
242:
224:
221:
213:
209:
205:
202:
199:
194:
190:
183:
176:
175:
174:
172:
168:
164:
156:
154:
152:
148:
144:
140:
136:
132:
128:
123:
121:
117:
113:
109:
101:
94:
90:
82:
74:
67:
63:
59:
55:
51:
47:
46:Alfred Tarski
43:
39:
35:
31:
27:
23:
19:
823:
785:
761:
728:
717:
690:
685:
681:
676:
672:
666:
662:
658:
654:
650:
639:
634:
630:
625:
621:
617:
613:
608:
604:
600:
592:
590:
572:
570:
523:
517:
502:
496:itself, the
493:
489:
485:
481:
477:
473:
469:
465:
463:
419:
411:
410:rather than
405:
395:
391:
387:
383:
379:
375:
370:
366:
359:
353:
349:
344:
340:
333:
329:
325:
321:
317:
313:
308:
240:
169:is a finite
166:
160:
131:constructive
124:
112:decidability
107:
99:
88:
80:
72:
37:
34:inequalities
25:
21:
15:
311:polynomials
93:quantifiers
18:mathematics
858:Categories
808:0728.12002
786:Fewnomials
774:0953.03045
709:References
669: +1
647:intervals
616:for each
547:−
498:empty set
439:−
416:hyperbola
382:for some
356: +1
271:…
203:…
157:Statement
818:(2003).
784:(1991).
760:(1998).
725:(1993).
697:See also
520:parabola
324: :
365:, ...,
339:, ...,
114:of the
100:for all
62:formula
42:theorem
830:
806:
796:
772:
741:
737:–347.
358:) to (
116:theory
108:exists
91:) and
20:, the
509:field
472:) in
171:union
127:proof
58:reals
828:ISBN
794:ISBN
739:ISBN
492:are
412:semi
316:and
309:for
290:>
241:and
48:and
32:and
804:Zbl
770:Zbl
735:345
657:to
612:of
599:on
522:in
480:in
476:to
418:in
165:in
118:of
102:),
89:not
83:),
81:and
75:),
16:In
860::
822:.
802:.
792:.
768:.
693:.
583:.
556:0.
515:.
468:,
448:0.
398:.
348:,
161:A
153:.
122:.
73:or
836:.
810:.
776:.
747:.
691:R
686:n
682:S
677:n
673:S
667:n
663:S
659:R
655:R
651:n
643:1
640:S
635:n
631:S
626:n
622:S
618:n
614:R
609:n
605:S
601:R
593:R
573:x
553:=
550:x
542:2
538:y
524:R
494:R
490:R
486:x
482:R
478:x
474:R
470:y
466:x
445:=
442:1
436:y
433:x
420:R
396:R
392:X
390:(
388:π
384:n
380:R
376:X
371:n
367:x
363:1
360:x
354:n
350:x
345:n
341:x
337:1
334:x
330:R
326:R
322:π
318:q
314:p
293:0
287:)
282:n
278:x
274:,
268:,
263:1
259:x
255:(
252:q
225:0
222:=
219:)
214:n
210:x
206:,
200:,
195:1
191:x
187:(
184:p
167:R
106:(
104:∃
98:(
96:∀
87:(
85:¬
79:(
77:∧
71:(
69:∨
38:n
26:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.