in Mathematical Logic edited by
15,569 views
113 votes
113 votes

Consider the following formula and its two interpretations \(I_1\) and \(I_2\).

\(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]\)

\(I_1\) : Domain: the set of natural numbers

\(P_x\) =  '$x$ is a prime number'

\(Q_{xy}\) = '$y$ divides $x$'

\(I_2\) : same as \(I_1\) except that \(P_x\) = '$x$ is a composite number'.

Which of the following statements is true?

  1. \(I_1\) satisfies \(\alpha\), \(I_2\) does not
  2. \(I_2\) satisfies \(\alpha\), \(I_1\) does not
  3. Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
  4. Both \(I_1\) and \(I_2\) satisfies \(\alpha\)
in Mathematical Logic edited by
15.6k views

4 Comments

The easiest and fastest way to solve the questions involving implications $(\rightarrow)$ is to start with $RHS$

In this question, $α: \forall x [P_x \leftrightarrow \forall y (Q_{xy} \leftrightarrow Q_{yy}’)] \rightarrow \forall x P_x’ $

Here, $RHS =\forall x P_x’$ is always true,

$\therefore$ the formula is valid.

Hence, it does not matter what the $LHS$ has.

2
2

@strawberry-jam How can RHS be true? It says, “for any natural no. x, x is not prime”. How can it be true? RHS is False, because there are natural nos. that are prime.

2
2
in the second step, you took the not of whole LHS to be true, but you can only do that in case of biconditional operators only!
0
0

6 Answers

304 votes
304 votes
Best answer

Given: $(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right])\\$
$Q_{yy}$ is always True, this makes  $\neg Q_{yy}$ False.

Writing $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]$ is same as writing $(\forall y)[Q_{xy} \Leftrightarrow \text{False}]]$

This is equivalent to saying that, for all y $Q_{xy}$ is false and finally we can rewrite $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]]$ as $(\forall y)[\neg Q_{xy}]$

$\alpha : (\forall \mathbf{x)[P_x \Leftrightarrow (\forall y)[ \neg Q_{xy}]] } \Rightarrow (\forall x)[\neg P_x]$

$\text{LHS}:(\forall x)[ P_x ⇔(\forall y)[\neg Q_{xy}]]$

consider only $(\forall \mathbf{y)[\neg Q_{xy}]}$ it says all values of $y$ does not divide $x$, but there will be at least one value of $y$ (when $y=x$, or when $y=1$) that divides $x$, i.e. $\mathbf{[\neg Q_{xy}]}$ is not true for all values of $y$.  $(∀ \mathbf{y)[¬Q_{xy}]}$ is false.

Now LHS becomes $(∀x)[P_x \Leftrightarrow \text{False}]$, "$P_x \Leftrightarrow \text{False}$" this means $P_x$ is False, which is same as writing "$ \neg P_x$".

Finally, we reduced LHS to $(∀x)[\neg P_x]$

$α: (∀\mathbf{x)[¬P_x]}⇒(∀x)[¬P_x]$  (which is trivial, $P(x)⇒ P(x)$ is trivially true)

Hence $(∀\mathbf{x)[¬P_x]}⇒(∀x)[¬P_x]$  is trivially true for any $P(x)$, doesn't matter if $P(x)$ is for prime number or for composite number $(I1$ or $I2)$.

$ ⇒ I1$ and $I2$ both satisfies $α$.

Option D.

edited by

4 Comments

@ankit3009 Yes you are correct, Qyy means y divides y(Which is always true for Natural numbers).

1
1
this solution is so beautiful
0
0
wht an explanation!!!
0
0
61 votes
61 votes

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

This is can be interpreted as:

  • $\alpha: \left( (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \right) \Rightarrow \left((\forall x)\left[\neg P_x\right] \right)$

See the RHS. It says $P(x)$ is false for any natural number. But there are natural numbers which are prime and hence this RHS is FALSE. Now, to make $\alpha$ TRUE, LHS must be FALSE for any $x$. Here, LHS is bit complex, so lets consider it separately. 

$ (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] $

LHS is TRUE only if the given implication is TRUE for all $x$. Here the rightmost double implication $(\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]$ is always FALSE, because $x$ can be equal to $y$ and hence forall can never be TRUE. So the LHS reduces to just $(\forall x) \neg P(x)$ and returns FALSE as we have prime as well as non-prime natural numbers. So, FALSE $\Rightarrow$ FALSE returns TRUE making both $I_1$ and $I_2$ satisfy $\alpha$. D choice. 

edited by
by

4 Comments

(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]

Now [Qxy⇔¬Qyy] becomes false as mentioned in answer.

(∀x)[Px⇔(∀y)[False]]

(∀x)[Px⇔[False]]

(∀x)[¬Px]

Please tell if i am wrong
1
1

@rahul sharma 5 correct !

0
0
Hi @Arjun sir

just one doubt
 when it says p(x): x is a prime number
 α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

then, in that (∀x) does that means x itself is a set of prime numbers and for all x quantifier is going to pick every prime number value from the set

when it says p(x): x is a composite number
 α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

then, in that (∀x) does that means x itself is a set of composite  numbers and for all x quantifier is going to pick every composite number value from the set

and the domain of Y:{set of all  natural numbers}
0
0
3 votes
3 votes

all logic concept is based on $T\rightarrow F$ .

1st let's see for $I_{2}$

If we somehow make a combination such that the implication will false, then we're done.

Now we have only one way to make an implication false, which is $T\rightarrow F$ combination.

If the domain is composite(means not prime) then right side of the $\alpha$ is always T, which implies we can't make $\alpha$ false.    $P_{x} = F$   i.e    $\sim P_{x} = T$ always.

So, $I_{2}$ satisfies $\alpha$.

 

Now, let's come in $I_{1}$

In $I_{1}$,  $\sim {Q_{yy}}$ is always false because in any circumstances y divides y.

now, try to make $T\rightarrow F$ combination.

let's forget about quantifiers & treat $\alpha$ as $[P_{x} \Leftrightarrow [Q_{xy}\Leftrightarrow Q_{yy}]] \rightarrow \sim P_{x}$.

take $P_{13}$, RHS is F.  LHS is $[P_{13} \Leftrightarrow [Q_{13.1}\Leftrightarrow Q_{1.1}]]$

So, $[P_{13} \Leftrightarrow [T\Leftrightarrow F]]$

$[P_{13} \Leftrightarrow F]$  = $F$, which means $F\rightarrow F$ implies T

So, using any number(composite or prime), we can't make the implication false.

So, $I_{1}$ also satisfies $\alpha$.

Option D is the answer.

 

 

0 votes
0 votes

Counter Example for I1 case :

X={11,121 }

Y={11}

 

Counter Example for I2 case :

X={4,6,2}

Y={2}

 

option D

2 Comments

Can you explain your with a few more words please?
0
0
Can someone explain how this counter example is working?
0
0
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true