Matematyka.pl

Dla funkcji g zdefiniowanej:
\(\displaystyle{ g(x, y)=\begin{cases} x &\text{dla } y=1\\x^{g(x, y-1)} &\text{dla } y>1 \end{cases}}\)
Udowodnij:
\(\displaystyle{ \forall_{x, n, k-1 \in \NN_{+}}: \exists!_{x \in \langle1; 2\cdot 3^n\rangle}:3^n|g(x, k) - 2}\)

Mateusz5324 pisze: ↑19 kwie 2023, o 00:35\(\displaystyle{ \forall_{\red{x}, n, k-1 \in \NN_{+}}: \exists!_{\blue{x} \in \langle1; 2\cdot 3^n\rangle}:3^n|g(x, k) - 2}\)

Coś Ci ten zapis nie wyszedł: za dużo \(\displaystyle{ x}\)-ów pod kwantyfikatorami.

JK

A da się jakoś powiększyć to wyrażenie w tagach [ latex ] żeby było lepiej widać?

Zawsze możesz dodać \large na początku. Ale póki co masz problem merytoryczny.

JK

Jaki błąd merytoryczny, skoro dla każdego naturalnego dodatniego x istnieje taki należący do podanego przedziału?
Mógłbyś powiedzieć wprost o co chodzi?

Zagnieżdżasz kwantyfikatory kwantyfikujące po tej samej zmiennej. W zapisie

\(\displaystyle{ \forall_{\red{x}, n, k-1 \in \NN_{+}}: \exists!_{\blue{x} \in \langle1; 2\cdot 3^n\rangle}:3^n|g(\blue{x}, k) - 2}\)

czerwony \(\displaystyle{ x}\) jest zupełnie zbędny, bo niczego nie dotyczy, gdyż wewnętrzny kwantyfikator już zakwantyfikował \(\displaystyle{ x}\)-a (pomijając już wątpliwy zapis \(\displaystyle{ k-1 \in \NN_{+}}\)). Zatem ten napis oznacza de facto tyle:

\(\displaystyle{ \forall_{n, k-1 \in \NN_{+}}: \exists!_{x \in \langle1; 2\cdot 3^n\rangle}:3^n|g(x, k) - 2,}\)

a zapewne nie o to Ci chodziło. Może zamiast próbować wszystko "zaznaczkować" zapisz swoją tezę słownie?

Dodatkowo nie określiłeś dziedziny funkcji \(\displaystyle{ g}\).

JK

To według ciebie czym różnią się zapisy:
\(\displaystyle{ \large \forall_{x,n,k-1 \in \NN_+}: \exists!_{x \in <1;2 \cdot 3^n>}:3^n|g(x,k)-2}\)
od:
\(\displaystyle{ \large \forall_{n,k-1 \in \NN_+}: \exists!_{x \in <1;2 \cdot 3^n> \wedge x \in \NN_+}:3^n|g(x,k)-2}\)
Bo według mnie jedynie zapisem i każdy człowiek jest w stanie zrozumieć je jako znaczące to samo.
Nie mówiąc nawet o tym, że przekopałem bardzo dużo tekstów dot. kwantyfikatorów i nigdzie nie było o czymś takim napisane. W szkole też nie uczono mnie, że jest to błędem. Jeśli postarasz się przeczytać oba zdania to wyjdzie ci w przypadku 1:
Dla każdego \(\displaystyle{ x}\)-a, \(\displaystyle{ n}\)-a i \(\displaystyle{ k-1}\) należących do zbioru liczb naturalnych dodatnich, istnieje dokładnie jeden taki \(\displaystyle{ x}\) z przedziału obustronnie domkniętego od 1 do 2 razy 3 do potęgi n, taki że 3 do potęgi n dzieli funkcję g od x-a i k pomniejszoną o 2.
Natomiast w przypadku 2:
Dla każdego n-a i k-1 należących do zbioru liczb naturalnych dodatnich, istnieje dokładnie jeden taki naturalny dodatni x z przedziału obustronnie domkniętego od 1 do 2 razy 3 do potęgi n, taki że 3 do potęgi n dzieli funkcję g od x-a i k pomniejszoną o 2.
Jak dla mnie brzmi to jakby oznaczało to samo i da się to zrozumieć, więc nie wiem z czego miałby wynikać zakaz kwantyfikowania kilkukrotnie po tej samej zmiennej.
Natomiast co do zapisu:
\(\displaystyle{ k-1 \in \NN_+ }\)
Jest to normalny zapis:
\(\displaystyle{ f(k) \in \NN_+ }\)
Gdzie:
\(\displaystyle{ f(k)=k-1}\)
Jest on używany by nie pisać, że k ma być całkowite większe od 1.

