Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
1  
What is $F$? $ $ –  Rasmus Jun 15 '11 at 19:08
3  
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
1  
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
1  
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
3  
@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

4 Answers 4

up vote 9 down vote accepted

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

share|improve this answer
2  
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$).

share|improve this answer
    
How do you know that $F(\emptyset) \subseteq \emptyset$? –  trutheality Jun 15 '11 at 19:15
1  
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
1  
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.