Прямая сумма матроидов

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
[math]M_1 = \langle X_1, I_1 \rangle [/math] и [math] M_2 = \langle X_2, I_2 \rangle [/math] — матроиды. Тогда [math] M_1 \oplus M_2 = \langle X = X_1 \times \mathcal {f} 1 \mathcal {g} \cup X_2 \times \mathcal {f} 2 \mathcal {g}, I = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2 \mathcal {g} \rangle [/math]. Иначе говоря, мы считаем, что носители матроидов [math]M_1[/math] и [math]M_2[/math] не пересекаются.
Лемма:
Прямая сумма матроидов является матроидом.
Доказательство:
[math]\triangleright[/math]

Докажем аксиомы независимости для [math] I [/math].

1. [math]\varnothing \in I[/math]

[math] A_1 = \varnothing \in I_1, A_2 = \varnothing \in I_2 \Rightarrow A_1 \cup A_2 = \varnothing \in I [/math]

2. [math]A \subset B, B \in I \Rightarrow A \in I[/math]

Пусть [math]B = B_1 \cup B_2, B_1 \in I_1, B_2 \in I_2, A = A_1 \cup A_2, A_1 \subset B_1, A_2 \subset B_2[/math]. [math]A_1 \subset B_1[/math], значит по второй аксиоме для [math]I_1[/math], [math]A_1 \in I_1[/math]. Аналогично [math]A_2 \in I_2[/math]. Значит [math]A_1 \cup A_2 \in I[/math].

3. [math]|A| \lt |B| \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I[/math]

Пусть [math]A = A_1 \cup A_2[/math], [math]B = B_1 \cup B_2[/math]. Тогда [math]|A_1| \lt |B_1|[/math] или [math]|A_2| \lt |B_2|[/math]. В первом случае по третьей аксиоме для [math] I_1[/math], [math]\mathcal {9} x \in B_1 \setminus A_1, A_1 \cup \mathcal{f} x \mathcal {g} \in I_1 [/math]. Значит [math] A_1 \cup \mathcal{f} x \mathcal {g} \cup A_2 \in I[/math]. Второй случай аналогичен первому.
[math]\triangleleft[/math]