Yarı düzen - Semiorder

Hasse diyagramı bir yarı düzenin. Dikey koordinatları en az bir birim farklılık gösterdiğinde (kesintisiz mavi çizgiler arasındaki boşluk) iki öğe karşılaştırılabilir.

İçinde sipariş teorisi, bir matematik dalı, bir yarı düzen sayısal puanları olan maddeler için, çok farklı puanlara sahip maddelerin puanlarına göre karşılaştırıldığı ve verilen bir hata payı kabul edilir kıyaslanamaz. Yarı siparişler tanıtıldı ve uygulandı matematiksel psikoloji tarafından Duncan Luce  (1956 ) bir insan tercihi modeli olarak. Genelleştiriyorlar katı zayıf siparişler eşit puana sahip maddeler berabere kalabilir ancak hata payı yoktur. Bunlar özel bir durumdur kısmi siparişler ve aralık emirleri ve kısmi siparişler arasında ek olarak karakterize edilebilir aksiyomlar veya iki yasaklanmış dört maddelik alt siparişle.

Tanım

Aksiyom 2
Aksiyom 3

İzin Vermek X bir dizi öğe olalım ve ikili ilişki açık XÖğeler x ve y Olduğu söyleniyor kıyaslanamaz, burada şu şekilde yazılmıştır x ~ y, eğer ikisi de değilse x < y ne de y < x doğru. Sonra çifti (X, <) aşağıdaki üç aksiyomu karşılıyorsa bir yarı sıradır:[1]

  1. Hepsi için x ve yher ikisi için de mümkün değil x < y ve y < x doğru olmak. Yani, asimetrik ilişki
  2. Hepsi için x, y, z, ve w, Eğer x < y, y ~ z, ve z < w, sonra x < w.
  3. Hepsi için x, y, z, ve w, Eğer x < y ve y < z, O zaman ya x < w veya w < z. Eşit olarak, aynı varsayımlarla x, y, z, diğer her öğe w en az biriyle karşılaştırılabilir olmalıdır x, yveya z.

İlk aksiyomdan şu sonuca varılır: x ~ xve bu nedenle ikinci aksiyom ( y = z) geçişli ilişki.

Yasaklı alt siparişler üzerinden

Bir kısmi sipariş aşağıdaki iki kısmi siparişi alt sipariş olarak içermemesi durumunda bir yarı sipariştir.[2]

  • Yarı siparişler için yasak alt siparişler
  • Karşılaştırılamaz dördüncü bir noktaya sahip üç noktalı [[doğrusal sıra]]
  • Birbirleriyle karşılaştırılamaz iki noktalı [[doğrusal sıra]] s

Diğer düzen türleriyle ilişki

Kısmi siparişler

Biri tanımlanabilir kısmi sipariş (X, ≤) bir yarı düzenden (X, <) beyan ederek x ≤ y ne zaman olursa olsun x < y veya x = y. Kısmi bir düzenin uyması gereken aksiyomlardan, dönüşlülük (x ≤ x) bu tanımdan otomatik olarak gelir, antisimetri (eğer x ≤ y ve y ≤ x sonra x = y) ilk yarı sıra aksiyomundan ve geçişlilikten (eğer x ≤ y ve y ≤ z sonra x ≤ z) ikinci yarı sıra aksiyomunu takip eder. Tersine, bu şekilde tanımlanan kısmi bir siparişten, yarı sipariş şu şekilde açıklanarak kurtarılabilir: x < y her ne zaman x ≤ y ve x ≠ y. Yukarıda listelenen yarı sıra aksiyomlarından ilki, kısmi bir sıralamayı tanımlayan aksiyomları otomatik olarak takip eder, ancak diğerleri yapmaz. İkinci ve üçüncü yarı sıra aksiyomları, iki ayrık zincir oluşturan dört öğenin kısmi siparişlerini yasaklar: ikinci aksiyom, her biri iki öğeden oluşan iki zinciri yasaklarken, üçüncü öğe, bir ilgisiz öğe içeren üç öğeli zinciri yasaklar.

Zayıf siparişler

Her katı zayıf sıralama da bir yarı emirdir. Daha özel olarak,

