Најважније из лекције
- Бинарна релација \( \rho \) је подскуп Декартовог производа \( A \times A \). Пишемо \( x \rho y \).
- Релација поретка мора бити: рефлексивна, антисиметрична и транзитивна (нпр. \( \le \), \( \subseteq \)).
- Релација еквиваленције мора бити: рефлексивна, симетрична и транзитивна (нпр. \( = \)).
- Релација еквиваленције дели скуп на дисјунктне подскупове који се зову класе еквиваленције.
Бинарна релација скупа \( A \) је било који подскуп Декартовог производа \( A \times A \). Овом релацијом се успостављају везе између елемената посматраног скупа.
Ако је пар \( (x, y) \in \rho \), уобичајено је да се пише \( x \rho y \) и чита „икс је у релацији ро са ипсилон”. Уколико нису у релацији, пише се \( x \not\rho y \).
Релације на коначним скуповима се најчешће сликовито приказују помоћу графа (где су елементи чворови, а релације усмерене стрелице) или помоћу таблице истинитости.
Нека је \( A = \{a, b, c\} \) и релација \( \rho = \{(a, a), (a, b), (c, a)\} \).
Тада важи \( a \rho a \), \( a \rho b \) и \( c \rho a \), али на пример важи \( b \not\rho c \) јер пар \( (b, c) \) не припада релацији.
Тада важи \( a \rho a \), \( a \rho b \) и \( c \rho a \), али на пример важи \( b \not\rho c \) јер пар \( (b, c) \) не припада релацији.
Бинарна релација \( \rho \) скупа \( A \) може имати неке од следећих особина:
- Рефлексивна: ако је \( x \rho x \) за свако \( x \) из \( A \). (Сваки елемент је у релацији са самим собом).
- Ирефлексивна: ако ни за једно \( x \) из \( A \) није \( x \rho x \).
- Симетрична: ако је за све \( x, y \in A \) тачна импликација \( x \rho y \Rightarrow y \rho x \). (Ако је \( x \) у релацији са \( y \), онда мора бити и \( y \) у релацији са \( x \)).
- Антисиметрична: ако је за све \( x, y \in A \) тачна импликација \( x \rho y \land y \rho x \Rightarrow x = y \). (Ако су узајамно у релацији, морају бити исти елемент).
- Линеарна: ако је за све \( x, y \in A \) тачна дисјункција \( x \rho y \lor y \rho x \). (Свака два елемента су упоредива).
- Транзитивна: ако је за све \( x, y, z \in A \) тачна импликација \( x \rho y \land y \rho z \Rightarrow x \rho z \). (Ако је први у релацији са другим, а други са трећим, онда је и први у релацији са трећим).
Релација \( \rho \) је релација поретка (уређење) ако је рефлексивна, антисиметрична и транзитивна.
Поред основне релације поретка, разликујемо још два специфична облика:
- Линеарни поретак: ако је релација рефлексивна, антисиметрична, линеарна и транзитивна.
- Строги поретак: ако је релација ирефлексивна и транзитивна (свакој релацији поретка одговара једна релација строгог поретка, нпр. релацији \( \le \) одговара строги поретак \( < \)).
У наредној табели приказане су три веома важне релације поретка у математици:
| Особина | \( \le \) на скупу \( \mathbb{R} \) | \( | \) (дељивост) на \( \mathbb{N} \) | \( \subseteq \) (инклузија) скупова |
|---|---|---|---|
| Рефлексивност | \( x \le x \) | \( n | n \) | \( A \subseteq A \) |
| Антисиметричност | \( x \le y \land y \le x \Rightarrow x = y \) | \( n | m \land m | n \Rightarrow n = m \) | \( A \subseteq B \land B \subseteq A \Rightarrow A = B \) |
| Транзитивност | \( x \le y \land y \le z \Rightarrow x \le z \) | \( n | m \land m | k \Rightarrow n | k \) | \( A \subseteq B \land B \subseteq C \Rightarrow A \subseteq C \) |
Релација \( \rho \) је релација еквиваленције ако је рефлексивна, симетрична и транзитивна. Типичан пример овакве релације је једнакост (\( = \)).
Класа еквиваленције: Свака релација еквиваленције неког скупа дели тај скуп на међусобно дисјунктне (не преклапају се) непразне подскупове. Сваки од тих подскупова назива се класа еквиваленције, а њихова унија даје цео почетни скуп.
Релација дефинисана са: "\( x \rho y \) ако је разлика \( x - y \) дељива са 2" на скупу целих бројева \( \mathbb{Z} \) је релација еквиваленције.
Ова релација дели скуп целих бројева на тачно две класе еквиваленције:
Ова релација дели скуп целих бројева на тачно две класе еквиваленције:
- Скуп парних бројева: \( \{..., -4, -2, 0, 2, 4, ...\} \)
- Скуп непарних бројева: \( \{..., -5, -3, -1, 1, 3, ...\} \)
Задаци за вежбање
Лаки ниво: Дата је релација \( \rho = \{(1,1), (2,2), (3,3), (1,2), (2,1)\} \) на скупу \( A = \{1, 2, 3\} \). Да ли је ова релација рефлексивна и симетрична?
Да. Релација је рефлексивна јер садржи парове \( (1,1), (2,2), (3,3) \), што значи да је сваки елемент у релацији са самим собом. Такође је симетрична јер за једини пар различитих елемената \( (1,2) \) постоји и обрнути пар \( (2,1) \).
Средњи ниво: Нека је релација \( \rho \) на скупу природних бројева \( \mathbb{N} \) дефинисана као \( x \rho y \) ако је \( x < y \). Да ли је ово релација поретка или релација строгог поретка? Објасните зашто.
Ово је релација строгог поретка.
Није релација поретка јер није рефлексивна (ниједан број није строго мањи од самог себе, тј. не важи \( x < x \)).
Она испуњава услове за строги поретак јер је ирефлексивна (никада не важи \( x \rho x \)) и транзитивна (ако је \( x < y \) и \( y < z \), онда мора бити \( x < z \)).
Није релација поретка јер није рефлексивна (ниједан број није строго мањи од самог себе, тј. не важи \( x < x \)).
Она испуњава услове за строги поретак јер је ирефлексивна (никада не важи \( x \rho x \)) и транзитивна (ако је \( x < y \) и \( y < z \), онда мора бити \( x < z \)).
Тежи ниво: На скупу свих ученика једне школе дефинисана је релација: ученик \( A \) је у релацији са учеником \( B \) ако иду у исто одељење. Докажите да је ово релација еквиваленције и наведите шта представљају класе еквиваленције у овом случају.
Да би била релација еквиваленције, мора да испуњава 3 особине:
1. Рефлексивност: Сваки ученик иде у исто одељење са самим собом (\( A \rho A \)).
2. Симетричност: Ако ученик \( A \) иде у исто одељење са учеником \( B \), онда и ученик \( B \) иде у исто одељење са учеником \( A \) (\( A \rho B \Rightarrow B \rho A \)).
3. Транзитивност: Ако ученик \( A \) иде у одељење са \( B \), а ученик \( B \) иде у одељење са \( C \), онда ученик \( A \) мора ићи у одељење са \( C \) (\( A \rho B \land B \rho C \Rightarrow A \rho C \)).
Класе еквиваленције: Свака класа еквиваленције представља један конкретан разред (одељење) у тој школи (нпр. класа свих ученика који иду у одељење I-1). Све класе заједно чине целу школу.
1. Рефлексивност: Сваки ученик иде у исто одељење са самим собом (\( A \rho A \)).
2. Симетричност: Ако ученик \( A \) иде у исто одељење са учеником \( B \), онда и ученик \( B \) иде у исто одељење са учеником \( A \) (\( A \rho B \Rightarrow B \rho A \)).
3. Транзитивност: Ако ученик \( A \) иде у одељење са \( B \), а ученик \( B \) иде у одељење са \( C \), онда ученик \( A \) мора ићи у одељење са \( C \) (\( A \rho B \land B \rho C \Rightarrow A \rho C \)).
Класе еквиваленције: Свака класа еквиваленције представља један конкретан разред (одељење) у тој школи (нпр. класа свих ученика који иду у одељење I-1). Све класе заједно чине целу школу.
