# Want to understand a set notation

I cannot picture $$\bigcap \{X\subseteq A| F(X)\subseteq X\}$$ in my head. Perhaps I could better understand it in symbolic logic. How do you write it in symbolic logic ?

-
What is $F$?  –  Rasmus Jun 15 '11 at 19:08
In words, it is the intersection of all subsets $X$ of $A$ fulfilling the condition $F(X)\subseteq X$. –  Rasmus Jun 15 '11 at 19:09
Curious, are you encountering this set in proving a monotonic function $F$ on $\mathscr{P}(A)$ has a fixed point? –  yunone Jun 15 '11 at 19:14
I'm not a big fan of that notation because it is ambiguous. I prefer $$\bigcap_{X \subseteq A, F(X)\subseteq X} X$$ –  lhf Jun 15 '11 at 19:21
@lhf: $\bigcap X$ is a very standard notation, just like $\bigcup X$ notation. I do not see what is ambiguous about it, except the case where $X=\emptyset$ which then requires you to specify the formula defining the intersection over $X$ ($\bigcap\emptyset$ could be empty, undefined, or the entire universe - depending on the definition). –  Asaf Karagila Jun 15 '11 at 19:57

Edited. It's unlikely that $F$ is the induced function of a map $F\colon A\to A$, because in that case the given intersection would necessarily be empty. Edited to reflect that.

Okay, presumably you have a set $A$.

Now, remember that whenever you have a set $A$, you also have the power set of $A$, which is a set whose elements are the subsets of $A$. The power set of $A$ is often represented something like $\mathcal{P}(A)$, or $\mathfrak{P}(A)$.

For example, if $A=\{1,2,3\}$, then $$\mathcal{P}(A) = \Bigl\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\Bigr\},$$ because those are exactly the subsets of $A$.

So, what we have is that a set $X$ satisfies $X\in\mathcal{P}(A)$ if and only if it satisfies $X\subseteq A$.

When you write: $$\bigl\{ X\subseteq A\mid \text{...stuff...}\}$$ you are saying that you want to consider those elements of $\mathcal{P}(A)$ which satisfy ...stuff...

You probably also have a function $F\colon\mathcal{P}(A)\to\mathcal{P}(A)$. If $X\in\mathcal{P}(A)$, then $F(X)$ is also a subset of $A$, so it makes sense to ask whether $F(X)\subseteq X$. For example, let's take the $A$ I take above, and define a function $F\colon\mathcal{P}(A)\to\mathcal{P}(A)$ as follows: $$\begin{array}{rcl} \emptyset & \longmapsto & \{1,3\}\\ \{1\} &\longmapsto & \{2\}\\ \{2\} &\longmapsto & \emptyset\\ \{3\} &\longmapsto & \{1,2,3\}\\ \{1,2\} &\longmapsto & \{1\}\\ \{1,3\} &\longmapsto & \{1,2,3\}\\ \{2,3\} &\longmapsto & \{1,3\}\\ \{1,2,3\} & \longmapsto & \{3\}. \end{array}$$

So, suppose we had that $A$ and that $F$. What would be the set $$\Bigl\{ X\subseteq A \mid F(X)\subseteq X\Bigr\}\quad?$$ Looking at the description above, we see that the sets that are mapped to subsets of themselves are: $\{2\}$, $\{1,2\}$, and $\{1,2,3\}$.

Finally, what does it mean to take the intersection of a single set? If $R$ is a set (whose elements are sets), then $\cap R$ is the result of intersecting all the elements of $R$; that is: $$\bigcap R = \Bigl\{ x \mid x\text{ is in }S\text{ for every element }S\in R\Bigr\}.$$ So, for my example above, we would have: \begin{align*} \bigcap\Bigl\{X\subseteq A\mid F(X)\subseteq X\Bigr\} &= \bigcap\Bigl\{ \{2\},\ \{1,2\}\, \{1,2,3\}\Bigr\}\\ &= \{2\}\cap\{1,2\}\cap\{1,2,3\}\\ &= \{2\}. \end{align*}

