Proof that ∀x∈Ω:¬a(x)⇔¬(∃x∈Ω:a(x))\forall x \in \Omega: \neg a(x) \Leftrightarrow \neg(\exists x \in \Omega: a(x))

Let Ω\Omega be a set and a(x)a(x) any statement about x∈Ωx \in \Omega.
Proof that

∀x∈Ω:¬a(x)⇔¬(∃x∈Ω:a(x))\forall x \in \Omega: \neg a(x) \Leftrightarrow \neg(\exists x \in
\Omega: a(x))

I think there is no way in proving this without giving an example or describing, right?

I tried:

What the left side is saying is that for all x in the set omega, we have that “not a(x)”.

This is equivalent to: There does not exist an x in the set omega so that we have a(x).

That’s what the task is saying in maths language.

So left side: No matter (=all) what x we choose, we will always get “not a(x)”.

Right side: There doesn’t exist an x to get a(x).

This is really the same but how can you prove this? This is very frustrating task because it makes sense but you cannot prove it / prove it easily : /




This is pretty straightforward. Assume first the LHS is true and the parenthesised part of the RHS as well (to go for a contradiction), and you easily deduce a contradiction. Also assuming the RHS and taking an arbitrary x∈Ωx\in\Omega, the assumption a(x)a(x) easily leads to a contradiction, so it must be false.Since xx was arbitrary, you get that conclusion for all xx.
– Marc van Leeuwen
Oct 20 at 17:20



This is the quantified version of DeMorgan’s Law.
– Gabriel Burns
Oct 20 at 17:23



Are you allowed to use the negation of \forall quantifier? If not, you can show the \Leftarrow quite easily, for \Rightarrow just assume \exists x \in \Omega: a(x) to be true and arrive at a contradiction. Then by the CTR rule, you derive FALSE which means your assumption must be true.
– bat_of_doom
Oct 20 at 17:24



You can prove ¬(p∧q)↔¬p∨¬q\neg ( p \wedge q) \leftrightarrow \neg p \vee \neg q using a truth table. Since, by definition, ∀x∈Ω:a(x)↔a(x1)∧a(x2)∧…a(xn)\forall {x \in \Omega}: a(x) \leftrightarrow a(x_1) \wedge a(x_2) \wedge \dots a(x_n) and ∃x∈Ω:a(x)↔a(x1)∨a(x2)∨…a(xn)\exists {x \in \Omega}: a(x) \leftrightarrow a(x_1) \vee a(x_2) \vee \dots a(x_n) where the xix_i are precisely the elements of Ω\Omega, the formula follows.
– Gabriel Burns
Oct 20 at 17:35



“aa is always false if and only if aa is never true”. This is a trivial result, it is meaningless to ask for a proof unless you specify a logic.
– DanielV
2 days ago