Mateusz5324 pisze: ↑19 kwie 2023, o 23:53 To według ciebie czym różnią się zapisy:
\(\displaystyle{ \large \forall_{x,n,k-1 \in \NN_+}: \exists!_{x \in <1;2 \cdot 3^n>}:3^n|g(x,k)-2}\)
od:
\(\displaystyle{ \large \forall_{n,k-1 \in \NN_+}: \exists!_{x \in <1;2 \cdot 3^n> \wedge x \in \NN_+}:3^n|g(x,k)-2}\)
Bo według mnie jedynie zapisem i każdy człowiek jest w stanie zrozumieć je jako znaczące to samo.

Jesteś w błędzie, bo różnią się bardzo istotnie. Zapisy formalne podlegają ścisłym regułom i jak ich nie znamy, to lepiej ich nie używać.

Wytłumaczyłem Ci, na czym polega problem z pierwszym zapisem. Jeżeli tego nie zrozumiałeś, to co ja na to poradzę? Drugi zapis już ujdzie, ale zgrzyta w zębach mocno. W wersji porządnej wyglądałby tak:

\(\displaystyle{ (\forall k,n\in\NN_+)(k\ge 2 \Rightarrow (\exists! x\in[1,2\cdot 3^n]\cap\NN)\,3^n|g(x,k)-2)}\)

lub nawet

\(\displaystyle{ (\forall k,n\in\NN_+)(k\ge 2 \Rightarrow (\exists! x\in\NN)(x\le 2\cdot 3^n\land 3^n|g(x,k)-2)).}\)

Mateusz5324 pisze: ↑19 kwie 2023, o 23:53Nie mówiąc nawet o tym, że przekopałem bardzo dużo tekstów dot. kwantyfikatorów i nigdzie nie było o czymś takim napisane. W szkole też nie uczono mnie, że jest to błędem.

Przepraszam bardzo, ale to nie jest żaden argument.

Mateusz5324 pisze: ↑19 kwie 2023, o 23:53Jeśli postarasz się przeczytać oba zdania to wyjdzie ci w przypadku 1:
Dla każdego \(\displaystyle{ x}\)-a, \(\displaystyle{ n}\)-a i \(\displaystyle{ k-1}\) należących do zbioru liczb naturalnych dodatnich, istnieje dokładnie jeden taki \(\displaystyle{ x}\) z przedziału obustronnie domkniętego od 1 do 2 razy 3 do potęgi n, taki że 3 do potęgi n dzieli funkcję g od x-a i k pomniejszoną o 2.
Natomiast w przypadku 2:
Dla każdego n-a i k-1 należących do zbioru liczb naturalnych dodatnich, istnieje dokładnie jeden taki naturalny dodatni x z przedziału obustronnie domkniętego od 1 do 2 razy 3 do potęgi n, taki że 3 do potęgi n dzieli funkcję g od x-a i k pomniejszoną o 2.
Jak dla mnie brzmi to jakby oznaczało to samo i da się to zrozumieć,

Popełniasz typowy błąd początkujących studentów, którym wydaje się, że dwa zupełnie różne zapisy symboliczne oznaczają "jakby to samo". A tymczasem wystarczy delikatnie przesunąć jeden nawias, żeby dostać zupełnie inną treść... Podobnie jest w tej sytuacji.

Mateusz5324 pisze: ↑19 kwie 2023, o 23:53więc nie wiem z czego miałby wynikać zakaz kwantyfikowania kilkukrotnie po tej samej zmiennej.

Wybacz, ale jakoś nie mam natchnienia, żeby robić teraz osobny wykład z podstaw rachunku kwantyfikatorów. Kwantyfikatory skutecznie kwantyfikują wyłącznie zmienne wolne, a zmienna zakwantyfikowana staje się zmienną związaną, więc nie można jej po raz drugi zakwantyfikować.

Mateusz5324 pisze: ↑19 kwie 2023, o 23:53 Natomiast co do zapisu:
\(\displaystyle{ k-1 \in \NN_+ }\)
Jest to normalny zapis:
\(\displaystyle{ f(k) \in \NN_+ }\)
Gdzie:
\(\displaystyle{ f(k)=k-1}\)
Jest on używany by nie pisać, że k ma być całkowite większe od 1.