It's also possible that your $F$ is actually a function $A\to A$. Remember that whenever you have a function $F\colon R\to S$, you automatically get another function $\overline{F}\colon \mathcal{P}(R)\to\mathcal{P}(S)$ (called the "direct image") which is defined by $$\overline{F}(X) = \{ F(x)\mid x\in R\}.$$ (You also get another function, $\underline{F}\colon \mathcal{P}(S)\to\mathcal{P}(R)$, called the "inverse image", which is defined by $$\underline{F}(Y) = \{ x\in R \mid F(x)\in Y\},$$ but this does not matter now). The direct image function is often, by abuse of notation, written just $F$ instead of $\overline{F}$. For example, going back to $A=\{1,2,3\}$, suppose you define $F\colon A\to A$ by $F(1)=2$, $F(2)=2$, and $F(3)=1$. Then the direct image function would have the following values: \begin{align*} F(\emptyset) &= \emptyset,\\ F(\{1\}) &= \{F(1)\} = \{2\}\\ F(\{2\}) &= \{F(2)\} = \{2\}\\ F(\{3\}) &= \{F(3)\} = \{1\}\\ F(\{1,2\}) &= \{F(1),F(2)\} = \{2,2\} = \{2\}\\ F(\{1,3\}) &= \{F(1), F(3)\} = \{2,1\} = \{1,2\}\\ F(\{2,3\}) &= \{F(2),F(3)\} = \{2,1\} = \{1,2\}\\ F(\{1,2,3\}) &= \{F(1),F(2),F(3)\} = \{2,2,1\} = \{1,2\}. \end{align*} In this case, you would have that the set $$\Bigl\{ X\subseteq A\mid F(X)\subseteq X\Bigr\}$$ consists exactly of $\emptyset$, $\{2\}$, $\{1,2\}$, and $\{1,2,3\}$, so that \begin{align*} \bigcap\Bigl\{ X\subseteq A\mid F(X)\subseteq X\Bigr\} &= \bigcap\Bigl\{ \emptyset,\ \{2\},\ \{1,2\},\ \{1,2,3\}\Bigr\}\\ &= \emptyset\cap\{2\}\cap\{1,2\}\cap\{1,2,3\}\\ &=\emptyset. \end{align*}

The reason I don't think (upon reflection) that this is the situation you have is that if your $F$ is the direct image function of some map that goes from $A$ to $A$, then the expression you have will always be the empty set (try to prove that, it's pretty easy).

-
Wow, your quality-to-time ratio is really high at this answer. ;) –  Rasmus Jun 15 '11 at 19:25

I assume $F$ is a function from $A$ to $A$. Rasmus's explanation is correct, the notation $$\bigcap \{X\subseteq A| F(X)\subseteq X\}$$ refers to the intersection (i.e. $\bigcap$) of all subsets $X$ of $A$ (i.e. $X\subseteq A$) such that (this is the symbol $\mid$; see set-builder notation) the image of $X$ under $F$ is contained in $X$ (i.e. $F(X)\subseteq X$).

If $F$ is a function from $A$ to $A$, this set is empty, as $\varnothing\subseteq A$ is a subset of $A$ for which $F(\varnothing)\subseteq\varnothing$.

yunone makes the point in the comments on this post that $F$ might be a function from ${\mathcal P}(A)$ to ${\mathcal P}(A)$. In that case, the notation $$\bigcap \{X\subseteq A| F(X)\subseteq X\}$$ refers to the intersection (i.e. $\bigcap$) of all subsets $X$ of $A$ (i.e. $X\subseteq A$) such that the set $F(X)\subseteq A$ that $F$ sends $X$ to is contained in $X$ (i.e. $F(X)\subseteq X$).

-
How do you know that $F(\emptyset) \subseteq \emptyset$? –  trutheality Jun 15 '11 at 19:15
My guess is $F\colon\mathscr{P}(A)\to\mathscr{P}(A)$, but of course I may be wrong. –  yunone Jun 15 '11 at 19:16
The set of all $a\in A$ such that there exists some $b\in\varnothing$ such that $F(b)=a$ is empty, since there are no $b\in\varnothing$. So $F(\varnothing)=\varnothing$. –  Zev Chonoles Jun 15 '11 at 19:17
@yunone: Good point, that would make more sense. –  Zev Chonoles Jun 15 '11 at 19:19
He said it twice: "if $F$ is a function from $A$ to $A$" Then for subsets $X$ we define $F(X)$ as the set of all $F(x)$ with $x \in X$. And of course then $F(\empty) = \nullset$. –  GEdgar Jun 15 '11 at 19:19

The notation $\bigcap T$, for a non-empty $T$, is the set $\{x\mid \forall a\in T(x\in a)\}$.

That is, all the elements which are in all the elements of $A$ (which are sets themselves).

If $T$ is finite, e.g. $T=\{A,B,C\}$ then $\bigcap T = A\cap B\cap C$. If it is infinite, then it is a bit shorter and clearer to use $\bigcap T$ instead.

In your specific case, it means the intersection of all $X\in\mathcal P(A)$ with a certain property.

-

$$\bigcap \{X\subseteq A| F(X)\subseteq X\}$$

Is the intersection of all sets $X$ such that $X$ is a subset of $A$ and $F(X) \subseteq X$.

So in terms of logic:

$$x \in \left( \bigcap \{X\subseteq A| F(X)\subseteq X\} \right) \Leftrightarrow (\forall X | X \subseteq A \land F(X) \subseteq X )( x \in X )$$

-