2
$\begingroup$

I've been studying logic as part of my Discrete Mathematics course and I understood most of the material so far: statements, predicates, connectives, arguments, etc. The book was very thorough and the material clear, however, now that it is moving to proofs of actual mathematical theorems, I feel it became much sloppier in explaining what's going on. In particular, when proving a mathematical proposition q from a premise p, the book does so by completely moving from the realm of logic to the realm of algebra, and it does not explain the connection between the algebraic manipulations we perform and their meaning (and validity) in logic.

For example, if we want to prove by contradiction that

for all integers n: it is not the case that ((n is even) and (n is odd))

logic teaches us to start with the negated premise there exists an integer n: (n is even) and (n is odd) and reach a contradiction.

This is when the book completely leaves the realm of logic and enters that of algebra. The following is my attempt at reconciling what is done algebraically to its meaning in logic.

The book first goes to the definitions of even and odd, which state:

An integer n is even <-> (there exists an integer j such that n=2j)
An integer n is odd <-> (there exists an integer k such that n=2k+1)

What is the corresponding operation in the realm of logic of this step, are we replacing the (sub)propositions in our premise with their definitions? Why are we allowed to do that? The book does not explain this, but I guess it makes sense that we are always allowed to substitute a proposition s for a proposition t inside a compound proposition, if the biconditional between s<->t holds.

So now we have

there exists an integer n: (there exists an integer j: n=2j) and (there exists an integer k: n=2k+1)

The next step in the book is to bring the two equations together, that is, informally:

Since (n=2j) and (n=2k+1), then 2j=2k+1

Why are we allowed to do this? In basic algebra, you can do this because the two equations have a common variable, but what about logic? Also, I feel this is only correct because the two propositions have the AND connective. Could we do the same if we had an OR? If we had a XOR, we surely couldn't, because while our original premise will lead to a contradiction, the version with XOR holds:

there exists an integer n: (there exists an integer j: n=2j) xor (there exists an integer k: n=2k+1)

i.e. an integer is either odd or even.

The next step in the book is to manipulate 2j=2k+1 so as to reach (j-k) = 1/2. This is declared to be a contradiction because j,k were integers thus their difference cannot be 1/2.

Again, two doubts: Why are we allowed to manipulate equations as we usually do in algebra when doing proofs? My intuitive explanation is that, again, a biconditional holds between any of the original equation and its manipulated version (for example, if we add 1 on both sides of an equation: x=2a <-> x+1=2a+1) and thus any manipulated version can substitute its corresponding proposition in the premise.

When exactly is a "non-sensical mathematical situation" a contradiction? My explanation is that, after applying all substitutions, we are left with there exists an integer n: (there exists integers j, k: j-k=1/2) Which is a false statement. Is this why we declare it to be a contradiction?

Where can I find a more rigorous explanation of what's going on in the realm of logic when we perform algebraic manipulations and do mathematical proofs in general?

$\endgroup$
9
  • 1
    $\begingroup$ Category theory $\endgroup$
    – jimjim
    Commented Jun 21 at 14:16
  • $\begingroup$ How much mathematical logic have you studied? Logic and algebra are deeply linked, and you can view logical manipulations algebraically - as well as viewing algebraic manipulations logically. There are many, many different lenses through which we can interpret this - my introduction was model theory, but any of the "major" branches of mathematical logic will give you a useful perspective. $\endgroup$ Commented Jun 21 at 14:28
  • 1
    $\begingroup$ @Daniel to do that in "full rigor" is actually a lot of work; you have to represent your algebraic primitives in terms of your logical primitives or vice-versa, which means doing a lot of tedious low-level proof of "basic" or "obvious" algebraic (or logical) facts. $\endgroup$ Commented Jun 21 at 15:17
  • 2
    $\begingroup$ Definitions, like even and odd, use biconditional allowing us to replace the new property (even, odd) with the corresponding formula. $\endgroup$ Commented Jun 21 at 15:40
  • 1
    $\begingroup$ This related answer may help: math.stackexchange.com/questions/4935498/… $\endgroup$ Commented Jun 21 at 16:06

1 Answer 1

3
$\begingroup$

I guess it makes sense that we are always allowed to substitute a proposition s for a proposition t inside a compound proposition, if the biconditional between s<->t holds.

Yes, after all, two propositions have the same truth value precisely when they are are equivalent.

Why are we allowed to manipulate equations as we usually do in algebra when doing proofs?

While these algebraic manipulations apply rules of inference, they are also premised on mathematical axioms.

When exactly is a "non-sensical mathematical situation" a contradiction? My explanation is that, after applying all substitutions, we are left with a false statement. Is this why we declare it to be a contradiction?

You have derived a contradiction precisely when you have derived a statement of the form Q and not Q, including (but not limited to) when you have derived a patently false statement.

(there exists an integer j: n=2j) and (there exists an integer k: n=2k+1) The next step in the book is to bring the two equations together, that is, Since (n=2j) and (n=2k+1), then 2j=2k+1. Why are we allowed to do this?

This deductive step is justified because ∃j P(j) and ∃k Q(k) implies ∃j ∃k ( P(j) and Q(k) ); in fact, they are logically equivalent. On the other hand, notice that ∃j ( P(j) and Q(j) ) does not imply ∃j P(j) and ∃j Q(j) (though the converse is logically true).

I feel this is only correct because the two propositions have the AND connective. Could we do the same if we had an OR?

∃j P(j) or ∃j Q(j) and ∃j ( P(j) or Q(j) ) are in fact logically equivalent, as are ∃j P(j) or ∃k Q(k) and ∃j ∃k ( P(j) or Q(k) ).

Where can I find a more rigorous explanation of what's going on in the realm of logic when we perform algebraic manipulations and do mathematical proofs in general?

I cite the above equivalences—which can all be derived from the basic rules of inference—merely to justify/invalidate the steps that you are asking about; in practice though, mathematical manipulations are justified by careful reasoning, not necessarily by invoking formal logic like this.

$\endgroup$
1
  • $\begingroup$ Thank you, this answer cleared up a lot of doubts for me $\endgroup$
    – Daniel
    Commented Jun 21 at 16:45

You must log in to answer this question.

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