Symbol funkcyjny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]