Are these statements are logically equivalent? If so, how can I prove their equivalence?

47 Views Asked by At

Let U = {t,u,v,w,x,y,z}, Let A = {w,x,y,z} and Let B = {y,z}.

$$ (\forall u \in U, u \in B \rightarrow u \in A) \leftrightarrow (\forall b \in B, b \in A) $$

I was. trying to translate the statement "All elements of B are elements of A" and came up with those two statements? Which one, if not both, would be a correct translation?

For reference I'm in an introductory computer science class.

Edit: "All elements of B are elements of A" was originally "All elements of B are elements of B"

1

There are 1 best solutions below

0
On

Traditionally $U$ means the universal set which is all elements that can be considered and all sets we will consider will be subsets of $U$. If so, then $A$ and $B$ must be subsets of $U$ and and all elements are in $U$.

I don't know if that is the case here. It is true that $A$ and $B$ are both subsets of $U$ and so it's very likely the author is intending $U$ to be the universal set.

If so:

Then $\forall u \in U$ goes without saying. There is nothing but elements in $U$. So "$\forall u \in U, Q$" is just the same thing as saying "$Q$".

And $u \in B \to P$ which means "if $u\in B$ then $P$" which is equivalent to "forall $u \in B, P$. So $u\in B\to u\in A$ is equivalent to $\forall u\in B, u \in A$.

And obviously switching a variable from "$u$" to "$b$" doesn't make any difference.

So yes, $\forall u \in U, u\in B\to u \in A$ is equivalent to $\forall b \in B, b\in A$.

(And both are equivalent, indeed are the definition of, $B \subset A$)

BUT that is assuming $U$ is meant to be the universal set.

If $U$ is just any old set, then $\forall u \in U, u\in B\to Q$ only applies to the $u\in U$> So this is "for all $u \in U$ if $u \in B$ as well then..." would be equivalent to either "$\forall u\in U\cap B, P$ or $u \in U\cap B \to P$.

So the LHS is saying $\forall u\in (B\cap U), u \in A$ (or in other words $(U\cap B) \subset A$ and the RHS is saying $\forall u\in B, u \in A$ (or in other words $B \subset A$).

These are not equivalent.

But in this case they are both true even if they are not equivalent[*].

There are true because $B\subset U$ so $U\cap B = B$. If we were to consider that $U$ were a universal set then $U\cap B = B$ and $B\subset U$ would go without saying and wouldn't need to be pointed out.

=====

[*] No, both being true does not mean they are equivalent. $n$ is a perfect square if $n = 9$. And $n$ is an odd number if $n=9$. But $n$ is a perfect is a completely different statement than $n$ is odd, even though they are both true for $n =9$.