2

enter image description here

I am trying to learn set theory on my own .. and the book introduced these suppositions I understand all of them except for the last one that converts the existential quantifier into the universal quantifier .. I understand what universal, existential quantifiers and negation mean .. so I understand that the conversion of one equals some form of negation of the other .. what I don’t understand though is the negation in front of the formula on the far right .. is it necessary ? why is it there ? What does it mean ? What does the whole sentence mean in this exact form ?

Thanks in advance

A. S.
  • 107
  • 2
    As long as you know that for any $P$, $\lnot(\forall x P(x))$ is equivalent to $\exists x\lnot P(x)$, and vice versa, the last line should be obvious by letting $\lnot\Phi=P$. – Rushabh Mehta Oct 14 '21 at 18:21
  • @DonThousand yea that makes sense .. thanks – A. S. Oct 14 '21 at 18:28
  • 3
    "Something makes the statement true" and "it's not the case that everything makes the statement false" are the same. – Charles Hudgins Oct 15 '21 at 03:45

2 Answers2

2

Reading the sentences $\quad\lnot\forall v\:\,\lnot\phi\quad$ and $\quad\exists v\:\, \phi\quad$ literally:

  • It is false that every $v$ fails to satisfy $\phi.$

  • There is some $v$ that satisfies $\phi.$

Does this clarify their logical equivalence?

ryang
  • 38,879
  • 14
  • 81
  • 179
1

To see what's going on here let's work with a concrete example. To do that we need to assign meaning with an interpretation, $\mathscr{I}$.

$\begin{array}{lrl}\mathscr{I}:&&\\ &\text{Domain:}&\text{{Alison, Bob, Craig}}\\ &\text{F:}&\ldots~\text{is a logician}\\ &\text{a:}&\text{Alison}\\ &\text{b:}&\text{Bob}\\ &\text{c:}&\text{Craig}\\ \end{array}$

Next, we need to know what it means for the formulas $\exists x[Fx]$ and $\forall x[Fx]$ to be true.

$\exists x[Fx]$ is true if, and only if, at least one member of the domain is an $F$. In other words, the formula is true if, and only if, Alison or Bob or Craig is a logician, in the inclusive sense of "or". Symbolically, we could represent that as $(Fa\lor Fb)\lor Fc$.

$\forall x[Fx]$ is true if, and only if, all members of the domain are an $F$. In other words, the formula is true if, and only if, Alison and Bob and Craig are logicians. Symbolically, that becomes $(Fa\land Fb)\land Fc$.

We can think of $\exists x[\dots]$ as disjunction, $\lor$, and $\forall x[\dots]$ as conjunction, $\land$. With that in mind, it's quite intuitive why $\exists x[Fx]=\lnot(\forall x[\lnot Fx])$.

Let's say $\exists x [Fx]$ is true. That means that someone is a logician. Consider the formula $\forall x[\lnot Fx]$ - can it be true at the same time? If someone is a logician, can we also claim that no one is a logician? No, that would be a contradiction. Hence, $\lnot\forall x[\lnot Fx]$ - it is not the case that no one is a logician. Symbolically, given $(Fa\lor Fb)\lor Fc$ is true $(\lnot Fa\land \lnot Fb)\land\lnot Fc$ is a contradiction, hence, $\lnot((\lnot Fa\land \lnot Fb)\land\lnot Fc)$, which is simply Double Negation and De Morgan's - $(P\lor Q)=\lnot\lnot(P\lor Q)=\lnot(\lnot P\land \lnot Q)=(\lnot\lnot P\lor\lnot\lnot Q).$

Ten O'Four
  • 1,056