Demostrar por inducción que $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ es impar

Question

Estoy tratando de demostrar la siguiente afirmación a través de la inducción:

Supongamos que $A_1,\ldots,A_n$ serie de Sets.

Demostrar que $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ es impar

Mis preguntas:

1. ¿El caso base comienza aquí desde uno o desde cero?
2. ¿Debo demostrar esta afirmación de dos maneras? ¿de derecha a izquierda y de izquierda a derecha? es decir, hacer dos inducciones?

Answer 1

Puedes empezar desde $0$ porque se puede definir la diferencia simétrica múltiple mediante $$ \mathop{\large\triangle}_{i=0}^0 A_i=\emptyset, \qquad \mathop{\large\triangle}_{i=0}^{n+1} A_i= \biggl(\mathop{\large\triangle}_{i=0}^{n} A_i\biggr)\mathbin{\triangle}A_{n+1} $$ Aquí, la asociatividad de la diferencia simétrica es importante.

Ahora el paso base de la inducción está claro: para $n=0$ tenemos $|\{i\mid a\in A_i\}|=0$ y $a\notin\emptyset$ .

Supongamos ahora que la afirmación es válida para $n$ conjuntos y set, para simplificar, $$ B=\mathop{\large\triangle}_{i=0}^{n} A_i $$ Tenemos que $a\in B\mathbin{\triangle}A$ si y sólo si $a\in B$ o $a\in A_{n+1}$ pero $a\notin B\cap A_{n+1}$ . Esto es equivalente, por la hipótesis de inducción, a

$|\{i\mid a\in A_i\}|$ es impar o $a\in A_{n+1}$ pero $a\notin B\cap A_{n+1}$ .

Comprueba los casos y ya está.

Answer 2

El caso base es para $n=1$ :

$$a \in A_1 \iff |\{i \in \{1\} : a \in A_i\}| = 1 \iff |\{i\in \{1\} : a \in A_i\}| \text{ is odd}$$

desde $|\{i \in \{1\} : a \in A_i\}| \in \{0,1\}$ .

Supongamos que $a \in A_1 \Delta\, \cdots \Delta\,A_n \iff |\{i \in \{1, \ldots, n\}: a \in A_i\}|$ es impar.

Para $n+1$ tenemos \begin{align} a \in A_1 \Delta\, \cdots \Delta\,A_n \Delta\,A_{n+1} &\iff \vee\begin{cases} \big(a \in A_1 \Delta\, \cdots \Delta\,A_n\big) \wedge (a \notin A_{n+1}), \\ \big(a \notin A_1 \Delta\, \cdots \Delta\,A_n\big) \wedge (a \in A_{n+1})\end{cases} \\ &\iff \vee \begin{cases} \big(|\{i \in \{1, \ldots, n\}: a \in A_i\}| \text{ is odd}\big) \wedge (a \notin A_{n+1}), \\ \big(|\{i \in \{1, \ldots, n\}: a \in A_i\}| \text{ is even}\big) \wedge (a \in A_{n+1})\end{cases} \\ &\iff \vee \begin{cases} |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}| \text{ is odd}, \\ |\{i \in \{1, \ldots, n,n+1\}: a \in A_i\}| \text{ is odd}\end{cases} \\ &\iff |{i \\\\\Nen {1, \ldots, n,n+1\\\}: a \\Nen A_i\}||\Nse impar} |end{align}