Formal Representation of Haskell Data-Types
Unter the assumption, that lists simply represents arbitrary sets, the mathematical notation should probably read:


  An ARE is an element of the following set:
  
  $\{ (P, Q) \mid P \subseteq ARF \times ARF, Q \subseteq ARF \} $    


But as you stated, lists in your domain are always finite, ordering is not important, but multiplicity is. Thus, I would model the lists as finite multisets. Using an explicit notation for mulitsets, a possible definition would be:


  An ARE is an element of the following set:
  
  $\{ (P_\chi, Q_\xi) \mid P \subseteq ARF \times ARF, 
                           P~\text{finite},~
                           \chi \in (P \to \mathbb{N}^+),
                           Q \subseteq ARF, Q~\text{finite},~
                           \xi \in (Q \to \mathbb{N}^+) \} $    


Here, the notation $P_\chi$ denotes a multiset with P being the underlying ordinary set and $\chi \in P \to \mathbb{N}^+$ being the multiplicity function of the multiset.