6

I'm reading the book on Discrete Mathematics by Kevin Ferland. In Section 1.5, he says truth tables are not an option for statements involving universal quantifiers.

It seems to me that a statement such as "$\forall\ x \in \mathcal{U}, p(x)$" is either true or false always. I can think of examples: "Any rational number is real." This is a universal statement, and it is true.

Is it possible to choose a universal set $\mathcal{U}$ and condition $p$ so that "$\forall\ x \in \mathcal{U}, p(x)$" does not evaluate to a logical statement (something that is either true or false, but not both)? If so, can you please give a concrete example? If not, why then can I not create a truth table, and going further, why can't I validate argument forms using the truth table?

As an example, let's try to validate the following argument form using a truth table. \begin{align*} \forall\ x \in \mathcal{U}, p(x)\vee q(x)\\ \forall\ x \in \mathcal{U}, \neg p(x)\\ \therefore, \forall\ x \in \mathcal{U}, q(x) \end{align*}

So, we need to show that whenever the premises are both true, the conclusion is also true. Since it's hard to write $\forall$ in the table, assume each of the columns is preceded by $\forall\ x \in \mathcal{U}$. In other words, each statement is universal.

p(x)  q(x)  p(x) v q(x)  ~p(x)  q(x)
----+-----+------------+------+-----
  T |  T  |    T       |   F  |  T
  T |  F  |    T       |   F  |  F
  F |  T  |    T       |   T  |  T
  F |  F  |    F       |   T  |  F

Now, whenever the premises are both true, the conclusion is true. So one would think that the argument form is valid. And indeed, it is valid. You can certainly use universal instantiation and proofs of basic argument forms (which CAN be validated with truth tables) to show that the argument form is valid. This is the way that makes sense to me.

What confuses me is why is the above method flawed? (In general).

Any explicit examples you can give me would greatly help! Thanks in advance.

gnat79
  • 61
  • 2
    How does your truth table method distinguish between $(\forall x\in\mathcal U),\neg p(x)$ and $\neg(\forall x\in\mathcal U), p(x)$? – Andreas Blass Sep 23 '13 at 20:52
  • Since it's not easy to write all that in the way I formed the table, let's just say $\neg p(x)$ means $\forall\ x \in \mathcal{U}, \neg p(x)$. – gnat79 Sep 23 '13 at 21:15
  • @gnat79 What rules are you applying to get the third column? Note that once you add universal quantifiers, the disjunction won't work the same way.- – Git Gud Sep 23 '13 at 21:15
  • Git Gud, can you explain why they don't work the same way? I think you are getting at the problem I'm having. – gnat79 Sep 23 '13 at 21:17
  • 2
    Let $\mathcal U=\Bbb R$ and for all $x\in \mathcal U$ let $p(x)$ mean $x\leq 0$ and $q(x)$ mean $x>0$. The third column corresponds to $\forall x\in \Bbb R(x\leq 0\lor x>0)$ which is a logical truth (something which is always true). However $\forall x\in \Bbb R(x\leq 0)\lor \forall x\in \Bbb R(x>0)$ isn't true, in fact it's false, because clearly each of the atoms is false. I really dislike what I'm saying because this isn't propositional calculus, you can't just give truth values to statements as you wish. They have truth values on their own. I'm just trying to convince you it doesn't work. – Git Gud Sep 23 '13 at 21:19
  • @Git Thank you for the concrete example. I can see what you mean now. – gnat79 Sep 23 '13 at 21:56

3 Answers3

3

Suppose $\mathcal{U}$ was some arbitrary set of infinite cardinality.

I think the issue that the book is touching on is that for some arbitrary statement containing a universal quantifier (like $\forall x \in \mathcal{U} \ p(x)$), although it does have a truth value, you cannot use a truth table to find that value directly by testing all values of $x$. (since you would have to have an infinitely large table to get all of the cases)

What made your example doable with a truth table was that in that particular case, you did not have to consider every possible $x$ (which could be infinite), you only needed to care about $p(x), q(x), p(x) \vee q(x)$, which can only take on finitely many values.

Dennis Meng
  • 1,397
  • Thanks. I don't see how it matters how you test the statement. Even if you need infinitely many values of $x$ to test it (which I agree, you do), it is still either true or false universally. I think... Of course, that depends on the universe, but once you pick it, and assuming you are super human, you can determine it. So no matter what, (and depending on the universe), you can always determine the truth value of the statement.

    With my truth table, I don't mean "fix a particular $x$", I mean the statements to be universal. I was not clear about that.

     – gnat79 Sep 23 '13 at 21:15
  • "Of course, that depends on the universe, but once you pick it, and assuming you are super human, you can determine it." 1) You still haven't stated how that determination process would go and 2) we're not super human, so why bother pretending we are? – Dennis Meng Sep 23 '13 at 21:24
  • "With my truth table, I don't mean "fix a particular x", I mean the statements to be universal. I was not clear about that." I never said fix a particular $x$. What I was pointing out is that you took a set of infinite cardinality, and in that instance can boil it down into a finite number of cases. That's not something that is a possibility in the general case. – Dennis Meng Sep 23 '13 at 21:27
  • It doesn't seem to me that the number of things in the set affects the truth value of the statement, even if it is a universal statement. If there is a particular $x$ so that $p(x)$ is not true, then the statement $\forall x \in \mathcal{U}, p(x)$ is false. On the other hand, no matter the cardinality of $\mathcal{U}$, if all $x \in \mathcal{U}$ make $p(x)$ true, then the statement $\forall\ x \in \mathcal{U}, p(x)$ is true. I appreciate your efforts; unfortunately this isn't sinking in for me. It seems I'm missing a subtlety. – gnat79 Sep 23 '13 at 21:43
  • The number of things in the set doesn't affect whether or not the statement can be true or false; but it does affect how the heck you can find out. If the set is finite, you can just test for every member of the set. Such a method doesn't work if the set has an infinite number of elements. – Dennis Meng Sep 23 '13 at 21:45
  • How this applies to truth tables is that barring some other statement that makes evaluation much simpler, you can't avoid having to test every member of the set. – Dennis Meng Sep 23 '13 at 21:46
0

The only problem I see with this is that it seems you might think it's okay for $\mathcal{U}$ to be the universe. Are you in fact saying that? What do you mean by a "universal set?" If instead $\mathcal{U}$ is some other set guaranteed by the axioms of ZFC, then the axiom of specification guarantees that for any formula $p$ there exists a set $S=\{x\in\mathcal{U}\mid p(x)\}$. It is then either true or false that $S=\mathcal{U}$, and the trueness or falsehood if this equation is equivalent to that of your statement $\forall x\in\mathcal{U}:p(x)$.

Upon making the desired truth table then, we are merely considering the truth values that result from varying $p$ and $q$, not from varying $x$. This puts us in exactly the same situation as we would be for an ordinary truth table, thus I don't see any problem. You just have to write it correctly.

j0equ1nn
  • 3,429
0

Remember that FOL is stronger than propositional logic. Ie. there are statements in FOL that can not be expressed in propositional logic. Your statement is not one of these.

Consider \begin{align*} \forall\ x \in \mathcal{U}, p(x)\vee q(x)\\ \neg p(a)\vee\forall\ x\in\mathcal{U}, q(x)\\ \therefore q(a) \end{align*}

What does your thruth table look like?

Taemyr
  • 528