Why am I obtaining $ \neg \forall x A(x) \equiv \forall x\neg A(x)$?

Question

Here is the proof of the theorem $$ \neg (\forall x) A(x) \equiv (\exists x)\neg A(x) $$ Proof:
Let the universe of discourse be $U$.
The sentence $ \neg (\forall x) A(x)$ is true in $U$
$\implies (\forall x) A(x)$ is false in $U$
$\implies$ the truth set of $ A(x)$ is not the universe $U$
$\implies$ the truth set of $ \neg A(x)$ is non-empty
$\implies$ $(\exists x)\neg A(x) $ is true in $U$.

I'm confused about the third implication "the truth set of $ \neg A(x)$ is non-empty". Because, if we imagine that $A(x) = \text{$x$ is God}$ and $U=\{\text{Human}\},$ then doesn't "the truth set of $ A(x)$ is not the universe $U$" imply that the negation "$x$ is not god" is true for Human and that the truth set of $ \neg A(x) $ is $U$ ?

If this is the case, then the fourth implication should be "$(\forall x)\neg A(x) $ is true in $U$", which ultimately leads to the relation $$ \neg (\forall x) A(x) \equiv (\forall x)\neg A(x).$$ But the theorem says something else. What am I missing here?

Answer 1

While $¬(\forall x)A(x)$ holds with your example, you actually chose an A(x) which is a special case of this, where $¬(\exists x)A(x)$ as well, which, after applying the negation, is in fact the expression you gave at the end. Try a more general example like A(x) = x is red, and you'll find what you want.

Answer 2

What you're missing is the

if we imagine

part you wrote. Because if we suppose that the truth set of $A(x)$ is the empty set, then yes, we get that $\neg A(x)$ corresponds to $U$ and hence a stronger implication. But in general, and the general case is the one we must assume in the proof, we can have that $A \neq U$ but still $A \neq \emptyset$, so the truth set of $\neg A(x)$ is only non-empty and not all of the universe, and thus we only get $(∃x) \ldots$ and not $(\forall x) \ldots$.

---

Edit:

The use of $\Rightarrow$ instead of $\Leftrightarrow$ that was pointed out in a comment actually highlights the source of the confusion here. The point is that it is not just a difference in symbols that can be ignored as you said.

To prove an equivalence $\equiv$ we find a chain of conversion steps that each apply in both directions, $\Leftrightarrow$, so that we can read the proof backwards and it still works. In the proof you showed, every conversion step also holds from the lower line to the upper line, so we have not only $\Rightarrow$ but $\Leftrightarrow$, and that is what we need for a proof of equivalence. If we don't have $\Leftrightarrow$ all the way through, we didn't show equivalence, we only showed logical implication.

For comparison, for your other formula, we have

The sentence ¬(∀x)A(x) is true in U
⇔ (∀x)A(x) is false in U
⇔ the truth set of A(x) is not the universe U
⇔ the truth set of ¬A(x) is non-empty
⇐ the truth set of ¬A(x) is the universe
⇔ (∀x)¬A(x) is true in U.

Note how the second-to-last step only works in the direction from the lower line to the upper line: If the truth set of $\neg A(x)$ is the universe, then it is also non-empty. The above is a proof that $\forall x \neg A(x)$ logically implies $\neg \forall x A(x)$; i.e. in the special case where $A$ holds for none of the elements from the universe, its truth set is not the universe.

But the second-to-last step does not work in the direction from the upper line to the lower line, because "non-empty" does not imply "the universe". So we don't have a chain of $\Leftrightarrow$'s, and that's why these formulas are not equivalent: ¬(∀x)A(x) $\not \equiv$ (∀x)¬A(x).

Answer 3

$$ \neg \forall x A(x) \quad\equiv\quad \exists x\neg A(x) \tag1$$ Proof:

This is orthogonal to the discussion, but it's worth noting that your excerpt does not show the other half/direction of the full proof.

the truth set of $ A(x)$ is not the universe $U$
$\implies$ the truth set of $ \neg A(x)$ is non-empty

if we imagine that $A(x) = \text{$x$ is God}$ and $U=\{\text{Human}\},$

then doesn't the above antecedent imply that "$x$ is not god" is true for Human? In other words, doesn't the above antecedent imply that the truth set of $ \neg A(x) $ is in fact $U$ ?

This is all true. You gave a particular example (a special case) that the above antedecent applies to, and derived a conclusion that does not actually contradict the above consequent. No issue here.

This ultimately leads to the relation $$\neg \forall x A(x) \quad\equiv\quad \forall x\neg A(x).\tag2$$ But the theorem says something else. What am I missing here?

No, you have not arrived at the logical equivalence $(2),$ nor even demonstrated that $$\neg \forall x A(x) \quad\to\quad \forall x\neg A(x)\tag3$$ is logically true (that is, true for every possible scenario). For your single-member-universe example, $\forall x\neg A(x)$ and $\neg \forall x A(x)$ and $\exists x\neg A(x)$ are actually equivalent to one another; so, in this interpretation, sentence $(3)$ is indeed true and does not contradict theorem $(1).$ However, it does not follow that sentence $(3)$ is true regardless of interpretation; in other words, it does not follow that sentence $(3)$ is a logical implication/validity.

---

Reply to comment

Can I say then that $$¬∀xA(x)≡∃x¬A(x)≡∀x¬A(x)$$

No: the counterexample $A(x):=x$ is even, where the universe is $\mathbb Z,$ shows that $¬∀xA(x)$ isn't logically equivalent (≡) to $∀x¬A(x).$ However, it is correct to assert these equivalences:

• when the universe is {Human} and $A(x)$ is defined as “$x$ is God”, $$¬∀xA(x)\leftrightarrow ∃x¬A(x)\leftrightarrow ∀x¬A(x);$$
• in real analysis (but not in complex analysis), $$\forall x\,(x^3=1\leftrightarrow x=1).$$

Answer 4

I am not familiar with your "truth sets," etc. but it may help to incorporate your universe as a predicate $U(x)$ as follows:

---

(Plain text version)

1   ~ALL(x):[U(x) => A(x)]
    Premise

2   ~~EXIST(x):~[U(x) => A(x)]
    Quant, 1

3   EXIST(x):~[U(x) => A(x)]
    Rem DNeg, 2

4   EXIST(x):~~[U(x) & ~A(x)]
    Imply-And, 3

5   EXIST(x):[U(x) & ~A(x)]
    Rem DNeg, 4

6 ~ALL(x):[U(x) => A(x)] => EXIST(x):[U(x) & ~A(x)] Conclusion, 1