da apatriarca » 08/06/2021, 09:06
Il metodo classico per provare l'equivalenza tra due insiemi consiste nel provare che un insieme è incluso nell'altro e viceversa. Sia quindi \(A'\) l'insieme definito dalla tua definizione non ricorsiva. Puoi iniziare mostrando che \(A \subseteq A'\) mostrando che \(A'\) soddisfa le proprietà ricorsive. Quindi puoi mostrare che \(b \in A'\) e che \(\forall x \in A'\) hai che \( axa \in A' \). A questo punto rimane da dimostrare che \(A' \subseteq A\). Probabilmente la tua definizione dipende da un numero intero \(n \in \mathbb N\) e puoi usare l'induzione su \(\mathbb N\) come al solito mostrando prima il caso base per \(n = 0\) e poi mostrare che se tutte le stringhe fino a \(n \leq k\) appartengono a \(A\) allora anche la stringa per \(n = k + 1\) appartiene ad \(A\). Spero di esserti stato d'aiuto senza fornirti tutta la soluzione.