Aralıklı siparişler

Bir ilişki, ancak ve ancak, bir aralık sırası birim uzunluk aralıkları .

Quasitransitive ilişkiler

Göre Amartya K. Sen,[3] yarı siparişler tarafından incelendi Dean T. Jamison ve Lawrence J. Lau[4] ve özel bir durum olduğu bulundu yarı geçişli ilişkiler. Aslında, her yarı düzen, geçişli olduğu için yarı geçişli bir ilişkidir. Dahası, belirli bir yarı düzene tüm karşılaştırılamaz öğe çiftlerini eklemek, ortaya çıkan ilişkiyi yarı geçişli bir ilişki olarak tutar.[5]

Şema Teorisi

Yarı-sınırlar getirmenin orijinal motivasyonu, karşılaştırılamazlığın önemli olduğunu varsaymadan (katı zayıf sıralamaların yaptığı gibi) insan tercihlerini modellemekti. geçişli ilişki. Örneğin, eğer x, y, ve z aynı malzemenin üç miktarını temsil eder ve x ve z fark olarak algılanabilen en küçük miktar kadar farklılık gösterirken, y ikisinin ortasına denk geliyorsa, aralarında bir tercihin var olması mantıklıdır. x ve z ancak diğer iki çift arasında değil, geçişliliği ihlal ediyor.[6]

