# What does $\forall a \in A \exists b \in B(b \in C \rightarrow a \in C)$ mean?

What does $\forall a \in A \exists b \in B(b \in C \rightarrow a \in C)$ mean?

I know it means that for all $a$ in $A$ there exists a $b$ in $B$ such that $b$ in $C$ implies $a$ in $C$, but what does that mean intuitively, because to me the interaction between the $\exists$ and the implication doesn't make any sense. It seems to be saying that there exists a $b$ in $B$ and if that $b$ happens to be in $C$, then it implies that $A \subseteq C$? Does it means that the entire set of $A$ is that one element of $B$ and it's also in $C$?

-
Do you mean to have $\forall C$ to left of $\forall a\in A$? Without quantifying $C$, the formula you're asking about doesn't mean anything. –  Git Gud Sep 4 '13 at 0:15
What would $\forall C$ mean? –  Matt Gregory Sep 4 '13 at 0:17
Usually we're within $\sf ZFC$ in which everything is a set. So $\forall C$ means for any set $C$. An informal of way of addressing this is: $$\quad$$ Let $C$ be a set. What does $\forall a \in A \exists b \in B(b \in C \rightarrow a \in C)$ mean? (I hope I am not confusing you further). Edit: and of course the same has to be said for $A$ and $B$ too. –  Git Gud Sep 4 '13 at 0:19
Yeah, I think that's understood. A, B, and C are arbitrary sets. –  Matt Gregory Sep 4 '13 at 0:20
I think this is irrelevant. Let's just assume $C$ is some fixed set. –  par Sep 4 '13 at 0:21

It is probably easiest to understand this by using the rule that $P\to Q$ means the same as $\neg P\lor Q$. So what we have here is

$$\forall a\in A. \exists b \in B. (b\notin C \lor a \in C)$$

Now, let's consider the subformula $\exists b \in B. (b\notin C \lor a \in C)$. It should be clear that if there is a $b$ such that $b\notin C$, then this is true no matter what $a$ is. On the other hand, if $a\in C$, then it is true if only $B$ contains some $b$. So this is equivalent to $(\exists b\in B. b\notin C) \lor (B\neq \varnothing \land a \in C)$. So we have

$\forall a \in A. \bigl( (\exists b\in B. b\notin C) \lor (B\neq \varnothing \land a \in C)\bigr)$

Now again this is certainly true if $\exists b\in B. b\notin C$ is. Otherwise we must have $B\neq\varnothing$ and $a\in C$ for all $a\in A$. So it is equivalent to

$$(\exists b\in B. b\notin C) \lor (B \neq \varnothing \land \forall a\in A. a\in C)$$

We can rewrite that to use set algebra instead of logic, so see that what the original formula "really" means is

$$B\setminus C \neq \varnothing \lor (B \neq \varnothing \land A\subseteq C)$$

-

Note that $b\in C\to a\in C$ is equivalent to $b\notin C\lor a\in C$. Thus, it says that there is a function $f:A\to B$ with the following property:

for each $a\in A$, either $f(a)\notin C$, or $a\in C$.

If $A\subseteq C$, this is guaranteed to be the case provided that $B\ne\varnothing$: we can pick any $b_0\in B$ and let $f(a)=b_0$ for each $a\in A$.

If $A\nsubseteq C$, fix $a_0\in A\setminus C$. In order for the highlighted statement to be true, we must be able to define $f(a_0)\in B$ in such a way that $f(a_0)\notin C$, which means that $B\setminus C$ must be non-empty. Conversely, if there is a $b_0\in B\setminus C$, we may let $f(a)=b_0$ for all $a\in A$, and this $f$ will have the desired property.

All of this boils down to saying that the statement is true if and only if $B\ne\varnothing$, and either $A\subseteq C$ or $B\nsubseteq C$.

-
In your last sentence you seem to have lost the "provided $B\neq \varnothing$" for the $A\subseteq C$ case. –  Henning Makholm Sep 4 '13 at 0:32
@Henning: So I did; thanks. (And it comes for free with the other case, so I might as well just make it an independent conjunct). –  Brian M. Scott Sep 4 '13 at 0:34
Wow, you blew my mind when you said it says there's a function. I need a minute to mull that over. –  Matt Gregory Sep 4 '13 at 0:43
@Matt: That’s just putting $\forall a\in A\exists b\in B$ into what may be more familiar terms. For each $a\in A$ there is some $b\in B$ with a certain property; I could call it $b_a$ to specify that it’s a chosen $b$ that ‘works’ for that $a$, but I chose instead to call it $f(a)$. –  Brian M. Scott Sep 4 '13 at 0:45
But actually it's not quite a function because there could be more than one $b$ that qualifies, right? In other words $\exists$ means there is at least one. –  Matt Gregory Sep 4 '13 at 0:47

Perhaps it is more illuminating to look at it written in the following form:

$$\forall_{a\in A}\left(\exists_{b\in B}\left(b\in C\implies a\in C\right)\right)$$

In this way, you can think of $\forall_{a\in A}$ as an operator acting on the stuff in the brackets. Like all other boolean operators, it will return truth or falsehood. A similar analogy holds for $\exists_{b\in B}$. Consider the following:

$$\forall_{a\in A}\left(p\left(a\right)\right)$$

Here, $p\colon A \rightarrow \left\{0,1\right\}$ is just a proposition: it maps elements of $A$ to true ($1$) or false ($0$). Concretely, if we assume as a means to an example that $A=\left\{a_1,a_2,\ldots,a_n\right\}$, we would have

$$\forall_{a\in A}\left(p\left(a\right)\right) = p\left(a_1\right) \wedge p\left(a_2\right) \wedge \ldots \wedge p\left(a_n\right)$$

where $\wedge$ is the and operator. Hope that helps.

All this having been said, the subscript notation is used almost nowhere, although it has the advantage of being unambiguous.

Edit: Here is an example with existence assuming $A$ is finite as before:

$$\exists_{a\in A}\left(p\left(a\right)\right) = p\left(a_1\right) \vee p\left(a_2\right) \vee \ldots \vee p\left(a_n\right)$$

where $\vee$ is the or operator.

Relation to your original problem: This doesn't imply that $A\subseteq C$. For example, take $A=\left\{a\right\}$ and $B = \left\{b\right\}$ and $C = \emptyset$. Then, clearly, the proposition is satisfied trivially, but $A$ is not a subset of $C$.

-

What does $\forall a \in A \exists b \in B(b \in C \rightarrow a \in C)$ mean?

I know it means that for all $a$ in $A$ there exists a $b$ in $B$ such that $b$ in $C$ implies $a$ in $C$, but what does that mean intuitively, because to me the interaction between the $\exists$ and the implication doesn't make any sense. It seems to be saying that there exists a $b$ in $B$ and if that $b$ happens to be in $C$, then it implies that $A \subseteq C$? Does it means that the entire set of $A$ is that one element of $B$ and it's also in $C$?

There is no suggestion here that $A \subseteq C$, or equivalently that $\forall a( a\in A\rightarrow a\in C)$.

Suppose $p\in A$. Then it follows that

$\exists b\in B(b\in C \rightarrow p\in C)$

or equivalently

$\exists b (b\in B\land(b\notin C \lor p\in C))$.

It does not necessarily follow that $p\in C$.

-