3
$\begingroup$

What exactly does it mean to make an intuitive argument rigorous?

I’m currently reading A Concise Introduction to Mathematical Logic by Wolfgang Rautenberg and in the first section, he says that, “…intuitively clear facts, such as the identical number of left and right parentheses in a formula, are rigorously provable.”

I will explicitly write down the intuitive steps that I made (and that many people probably make) to justify that the number of left and right parentheses in a formula must be balanced:

(2) We first observe that left and right parenthesis are always introduced in pairs (1) because each generative rule adds zero or two parenthesis. We intuitively realize that (3) this observation is sufficient to conclude that the left and right parentheses in any formula must be balanced. Finally we use our intuitive understanding that, in this context, (4) a formula having balanced parentheses is sufficient to conclude that the number of occurrences of each type of parenthesis must be equivalent.

Any attempts that I’ve seen to make these statements rigorous fail in capturing every mechanism used in the argument. These proofs will have gaps which must be filled in by the reader. The dilemma is that to fill in these gaps, the reader must already be familiar with the underlying intuition that originally motivated the proof.

Moreover, let’s say a mathematician claims to have completely formalized their intuition of some concept. How are they to know that this formalization matches their intuition? If the formalization they created is entirely independent of their intuition wouldn’t this information be unknowable?

If I am wrong in believing that a rigorous proof is one that doesn’t require any leaps of intuition to understand, what then is meant by one author or another when they refer to mathematical rigor?

What then would a truly rigorous proof actually look like? In general or for the specific statement above.

$\endgroup$
7
  • 1
    $\begingroup$ In a nutshell, it means move from "We first observe that left and right parenthesis are..." to "We prove that..." $\endgroup$
    – Mauro ALLEGRANZA
    Commented Jan 19, 2022 at 9:36
  • 1
    $\begingroup$ The real meaning of these type of problems is to practice with proof by induction on the complexity of formulas (on the formation tree). The benefit is to learn how to use it in "real" examples like e.g "Show that a proposition with n connectives has at most 2n+1 subformulas." $\endgroup$
    – Mauro ALLEGRANZA
    Commented Jan 19, 2022 at 11:28
  • 1
    $\begingroup$ Two things: 1. For a decently rigorous proof, I would replace (3) and (4) with induction proof of the literal numbers of left and right parentheses; who cares if they're balanced if that's not the goal? 2. Mathematical rigor is a spectrum. A proof that mentions induction or similar is likely more rigorous than one that doesnt. Depending on your standards, a "truly rigorous proof" of a claim might look like the formal proofs that I assume are covered later in the book, or maybe something like that but with extra checking that you're using legal strings, etc. $\endgroup$
    – Mark S.
    Commented Jan 19, 2022 at 13:14
  • 1
    $\begingroup$ @MarkS. This still doesn't address how we make rigorous the connection between the recursive definition of a formula and induction on the number of symbols in a string. This seems to require (at one point or another) that the reader is able to "observe" the definition and visually count the number of characters being added. The reader is then expected to make the intuitive connection between concatenation on a string and arithmetic summation, two mathematically distinct concepts. The reason I mention (3) is because this is a non-arithmetic observation whereas (4) is inherently arithmetic $\endgroup$
    – stam_a
    Commented Jan 19, 2022 at 16:56
  • 1
    $\begingroup$ @MauroALLEGRANZA How do you make rigorous the concept of observation? At which point in the process of translating "We first observe that left and right parenthesis are..." into "We prove that left and right parenthesis are..." do we rigorously capture the metamathematical concept of observation? Is it possible to write a proof of this problem without requiring that the reader can physically see and count or relying on them to understand the connection between concatenation of a string and induction on a numerical property? $\endgroup$
    – stam_a
    Commented Jan 19, 2022 at 17:22

1 Answer 1

Reset to default
0
$\begingroup$

Hint: Use induction on the complexity of formulas.

  • Does the statement hold for atomic formulas?
  • If it holds for a wff $\phi$ then does it hold for $(\neg\phi)$?
  • If it holds for wffs $\phi$ and $\psi$ does it hold for $(\phi \square \psi$)?

The answer to these three questions is yes,by the induction principle that means that the statement is true for all wffs.

This is a rigorous argument.

$\endgroup$
11
  • $\begingroup$ What do you mean by $ɸ□ψ$? Is there an $\&$ missing? $\endgroup$
    – user946772
    Commented Jan 19, 2022 at 5:05
  • $\begingroup$ @11qq00 It’s a common abbreviation ,$\square$ is any of $\land$ ,$\lor$ ,$\implies$ $\endgroup$
    – Vivaan Daga
    Commented Jan 19, 2022 at 5:06
  • 1
    $\begingroup$ @11qq00 not at least one, all of them, imagine replacing the third condition ,by three staments with the box replaced by a connective $\endgroup$
    – Vivaan Daga
    Commented Jan 19, 2022 at 5:13
  • 1
    $\begingroup$ I'm aware that we can perform induction on the complexity of a formula. The point I'm trying to make is that this technique relies on the fact that we understand there exists a connection between these recursively defined formulas and the number of different characters in a string. This is step (4) in the line of reasoning above. To me it seems like this connection is being made in the mind of the reader (i.e. intuitively), not in the words of the proof. $\endgroup$
    – stam_a
    Commented Jan 19, 2022 at 5:32
  • 1
    $\begingroup$ @stam_a What do you mean by appreciate a connection?,do you fully understnad why the induction principle is true? $\endgroup$
    – Vivaan Daga
    Commented Jan 19, 2022 at 17:42

You must log in to answer this question.

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