Öyleyse varsayalım ki X bir dizi öğedir ve sen bir fayda fonksiyonu üyelerini eşleyen X -e gerçek sayılar. Üzerinde katı bir zayıf sıralama tanımlanabilir x eşit faydalara sahip olduklarında iki maddenin karşılaştırılamaz olduğunu beyan ederek ve aksi takdirde sayısal karşılaştırmayı kullanarak, ancak bu zorunlu olarak geçişli bir karşılaştırılamazlık ilişkisine yol açar. Bunun yerine, biri sayısal bir eşik belirlerse (1'e normalleştirilebilir) öyle ki birbirinin bu eşik içindeki hizmet programları karşılaştırılamaz ilan edilir, o zaman bir yarı sıra ortaya çıkar.

Özellikle, bir ikili ilişki tanımlayın < X ve sen ayarlayarak x < y her ne zaman sen(x) ≤ sen(y) - 1. Sonra (X, <) bir yarı sıradır.[7] Eşdeğer olarak şu şekilde tanımlanabilir: aralık sırası aralıklarla tanımlanmış [sen(x),sen(x) + 1].[8]

Diğer yönde, her yarı-düzen bu şekilde sayısal yardımcı programlardan tanımlanamaz. Örneğin, bir yarı sipariş (X, <) bir sayılamaz tamamen sıralı alt küme bu durumda, bu alt kümeyi sayısal olarak temsil etmek için yeterince iyi aralıklı çok sayıda gerçek sayı yoktur. Bununla birlikte, her sonlu yarı düzen bir fayda fonksiyonundan tanımlanabilir.[9] Fishburn (1973) sayısal olarak tanımlanabilen yarı sıraların kesin bir karakterizasyonunu sağlar.

Bir yarısıra, yalnızca eleman çiftleri arasındaki düzen ilişkisi açısından verilmişse, o zaman sırayı temsil eden bir fayda fonksiyonu oluşturmak mümkündür. Ö(n2), nerede n yarı sıradaki elemanların sayısıdır.[10]

Kombinatoryal numaralandırma

Üzerindeki farklı yarı siparişlerin sayısı n etiketlenmemiş öğeler, Katalan numaraları

[11]

yarı sipariş sayısı açıkken n etiketli öğeler sıraya göre verilir

1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... (sıra A006531 içinde OEIS ).[12]

Diğer sonuçlar

Herhangi bir sonlu yarı düzenin sipariş boyutu en fazla üç.[13]

Sabit sayıda öğeye ve sabit sayıda karşılaştırılabilir çifte sahip tüm kısmi siparişler arasında, en fazla sayıda parçaya sahip olan kısmi siparişler doğrusal uzantılar yarı sipariştir.[14]

Yarı siparişlerin itaat ettiği bilinmektedir. 1 / 3–2 / 3 varsayımı: toplam düzen olmayan herhangi bir sonlu yarı düzende, bir çift eleman vardır x ve y öyle ki x daha erken görünür y yarı düzenin doğrusal uzantılarının 1 / 3'ü ile 2 / 3'ü arasında.[2]

Bir üzerinde yarı sipariş kümesi n-element seti Iyi derecelendirilmiş: aynı setteki iki yarı siparişin eklenmesi veya çıkarılmasıyla birbirinden farklıysa k ilişkileri düzenledikten sonra bir yol bulmak mümkündür k yolun her adımının tek bir sıra ilişkisini eklediği veya kaldıracağı ve yoldaki her ara durumun kendisi bir yarı sıra olacak şekilde birinci yarı düzenden ikinciye adımlar.[15]

karşılaştırılamazlık grafikleri yarı siparişlerin sayısı kayıtsızlık grafikleri ve özel bir durumdur aralık grafikleri.[16]

Notlar

  1. ^ Luce (1956) ilk ikisi karşılaştırılamazlık tanımını ve burada listelenen ilk aksiyomu birleştiren eşdeğer bir dört aksiyom kümesini açıklar.
  2. ^ a b Brightwell (1989).
  3. ^ Sen (1971 Bölüm 10, s. 314) Luce aralarındaki kayıtsızlığı modellediğinden x ve y "hiçbiri xRy ne de yRx", Sen ise" her ikisi de " xRy ve yRx", Sen'in s.314'teki yorumu muhtemelen ikinci mülk anlamına gelecektir.
  4. ^ Jamison ve Lau (1970).
  5. ^ Burghardt (2018), Lemma 20, s. 27.
  6. ^ Luce (1956), s. 179.
  7. ^ Luce (1956) Teorem 3, iki yardımcı program arasındaki karşılaştırılabilirlik eşiğinin aynı 1 olmaktan ziyade yardımcı programın bir işlevi olduğu daha genel bir durumu açıklar.
  8. ^ Balıkburnu (1970).
  9. ^ Bu sonuç genellikle kredilendirilir Scott ve Suppes (1958); örneğin bkz. Rabinovitch (1977). Ancak, Luce (1956) Teorem 2, daha genel bir ifadeyi kanıtlar: sonlu bir yarı düzenin, belirli bir temelde yatan zayıf düzen sayısal olarak tanımlanabildiğinde, bir fayda fonksiyonundan ve bir eşik fonksiyonundan tanımlanabilir. Sonlu yarı-sıralar için, zayıf sıranın bir birim eşik fonksiyonu ile sayısal olarak tanımlanabilmesi önemsizdir.
  10. ^ Avery (1992).
  11. ^ Kim ve Roush (1978).
  12. ^ Chandon, Lemaire ve Pouget (1978).
  13. ^ Rabinovitch (1978).
  14. ^ Fishburn ve Trotter (1992).
  15. ^ Doignon ve Falmagne (1997).
  16. ^ Roberts (1969).

Referanslar

  • Avery, Peter (1992), "Yarı sınırların gösterilebilir olduğunun algoritmik bir kanıtı", Algoritmalar Dergisi, 13 (1): 144–147, doi:10.1016 / 0196-6774 (92) 90010-A, BAY  1146337.
  • Brightwell, Graham R. (1989), "Semiorders ve 1 / 3-2 / 3 varsayımı", Sipariş, 5 (4): 369–380, doi:10.1007 / BF00353656.
  • Burghardt, Jochen (Kasım 2018), İkili İlişkilerin Belirgin Olmayan Özellikleri Hakkında Basit Yasalar, arXiv:1806.05036v2
  • Chandon, J.-L .; Lemaire, J .; Pouget, J. (1978), "Dénombrement des quasi-ordres sur un ensemble fini", Center de Mathématique Sociale. Ecole Pratique des Hautes Études. Mathématiques et Sciences Humaines (62): 61–80, 83, BAY  0517680.
  • Doignon, Jean-Paul; Falmagne, Jean-Claude (1997), "İyi derecelendirilmiş akraba aileleri", Ayrık Matematik, 173 (1–3): 35–44, doi:10.1016 / S0012-365X (96) 00095-7, BAY  1468838.
  • Fishburn, Peter C. (1970), "Eşit olmayan kayıtsızlık aralıklarıyla geçişsiz kayıtsızlık", J. Matematiksel Psikoloji, 7: 144–149, doi:10.1016/0022-2496(70)90062-3, BAY  0253942.
  • Fishburn, Peter C. (1973), "Aralık sıraları ve yarı sıralar için aralık gösterimleri", J. Matematiksel Psikoloji, 10: 91–105, doi:10.1016/0022-2496(73)90007-2, BAY  0316322.
  • Fishburn, Peter C.; Trotter, W. T. (1992), "Yarı sınırların doğrusal uzantıları: bir maksimizasyon problemi", Ayrık Matematik, 103 (1): 25–40, doi:10.1016 / 0012-365X (92) 90036-F, BAY  1171114.
  • Jamison, Dean T.; Lau, Lawrence J. (Eylül 1973), "Semiorders and the Theory of Choice", Ekonometrik, 41 (5): 901–912, doi:10.2307/1913813, JSTOR  1913813.
  • Jamison, Dean T .; Lau, Lawrence J. (Eylül – Kasım 1975), "Yarı Sınırlar ve Seçim Teorisi: Bir Düzeltme", Ekonometrik, 43 (5–6): 979–980, doi:10.2307/1911339, JSTOR  1911339.
  • Jamison, Dean T .; Lau, Lawrence J. (Temmuz 1970), Yarı Sıralar, Açığa Çıkan Tercih ve Tüketici Talebi Teorisi, Stanford Üniversitesi, Sosyal Bilimlerde Matematiksel Çalışmalar Enstitüsü. Eylül 1970'de Cambridge'de Dünya Ekonomi Kongresi'nde sunulmuştur.
  • Jamison, Dean T .; Lau, Lawrence J. (Ekim 1977), "Yarı sıralı tercihlerle dengenin doğası", Ekonometrik, 45 (7): 1595–1605, doi:10.2307/1913952, JSTOR  1913952.
  • Kim, K. H .; Roush, F. W. (1978), "Yarı sınırların izomorfizm sınıflarının numaralandırılması", Kombinatorik, Bilgi ve Sistem Bilimleri Dergisi, 3 (2): 58–61, BAY  0538212.
  • Luce, R. Duncan (1956), "Yarı sınırlar ve fayda ayrımcılığı teorisi" (PDF), Ekonometrik, 24: 178–191, doi:10.2307/1905751, JSTOR  1905751, BAY  0078632.
  • Rabinovitch, Issie (1977), "Yarı sınırlarda Scott-Suppes teoremi", J. Matematiksel Psikoloji, 15 (2): 209–212, doi:10.1016 / 0022-2496 (77) 90030-x, BAY  0437404.
  • Rabinovitch, Issie (1978), "Yarı sınırların boyutu", Kombinatoryal Teori Dergisi, Seri A, 25 (1): 50–61, doi:10.1016/0097-3165(78)90030-4, BAY  0498294.
  • Roberts, Fred S. (1969), "Kayıtsızlık grafikleri", Çizge Teorisinde İspat Teknikleri (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, s. 139–146, BAY  0252267.
  • Scott, Dana; Destekler, Patrick (1958), "Ölçüm teorilerinin temel yönleri", Sembolik Mantık Dergisi, 23: 113–128, doi:10.2307/2964389, BAY  0115919.
  • Sen, Amartya K. (Temmuz 1971), "Seçim İşlevleri ve Ortaya Çıkan Tercih" (PDF), Ekonomik Çalışmalar İncelemesi, 38 (3): 307–317.

daha fazla okuma

  • Pirlot, M .; Vincke, Doktora (1997), Yarı siparişler: Özellikler, temsiller, uygulamalar, Teori ve Karar Kitaplığı. Seri B: Matematiksel ve İstatistiksel Yöntemler, 36, Dordrecht: Kluwer Academic Publishers Group, ISBN  0-7923-4617-3, BAY  1472236.