To nie jest normalny zapis, bo nie wolno napisać \(\displaystyle{ (\forall f(k)\in\NN_+)}\). Kwantyfikatory dotyczą zmiennych, a \(\displaystyle{ f(k)}\) nie jest zmienną.

Do sformułowania Twojego pytania nie potrzeba zapisu symbolicznego. Wystarczyło napisać, że chcesz udowodnić, iż dla dowolnych liczb naturalnych dodatnich \(\displaystyle{ n,k}\), gdzie \(\displaystyle{ k\ge 2}\), istnieje dokładnie jedna liczba naturalna dodatnia \(\displaystyle{ x\le2\cdot 3^n}\), dla której mamy \(\displaystyle{ 3^n\mid g(x,k)-2.}\) Byłoby to na pewno jasne i czytelne. Skoro jednak postanowiłeś użyć samych znaczków, żeby zapis wyglądał "formalnie", to ja się do tego z zawodowego przyzwyczajenia przyczepiłem (bo już ponad ćwierć wieku uczę studentów matematyki, jak to powinno robić się poprawnie).

JK

Jan Kraszewski pisze: ↑20 kwie 2023, o 02:41

Mateusz5324 pisze: ↑19 kwie 2023, o 23:53Jeśli postarasz się przeczytać oba zdania to wyjdzie ci w przypadku 1:
Dla każdego \(\displaystyle{ x}\)-a, \(\displaystyle{ n}\)-a i \(\displaystyle{ k-1}\) należących do zbioru liczb naturalnych dodatnich, istnieje dokładnie jeden taki \(\displaystyle{ x}\) z przedziału obustronnie domkniętego od 1 do 2 razy 3 do potęgi n, taki że 3 do potęgi n dzieli funkcję g od x-a i k pomniejszoną o 2.
Natomiast w przypadku 2:
Dla każdego n-a i k-1 należących do zbioru liczb naturalnych dodatnich, istnieje dokładnie jeden taki naturalny dodatni x z przedziału obustronnie domkniętego od 1 do 2 razy 3 do potęgi n, taki że 3 do potęgi n dzieli funkcję g od x-a i k pomniejszoną o 2.
Jak dla mnie brzmi to jakby oznaczało to samo i da się to zrozumieć,

Popełniasz typowy błąd początkujących studentów, którym wydaje się, że dwa zupełnie różne zapisy symboliczne oznaczają "jakby to samo". A tymczasem wystarczy delikatnie przesunąć jeden nawias, żeby dostać zupełnie inną treść... Podobnie jest w tej sytuacji.
JK

Chodziło mi o to, że przerabiając oba zapisy na tekst znaczą dokładnie to samo, a nie że wyglądają podobnie. Od Ciebie słyszę, że nie można tak robić, bo tak. Matematyka jest nauką, w której wszystkie prawa z czegoś wynikają, jednak w tym przypadku nie widzę argumentu przemawiającego za zakazem takiego zapisu. Rozumiem, że możesz uczyć tego od ćwierć wieku, ale fakt poprawności jednej konwencji nie wyklucza poprawności innej. Oczekiwałem od Ciebie prostego wyjaśnienia dlaczego tak nie można, bo zawsze takowe istnieje. Przykład:
Kolejność działań jest istotna, bo gdyby nie była, to nie dało by się jednoznacznie wyznaczyć wartości:
\(\displaystyle{ 2 + 2 \cdot 2}\)
I oczekiwałem podobnego rozumowania tłumaczącego dlaczego to rzekome prawo "Zakazu kwantyfikowania kilkukrotnie po tej samej zmiennej" ma jakikolwiek sens. Ja przedstawiam ci kilka przesłanek mówiących, że zapis ten powinien być dozwolony, a twoją jedyną przesłanką za jego niepoprawnością jest to, że ty tak wiesz. I dobrze, że wiesz ale ja chciałbym zrozumieć dlaczego tak nie wolno. Skoro jak twierdzisz są to podstawy, to wytłumaczenie tego nie powinno być zbyt skomplikowane, więc czy mógłbym Cię o nie poprosić?

Mateusz5324 pisze: ↑20 kwie 2023, o 22:57Chodziło mi o to, że przerabiając oba zapisy na tekst znaczą dokładnie to samo, a nie że wyglądają podobnie.

