[Math] Understanding mathematical set theory syntax

computer scienceelementary-set-theorynotation

While reading a paper, I came across some operators and syntax that I am not familiar with, and I'm not sure how to google to find the definitions or explanations I am looking for.

For reference, I am reading this paper, page 6.

In this line:
$$f\colon S \to 2^{R \cup AR}$$

I understand that this means- $f$ is a function that maps from $S$ to the union of the set of all $R$ and $AR$. But what is the significance of mapping $S$ to $2$ raised to this union?

On the same page, there are a couple expressions involving blocks in $[]$ tags enclosed in $\{ \}$. I know that $\{\,r \mid\dots\}$ reads, the set of all $r$ such that .., but what is the significance of $\{\,r \mid\dots [\dots]\}$. How does this read in English? Examples are in the same page on the linked paper, my formatting skills aren't good enough to type it out here.

Best Answer

Often in set theory we write $A^B$ for the collection of all functions from $B$ to $A$. Additionally by $0$ we mean $\varnothing$ and by $n$ we mean $\{0,1,\ldots,n-1\}$.

Hence in your example $f$ takes an element of $S$ to a function from $A\cup AR$ to the set $2=\{0,1\}=\{\varnothing,\{\varnothing\}\}$. By identifying characteristic functions with subsets, you can consider this as a function from $S$ to $\mathcal{P}(A\cup AR)$

Related Question