0
$\begingroup$

$S$ is a set and $f(x)$ is an arbitrary statement where $x \in S$

Show that $\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 $\forall x \in S:f(x) \Leftrightarrow f(x_{1}) \wedge f(x_{2}) \wedge .. \wedge f(x_{n})$ and that $\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:

$$(\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?

$\endgroup$
2
  • $\begingroup$ Assuming $S$ is a finite set, this could be done (with $2^{2^|S|}$) rows in the truth table. $\endgroup$ – Math1000 Oct 21 '16 at 16:00
  • $\begingroup$ 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... $\endgroup$ – tenepolis Oct 21 '16 at 16:19
1
$\begingroup$

If there are no restrictions on the set $S$, then this equivalence cannot be proven using a truth-table, since truth-tables can only handle finite sets. Even if you try something like $\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.

$\endgroup$
2
  • $\begingroup$ But how else would you solve this? This makes so much sense that it is almost impossible to prove : / $\endgroup$ – tenepolis Oct 22 '16 at 20:25
  • 1
    $\begingroup$ @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 $f$, 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 $f$ iff there is some object that satisfies $\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 $\endgroup$ – Bram28 Oct 23 '16 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.