Tanımlanabilir küme - Definable set

Olarak matematiksel mantık , bir tanımlanabilir grubu , bir olduğu , n -ary ilişkisi üzerinde etki a yapı elemanları bir tatmin tam olan elemanlardır formülü olarak birinci dereceden dili bu yapının. Bir küme , ilişkiyi tanımlayan formülde başvurulabilen etki alanının öğeleri olan parametrelerle veya parametreler olmadan tanımlanabilir.

Tanım

Let birinci dereceden dili olması bir alan adına sahip -Yapı , sabit bir alt kümesi içinde ve bir doğal sayı . Sonra:

  • Bir dizi olduğu tanımlanabilen parametrelerle bir formül vardır, ancak ve ancak ve elemanlar için tüm bu tür ,
ancak ve ancak
Buradaki parantez gösterimi , formüldeki serbest değişkenlerin anlamsal değerlendirmesini gösterir .
  • Bir dizi olarak tanımlanabilir olması parametreler olmadan bu tanımlanabilen ise parametrelerle boş grubu (tanımlayan formülde herhangi bir parametre ile).
  • Bir fonksiyon, içinde grafiği tanımlanabiliyorsa (parametrelerle) içinde tanımlanabilir (bu parametrelerle) .
  • Tekil set (bu parametrelerle) içinde tanımlanabiliyorsa ( parametrelerle) içinde bir öğe tanımlanabilir .

Örnekler

Yalnızca sıra ilişkisi olan doğal sayılar

Olağan sıralamayla doğal sayılardan oluşan yapı olsun . O zaman her doğal sayı parametresiz olarak tanımlanabilir . Sayı , x'ten daha az öğe olmadığını belirten formülle tanımlanır : ve doğal bir sayı , tam olarak x'ten küçük öğelerin var olduğunu belirten formülle tanımlanır :

Bunun tersine, normal sıralamaya sahip tamsayılardan oluşan yapıda parametreler olmadan herhangi bir spesifik tamsayı tanımlanamaz ( aşağıdaki otomorfizmlerle ilgili bölüme bakın).

Aritmetik işlemleriyle doğal sayılar

Doğal sayılardan ve bunların genel aritmetik işlemlerinden ve sıra ilişkisinden oluşan birinci dereceden yapı olalım . Bu yapıda tanımlanabilen kümeler aritmetik kümeler olarak bilinir ve aritmetik hiyerarşide sınıflandırılır . Yapı, birinci dereceden mantık yerine ikinci dereceden mantıkta ele alınırsa, sonuçta ortaya çıkan yapıdaki tanımlanabilir doğal sayı kümeleri analitik hiyerarşide sınıflandırılır . Bu hiyerarşiler, bu yapıdaki tanımlanabilirlik ile hesaplanabilirlik teorisi arasındaki birçok ilişkiyi ortaya çıkarır ve ayrıca tanımlayıcı küme teorisine de ilgi gösterir .

Gerçek sayılar alanı

Izin oluşan yapı olmak alanın içinde gerçek sayılar . Olağan sıralama ilişkisi doğrudan yapıya dahil edilmese de, negatif olmayan gerçekler kümesini tanımlayan bir formül vardır, çünkü bunlar kareköklere sahip tek gerçeklerdir:

Bu nedenle herhangi biri olumsuz değildir, ancak ve ancak . Bir reel sayı katkı tersini tanımlayan bir formül ile bağlantılı olarak , tek bir kullanabilir olağan sipariş tanımlamak için : için ayarlanmış, ancak ve ancak negatif olmayan bir. Büyütülmüş yapıya , orijinal yapının tanımsal bir uzantısı denir . Orijinal yapıyla aynı ifade gücüne sahiptir; bir küme, bir dizi parametreden büyütülmüş yapı üzerinde tanımlanabilir olması koşuluyla, ancak ve ancak, aynı parametreler kümesinden orijinal yapı üzerinde tanımlanabilirse.

Teori arasında yer alır miktar belirleyici ortadan kaldırılması . Böylece tanımlanabilir kümeler, polinom eşitliklerine ve eşitsizliklere yönelik Boole çözüm kombinasyonlarıdır; bunlara yarı cebirsel kümeler denir . Gerçek doğrunun bu özelliğini genellemek, o-minimalite çalışmasına götürür .

Otomorfizmler altında değişmezlik

Tanımlanabilir kümelerin önemli bir sonucu, otomorfizmler altında korunmalarıdır .

Izin bir olmak alanı ile -Yapı , ve de tanımlanabilir gelen parametrelerle . Izin vermek özdeşliği olan bir otomorfizm olalım . Sonra herkes için ,
ancak ve ancak

Bu sonuç bazen belirli bir yapının tanımlanabilir alt kümelerini sınıflandırmak için kullanılabilir. Örneğin, yukarıdaki durumda , herhangi bir çevirisi , boş parametre kümesini koruyan bir otomorfizmdir ve bu nedenle, bu yapıda herhangi bir belirli tamsayıyı, içinde parametreler olmadan tanımlamak imkansızdır . Aslında, herhangi iki tam sayı birbirine bir çeviri ve tersi ile taşındığından, parametresiz olarak tanımlanabilen tek tamsayı kümesi boş küme ve kendisidir. Bunun aksine, herhangi bir otomorfizm (dönüştürme) iki eleman arasındaki "mesafeyi" koruduğu için , elemanlarının sonsuz sayıda tanımlanabilir çifti (veya herhangi bir sabit n > 1 için aslında n- çiftleri ) vardır.

Ek sonuçlar

Tarski-Vaught testi karakterize etmek için kullanılan temel alt yapılar , belirli bir yapı.

Referanslar

  • Hinman, Peter. Matematiksel Mantığın Temelleri , AK Peters, 2005.
  • İşaretçi, David. Model Teorisi: Giriş , Springer, 2002.
  • Rudin, Walter. Matematiksel Analizin İlkeleri , 3. ed. McGraw-Hill, 1976.
  • Slaman, Theodore A. ve W. Hugh Woodin. Matematiksel Mantık: Berkeley Lisans Dersi . 2006 baharı.