[Metodi Matematici per info.] Esercizio chiarimenti

[epdragon]

Fornire una definizione non ricorsiva dell’insieme definito come segue:
Passo Base: b ∈ A
Passo ricorsivo: Se x ∈ A allora axa ∈ A.

Provare che le due definizioni sono equivalenti, usando l’induzione (specificando quale induzione
si usa)

Volevo chiarimenti su come fare per provare che le due definizioni sono equivalenti. Grazie in anticipo

[apatriarca]

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.

[epdragon]

In generale ho capito come fare, però ho paura di sbagliare a scrivere qualcosa o nel mancare qualche passaggio importante. E' possibile spiegarmi passo per passo? oppure anche un esercizio simile già svolto mi aiuterebbe molto. p.s. ti ho inviato una soluzione in pvt.

[apatriarca]

Prova a scrivere la tua soluzione e la commentiamo.

[epdragon]

Ti ho inviato una soluzione con un messaggio in pvt