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

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

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

[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]\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]\mid A \mid \lt \mid B \mid \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]\mid A_1 \mid \lt \mid B_1 \mid[/math] или [math]\mid A_2 \mid \lt \mid B_2 \mid[/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]