Talk:Equivalences are Interderivable

From ProofWiki
Jump to navigation Jump to search

I'm no logician, but this proof doesn't sit right with me. For example, neither application of the rule of implication in the forward implication proof actually follow the proper form. I believe the problem is that this is really a meta-theorem, and we don't have/aren't using the machinery to handle that. --Dfeuer (talk) 01:20, 30 May 2013 (UTC)

"I'm no logician" ... I see what the problem is, right there. --prime mover (talk) 05:11, 30 May 2013 (UTC)
Please address the specific problem I raised with the application of the rule of implication. Also, it certainly "feels" like $a \vdash b$ is a different kind of statement than $a \implies b$. $a \vdash b$ seems to be a statement about how $a$ and $b$ relate within a certain logic, while $a \implies b$ seems to be a statement within that logic. Am I mistaken? If I am not mistaken, then there needs to be some separation between these different levels, no? --Dfeuer (talk) 06:36, 30 May 2013 (UTC)
The usual way of proving this theorem is along the lines of: "Let $\mathsf P$ be a proof that $p \vdash q$; then $\mathsf P$ continued by $\implies \mathcal I$ proves $\vdash p \implies q$." and mutatis mutandis for $p$ and $q$ interchanged. Of course, the converse is just MP. In this sense it is a metatheorem, because we reason with rules from outside the proof system $\vdash$ to arrive at our conclusion. This indeed makes the present proof incorrect. One may consider it as appended on my list of things to be reviewed in PropLog. But one is free to resolve it along the sketched lines, of course. I have no monopoly. — Lord_Farin (talk) 08:54, 30 May 2013 (UTC)
Would I be correct to guess that the two $\vdash$s in the proof are actually distinct, and should have different names, or that one should perhaps even be a different symbol? I really don't know much about this stuff yet, but that's what intuition would suggest. --Dfeuer (talk) 14:29, 30 May 2013 (UTC)
The $\vdash$ symbol in the middle of the expression is not allowed since it refers to "proves by a meta/external argument" instead of "proves by an internal argument". It would best be replaced by a word; anything conveying "implies" should be fine. — Lord_Farin (talk) 14:46, 30 May 2013 (UTC)
Going in the other direction requires a different sort of careā€”it only holds for a complete system. --Dfeuer (talk) 15:11, 30 May 2013 (UTC)

That is just not true. One needs the $\implies\mathcal I$ rule, and modus ponens. Nothing else. The problem is purely notational. — Lord_Farin (talk) 15:35, 30 May 2013 (UTC)

I never claimed to be perfect, did I? --Dfeuer (talk) 15:47, 30 May 2013 (UTC)
Perhaps an overly caustic response on my part; I'll watch my own tone more closely (not to be overlooked when commenting on others'). — Lord_Farin (talk) 15:50, 30 May 2013 (UTC)
Apology accepted. But I'm still troubled by these concepts. Modus Ponens certainly says $a \implies b, a \vdash b$. That is, if I assume $a \implies b$ then I can argue $a \vdash b$ internally. But from an external perspective, couldn't $a \implies b$ hold in all models without there being an internal way to prove $b$ from $a$? I'm sure I'm mixing the language up something awful. --Dfeuer (talk) 15:53, 30 May 2013 (UTC)

Going halfway back into the discussion, isn't "$\vdash$" meta anyway? Do we need to distinguish between meta and metameta? --GFauxPas (talk) 15:54, 30 May 2013 (UTC)

