3

Suppose that we know all proper implications of a certain unknown statement $p$, i.e., all propositions $q$ such that $p\Rightarrow q$ but not $q \Rightarrow p$.

Is that information enough to recover $p$?

HeMan
  • 3,119

1 Answers1

1

For any statement $q$ that is not equivalent to $p$, there are the following options:

$q$ is strictly implied by $p$. Then $q$ is in the given set.

$q$ is not strictly implied by $p$. Then $q$ is not in the given set, but $q \lor p$ is.

So, if $\Gamma$ is the given set of implied statements, and if $L$ is the set of all possible statements, then the following set:

$S = \{ x \in L | x \not \in \Gamma \land \neg \exists y \in L: x \lor y \in \Gamma) \}$

will be the set of all statements equivalent to $p$.

In plain language: given the set of implied statements $\Gamma$, and trying to find the implying statement $p$ (or equivalent thereof) by working through the set of all possible statements $L$: toss out any statement $q$ that is in $\Gamma$, or for which there is a statement strictly implied by $q$ that is in $\Gamma$. What's left will be any statements equivalent to $p$.

I would have no idea how to find that statement in practice though, since there are infinitely many statements implied by any statement, and having worked through any finite amount of them always leaves multiple non-equivalent options as to what $p$ could be: Say the finite statements you have worked through are $\phi_1, ... , \phi_n$. Then $p$ could be any statement of the form $\phi_1 \land ... \land \phi_n \land \phi_{n+1}$ for any $\phi_{n+1}$ not implied by $\phi_1 \land ... \land \phi_n$ (of which there are infinitely many)

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • what do yo mean by "strongest statement"? – HeMan Dec 21 '17 at 17:50
  • What if none of the statements in the set are equivalent to $p$, i.e., all statements $q$ we know are strictly $p\implies q$ ? – Prasun Biswas Dec 21 '17 at 17:52
  • @PrasunBiswas Impossible. It was assumed that we were given the set of all implied statements .. that includes $p$ itself. .... Of course, it's possible that what you say is in fact exactly what the OP meant ... in which case the OP will need to edit the question. Because in logic, 'implies' has a very clear definition which entails that every statement implies itself. – Bram28 Dec 21 '17 at 17:58
  • @HeMan When $p$ implies $q$, $p$ is considered the 'stronger' statement. The 'stronger' statement 'says more' ... and is therefore more likely to be false. – Bram28 Dec 21 '17 at 17:59
  • Yes, in fact my question is that one that Prasun asks. I have made the edit. – HeMan Dec 21 '17 at 18:10
  • @HeMan OK, I changed my answer accordingly as well. – Bram28 Dec 21 '17 at 19:34