definiowanie w strukturze

[foundofmath]

Jak się formalnie pokazuje, że nie można zdefiniować predykatu w danej strukturze? Przeczuwam, że tak jest, ale nie wiem jak to formalnie pokazać. Czy może ktoś podać jakąś w miarę przystępną książkę, w której będą omówione podstawowe techniki i ew. jakieś przykłady postępowania? Potrzebuję to do zrobienia zadania ze wstępu do matematyki, a na wykładzie nic o tym nie było mówione do tej pory.

[Jan Kraszewski]

A może napisałbyś, co to za zadanie? Bo na razie Twoje pytanie brzmi dla mnie dość enigmatycznie.

JK

[foundofmath]

Chodzi o napisanie formuły definiującej dane pojęcie za pomocą dozwolonych symboli.

[Jan Kraszewski]

Czyli zwykłe, standardowe zadanie ze "Wstępu...".

Podchodzisz do tego zdecydowanie zbyt formalnie. Zapewniam Cię, że nie chodzi tu o definiowanie predykatu w strukturze, tylko o naukę poprawnego (pod względem merytorycznym i składniowym) używania symboliki matematycznej.

JK

[foundofmath]

Ale jest explicite powiedziane czego można używać, więc jeśli czegoś nie wyrażę za pomocą tego, co dozwolone, to nie mogę tego użyć. Moim zdaniem to nie jest kwestia formalnego podejścia, tylko zrozumienia polecenia zadania.

[Jan Kraszewski]

Myślę, że można spokojnie przyjąć, iż zadanie jest wykonalne. Dlaczego starasz się pokazać, że czegoś nie da się zrobić zamiast spróbować jednak to zrobić?

JK

[foundofmath]

Dlatego że kompletnie nie mam pomysłu jak zdefiniować (skądinąd potrzebne) stałe w danej strukturze, a intuicja podpowiada mi, że bez jakichś funktorów podanie odpowiednich definiensów może być niewykonalne. Czy mógłby Pan polecić jakąś książkę, w której byłyby omówione podstawowe techniki rozwiązywania tego rodzaju problemów?

PS. Przy bardziej liberalnym podejściu sobie poradzę.

[Jan Kraszewski]

Nie sądzę, by istniała jakaś specjalna książka do rozwiązywania tego typu problemów.

A może pokażesz ten przykład?

JK

[foundofmath]

Tych przykładów mam kilka, zasadniczo chodzi o coś takiego:

Mamy do dyspozycji zmienne (powiedzmy, że jest ich przeliczalnie wiele), predykaty \(\displaystyle{ x<y,x=y}\) określone (w sposób naturalny) w dziedzinie liczb rzeczywistych, predykat \(\displaystyle{ x\in \mathbb{N}}\), funktory zdaniotwórcze (negacja, alternatywa, implikacja, koniunkcja, równoważność) oraz kwantyfikatory i należy za pomocą ww. napisać pewne własności rzeczywistego ciągu \(\displaystyle{ (f(n))_{n \in \mathbb{N}}}\). I tak np. jak zapisać, że ten ciąg przyjmuje tylko wartości dodatnie? Ja rozumiem, to tak, że należy przetłumaczyć \(\displaystyle{ \forall_n(n \in \mathbb{N}\Rightarrow 0<f(n))}\) określone w \(\displaystyle{ \left\langle \mathbb{R},\left\{ <,=\right\},\left\{ 0\right\} \right\rangle}\) na redukt \(\displaystyle{ \left\langle \mathbb{R},\left\{ <,=\right\}\right\rangle}\). Mój problem polega na zdefiniowaniu explicite predykatu \(\displaystyle{ x=0}\) formułą jako że nie mam do dyspozycji żadnych funktorów algebraicznych i przypuszczam, że bez nich może się to okazać niemożliwe. No więc jak powinien wyglądać formalny dowód, że tak jest? Indukcyjnie (ew. korzystając z możliwości okrojenia języka, by zmniejszyć liczbę przypadków indukcyjnych) po złożoności formuł w tej strukturze z odwołaniem do jakichś własności z teorii modeli "dlaczego się nie da"? Ja po prostu nie mam pojęcia jak to powinno wyglądać formalnie, a tylko się (głośno) zastanawiam...

