4
$\begingroup$

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 ?

  • 0
    @amWhy: There are two notations here: $\bigcap X$ to denote the intersection of all the _elements_ of $X$ when $X$ is a set of sets, and $\bigcap_{X|condition} X$ to denote the intersection of all $X$ that satisfy the condition.2011-06-15

4 Answers 4

9

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

  • 2
    Wow, your quality-to-time ratio is really high at this answer. ;)2011-06-15
2

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

  • 0
    emptyset $\emptyset$ varnothing $\varnothing$2011-06-15
1

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.

0

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