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 ${\displaystyle f(x)}$ symbolem funkcyjnym jest ${\displaystyle f,}$ w ${\displaystyle x+y}$ jest nim +, w ${\displaystyle f(x)+y-g(z)}$ są nimi ${\displaystyle f,g,+}$ oraz ${\displaystyle -.}$

Symbole funkcyjne i termy w logikach pierwszego rzędu

Wprowadzając język pierwszego rzędu najpierw określamy jego alfabet ${\displaystyle \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 ${\displaystyle x_{0},x_{1},\dots }$).

Definiujemy termy języka ${\displaystyle {\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 ${\displaystyle t_{1},\dots ,t_{n}}$ są termami, i ${\displaystyle f\in \tau }$ jest ${\displaystyle n}$-arnym symbolem funkcyjnym, to ${\displaystyle 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 ${\displaystyle n}$-arny symbol funkcyjny ${\displaystyle f}$ może być zastąpiony przez ${\displaystyle n+1}$-argumentową relację ${\displaystyle R,}$ tak że intuicyjny związek między nimi jest wyrażony przez

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

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

• W algebrze, dwuczłonowe symbole funkcyjne są zapisywane pomiędzy termami. Tradycyjnie piszemy więc ${\displaystyle x_{1}+x_{2}}$ (a nie ${\displaystyle +(x_{1},x_{2})}$) itd.

Przykłady

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

${\displaystyle (x_{1}*x_{2})*(x_{1}*x_{3})}$

${\displaystyle x_{1}*(x_{1}*(x_{1}*x_{1}))}$

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

${\displaystyle (x_{1}+x_{2})+(x_{1}\cdot x_{3})}$

${\displaystyle x_{1}+(x_{1}\cdot (x_{1}+x_{1}))}$

${\displaystyle 0+(1+(0+(1+0)))}$

Interpretacje termów w modelu

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

${\displaystyle {\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:

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

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

Zobacz też

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