Matematyka.pl

Jak udowodnić, że taki zbiór nie jest funkcjonalnie pełny? \(\displaystyle{ \left\{ \Rightarrow \right\} }\)

Pokazujesz, że zbiór funkcji binarnych \(\displaystyle{ F_{ \Rightarrow } }\), które można zdefiniować przy pomocy samej implikacji (i zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\)) jest co najwyżej sześcioelementowy (a wszystkich funkcji binarnych jest \(\displaystyle{ 2 ^{4}=16}\)).
W tym celu pokazujesz indukcyjnie, że jeśli formuła zbudowana jedynie ze spójnika implikacji \(\displaystyle{ \Rightarrow }\) i zmiennych (\(\displaystyle{ x}\) i \(\displaystyle{ y}\)) kończy się zmienną \(\displaystyle{ x}\), to każde wartościowanie, które ostatnią zmienną \(\displaystyle{ x}\) wartościuje na prawdę, wartościuje również całą formułę na prawdę.
Następnie pokazujesz, analogiczny fakt dla zmiennej \(\displaystyle{ y}\).
Oznacza to, dla tabeli funkcji binarnych, że ostatni wiersz jest stale równy \(\displaystyle{ 1}\) lub ostatnia kolumna jest stale równa \(\displaystyle{ 1}\), a takich tabel jest dokładnie \(\displaystyle{ 6}\). Wobec czego przy pomocy implikacji nie da się zdefiniować więcej niż sześciu funkcji binarnych. A wszystkich funkcji binarnych jest \(\displaystyle{ 16}\), wobec czego nie wszystkie funkcje binarne można zdefiniować w ten sposób. Pozostaje może jeszcze kwestia, czy można używać większej ilości zmiennych, ale dla funkcji binarnych mamy tylko dwie zmienne, i w definicji dowolnego takiego spójnika dwuargumentowego możemy używać chyba tylko tych dwóch zmiennych. A dla innych oznaczeń zmiennych otrzymamy chyba ten sam wynik, bo prawa logiczne pozostaje prawdziwe po dowolnej zamianie zmiennych (odpowiednie zmienne zamieniamy za odpowiednio dobrane zmienne). Może niech ktoś kompetentny potwierdzi czy to jest dobrze??
(To nie jest teoria mnogości, to logika...)