Оператор замыкания для матроидов

Определение:

[math]M =\; \langle X,I \rangle[/math] - матроид. Тогда замыкание (closure) множества [math]A \subset X[/math] - это множество [math]\langle A \rangle \subset X[/math] такое, что [math]\langle A \rangle = A \cup \mathcal {f} x\; |\; \exists B \subset A : B \in I ,\; B \cup x \notin I \mathcal {g}[/math]

Теорема:

Оператор замыкания для матроидов обладает следующими свойствами: [math]A \subset B \Rightarrow \langle A \rangle \subset \langle B \rangle[/math] [math]q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle[/math] [math]\langle \langle A \rangle \rangle = \langle A \rangle [/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]\langle A \rangle \subset \langle B \rangle,[/math] тогда [math]\exists x \notin \langle B \rangle, x \in \langle A \rangle.[/math] Следовательно, [math]\exists C \in I, C \subset A : C \cup x \notin I.[/math] Но так как [math]C \subset B,[/math] то [math]x \in \langle B \rangle.[/math] Получили противоречие. Так как [math]q \in \langle A \cup p \rangle [/math] и [math]q \notin \langle A \rangle,[/math] то существует зависимое множество [math]\mathcal {f} a_1, a_2, ... a_n, p, q \mathcal {g} (a_i \in A).[/math] Заметим, что множество [math]\mathcal {f} a_1, a_2, ... a_n, q \mathcal {g} \in I.[/math] То есть [math]\mathcal {f} a_1, a_2, ... a_n, p, q \mathcal {g} - [/math] цикл. Ч.т.д.

[math]\triangleleft[/math]