To Ty uważasz, że znaczą dokładnie to samo. Fakt, że zamienisz symbole na słowa niczego nie zmienia.

Mateusz5324 pisze: ↑20 kwie 2023, o 22:57Od Ciebie słyszę, że nie można tak robić, bo tak. Matematyka jest nauką, w której wszystkie prawa z czegoś wynikają, jednak w tym przypadku nie widzę argumentu przemawiającego za zakazem takiego zapisu.

Chyba niezbyt uważnie przeczytałeś to, co napisałem. A była tam zarówno uwaga, że nie chce mi się robić wykładu (co oznacza, że wytłumaczenie tego wymaga odpowiedniego wprowadzenia), jak i skrótowy argument dotyczący zmiennych wolnych i związanych.

Mateusz5324 pisze: ↑20 kwie 2023, o 22:57Rozumiem, że możesz uczyć tego od ćwierć wieku, ale fakt poprawności jednej konwencji nie wyklucza poprawności innej.

To nie jest "konwencja" to tylko rachunek kwantyfikatorów, który ma swoje prawa. Możesz oczywiście wymyślić na własny użytek swój indywidualny formalizm matematyczny, ale czy o to chodzi?

Mateusz5324 pisze: ↑20 kwie 2023, o 22:57Oczekiwałem od Ciebie prostego wyjaśnienia dlaczego tak nie można, bo zawsze takowe istnieje. Przykład:
Kolejność działań jest istotna, bo gdyby nie była, to nie dało by się jednoznacznie wyznaczyć wartości:
\(\displaystyle{ 2 + 2 \cdot 2}\)
I oczekiwałem podobnego rozumowania tłumaczącego dlaczego to rzekome prawo "Zakazu kwantyfikowania kilkukrotnie po tej samej zmiennej" ma jakikolwiek sens.

Przykro mi, że nie spełniłem Twoich oczekiwań. Zastanawia mnie tylko, skąd to przekonanie, że każdy problem ma proste wyjaśnienie.

Mateusz5324 pisze: ↑20 kwie 2023, o 22:57 Ja przedstawiam ci kilka przesłanek mówiących, że zapis ten powinien być dozwolony, a twoją jedyną przesłanką za jego niepoprawnością jest to, że ty tak wiesz. I dobrze, że wiesz ale ja chciałbym zrozumieć dlaczego tak nie wolno. Skoro jak twierdzisz są to podstawy, to wytłumaczenie tego nie powinno być zbyt skomplikowane, więc czy mógłbym Cię o nie poprosić?

Porządne wytłumaczenie zajmuje mi zazwyczaj dwie godziny wykładu ze Wstępu do matematyki. Po ominięciu rzeczy niezwiązanych bezpośrednio z tym zagadnieniem byłoby krócej, ale nadal długo. Czy wiesz np. czym jest zasięg kwantyfikatora, co to są zmienne wolne i związane i czym się od siebie różną itd. ?

Poza tym (patrząc na to syntaktycznie) nie ma "zakazu kwantyfikowania kilkukrotnie po tej samej zmiennej", natomiast z powodów semantycznych nie należy tego robić - problem z Twoim wyjściowym zapisem był taki, że nie znaczył tego, co Ci się wydawało, że znaczy.

JK

Tak:
Zasięg kwantyfikatora to wyrażenie następujące po kwantyfikatorze i objęte nim.
Zmienne wolne - nie związane przez żaden kwantyfikator
Zmienne związane - zmienna w zasięgu kwantyfikatora ( dla \(\displaystyle{ \forall x \in \NN : x \ge 0}\) x jest zmienną związaną).

No i dobrze.

Teraz tak: dla każdej formuły rachunku kwantyfikatorów można określić jej zbiór zmiennych wolnych. Jeżeli tworzymy teraz nową formułę poprzez dopisanie kwantyfikatora do wcześniej istniejącej formuły, to zbiór zmiennych wolnych nowej formuły jest mniejszy od zbioru zmiennych "starej" formuły o zmienną, po której kwantyfikuje kwantyfikator. A jeżeli kwantyfikujemy formułę, w której zmienna występująca przy kwantyfikatorze nie jest zmienną wolną, to z semantycznego punktu widzenia jest to czynność "pusta" - ten kwantyfikator niczego nie dotyczy, więc równie dobrze można go opuścić. I właśnie dlatego nie należy zagnieżdżać kwantyfikatorów kwantyfikujących po tej samej zmiennej.

JK