PS. Gdyby np. dorzucić \(\displaystyle{ +}\), to w \(\displaystyle{ \left\langle \mathbb{R},\left\{ <,=\right\},+ \right\rangle}\) można by było napisać \(\displaystyle{ \forall_n(n \in \mathbb{N} \Rightarrow \exists_y(y=+(y,y) \wedge y<f(n)))}\) (lub równoważnie \(\displaystyle{ \forall_n(n \in \mathbb{N} \Rightarrow \forall_y(y=+(y,y)\Rightarrow y<f(n)) )}\)).

[matmatmm]

Mój problem polega na zdefiniowaniu explicite predykatu \(\displaystyle{ x=0}\) formułą jako że nie mam do dyspozycji żadnych funktorów algebraicznych (...)

Jaką masz zatem definicję \(\displaystyle{ \RR}\)?

P.S.
\(\displaystyle{ \left\langle \mathbb{R},\left\{ <,=\right\},\left\{ 0\right\} \right\rangle}\) jest izomorficzne z \(\displaystyle{ \left\langle \mathbb{R},\left\{ <,=\right\},\left\{ x\right\} \right\rangle}\) dla każdego \(\displaystyle{ x\in\RR}\).

[krl]

@foundofmath: piszesz przecież, że masz predykat \(\displaystyle{ x\in\mathbb{N}}\), zatem Twoja struktura to:
\(\displaystyle{ (\mathbb{R}; <, \mathbb{N})}\), gdzie \(\displaystyle{ \mathbb{N}}\) to predykat, więc można go używać w formułach. W tej strukturze łatwo zdefiniować zero. Symbol równości traktuje się zazwyczaj jako symbol logiczny, nie trzeba go dopisywać w określeniu struktury.
Problem polega jednak na tym, że by zapisać jakieś zdanie o ciągu \(\displaystyle{ (f(n))}\), trzeba mieć w strukturze odpowiednią funkcję \(\displaystyle{ f}\), a tego tam nie ma...

[foundofmath]

@foundofmath: piszesz przecież, że masz predykat \(\displaystyle{ x\in\mathbb{N}}\), zatem Twoja struktura to:
\(\displaystyle{ (\mathbb{R}; <, \mathbb{N})}\), gdzie \(\displaystyle{ \mathbb{N}}\) to predykat, więc można go używać w formułach.

Tzn. \(\displaystyle{ \mathbb{N}}\) traktujemy tutaj jako zbiór elementów wyróżnionych, a \(\displaystyle{ \mathbb{R}}\) jako tzw. uniwersum? A nie jest tak, że strukturą jest układ \(\displaystyle{ \left\langle X;\mathcal{R},\mathcal{F},\mathcal{C} \right\rangle}\) gdzie \(\displaystyle{ X}\) jest zbiorem (niepustym?), \(\displaystyle{ \mathcal{R}}\) - rodziną pewnych relacji na \(\displaystyle{ X}\), \(\displaystyle{ \mathcal{F}}\) - rodziną funkcji na \(\displaystyle{ X}\), \(\displaystyle{ \mathcal{C}}\) - podzbiorem \(\displaystyle{ X}\) (zbiór tzw. elementów wyróżnionych)? Bo jeśli tak, to byłoby \(\displaystyle{ \left\langle \mathbb{R};\left\{ <, \in \right\},\mathbb{N} \right\rangle}\) zamiast \(\displaystyle{ (\mathbb{R}; <, \mathbb{N})}\) (ew. w formie \(\displaystyle{ (\mathbb{R}; <,\in, \mathbb{N})}\))?

W tej strukturze łatwo zdefiniować zero.

