4

Most often when a certain axiom or proposition implies another proposition, this implication is not trivial, or "immediate". That is, you need a proof consisting of some number of steps to reach the second proposition.

So in that case we can say, proposition A implies but does not trivially imply proposition B.

My (philosophical) question is: what does it mean for a proposition to trivially imply another, or in other words, that it follows "immediately"? Is there a way to objectively determine whether an implication is trivial? Does a trivial implication only rely on an appeal to an intuition about "primitive notions"?

Perhaps we should exclude from this analysis cases where a theorem is implicitly used but simply not explicitly stated for the sake of brevity.

3
  • I do not think you can find a precise definition. An example can be an implication P→Q where the consequent Q is true (e.g. a theorem); in this case, the said implication is true whatever P is. Sep 12, 2016 at 8:38
  • @Programmer2134: Do you have a concrete example for such a trivial implication?
    – Moritz
    Sep 12, 2016 at 14:01
  • the q is ambiguous. "Implication" (->) is a logical constant that does not involve inference. with truth tables A->B is either true or false, full stop, which is arguably trivial. you can use A->B in an inference (A->B; but A, therefore B), but that is not implication - modus poems is the standard term for the rule of inference that licenses the reasoning. it sounds like you're really interested in trivial consequence?
    – user20153
    Sep 12, 2016 at 18:19

4 Answers 4

3

"Trivial" in mathematics is a subjective term. Something is "trivial" if my audience, in my opinion, comes faster to the conclusion that they can definitely provide a proof, then the time it takes me to demonstrate such a proof.

Such a proof can actually be quite lengthy, as long as all the steps involved are simple or purely mechanical. For example, one proof that some 16 digit number is a prime would be trivial (because it is completely mechanical) but would still be very long.

The same proof can be trivial if the audience consists of experienced mathematicians and be not trivial if the audience consists of beginners.

1

the key word here is "immediate", not "trival". The latter is an informal, psychologistic term; the latter can be expressed formally in terms of complexity. in logic, though the usual term is "cannonical". loosely, a cannonical proof cannot be simplified. for example, if you have A, and you also have B, then you ipso facto have A /\ B, by the intro rule for /\ . So the proof (explicitly written out) is cannonical - immediate. If your proof has steps that can be eliminated then it is non-cannonical. Note that a cannonical proof could have many steps. so we might say that a trivial proof is a cannonical proof of one step. Also note that this is closely related to the notion of normal form.

Dag Prawitz has written extensively about this sort of thing. It's quite subtle. Note also there is a difference between inference (something we do) and proof (a mathematical structure? something we endorse?) A web search will show some publicly available papers.

2
  • 1
    Please change "cannonical" to "canonical". There are no cannons involved, but canons.
    – gnasher729
    Sep 14, 2016 at 8:16
  • ok so what I am talking about is a one-step canonical proof then. let's call that an immediate proof. You can see such immediate proofs simply as "the application of a logical axiom", but whether you do so or not, it is in the end based on an "intuitive" justification (whatever "intuitive" even means). I am trying to understand this better.
    – user56834
    Sep 16, 2016 at 7:54
0

Let A denote an arbitrary formula (say for example 0=1 in the language of arithmetic) then most people would say the formula A => A is a trivial implication, since the proof follows almost immediately from the =>-intro rule, i.e., assume A, since A is an assumption, we can conclude A, by the =>-intro rule, discharging assumption A we have A => A.

In general though I think a trivial implication can be defined as a conditional A => B (where A and B denote some formula in a set language) whose normalized natural deduction proof's inferences are lower than a specific number (say 40 inferences).

0

What my Logic teacher taught me 50 odd years ago
[Ive not seen it in any book, hence the caveat]

Let's say a math theorem is stated, and pulling out the quantifications we put it as:
Given the pre-conditions pre we can (always) conclude result

Let us state this as pre ⇒ result

Now in the proof (typically subcases of the pre-conditions) result is true without any (further) pre-conditions. This is called trivially proved true. Vacuous proof is the complementary case — when pre is false. In short:

  • Trivial proof of p ⇒ q : q is true, without reference to p
  • Vacuous proof of p ⇒ q : p is false

Diagrammatically

P Q P ⇒ Q
1 T T T
2 T F F
3 F T T
4 F F T

The vacuous case arises when we only need look at the second half of the table — row 3,4.
The trivial case arises when we only need look at odd rows — 1,3

You must log in to answer this question.

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