Matematyka.pl

Witam.

Jestem w trakcie nauki na egzamin z matematyki dyskretnej. Straszny problem mam ze zrozumieniem w jaki sposób w ogóle zacząć prace nad zadaniami z serii "sprawdź czy relacja jest ... <typ relacji>".

Przykładowo:

Czy relacja
\(\displaystyle{ R \subset N^{2} : \forall x,y \in N \ \ \ \ xRy \Leftrightarrow 4|(2x + 2y)}\)
jest relacją równoważności.

Czy mógłby ktoś mi podpowiedzieć jak zacząć w ogóle rozwiązywanie takich zadań? Z teorii wiem, że powinienem sprawdzić czy relacja jest zwrotna, symetryczna oraz przechodnia. Nie do końca jednak rozumiem, co to znaczy, że ralacja zachodzi dla jakiejś pary? Np. relacja jest zwrotna, gdy zachodzi dla \(\displaystyle{ xRx}\).

Za wszelką pomoc będę bardzo wdzięczny.

Drozdowski Tomasz

Masz sformułowane, że dwie liczby x i y są w relacji, jeżeli 4 jest dzielnikiem ich podwojonej sumy. 1 jest w relacji z 1 bo \(\displaystyle{ 2+2=4, 4|4}\), ale 2 i 5 już nie są w relacji bo \(\displaystyle{ 4+10=14}\), jak wiadomo 4 nie dzieli 14. To właśnie znaczy ta relacja. Teraz z definicji relacji równoważności sprawdzasz warunki i stwierdzasz, czy jest to relacja równoważności, czy nie.

Czyli np. jeżeli chciałbym pokazać pierwszy warunek to byłoby tak:

\(\displaystyle{ xRx \Leftrightarrow 4|(2x + 2x) \Leftrightarrow 4|4x \Leftrightarrow 1|x = zawsze \ prawda}\)
Jako, że x jest naturalną liczbą.
I dalej:
\(\displaystyle{ xRy \Leftrightarrow 4(2x + 2y) \Leftrightarrow 4|(2y + 2x) \Leftrightarrow yRx}\)
Finalnie:
\(\displaystyle{ xRy \Leftrightarrow 4|(2x + 2y) \Leftrightarrow 2|(x + y) \\
yRz \Leftrightarrow 4|(2y + 2z) \Leftrightarrow 2|(y + z)}\)

Żeby 2 dzieliło sume dwóch liczb, to obydwie muszą być parzyste (co można łatwo udowodnić). Z tego wynika, że 2 dzieli x, y oraz z, a skoro tak to:
\(\displaystyle{ ((2|(x + y) \wedge 2|(y + z)) \Rightarrow 2 | (x + z)}\) jest zawsze prawdziwe
Ma to sens?

Mogą też być obydwie nieparzyste. Jeżeli zepniesz te 2 przypadki to wychodzi, że dla każdych x, y oraz y, z będących w relacji x i z również w niej są, zatem relacja jest relacją równoważności na mocy tego stwierdzenia i dwóch poprzednich elementów definicji.

A czy byłbyś tak miły i napisał mi jak sprawdzić czy relacja jest porządkująca? Bo tutaj nawet teorii nie umiem szczerze mówiąc znaleźć, a jeżeli potrafię to nie jestem w stanie się przez nią przegryźć.

Przechodnia musi być antysymetryczna, zwrotna i przechodnia. Sprawdziłeś, że jest symetryczna, więc nie jest przechodnia.