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.

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$?

share|improve this question
1  
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
1  
I think this is irrelevant. Let's just assume $C$ is some fixed set. –  par Sep 4 '13 at 0:21

4 Answers 4

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

share|improve this answer

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

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

share|improve this answer

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

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.