relacje-pomocy monika: Ile jest relacji równoważności na zbiorze 4−elementowym, uzasadnij. Proszę o pomoc!

PW : Elementy zbioru X, na którym jest określona relacja, możemy utożsamić z liczbami naturalnymi 0, 1, 2, 3, wówczas iloczyn kartezjański X×X ma prostą interpretację geometryczną: siatka 16 punktów kwadratu. Relacją na zbiorze Z nazywamy dowolny podzbiór iloczynu kartezjańskiego, a więc relacji jest aż 2¹⁶. Definicja relacji zwrotnej ogranicza jednak poszukiwania: relacja taka musi zawierać wszystkie punkty "przekątnej", czyli pary (0,0), (1,1), (2,2), (3,3). Relacja złożona tylko z tych par spełnia wszystkie warunki równoważności (sprawdzić) .Jeżeli weźmiemy jakikolwiek punkt spoza przekątnej, czyli parę (x, y), w której x ≠ y, to symetryczność relacji wymaga, aby należała do niej również para (y, x). Liczbę pozostałych relacji będących jednocześnie zwrotnymi i symetrycznymi można więc policzyć z łatwością − jest ich tyle, na ile sposobów można wybrać 1−, 2−, 3−, 4−, 5− lub 6−elementowe podzbiory z 6 punktów siatki leżących poniżej przekątnej. To jednak za dużo, relacje muszą być jeszcze przechodnie, na przykład jeśli wybrano (2,1) i (1,0), to musi być wybrany także (2, 0). Jakaś wskazówka jest, ale pewnie można to policzyć łatwiej − bez żmudnej analizy tych podzbiorów.