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 ?

  • 1
    What is $F$? $ $2011-06-15
  • 3
    In words, it is *the intersection of all subsets $X$ of $A$ fulfilling the condition $F(X)\subseteq X$.*2011-06-15
  • 1
    Curious, are you encountering this set in proving a monotonic function $F$ on $\mathscr{P}(A)$ has a fixed point?2011-06-15
  • 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$$2011-06-15
  • 1
    @user11750 posted less than 30 minutes ago; questions regarding clarification of what F is, the ambiguity of the expression, edits were made that make it difficult to ascertain that meaning, ...and instead of waiting for clarification, we have "if you meant this....then...." on the other hand if you meant this, ....then this...". Another post: but if the user meant this..., then this..... Not to mention repetition in answers... Can there not be a certain degree of restraint in answering until we know what the question actually is? At least give the OP a chance to clarify...2011-06-15
  • 0
    And now...we have edited answers to adjust for "jumping the gun!"2011-06-15
  • 0
    @amWhy: To be honest, it didn't occur to me at first that there was more than one possible meaning; it wasn't until later that the penny dropped. Perhaps I should have deleted instead of adjusting.2011-06-15
  • 0
    No @Arturo: no need for deleting...the efforts at answering do reveal the process of "problem solving": ascertaining the meaning of a question, attempting to define a problem in more familiar terms, adjusting for added information, or "dead ends"...etc. So I'm not asking that answers be deleted: it was perfectly appropriate to indicate changes in an answer by flagging as an "Edit" (I wish more people would modify answers as clarification emerges...so as not to confuse down the road.) I do think, though, just as we ask OPs to "think" (and provide context, clarification, etc) before they ask...2011-06-15
  • 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).2011-06-15
  • 0
    there are times where we may need to show restraint...think through the problem, any ambiguity, ask for clarification, discuss the question in comments, with OP and other users...etc., before "jumping in" with an answer. Arturo is a rare exception in terms of being able to provide really thorough answers in very little time. But most of us (at least me) require a bit of time to formulate a helpful, insightful answer, (and get it typed!) I guess I just worry that competition? gets a little out of hand. Sorry if it seems I'm making a mountain out of a molehill.2011-06-15
  • 0
    Sorry for the lengthy response(s), BTW. Perhaps I should save the concern I raise here for meta.2011-06-15
  • 0
    @Asaf: I interpreted lhf as saying that the set-builder notation following the $\bigcap$ symbol to be confusing, not the use of the $\bigcap$ symbol, itself?2011-06-15
  • 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
    How do you know that $F(\emptyset) \subseteq \emptyset$?2011-06-15
  • 1
    My guess is $F\colon\mathscr{P}(A)\to\mathscr{P}(A)$, but of course I may be wrong.2011-06-15
  • 0
    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$.2011-06-15
  • 0
    @yunone: Good point, that would make more sense.2011-06-15
  • 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$.2011-06-15
  • 0
    Oh, "If $F$ is a function from $A$ to $A$...". Got it. I was guessing more in line with yunone.2011-06-15
  • 0
    @GEdger: `\emptyset` should work.2011-06-15
  • 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 )$$