Np. \(\displaystyle{ \exists_y(x=y\wedge y \in \mathbb{N}\wedge \forall_z(z \in \mathbb{N}\Rightarrow ( (\neg z=y)\Rightarrow y<z) ) )}\) ?

Problem polega jednak na tym, że by zapisać jakieś zdanie o ciągu \(\displaystyle{ (f(n))}\), trzeba mieć w strukturze odpowiednią funkcję \(\displaystyle{ f}\), a tego tam nie ma...

Dlatego, że ciąg nie jest funkcją o dziedzinie \(\displaystyle{ \mathbb{R}}\) i - co za tym idzie - taka interpretacja tego zadania nie ma sensu?

PS. Wybacz te irytujące pytania, na wykładzie ze wstępu do matematyki nie mam praktycznie nic z teorii modeli.

[krl]

Tzn. \(\displaystyle{ \mathbb{N}}\) traktujemy tutaj jako zbiór elementów wyróżnionych, a \(\displaystyle{ \mathbb{R}}\) jako tzw. uniwersum? A nie jest tak, że strukturą jest układ \(\displaystyle{ \left\langle X;\mathcal{R},\mathcal{F},\mathcal{C} \right\rangle}\) gdzie \(\displaystyle{ X}\) jest zbiorem (niepustym?), \(\displaystyle{ \mathcal{R}}\) - rodziną pewnych relacji na \(\displaystyle{ X}\), \(\displaystyle{ \mathcal{F}}\) - rodziną funkcji na \(\displaystyle{ X}\), \(\displaystyle{ \mathcal{C}}\) - podzbiorem \(\displaystyle{ X}\) (zbiór tzw. elementów wyróżnionych)? Bo jeśli tak, to byłoby \(\displaystyle{ \left\langle \mathbb{R};\left\{ <, \in \right\},\mathbb{N} \right\rangle}\) zamiast \(\displaystyle{ (\mathbb{R}; <, \mathbb{N})}\) (ew. w formie \(\displaystyle{ (\mathbb{R}; <,\in, \mathbb{N})}\))?

Twoja definicja struktury jest dobra. Dla prostoty zwykle zapisuje się strukturę łatwiej, jako układ: zbiór (uniwersum) oraz pewna liczba relacji, funkcji i stałych. Równości nie trzeba tu zapisywac, gdyż traktuje się ją jako symbol logiczny (interpretowany w każdej strukturze jako prawdziwa równość).

Napisałeś, że \(\displaystyle{ \mathbb{N}}\) to predykat, tzn. relacja w naszej strukturze. I jako taki traktuję go w zapisie: \(\displaystyle{ (\mathbb{R},<,\mathbb{N})}\). To, że jakiś element \(\displaystyle{ a}\) struktury spełnia ten predykat, można zapisać (najpoprawniej) jako: \(\displaystyle{ \mathbb{N}(a)}\) lub (mniej poprawnie, ale zgodnie z praktyką matematyczną) jako: \(\displaystyle{ a\in\mathbb{N}}\).

W tej strukturze łatwo zdefiniować zero.

Np. \(\displaystyle{ \exists_y(x=y\wedge y \in \mathbb{N}\wedge \forall_z(z \in \mathbb{N}\Rightarrow ( (\neg z=y)\Rightarrow y<z) ) )}\) ?

Tak, to jest dobra definicja, ale można prościej: \(\displaystyle{ \mathbb{N}(x)\land\forall y(\mathbb{N}(y)\land x\neq y\rightarrow x<y)}\).

Problem polega jednak na tym, że by zapisać jakieś zdanie o ciągu \(\displaystyle{ (f(n))}\), trzeba mieć w strukturze odpowiednią funkcję \(\displaystyle{ f}\), a tego tam nie ma...

Dlatego, że ciąg nie jest funkcją o dziedzinie \(\displaystyle{ \mathbb{R}}\) i - co za tym idzie - taka interpretacja tego zadania nie ma sensu?

