İmza (mantık) - Signature (logic)

In mantığı , özellikle matematiksel mantık , bir imza listeleri ve mantıksal olmayan semboller a resmi dili . Gelen evrensel cebir , bir imza listeleri bir karakterize işlemler cebirsel yapısı . In modeli teorisi , imzalar hem amaçlar için kullanılır. Mantığın daha felsefi incelemelerinde nadiren açık hale getirilirler.

Tanım

Resmi olarak, bir (tek sıralı) imza üçlü bir σ = ( S func , S rel , ar) olarak tanımlanabilir, burada S fonk ve S rel diğer temel mantıksal semboller içermeyen ayrık kümelerdir , sırasıyla denir.

  • işlev sembolleri (örnekler: +, ×, 0, 1) ve
  • ilişki sembolleri veya yüklemleri (örnekler: ≤, ∈),

ve her fonksiyona veya ilişki sembolüne arity adı verilen doğal bir sayı atayan bir ar: S func  S rel → fonksiyonu. Bir fonksiyon veya ilişki sembolü olarak adlandırılır n onun Arity ise -ary n . Sıfır ( 0 -ary) bir fonksiyon sembolüne sabit sembol denir .  

İşlev sembolü olmayan bir imzaya ilişkisel imza denir ve ilişki sembolü olmayan bir imzaya cebirsel imza denir . Bir sonlu imza bir imza şekildedir S fonk ve S rel olan sonlu . Daha genel olarak, önem düzeyi bir imza σ = (arasında S fonksiyon , S rel , ar) gibi tanımlanmıştır | σ | = | S fonk | + | S rel |.

Bir imzanın dil mantıksal sistemde semboller olan imza grubu içinde sembollerden inşa tüm iyi oluşturulmuş cümlelerin kümesidir.

Diğer sözleşmeler

Evrensel cebirde kelime türü veya benzerlik türü genellikle "imza" ile eşanlamlı olarak kullanılır. Model teorisinde, bir imza σ genellikle bir kelime dağarcığı olarak adlandırılır veya mantıksal olmayan sembolleri sağladığı (birinci dereceden) L dili ile tanımlanır . Ancak, kardinalite dili L daima sonsuz olacaktır; σ sonlu ise | L | ℵ 0 olacaktır .

Resmi tanım günlük kullanım için uygun olmadığından, belirli bir imzanın tanımı genellikle aşağıdaki gibi gayri resmi bir şekilde kısaltılır:

" Değişmeli gruplar için standart imza σ = (+, -, 0) 'dır, burada - tekli bir operatördür."

Bazen bir cebirsel imza aşağıdaki gibi sadece bir eser listesi olarak kabul edilir:

"Değişmeli gruplar için benzerlik türü σ = (2,1,0) 'dır."

Resmi olarak bu, imzanın işlev sembollerini f 0  (sıfır), f 1  (tekli) ve f 2  (ikili) gibi bir şey olarak tanımlar , ancak gerçekte bu konvansiyonla bağlantılı olarak bile olağan isimler kullanılır.

Gelen matematiksel mantık bu sabit semboller yerine nullary işlev simgeleriyle olarak daha ayrı olarak ele alınmalıdır, böylece çok sık semboller, nullary izin verilmez. Bir dizi oluşturan S const gelen gg ayrık S fonksiyon Arity işlevi üzerinde, ar tanımlanmadı. Bununla birlikte, bu yalnızca, özellikle ek bir durumun dikkate alınması gereken bir formülün yapısı üzerine tümevarım yoluyla ispatlarda meseleleri karmaşıklaştırmaya hizmet eder. Böyle bir tanım kapsamında da izin verilmeyen herhangi bir sıfır ilişki sembolü, değerinin tüm öğeler için aynı olduğunu ifade eden bir cümle ile birlikte tekli bir ilişki sembolü ile taklit edilebilir. Bu çeviri yalnızca boş yapılar için başarısız olur (bunlar genellikle konvansiyon tarafından hariç tutulur). Eğer sıfır sembollere izin veriliyorsa, bu durumda önermeler mantığının her formülü aynı zamanda birinci dereceden mantığın bir formülüdür .

Sonsuz imza kullanımları için bir örnek, S fonksiyon = {+} ∪ {f bir : bir ∈ F } ve S rel = {=} yaklaşık bir ifade ve denklem şekillendirmek için vektör alan sonsuz skaler alanın üzerine F burada, f her bir belirtmektedir a ile skaler çarpmanın tek terimli operasyonu . Bu şekilde, imza ve mantık tek sıralı tutulabilir ve vektörler tek sıralama olur.

İmzaların mantık ve cebirde kullanımı

Bağlamında birinci dereceden mantık , bir imza semboller şekilde bilinmektedir mantıksal olmayan semboller birlikte mantıksal semboller ile iki, üzerinde yatan alfabe oluşturduklarından, resmi dil kümesi: indüktif tanımlandığı açısından fazla imza ve imza üzerindeki (iyi biçimlendirilmiş) formül seti .

Bir de yapının , bir yorumlama bağları isimlerini haklı matematiksel nesnelere fonksiyonu ve ilişki sembolleri: Bir yorumlanması n -ary işlev simgesi f bir yapı içinde A ile etki alanı A bir işlevdir f A :  A n  →  A ve n -terli bir ilişki sembolünün yorumlanması, bir R A  ⊆  A n ilişkisidir . Burada A , n = A x bir x ... x bir O anlamına gelir , n kat kartezyen ürün alan bir A kendisi ile, ve bu ön aslında bir olduğu , n -ary fonksiyonu ve R, bir N -ary ilişkisi.

Çok sınıflandırılmış imzalar

Çok sıralı mantık ve çok sıralı yapılar için imzalar, türler hakkındaki bilgileri kodlamalıdır. Bunu yapmanın en basit yolu , genelleştirilmiş toplulukların rolünü oynayan sembol türleri yoluyladır.

Sembol türleri

Let S (sıralar) bir dizi sembolleri içeren × veya → olabilir.

S üzerindeki sembol türleri , alfabe üzerindeki belirli kelimelerdir : ilişkisel sembol türleri s 1 ×… × s n ve fonksiyonel sembol türleri s 1 ×… × s n → s ′ , negatif olmayan tamsayılar için n ve . ( N = 0 için, s 1 ×… × s n ifadesi boş kelimeyi belirtir.)

İmza

Bir (çok sıralı) imza, aşağıdakilerden oluşan üçlü ( S , P , tip)

  • bir dizi S ,
  • bir dizi P sembolü ve
  • her sembole bir harita türü olan ortakları P üzerinde bir sembol tipi S .

Notlar

  1. ^ Mokadem, Riad; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas (Eylül 2007). "Cebirsel İmzaları Kullanarak Kodlanmış Veri Üzerinden Hızlı nGram Tabanlı Dizi Arama" (PDF) . 33. Uluslararası Çok Büyük Veri Tabanları Konferansı (VLDB) . Erişim tarihi: 27 Şubat 2019 . CS1 Maint: önerilmeyen parametre ( bağlantı )
  2. ^ George Grätzer (1967). "IV. Evrensel Cebir". James C. Abbot (ed.). Kafes Teorisindeki Eğilimler . Princeton / NJ: Van Nostrand. s. 173–210. CS1 Maint: önerilmeyen parametre ( bağlantı ) Burada: s. 173.
  3. ^ Çok Sıralı Mantık , Ders notlarının ilk bölümü , Calogero G. Zarba tarafından yazılmıştır .

Referanslar

Dış bağlantılar