Lord_Farin, the notational issues are not resolved, and the proof remains problematic—certainly the applications of Rule of Implication don't follow the proper form. Whether this signals a deep problem or a shallow one I couldn't say. --Dfeuer (talk) 16:22, 30 May 2013 (UTC)
Oh, I mistakenly took the questionable flag to accompany your earlier mistake. Sorry.
@GFP: $\vdash$ is notation which indicates a well-defined statement in metalanguage, but about the system under consideration. This notation may not be used for metastatements; that'd effectively amount to overloading of the symbol which is not what we want to do. — Lord_Farin (talk) 17:38, 30 May 2013 (UTC)
There are a number of deduction rules that use forms like this. Rule of Implication and Proof by Contradiction come to mind. Are those stated improperly, or is there something we're missing? --Dfeuer (talk) 18:42, 30 May 2013 (UTC)
I would say there can be no sequent form of those rules. At least, I've never seen it in any source works and I consider it an abuse of notation. — Lord_Farin (talk) 21:37, 30 May 2013 (UTC)
@GFauxPas: to expand on what Lord_Farin said earlier:
As suggested by Definition:Truth Function, it's possible to consider a proposition in propositional logic to be a mapping from truth values to truth values. For example, $\lnot$ in a Boolean domain gives the truth function $f^\lnot: \mathbb B \to \mathbb B$, where $f(0) = 1$ and $f(1) = 0$. The proposition $p \implies q$ gives the truth function $f^{\implies}: \mathbb B \times \mathbb B \to \mathbb B$ where $f^{\implies}(x, y) = f^\lor (f^\lnot(x), y)$, etc. In this context, the statement $p \vdash q$ can be interpreted as $p \preceq q$ (or something close to that, anyway—I'm still learning these ideas), where $0 < 1$ as usual.
But then $(p \vdash q) \vdash p \implies q$ becomes something like $(p \preceq q) \preceq (\neg p \lor q)$, which doesn't make any sense. --Dfeuer (talk) 03:19, 1 June 2013 (UTC)
$p \preceq q$ can itself be considered as a propositional function $\preceq: \mathbb B \times \mathbb B \to \mathbb B$. Thus $(p \vdash q) \vdash p \implies q$ can be considered as a valid statement in Boolean algebra which (reinterpreted in the language used above) would be written $f^\preceq \left({f^\preceq \left({p, q}\right), f^{\implies}\left({p, q}\right)}\right)) = \top$. At the worst it's abuse of notation. --prime mover (talk) 07:51, 1 June 2013 (UTC)
Incidentally, there's a problem (as there well might be) with $f^{\implies}$ - you need brackets round the $\implies$ construct because it's a composite of "space, Longrightarrow, space" and "f^\implies" is intrerpreted by MathJax as being "f^{space}, \Longrightarrow, space". --prime mover (talk) 07:57, 1 June 2013 (UTC)
If you adopt that, the theorem becomes tautologous, because then $f^{\implies}$ is identical to $f^{\preceq}$ -- at least in the present case where $\Bbb B$ is the simple 2-element Boolean algebra. Let us conclude that this needs some love. — Lord_Farin (talk) 09:11, 1 June 2013 (UTC)

The metalogic presumably may use an entirely different set of truth values, no? But yes, some love. Lots of reading, and some love. --Dfeuer (talk) 14:29, 1 June 2013 (UTC)


Revisited

The above discussion predominantly highlights notational issues with this page. Further problems originate from the refactoring of PropLog -- the page no longer makes sense as-is.

I have no access to a copy of Kalish-Montague, so I can't refer to that either to resolve this issue. What should be the course of action? — Lord_Farin (talk) 21:38, 3 February 2014 (UTC)

I don't have my K&M to hand so I can't immediately check. However, I believe them to gloss over the matter.
My view is: one of two things applies. Either (1) there is either an incredibly deep philosophical problem in the expression of the theorem which none of my reading has even begun to address, or (2) at root it is a trivially simple truth over which needless hairs are being split and there is no need to worry. At root I understand this to be a bidirectional Modus Ponens / Rule of Implication, and using the $\vdash$ metasymbol as a meta-metasymbol is at worst a minor abuse of notation.
I would love to find a source which goes into full detail of explaining exactly which one of the above applies, without handwavery, but haven't found one yet. --prime mover (talk) 22:06, 3 February 2014 (UTC)