Show that ¬(∀x∈S:f(x))⇔∃x∈S:¬f(x)\neg(\forall x \in S: f(x)) \Leftrightarrow \exists x \in S: \neg f(x)

SS is a set and f(x)f(x) is an arbitrary statement where x∈Sx \in S

Show that ¬(∀x∈S:f(x))⇔∃x∈S:¬f(x)\neg(\forall x \in S: f(x)) \Leftrightarrow \exists x \in S: \neg f(x).

I planned to solve this by making a truth table. To make a truth table, we somehow have to get its formula. Since we know that ∀x∈S:f(x)⇔f(x1)∧f(x2)∧..∧f(xn)\forall x \in S:f(x) \Leftrightarrow f(x_{1}) \wedge f(x_{2}) \wedge .. \wedge f(x_{n}) and that ∃x∈S:f(x)⇔f(x1)∨f(x2)∨..∨f(xn)\exists x \in S: f(x) \Leftrightarrow f(x_{1}) \vee f(x_{2}) \vee .. \vee f(x_{n}) we will get to this formula:

(¬a∧¬b)⇔¬(a∨b)(\neg a \wedge \neg b) \Leftrightarrow \neg (a \vee b)

And then, simply make a truth table for this..?

Could it be done like that or is there another, better way of doing it?




Assuming SS is a finite set, this could be done (with 22|S|2^{2^|S|}) rows in the truth table.
– Math1000
2 days ago



Wouldn’t it be possible to just make a truth table for the formula above? It would cost you 4 rows and about 7 columns, assuming the formula is correct at all…
– tenepolis
2 days ago


1 Answer


If there are no restrictions on the set SS, then this equivalence cannot be proven using a truth-table, since truth-tables can only handle finite sets. Even if you try something like ∀x∈Sf(x)≡f(x1)∧f(x2)∧…\forall x \in S \: f(x) \equiv f(x_1) \wedge f(x_2) \wedge …, you are already assuming the set to be countable.

So it seems to me this is just a bad question. Once you get to quantificational logic, truth-tables are basically no longer useful.



But how else would you solve this? This makes so much sense that it is almost impossible to prove : /
– tenepolis



@tenepolis You can define a formal semantics for quantificational logic, mathematically defining what it means for quantificational statements to be true. For example, an existential is said to be true is there is an object that satisfies the predicate ff, while for a universal all objects need to satisfy it. So hopw do we now prove that the equivalence holds? Because we say that not all objects satisfy ff iff there is some object that satisfies ¬f\neg f! That is, we do the same thing, but now in math, rather than formal logic. As Tarski said: “Snow is white” is true iff snow is white! Weird
– Bram28
6 hours ago