Intereting Posts

Big O/little o true/false
Evaluate $\int_{0}^{\infty}\dfrac{\mathrm dx}{(e^{\pi x}+e^{-\pi x})(16+x^2)}$
Show that the following recurrence relation satisfies the inequality $\displaystyle f(1) + 2f(2) + \cdots + nf(n) \le \frac{n(n+1)(2n+1)}{6}$
Uniform Continuity of $x \sin x$
Show that $\prod (1- P(A_n))=0$ iff $\sum P(A_n) = \infty$
Decomposition of semimartingales
A projection satisfying $\| Px \| \leq \|x\|$ for all $x$ is an orthogonal projection
Fourier Cosine Transform (Parseval Identity) for definite integral
Taking Calculus in a few days and I still don't know how to factorize quadratics
1 to the power of infinity, why is it indeterminate?
What does the discriminant of an algebraic number field mean intuitively?
Compactness of Multiplication Operator on $L^2$
$\sum_{k=0}^n (-1)^k \binom{n}{k}^2$ and $\sum_{k=0}^n k \binom{n}{k}^2$
What's the problem this logic
How do different definitions of “degree” coincide?

Good day,

Usually, proofs by contradictions are the easier, and sometimes, even the only ones available. However, there are cases where the easiest proof is not the proof by contradiction. For example, the one below:

From the definition of the rational numbers, all of them can be expressed as quotients of two integers. And from this, logically all rationals quotients as well, because:

- Explanation of proof of Gödel's Second Incompleteness Theorem
- Does algorithmic unsolvability imply unsolvability in general?
- Formal deductions on Hilbert system
- Logical puzzles and arguments
- What is an Empty set?
- Are variables logical or non-logical symbols in a logic system?

$$

\forall a\ \forall b\ \forall c\ \forall d:\{a;b;c;d\}\subset\mathbb Z\setminus\{0\}\\

\left\{\frac a b;\frac c d\right\}\subset\mathbb Q;\

\frac{\ \frac a b\ }{\ \frac c d\ }=

\frac{\frac a b\times bd}{\frac c d\times bd}=

\frac{ad}{bc}\in \mathbb Q

$$

or more generally (and that in fact makes the proof almost superfluous as division is a multiplication and multiplication is commutative) for $m$ fractions:

$$

\forall a\ \forall b:\{a;b\}\subset\mathbb Z\setminus\{0\}\\

\bigcup_ {n=1}^m\left\{\frac {a_n} {b_n}\right\}\subset\mathbb Q;\

\prod_{n=1}^m \frac {a_n} {b_n}=

\frac {\prod_{n=1}^m a_n} {\prod_{n=1}^m b_n}

\in \mathbb Q

$$

(end example)

When I say proof by contradiction, I mean the false statement you assume in order to cause the contradiction must be fundamental to the proof, in such a way that if you remove it, there is no proof. Can such a proof always be found for any proven theorem/conjecture/formula?

- Formal deductions on Hilbert system
- Proving a property of a Logic Formal Language
- Applications of descriptive set theory to mathematical logic?
- If $\forall x \exists y : R(x, y)$, then is it true that $y = y(x)$?
- Entailment relations that are not partial orders
- proving tautologically equivalent
- How can I get the negation of $\exists!$ (unique existential quantification)?
- This sentence is false
- Why isn't this a valid argument to the “proof” of the Axiom of Countable Choice?
- What's the difference between 'any', 'all' and 'some'?

Whenever something is provable *at all*, it is possible to disguise that proof as one by contradiction. But the result is not necessarily very enlightening.

Suppose we have some kind of valid argument for the proposition $P$. We can then also prove $P$ by contradiction:

$P$ is true. Namely, assume for a contradiction that $\neg P$. Then

(insert the existing argument here)and therefore $P$. But then both $\neg P$ (by assumption) and $P$ (by the argument we just gave), and that is a contradiction. Therefore $P$ is true, Q.E.D.

You may then object that the assumption $\neg P$ was not really used to produce the contradiction. Usual mathematical logic doesn’t care about that, it allows assumptions to go unused without affecting the validity of a conclusion. But there are things called **relevance logics** that try to capture the idea that it is somehow wrong not to make any use of an assumption.

