Tarski–Seidenberg teoremi - Tarski–Seidenberg theorem

Gelen matematik , Tarski-Seidenberg teoremi (bir dizi belirtmektedir , n  ile tanımlanan + 1) boyutlu alan polinom denklemler ve eşitsizlikler üzerine aşağı yansıtılabilir n boyutlu alan ve elde edilen resim polinom kimlikleri açısından ve halen tanımlanabilirdir eşitsizlikler. Tarski-Seidenberg izdüşüm özelliği olarak da bilinen teorem, adını Alfred Tarski ve Abraham Seidenberg'den almıştır . Bu, niceleyicilerin ortadan kaldırılmasının gerçekler üzerinden mümkün olduğunu, yani polinom denklemlerinden ve eşitsizliklerden oluşturulan her formülün şu şekilde olduğu anlamına gelir .mantıksal bağlaçlar ∨ ( veya ), ∧ ( ve ), ¬ ( değil ) ve niceleyiciler ∀ ( tümü için ), ∃ ( var ) niceleyici içermeyen benzer bir formüle eşdeğerdir. Önemli bir sonuç, reel-kapalı alanlar teorisinin karar verilebilirliğidir .

Teoremin orijinal kanıtı yapıcı olmasına rağmen, ortaya çıkan algoritma, yöntemi bir bilgisayarda kullanmak için çok yüksek bir hesaplama karmaşıklığına sahiptir. George E. Collins , çift ​​üstel zamanda gerçekler üzerinde niceleyicinin ortadan kaldırılmasına izin veren silindirik cebirsel ayrıştırma algoritmasını tanıttı . Çıktının iki kat üstel sayıda bağlı bileşene sahip olduğu örnekler olduğu için bu karmaşıklık en uygunudur. Bu algoritma bu nedenle temeldir ve hesaplamalı cebirsel geometride yaygın olarak kullanılır .

Beyan

R n'deki bir yarı cebirsel küme , sonlu sayıda polinom denklemi ve eşitsizlikle, yani sonlu sayıda formun ifadesiyle tanımlanan kümelerin sonlu bir birleşimidir .

ve

p ve q polinomları için . ( x 1 , ..., x n , x n +1 ) 'e ( x 1 , ..., x n ) bir nokta göndererek bir projeksiyon haritası π  : R n +1  →  R n tanımlarız . O zaman Tarski–Seidenberg teoremi, eğer X , bazı n  ≥ 1 için R n + 1'de bir yarı cebirsel küme ise , o zaman π ( X ) R n'de bir yarı cebirsel kümedir .

Cebirsel kümelerde başarısızlık

Kümeleri yalnızca polinom denklemlerini kullanarak tanımlarsak ve eşitsizlikleri değil, yarı cebirsel kümeler yerine cebirsel kümeleri tanımlarız . Bu kümeler için teorem başarısız olur, yani cebirsel kümelerin izdüşümlerinin cebirsel olması gerekmez. Basit bir örnek olarak dikkate hiperbol içinde R 2 denklemi ile tanımlanır

Bu gayet iyi bir cebirsel grubu olmakla birlikte, (göndererek aşağı çıkıntı x , y olarak) R 2 için X in R tatmin noktaları kümesi üretir X Bu semialgebraic dizi ≠ 0, ama o kadar bir cebirsel grubu değildir R'deki cebirsel kümeler , R'nin kendisi, boş küme ve sonlu kümelerdir.

Bu örnek ayrıca, karmaşık sayılar üzerinde, bir cebirsel kümenin izdüşümü cebirsel olmayabilir. Böylece cebirsel olmayan izdüşümlere sahip gerçek cebirsel kümelerin varlığı, gerçek sayılar alanının cebirsel olarak kapalı olmadığı gerçeğine dayanmaz .

yapılarla ilişkisi

Bu sonuç, R n'deki yarı cebirsel kümelerin , şimdi R üzerinde o-minimal yapı olarak bilinen şeyi oluşturduğunu doğruladı . Bu alt kümeler derlemeleridir S n içinde R n her biri için n  biz sonlu sendikalara ve alabilir 1, öyle ki ≥ tamamlar kümelerden bir S n ve sonuç hala olacaktır S n dahası elemanları, S 1 basitçe sonlu birlikleri vardır arasında aralıklarla ve noktaları. Bu tür bir toplama için son durumu bir o-minimal yapının izdüşümü birinci harita olmasıdır olması , n koordinatlarını R , n + 1 için R , n kümeler göndermelidir S , n + 1 de alt kümelerine S , n . Tarski–Seidenberg teoremi, S n'nin R n'deki yarı cebirsel kümeler kümesi olması durumunda bunun geçerli olduğunu söyler .

Ayrıca bakınız

Referanslar

Dış bağlantılar