In set theory what is A* and how does it differ from the power set of A? I am having a difficult time understanding the use of $A^*$ and how it differs from the usage of a power set.
$A^*$ is defined as "the set of all (finite) lists over A". I understand $\wp(A)$ to be the power set of A defined as "the set of all subsets of A."
How is "all lists over A" different from "all subsets of A"?
Here are both definitions as denoted in my textbook:
$$A^* := \{[a_1,...,a_n]\ |\ n \in \mathbb N;\ a_1,...,a_n \in A\}$$
$$\wp(A) = \{X\ |\ X \subseteq A\}$$
 A: There are several differences:

*

*Finite lists are ordered (and allow duplicates) while sets are not: e.g. $$[1,2,1]\quad\mbox{and}\quad[2,1,1]$$ are different lists, while $$\{1,2\}=\{2,1\}=\{1,2,1\}.$$


*Finite lists are finite while elements of $\mathcal{P}(A)$ (= subsets of $A$) need not be: if we take $A=\mathbb{N}$, then the set of even numbers is an element of $\mathcal{P}(A)$ but there is no finite sequence which in any sense "corresponds" to it. Meanwhile, subsets of $A$ are at most as big as $A$, while finite lists can have arbitrarily large finite lengths - this means that if $A$ is finite there will be finite lists of elements of $A$ which are "longer than $A$ is big" (consider e.g. $A=\{1,2\}$ and the finite list $[1,2,1,2,1,2]$).
So $A^*$ and $\mathcal{P}(A)$ are really very different objects.

On a technical note, it's a good idea at this point to give a formal definition of "finite sequence." The definition you've given isn't really rigorous, since the notation "$[...]$" is itself undefined.
The most convenient one winds up being: "a finite list (of elements of some set $X$) is a function $f$ with domain $\{i\in\mathbb{N}:i<n\}$ for some $n\in\mathbb{N}$ (and codomain $X$)." We think of $f(i)$ as the $i$th term of $f$.
This winds up being a very useful definition in that it generalizes broadly - see e.g. here.
A: The two have basically nothing in common. $A^*$ is the set of all (finite) words you can write using the elements of $A$ as letters, whereas $P(A) $ is the set of all subsets of $A$.
As a very simple example, if $A = \{a\} $, then $A^* = \{\varepsilon, a, aa, aaa, aaaa, \dots\} $ ($\varepsilon $ is the empty word) whereas $P(A) =\{\emptyset, \{a\} \} $.
