# Finding a logical expression (under some constrains) s.t. it is equivalent to another one

In this question, it was made clear, when

$\bullet$ some statement $A$ is stronger than another statement $B$, namely if $A\Rightarrow B$ holds; and when the statement $A$ is weaker than another statement $B$, namely if $B\Rightarrow A$ holds.

and

$\bullet$ when a theorem $A\Rightarrow B$ (every mathematical theorem is from the point of view of propositional logic an implication) is stronger another theorem $A'\Rightarrow B'$, namely if $[(A'\Rightarrow A) \ \land (B=B')]$ or $[(B\Rightarrow B') \ \land (A=A')]$ holds (i.e. the hypothesis of the first theorem is weaker (viewed as a statement) than the hypothesis if the second and the conclusions are equivalent or if the conclusion of the first theorem is stronger than the conclusion of the second theorem and the hypothesis' are equal).

(One could also define analogously the notation if "weaker" for theorems - for statements we had to define this notion - but for the sake of simplicity let's treat only the case of "stronger" in this question.)

Since a theorem is also a statement, I'm interested in the connection between the use of the words stronger for statements and theorems: Let $A$,$A'$,$B$ and $B'$ be some statements and $$\boldsymbol{X}:=[(A' \Rightarrow A) \land (B=B')] \lor [(B \Rightarrow B') \land (A=A')]$$ and $$\boldsymbol{Y}:=(A \Rightarrow B) \Rightarrow ( A' \Rightarrow B').$$ Then $\boldsymbol{X}$ models the statement, that "the theorem "$A\Rightarrow B$ is stronger than the theorem $A' \Rightarrow B'$", and $\boldsymbol{Y}$ models the statement that "the statement $A \Rightarrow B$ is stronger than the statement $A' \Rightarrow B'$".

Now it isn't very hard to prove that $$\boldsymbol{X} \Rightarrow \boldsymbol{Y},$$ but the converse doesn't hold.

My question is, how would I have to modify the definition of one theorem being stronger than another, i.e. of $\boldsymbol{X}$, in a meaningful way that actually reflects how we think about one theorem being stronger than another ?

(So letting the definition of one theorem being stronger than another be something tautological, like $\boldsymbol{X}=\boldsymbol{Y}$, or something meaningless for our way to think of theorems, like $\boldsymbol{X}=\top$, is not allowed.)

For example, suppose we let $\boldsymbol{X}:=A' \Rightarrow A )\lor (B \Rightarrow B')$, meaning the hypothesis of the first theorem has to be weaker than that of the second theorem (but we don't say anything about how the conclusion of the theorems have to relate to each other) or the conclusion of the first theorem is stronger than the one of then second theorem but we don't say how the hypothesis' have to relate). The we get that $\boldsymbol{X}\Leftarrow \boldsymbol{Y}$, but this time the other direction fails.

BTW, we can also convince ourselves that modifying only $\boldsymbol{X}$ makes sense, since tampering with the definition of $\boldsymbol{Y}$ would be pointless because the meaning of the words "stronger" and "weaker" for statements is clear and since the correct way to model some mathematical theorem with hypothesis $A$ and conclusion $B$ via propositional logic is via the implication $A \Rightarrow B$.

I'm also aware that this might be a soft question, since it what one understands to be a "meaningful way" that reflects how we think about one theorem being stronger than another.

• Could you clarify what you mean by modify? Because you can simply "modify" $X$ by replacing it with $Y$ and you get the desired equivalence. – Petr Pudlák Nov 4 '12 at 14:09
• @PetrPudlák Sorry, I didn't think if this case, which I want to exclude, so by modifying $X$ I mean providing an $X$ that is different from $Y$ such that equivalence holds and only the logical connectives of implication and equality are used. If you want to know how I got to this, see math.stackexchange.com/questions/216294/… This question was inspired by that question, were it occurred to me that actually a theorem isn't stronger than another (both being viewed as statements) if and only if the hypothesis is weaker or the conclusion is [...] – temo Nov 6 '12 at 9:39
• [...] stronger ($A$ and $B$ denote the hypothesis and conclusion of one theorem $A'$, $B'$ those of the other theorem). You only have the only if part (which, translated to this question, means $X \Rightarrow Y$). And what I actually, secretly was asking here was, how should I modify the definition of one theorem being stronger than another to get " if and only if ". – temo Nov 6 '12 at 9:40
• I'm afraid your assignment is imprecise. Unless you specify very precisely what $X$ may be, it's very vague. You can for example take $X:=Y=(A=A)$ or $X:=(A\Rightarrow A)\Rightarrow Y$ etc. There are infinitely many possibilities how to make $X$ equivalent to $Y$ and yet different. | The bottom line is: Two propositions of the same "strength" are always equivalent. Like two tautologies are always equivalent, or two contradictions, etc. You can distinguish them only syntactically (that's why I'm asking for a syntactic criterion for $X$). – Petr Pudlák Nov 11 '12 at 20:57
• I think there are two possible views: (1) you only want to add something to $X$, then the answer is to take $X':=X\lor Y$, or something equivalent to it, like $X':=\lnot Y\Rightarrow X$. (2) $Y$ is arbitrary and you want to construct $X$ which is equivalent to it using only $=$ and $\Rightarrow$. If you also allow $\lnot$ or $\bot$ (logical false) this is possible. If you allow only $=$ and $\Rightarrow$ you fail for $Y:=\lnot A$. – Petr Pudlák Nov 11 '12 at 21:01

## 1 Answer

I'm afraid there is no "good" answer to that. As you said, $X$ is a sufficient condition for $Y$, but not vice versa. For example: If $B\Rightarrow B'$ and $A'\Rightarrow A$ (the assumption is weaker and the conclusion stronger) then $Y$ holds but $X$ doesn't. So we could generalize $X$ to $$X_1\,:=\,(B\Rightarrow B') \land (A'\Rightarrow A)$$

This is probably the best where we can get, but still $X_1$ isn't equivalent to $Y$. In fact, it cannot be. We cannot really compare two implicative theorems just by looking at their assumptions and conclusions separately. The reason is that we can have one theorem stronger than another without such a direct relationship between their assumptions and conclusions. Consider these formulas: \begin{align} U &\,:=\, A \Rightarrow B \\ V &\,:=\, ((A\lor C)\land D) \Rightarrow ((B\lor C)\land D) \end{align} $U$ is stronger than $V$ because $\vdash U\Rightarrow V$ (i.e. in the sense of your $Y$). But there is no reasonable correlation between $A$ and $(A\lor C)\land D$ or $B$ and $(B\lor C)\land D$. Depending on other circumstances ($C$ and $D$), $A$ can be stronger or weaker than $(A\lor C)\land D$.

So $Y$ (or something equivalent to it) is the only reasonable way to say that one theorem is stronger than another.

• Then again, all theorems are tautological. Is "Every continuous real function on a compact space assumes its maximum" really stronger than "Every affine linear function on $[0,1]$ assumes its maximum" if both are simply true? One rather has to resolve to inverstigate the different theories in which both statements are theorems. – Hagen von Eitzen Nov 17 '12 at 18:56
• @PetrPudlák Ok, but before I accept the answer, please tell me: Would you agree, that in case the assumptions and conclusions involve the same "circumstances" (i.e. only $A$ and $B$ may appear in both theorems) that the definition of "one theorem being stronger than another" that I had in mind, is "good" ? – temo Nov 18 '12 at 21:33
• @HagenvonEitzen Could you please tell me, what you mean with "investigating different theories in which both statements are theorems" ? Aren't we always in the big "theory" of ZFC ? – temo Nov 18 '12 at 21:34
• @temo I'm not sure what you mean, could you make an example of such theorems? – Petr Pudlák Nov 18 '12 at 21:50
• @PetrPudlák Consider for example these two theorems (which where given in my original question math.stackexchange.com/questions/216294/…):  Theorem 1. Let $X$ be a complete metric space, and suppose that $\{G_n:n\in\Bbb N\}$ is a family of dense open subsets of $X$; then $\bigcap_{n\in\Bbb N}G_n\ne\varnothing$.  Theorem 2. Let $X$ be a complete metric space, and suppose that $\{G_n:n\in\Bbb N\}$ is a family of dense open subsets of $X$; then $\bigcap_{n\in\Bbb N}G_n$ is dense in $X$.  Then these have the same hypothesis [...] – temo Nov 19 '12 at 12:10