Изменения
Нет описания правки
3) <tex>\mid A \mid < \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
}}
==Универсальный матроид==
{{Определение
|definition=
'''Универсальным матроидом''' называют объект <tex>U_n,_k = \langle X = \{1, 2, 3, ..., n\}, I = \{A| \mid A \mid \leq k\} \rangle </tex>
}}
{{Лемма
|statement = Универсальный матроид является матроидом.
|proof =
Проверим выполнение аксиом независимости:
1) <tex>\varnothing \in I</tex>
<tex> \mid \varnothing \mid = 0 \leq k \Rightarrow \varnothing \in I</tex>
2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
<tex> \mid A \mid \leq \mid B \mid \leq k \Rightarrow \mid A \mid \leq k \Rightarrow A \in I </tex>
3) <tex>\mid A \mid < \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
Так как <tex>\mid A \mid < \mid B \mid </tex> и числа в каждом множестве различны, найдётся такое число <tex> x \in B </tex>, которое не будет принадлежать меньшему по мощности множеству <tex> A </tex>.
Рассмотрим <tex> A \cup \mathcal{f} x \mathcal {g} </tex>. <tex>\mid A \mid < \mid B \mid \Rightarrow \mid A \cup \mathcal{f} x \mathcal {g} \mid = \mid A \mid + 1 \leq \mid B \mid \leq k \Rightarrow A \cup \mathcal{f} x \mathcal {g} \in I</tex>
}}
