1
$\begingroup$

I am stuck at this problem.

Build an infinite set $\Sigma$ of logical expression (I.e. strings of the form $(P\land Q)$ or $\lnot(P\lor \lnot (Q\land R))$ etc.).

That satisfies the following two properties:

(1) for all $\alpha,\beta\in\Sigma$, $\alpha \Rightarrow \beta$ or $\beta \Rightarrow\alpha$.

(2) for all $\alpha\in\Sigma$, there exist $\beta\in\Sigma$ such that $\alpha \nRightarrow \beta$.

(The symbol $\Rightarrow$ denotes Logical consequence (or implication), That is, if $\alpha$ and $\beta$ are logical expressions such that $\alpha \Rightarrow \beta$, then it must be the case that for each row in the truth table where $\alpha$ is $T$, $\beta$ must also be $T$. And if $\alpha \nRightarrow \beta$, then it must be the case that there exist a row in the truth table where $\alpha$ is $T$ and $\beta$ is $F$).

I tried to build several sets that satisfy the properties but I failed to find one.

I tried the infinite set $\Sigma=\{P,(P\lor\lnot P),((P\lor\lnot P)\lor P),(((P\lor\lnot P)\lor P)\lor P),(((P\lor\lnot P)\lor P)\lor P, ...\}$

Then propery (1) holds for all the elements in the set but property (2) holds for all the elements after the first one and it doesn't holds for the first element $P$.

Then I tried the infinite set $\Sigma=\{P_1,(P_1\lor P_2),((P_1\lor P_2)\lor P_3),(((P_1\lor P_2)\lor P_3)\lor P_4), ...\}$ And the same thing happens here.

I tired several other sets but similiar things happen.

Thanks for any hint/help.

$\endgroup$
2
  • $\begingroup$ I just have a modest undergraduate understanding of logic, but: Is this even possible? If there is a false statement $\alpha$ in this set, then $\forall \beta$, $\alpha \implies \beta$, and this contradicts the assumption $2$. So all the elements of the set must be true. On the other hand, for $2$ to be fulfilled there must be a false statement in the set. This is a contradiction. Or not? $\endgroup$
    – goldenratio
    Apr 11, 2015 at 10:09
  • $\begingroup$ @goldenratio No it isn't a a contradiction. indeed we get by assumption 2 that there cannot be a contradiction in the set. But assumption 2 simply says that for each $\alpha\in\Sigma$ there exist some $\beta\in\Sigma$ that is not necessarily unique (I.e for different $\alpha_1,\alpha_2\in\Sigma$ there may be different $\beta$'s) that satisfy $\alpha\nRightarrow\beta$. $\endgroup$
    – MathNerd
    Apr 11, 2015 at 10:25

1 Answer 1

Reset to default
2
$\begingroup$

HINT: The intuition is that propositions $\varphi_n$ such that

$$\varphi_1\leftarrow\varphi_2\leftarrow\varphi_3\leftarrow\ldots$$

would do the trick nicely. Using infinitely many distinct proposition letters it’s not hard to build such propositions. I’ll spoiler-protect one possibility; mouse-over to see it.

Let $\varphi_n$ be $P_1\land P_2\land\ldots\land P_n$ for $n\in\Bbb Z^+$. Then $\varphi_m\to\varphi_n$ if and only if $m\ge n$. In particular, $\varphi_n\not\to\varphi_{n+1}$.

$\endgroup$
2
  • $\begingroup$ The moment I added the comment I got that $\phi_1$ doesn't imply the others and so I deleted my previous comment. I think I got it, Thanks a lot. $\endgroup$
    – MathNerd
    Apr 11, 2015 at 15:14
  • $\begingroup$ @Saita: You’re very welcome. $\endgroup$
    – Brian M. Scott
    Apr 11, 2015 at 15:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .