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

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},\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 ${\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}},\dots ,f^{\mathcal {M}},\dots ,c^{\mathcal {M}},\dots )_{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},\dots ,x_{n}$ i dla elementów $m_{1},\dots ,m_{n}\in M$ definiujemy $t^{\mathcal {M}}[m_{1},\dots ,m_{n}]\in M$ następująco:

• Jeśli $t$ jest stałą $c$ alfabetu $\tau ,$ to $t^{\mathcal {M}}[m_{1},\dots ,m_{n}]=c^{\mathcal {M}}.$
• Jeśli $t$ jest zmienną $x_{i},$ to $t^{\mathcal {M}}[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^{\mathcal {M}}[m_{1},\dots ,m_{n}]=f^{\mathcal {M}}(t_{1}^{\mathcal {M}}[m_{1},\dots ,m_{n}],\dots ,t_{k}^{\mathcal {M}}[m_{1},\dots ,m_{n}]).$