Unfortunately that doesn’t help us here — even according to relevance logic, the $\neg P$ assumption certainly *was* used to produce the contradiction in the above proof. Without it there wouldn’t have been any contradiction at all, and the proof would fall apart.

It is a much more interesting question whether there are things that can **only** be proved by contradiction. Arguments that never use proof by contradiction are studied in **intuitionistic logic**, and it turns out that there are statements whose proofs depend essentially on intermediate steps by contradiction. For example, *Peirce’s law*:

$$ ((P\Rightarrow Q)\Rightarrow P)\Rightarrow P $$

cannot be proved without admitting proof by contradiction, or something that is essentially equivalent to it.

There are many directions a proof can take.

Some proofs start with the conclusion, and each new step is a reverse implication until you reach “true”.

Some proofs start with the assumptions (or “true”), and each new step is an implication until you reach the conclusion.

A proof by contradiction starts with the negation of the assumption, and each new step is an implication until you reach “false”. Logically speaking, you can *always* convert a proof by contradiction into a direction proof of the first type using demorgan’s transforms.

Proof by contradiction:

$$ \lnot conclusion \rightarrow false $$

is equivalent to to

$$ conclusion \leftarrow true $$

and any intermediate steps

$$ a \rightarrow b$$

may be converted to

$$ \lnot a \leftarrow \lnot b $$

…unless of course, you are working with a very limited set of rules of inferences that don’t admit both type of proofs.

Any proof by contradiction in a consistent propositional calculus requires that a premise get discharged. Consequently, that premise does not belong to the axiom/theorem set of that propositional calculus. Discharging of premises for a propositional calculus *requires that you have a deduction metatheorem around*. However, if you have no deduction metatheorem around, then proof by contradiction becomes *illegal* for that propositional calculus.

Suppose we have the following formation rules for well-formed formulas (wffs) following a Polish notation scheme.

- All lower case letters of the Latin alphabet qualifies as a wff.
- If $\alpha$ qualifies as a wff, then N$\alpha$ qualifies as a wff.
- If $\alpha$ qualifies as a wff, and so does $\beta$ then C$\alpha$$\beta$ qualifies as a wff.

Suppose our only axiom is

1 CCpqCCqrCpr.

And we have the rule of detachment “From $\vdash$C$\alpha$$\beta$, as well as $\vdash$$\alpha$, we may infer $\vdash$$\beta$” and the rule of uniform substitution. Such a system does qualify as consistent in that it is never the case that we have $\vdash$ $\alpha$ and $\vdash$ N$\alpha$.

We can prove

2 CCCCqrCprsCCpqs.

and

3 CCpCqrCCsqCpCsr.

Additionally, since every theorem of this system comes as a conditional, there exists no last theorem to this system. However, neither the above theorems nor any other theorems of this system can get proven by contradiction according to the relevant definition of a proof for this system (something like every theorem is either the axiom CCpqCCqrCpr or can deduced in a finite sequence of well-formed formulas which starts with CCpqCCqrCpr, and uses only uniform substitution and detachment and ends with the theorem).

So, most definitely, NO, proof by contradiction doesn’t always exist.

- Tough Legendre Integral
- Convergence of $\sum \frac{(2n)!}{n!n!}\frac{1}{4^n}$
- Logic question: Ant walking a cube
- Group Ring calculation
- Irreducibility of a polynomial if it has no root (Capelli)
- Possible ways to walk to school
- If $f'$ is increasing and $f(0)=0$, then $f(x)/x$ is increasing
- How to define a recurrence relation in Maple?
- Finding all solutions to a Diophantine equation involving partial sums of a given series
- How to evaluate $\int \cos^2x \ dx$
- Universal property of universal bundles.
- Expected Number of Coin Tosses to Get Five Consecutive Heads
- Subgroups of $S_n$ of index $n$ are isomorphic to $ S_{n-1}$
- Suppose $X$ is a metric space and $S \subseteq X.$ Then, $S^o=\{x \in X~|~dist(x,S^c)>0\}$.
- Why this vector field $f$ belongs to $C^1({\bf R}^2\times {\bf R})$?