Rozumiem twoje tłumaczenia ale mam jedno zastrzeżenie. Mianowicie prawdziwość stwierdzenia: "jeśli utworzymy nową formułę poprzez dodanie kolejnego kwantyfikatora, to musi się zmienić ilość zmiennych wolnych" nie jest dla mnie oczywista. Mogę po prostu uwierzyć Ci, ale wolałbym to zrozumieć, a nie wiedzieć, że ze stwierdzenia, co do którego prawdziwości nie jestem przekonany, wynika że kwantyfikowanie po zmiennej związanej jest "pustą" czynnością. Mam nadzieję że rozumiesz moje "zastrzeżenia" co do tego tłumaczenia, bo jestem pewien że to co piszesz ma ogromny sens, ale nadal w tym, "łańcuszku" równoważności nie doszliśmy do stwierdzenia co do którego prawdziwości byłbym przekonany.

Mateusz5324 pisze: ↑21 kwie 2023, o 02:35 Rozumiem twoje tłumaczenia ale mam jedno zastrzeżenie. Mianowicie prawdziwość stwierdzenia: "jeśli utworzymy nową formułę poprzez dodanie kolejnego kwantyfikatora, to musi się zmienić ilość zmiennych wolnych" nie jest dla mnie oczywista.

Nie "musi". Zbiór zmiennych wolnych formuły definiuje się rekurencyjnie względem złożoności formuły. W szczególności jeśli \(\displaystyle{ V}\) jest zbiorem zmiennych wolnych formuły \(\displaystyle{ \varphi}\), to zbiorem zmiennych wolnych formuły \(\displaystyle{ \forall x\varphi}\) jest \(\displaystyle{ V \setminus \{x\}}\). Jeśli zatem \(\displaystyle{ x}\) było zmienną wolną w formule \(\displaystyle{ \varphi}\), to liczba zmiennych wolnych spadnie, a jeśli nie, to pozostanie bez zmian.

Potocznie, formuła w której \(\displaystyle{ x}\) jest zmienną wolną opisuje pewną własność \(\displaystyle{ x}\)-a. Zakwantyfikowanie tej formuły kwantyfikatorem \(\displaystyle{ \forall x}\) lub \(\displaystyle{ \exists x}\) oznacza stwierdzenie, że rzeczona własność zachodzi zawsze lub może zachodzić. Jeżeli kwantyfikujesz kwantyfikatorem \(\displaystyle{ \forall x}\) formułę, w której \(\displaystyle{ x}\) nie jest zmienną wolną, to po prostu nic nie stwierdzasz.

JK

Sam napisałeś, że jeśli tak nie będzie, to czynność związana z dodaniem do aktualnej formuły kolejnego kwantyfikatora jest "pusta". Aby więc nie wykonywać pustych czynności musi tak być. Natomiast patrząc na wzór jeśli x nie jest zmienną pustą, to ich liczba się nie zmieni, co jest wręcz kolejnym argumentem za poprawnością mojego pierwszego zapisu, gdyż to że jeśli x nie jest zmienną wolną, to kwantyfikowanie po nim jest "puste" czytam od początku w twoich postach i tyle, bo ja czytając twoje posty ciągle dowiaduję się prawie tego samego, tylko powiedzianego innymi słowami, natomiast jeśli już uda mi się wyczytać coś co jest równoważne z tym stwierdzeniem i rozumiem z jakiego powodu jest równoznaczne, to nie wiem dlaczego to równoważne stwierdzenie jest prawdziwe, więc ostatecznie pozostaje z nieznaną wartością logiczną stwierdzenia:
"Jeżeli kwantyfikujesz kwantyfikatorem \(\displaystyle{ \forall x}\) formułę, w której \(\displaystyle{ x}\) nie jest zmienną wolną, to po prostu nic nie stwierdzasz.", lub wierzę Ci na słowo i liczę, że jest prawdziwe. Postaraj się przeczytać swoje posty i zastanowić się, czy nie da się tam wyodrębnić tego samego powiedzianego innymi słowami, i gdy wyrzucimy tą treść, to zostaje tam coś, co przynajmniej mi nie odpowiada na pytanie "dlaczego?". Dla mnie to tłumaczenie wygląda tak, jakbym zapytał się dlaczego MTF jest prawdziwe, a ktoś powie mi, że istnieje, bo Fermat je wymyślił. I niewątpliwie jest to prawdą, ale nie sprawia, że rozumiem dlaczego jest prawdziwe.