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 : /

=================

1

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

1

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

1

“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

=================

=================