Symbol funkcyjny

Szablon:Dopracować Symbol funkcyjny – symbol używany w logice matematycznej i pokrewnych dziedzinach matematyki (np. algebrze abstrakcyjnej). Symbole funkcyjne są elementami alfabetów języków pierwszego rzędu (a także innych logik) i charakteryzują się tym, że zastosowane do obiektów zwanych termami produkują nowe termy.

W potocznym języku matematyki, symbole funkcyjne w wyrażeniach matematycznych oznaczają funkcje, np.: w wyrażeniu $f(x)$ symbolem funkcyjnym jest $f,$ w $x+y$ jest nim +, w $f(x)+y-g(z)$ są nimi $f,g,+$ oraz $-.$

Symbole funkcyjne i termy w logikach pierwszego rzędu

Wprowadzając język pierwszego rzędu najpierw określamy jego alfabet $\tau ,$ czyli zbiór symboli funkcyjnych, symboli relacyjnych i stałych. Każdy z tych symboli ma jednoznacznie określony charakter (tzn. wiadomo czy jest to stała, czy symbol funkcyjny, czy też predykat) i każdy z symboli funkcyjnych i predykatów ma określoną arność (która jest dodatnią liczbą całkowitą). Ustalmy też nieskończoną listę zmiennych (zwykle $x_0,x_1,\dots$).

Definiujemy termy języka $ℒ(\tau )$ przez indukcję po ich złożoności w następujący sposób:

• wszystkie stałe i zmienne są termami,
• jeśli $t_1,\dots ,t_n$ są termami, i $f\in \tau$ jest $n$-arnym symbolem funkcyjnym, to $f(t_1,\dots ,t_n)$ jest termem.

Różne ujęcia i oznaczenia

• W niektórych ujęciach rachunku kwantyfikatorów, stałe języka są traktowane jako 0-argumentowe symbole funkcyjne. Wówczas alfabet języka składa się jedynie z symboli funkcyjnych i symboli relacyjnych, ale arność tych pierwszych może wynosić zero.
• W teorii modeli czasami jest wygodniej zakładać, że alfabet rozważanego języka nie zawiera żadnych symboli funkcyjnych. Nie wprowadza to żadnego istotnego ograniczenia, bowiem każdy $n$-arny symbol funkcyjny $f$ może być zastąpiony przez $n+1$-argumentową relację $R,$ tak że intuicyjny związek między nimi jest wyrażony przez

$f(x_1,\dots ,x_n)=x_{n+1}$ wtedy i tylko wtedy, gdy $R(x_1,\dots ,x_n,x_{n+1}).$

(Wymaga to dodania do rozważanych teorii zdania wyrażającego własność predykatu $R,$ że „pochodzi” on od pewnej funkcji.)

• W algebrze, dwuczłonowe symbole funkcyjne są zapisywane pomiędzy termami. Tradycyjnie piszemy więc $x_1+x_2$ (a nie $+(x_1,x_2)$) itd.

Przykłady

• Język teorii grup to $ℒ(\{*\}),$ gdzie $*$ jest binarnym symbolem funkcyjnym. Przykładowe termy w tym języku to:

$(x_1*x_2)*(x_1*x_3)$

$x_1*(x_1*(x_1*x_1))$

• Język ciał uporządkowanych to $ℒ(\{+,\cdot ,0,1,⩽\})$ gdzie $+,\cdot$ są binarnymi symbolami funkcyjnymi, a $⩽$ jest binarnym symbolem relacyjnym. Przykładowe termy w tym języku to:

$(x_1+x_2)+(x_1\cdot x_3)$

$x_1+(x_1\cdot (x_1+x_1))$

$0+(1+(0+(1+0)))$

Interpretacje termów w modelu

Niech $\tau$ będzie alfabetem jakiegoś języka pierwszego rzędu i niech $S_{\tau }$ będzie zbiorem stałych tego alfabetu, $F_{\tau }$ będzie zbiorem symboli funkcyjnych, a $R_{\tau }$ będzie zbiorem symboli relacyjnych. Modelem języka $ℒ(\tau )$ nazywamy układ

$ℳ=(M;R^{ℳ},\dots ,f^{ℳ},\dots ,c^{ℳ},\dots {)}_{R\in R_{\tau },f\in F_{\tau },c\in S_{\tau }}$

gdzie:

• $M$ jest niepustym zbiorem zwanym dziedziną lub uniwersum modelu $ℳ$ (często uniwersum modelu $ℳ$ oznacza się przez $|ℳ|$),
• dla $n$-arnego symbolu relacyjnego $R\in R_{\tau },$ $R^{ℳ}$ jest $n$-argumentową relacją na zbiorze $M,$ tzn. $R^{ℳ}\subseteq M^n,$
• dla $n$-arnego symbolu funkcyjnego $f\in F_{\tau },$ $f^{ℳ}$ jest $n$-argumentowym działaniem na zbiorze $M,$ tzn. $f^{ℳ}:M^n⟶M,$
• dla stałej $c\in S_{\tau },$ $c^{ℳ}$ jest elementem zbioru $M.$

Tak więc w modelach danego języka symbole funkcyjne są interpretowane jako funkcje. Przez indukcję po złożoności termów definiujemy też interpretację termu w modelu $ℳ$. Dla termu $t$ o zmiennych wolnych zawartych wśród $x_1,\dots ,x_n$ i dla elementów $m_1,\dots ,m_n\in M$ definiujemy $t^{ℳ}[m_1,\dots ,m_n]\in M$ następująco:

• Jeśli $t$ jest stałą $c$ alfabetu $\tau ,$ to $t^{ℳ}[m_1,\dots ,m_n]=c^{ℳ}.$
• Jeśli $t$ jest zmienną $x_i,$ to $t^{ℳ}[m_1,\dots ,m_n]=m_i.$
• Jeśli $t_1,\dots ,t_k$ są termami i $f\in F_{\tau }$ jest $k$-arnym symbolem funkcyjnym, to $t^{ℳ}[m_1,\dots ,m_n]=f^{ℳ}(t_1^{ℳ}[m_1,\dots ,m_n],\dots ,t_k^{ℳ}[m_1,\dots ,m_n]).$