Understanding mathematical set theory syntax

Question

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.

Answer 1

Well, the set

$$Y^{X} = \{ f\colon X\to Y\}$$

describes the set of all functions from $X$ to $Y$.

So $2^{X}$ are the indicator functions on all possible subsets of $X$. This is usually identified as the powerset of $X$, i.e., the set of all possible subsets of $X$.

So

$$f\colon S\to 2^{X}$$

describes a function $f$ from a set $S$ to the powerset of $X$, i.e., assigns to each element $s\in S$ a subset $f(s)\subset X$. NB: it is entirely possible that $f(s)=\emptyset$.

Example. Consider the set $A=\{1,2\}$. Then we have 4 elements of $2^{A}$, namely

$$\chi_{1}(x)=\begin{cases}1 & x=1\\ 0 &\mbox{otherwise}\end{cases}$$

and likewise $\chi_{2}(x)=1$ if $x=2$, and $0$ otherwise. Then we have $\chi_{0}(x)=0$, which is the characteristic function for the empty set...and $\chi_{1,2}(x)=1$ for any $x\in A$.

Observe these are the characteristic functions for $\{1\}$, $\{2\}$, $\emptyset$, and $A$ (respectively).

Point 2. Regarding the notation of square brackets [] inside the set, this is an obscure notation used by logicians sometimes. They use quantifiers $\exists$ or $\forall$ and then some predicate afterwards, and the predicate is in square brackets. So, for example:

$$(\exists y)[y<2\land y>0]$$

This is a proposition "There is some $y$ such that $y<2$ and $y>0$."

The quantifier portion is placed in parentheses, the predicate inside square brackets.

Answer 2

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)$

Answer 3

The notation $2^E$ is a standard notation meaning the set of subsets of $E$. It is convenient because when looking at the cardinal of this set (if $E$ is finite), we have $|2^E|=2^{|E|}$. It is a particular instance of the general notation $F^E$ for functions $E\to F$, as $2$ is short for $\{0,1\}$ and a subset of $E$ is the same as a function $E\to\{0,1\}$.

So the function $f:S\to 2^{R\cup AR}$ actually maps each element of $S$ to a subset of $R\cup AR$.

The notation with [] enclosed in {} is not standard, but from the context in your paper, it seems that (A)[B] means "A such that B". So $\{A~|~(\exists B)[C]\}$ means "the set of all A such that there exists B such that C"