Trochę tak (choć to mały problem). Głównie chodzi o to, że w formulach języka struktury wolno używać tylko symboli relacji, funkcji i stałych wyspecyfikowanych w opisie struktury (oraz symboli logicznych).
Gdyby w strukturze była wyróżniona funkcja \(\displaystyle{ f}\), to można by jej używać w formułach języka struktury. Wtedy \(\displaystyle{ f}\) powinna mieć całe uniwersum struktury jako dziedzinę (ale to jest mały problem, zawsze mozna taką funkcję jakoś trywialnie rozszerzyć do całego uniwersum).

PS. Wybacz te irytujące pytania, na wykładzie ze wstępu do matematyki nie mam praktycznie nic z teorii modeli.

Te pytania nie są wcale irytujące. Nic dziwnego, że na wstępie do matematyki nie masz nic z teorii modeli - nie taka jest rola tego przedmiotu. (Poza tym w Polsce główne miejsce, gdzie można się nauczyć teorii modeli, to Wrocław...)
Skrótowe definicje formalizmu teoriomodelowego związanego z pisaniem formuł/zdań w języku struktury znajdziesz np. tu:

15 paź 2017, o 10:32 --c.d. Właściwą strukturą, w której należałoby zapisać to zdanie, powinna być chyba:
\(\displaystyle{ (\mathbb{R};<,\mathbb{N}; f)}\), gdzie \(\displaystyle{ \mathbb{N}}\)traktujemy jako relację unarną, zaś \(\displaystyle{ f}\) jako funkcję unarną. I oczywiscie zapisanie takiego zdania w języku tej struktury jest możliwe. Niekiedy zapisanie pewnych właśności w języku stuktury możliwe nie jest. Wtedy są różne metody (zasadniczo teoriomodelowe) by to uzasadnić. Czasami jest to trudne.

[foundofmath]

Napisałeś, że \(\displaystyle{ \mathbb{N}}\) to predykat, tzn. relacja w naszej strukturze. I jako taki traktuję go w zapisie: \(\displaystyle{ (\mathbb{R},<,\mathbb{N})}\). To, że jakiś element \(\displaystyle{ a}\) struktury spełnia ten predykat, można zapisać (najpoprawniej) jako: \(\displaystyle{ \mathbb{N}(a)}\) lub (mniej poprawnie, ale zgodnie z praktyką matematyczną) jako: \(\displaystyle{ a\in\mathbb{N}}\).

Ten fragment mi sporo rozjaśnił.

c.d. Właściwą strukturą, w której należałoby zapisać to zdanie, powinna być chyba:
\(\displaystyle{ (\mathbb{R};<,\mathbb{N}; f)}\), gdzie \(\displaystyle{ \mathbb{N}}\)traktujemy jako relację unarną, zaś \(\displaystyle{ f}\) jako funkcję unarną. I oczywiscie zapisanie takiego zdania w języku tej struktury jest możliwe. Niekiedy zapisanie pewnych właśności w języku stuktury możliwe nie jest. Wtedy są różne metody (zasadniczo teoriomodelowe) by to uzasadnić. Czasami jest to trudne.

Mam jeszcze np. taki przykład: zapisać, że \(\displaystyle{ (f(n))_{n \in \mathbb{N}}}\) jest zbieżny w (jak rozumiem) strukturze \(\displaystyle{ (\mathbb{R};<,\mathbb{N}; f)}\). I tu chyba pojawia się problem, bo definicja zbieżności ciągu jest z grubsza taka:
\(\displaystyle{ \exists_g(\forall_\epsilon(\exists_y(\mathbb{N}(y)\wedge y<\epsilon \wedge \forall_z((\mathbb{N}(z)\wedge (\neg y=z) )\Rightarrow y<z))\Rightarrow \\\exists_k(\mathbb{N}(k)\wedge \forall_n( (\mathbb{N}(n)\wedge k<n)\Rightarrow(f(n)-g< \epsilon \wedge g-f(n)<\epsilon) ) )))}\)

