Symbol funkcyjny

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,\ldots$).

Definiujemy termy języka ${\mathcal L}(\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,\ldots,t_n$ są termami, i $f\in\tau$ jest $n$-arnym symbolem funkcyjnym, to $f(t_1,\ldots,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,\ldots,x_n)=x_{n+1}$ wtedy i tylko wtedy, gdy $R(x_1,\ldots,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 ${\mathcal L}(\{*\})$, 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 ${\mathcal L}(\{+,\cdot,0,1,\leqslant\})$ gdzie $+,\cdot$ są binarnymi symbolami funkcyjnymi, a $\leqslant$ 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 ${\mathcal L}(\tau)$ nazywamy układ

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

gdzie

• M jest niepustym zbiorem zwanym dziedziną lub uniwersum modelu ${\mathcal M}$ (często uniwersum modelu ${\mathcal M}$ oznacza się przez $|{\mathcal M}|$),
• dla n-arnego symbolu relacyjnego $R\in R_\tau$, $R^{\mathcal M}$ jest n-argumentową relacją na zbiorze M, tzn. $R^{\mathcal M}\subseteq M^n$,
• dla n-arnego symbolu funkcyjnego $f\in F_\tau$, $f^{\mathcal M}$ jest n-argumentowym działaniem na zbiorze M, tzn. $f^{\mathcal M}: M^n\longrightarrow M$,
• dla stałej $c\in S_\tau$, $c^{\mathcal M}$ 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 ${\mathcal M}$. Dla termu $t$ o zmiennych wolnych zawartych wśród $x_1,\ldots,x_n$ i dla elementów $m_1,\ldots,m_n\in M$ definiujemy $t^{\mathcal M}[m_1,\ldots,m_n]\in M$ następująco:

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

Zobacz też

• funkcja zdaniowa
• język (logika)
• skolemizacja