Tutaj jednak mam problem z eliminacją termów \(\displaystyle{ f(n)-g}\) oraz \(\displaystyle{ g-f(n)}\) - te różnice nie muszą być naturalne, więc predykat \(\displaystyle{ \mathbb{N}}\) może być bezwartościowy. Z drugiej strony nie mam w strukturze funktorów algebraicznych i wydaje się, że w tym przypadku same predykaty mogą nie wystarczyć do zdefiniowania odejmowania. Czy to prawda? A jeśli tak, to jaka jest idea dowodu, że się nie da - indukcja po złożoności formuł danej struktury z wykorzystaniem narzędzi teorii modeli do argumentowania przeciw? Czy mógłbyś polecić jakąś książkę która omawia te sprawy?

[krl]

Mam jeszcze np. taki przykład: zapisać, że \(\displaystyle{ (f(n))_{n \in \mathbb{N}}}\) jest zbieżny w (jak rozumiem) strukturze \(\displaystyle{ (\mathbb{R};<,\mathbb{N}; f)}\). I tu chyba pojawia się problem, bo definicja zbieżności ciągu jest z grubsza taka:
\(\displaystyle{ \exists_g(\forall_\epsilon(\exists_y(\mathbb{N}(y)\wedge y<\epsilon \wedge \forall_z((\mathbb{N}(z)\wedge (\neg y=z) )\Rightarrow y<z))\Rightarrow \\\exists_k(\mathbb{N}(k)\wedge \forall_n( (\mathbb{N}(n)\wedge k<n)\Rightarrow(f(n)-g< \epsilon \wedge g-f(n)<\epsilon) ) )))}\)

Tutaj jednak mam problem z eliminacją termów \(\displaystyle{ f(n)-g}\) oraz \(\displaystyle{ g-f(n)}\) - te różnice nie muszą być naturalne, więc predykat \(\displaystyle{ \mathbb{N}}\) może być bezwartościowy. Z drugiej strony nie mam w strukturze funktorów algebraicznych i wydaje się, że w tym przypadku same predykaty mogą nie wystarczyć do zdefiniowania odejmowania. Czy to prawda? A jeśli tak, to jaka jest idea dowodu, że się nie da - indukcja po złożoności formuł danej struktury z wykorzystaniem narzędzi teorii modeli do argumentowania przeciw? Czy mógłbyś polecić jakąś książkę która omawia te sprawy?

1. Termu \(\displaystyle{ f(n)-g}\) nie da się zdefiniować w podanej strukturze (w języku z symbolami \(\displaystyle{ <,\mathbb{N},f}\)). Natomiast użycie tego termu nie jest konieczne dla zdefiniowania zbieżności ciągu. Tzn. można to zapisać w języku tej struktury. Postaraj się bardziej...
2. Nie znam książek, które byłyby poświęcone dokładnie kwestii niedefiniowalności jakichś zbiorów w danej strukturze. To zagadnienie ja widzę w kontekście teorii modeli. Myślę, że dla Ciebie poznawanie teorii modeli może być przedwczesne. Nie ma dobrych polskich książek wprowadzajacych dobrze do logiki matematycznej (i wstępnej teorii modeli). Z angielskojęzycznych jest np. Introduction to Mathematical Logic Mendelsona. Ale to jest przedwczesne...
3. Chciałbym podkreślić, że poziom formalizmu, jaki starasz się stosować do symbolicznego zapisywania zdań matematycznych, nie jest typowy dla typowego wykładu ze wstępu do matematyki. Przypuszczalnie wykładowcy chodzi tu o prostsze formuły (np. używające symboli dla zera, odejmowania itp.). Szczerze mówiąc nie widzę wiele sensu w żmudnym zapisywaniu formuł w bardzo ograniczonym języku. Natomiast nauczenie się stosowania typowego zapisu symbolicznego ma sens.