Intuitionistic Logic and Classical Logic on the proof of (A or B)

Question

In intuitionist logic, a proof of (A or B) means a proof of A, or a proof of B, whereas in Classical logic, a proof of (A or B) may be done withouth either proving A or proving B.

I'm trying to get an example ( preferably simple, because i'm really beginner in mathematics ) where we can prove (A or B), withouth either proving A or B.

Someone told me that considering Riemann Hypothesis as RH, we can prove RH or ~RH withouth either proving RH or ~RH . But riemann Hypothesis is too advanced for me.

Can anyone provide me a simpler example of a proof of A or B that doesnt prove A, and also doesnt prove B ?

Is this kind of proof will always be a proof by contradiction ( proving that ~A and ~B derives a contradiction ) ? Is that why intuitionistic logic rejects proof by contradiction ?

Thanks a lot

Answer 1

One such problem is: can an irrational number raised to irrational power yield a rational number? Now consider three numbers:

\begin{align} a &= \sqrt{2} \\ b &= a^\sqrt{2} = \sqrt{2}^\sqrt{2}\\ c &= b^\sqrt{2} = (\sqrt{2}^\sqrt{2})^\sqrt{2} = \sqrt{2}^2 = 2\\ \end{align}

Now either $b$ is irrational or not. If it is, then $b$ raised to an irrational power yields $2$, a rational number. On the other hand, if $b$ is rational, then $a$ works. To adapt this to your question, let $P(x)$ be \begin{align} P(x) =\ &x\text{ is an irrational number that raised to }\\ &\text{an irrational power yields a rational number}, \end{align} then you prove a statement $$P(a) \lor P(b)$$ which means that either $a$ or $b$ is a number you are looking for, but you don't know which.

Edit:

There another example a bit closer to logic. Consider three people: Alice, Bob and Charlie standing like this: Alice sees the back of Bob, while Bob sees the back of Charlie (Alice does not see the back of Charlie).

$$A \to B \to C.$$

Alice is married and Charlie is unmarried (and let's assume for simplicity that any person is either married or unmarried). Does a married person see the back of an unmarried person?

There are two cases: either Bob is married or not. If he is, then he sees the back of Charlie, and if he's not, then Alice sees his back. In both the final answer is yes, so the answer to the question is affirmative, but we don't know who that person is. Again, we prove $Q(A) \lor Q(B)$ for appropriate $Q$.

I hope this helps $\ddot\smile$

Answer 2

Sure, here's a simple proof of the existence of a pair of irrational numbers $x,y$ such that (at least one, since it's a multibranched function) of the values of $x^y$ is rational

Consider statement A: With $x=\sqrt 2,y=\sqrt 2:,x,y\notin \mathbb Q \land x^y \in \mathbb Q$. And statement B: With $x={\sqrt 2}^{\sqrt 2},y=\sqrt 2,x,y\notin \mathbb Q \land x^y\in \mathbb Q$.

Now, to prove $A \lor B$, if $A$ is true, then we are done. If $A$ is false, then $\sqrt 2^{\sqrt 2}$ is irrational, therefore the first part of statement B is true ($x,y \notin \mathbb Q$) and (at least one value) of $x^y=({\sqrt 2}^{\sqrt 2})^{\sqrt 2}=\sqrt 2 ^2=2\in \mathbb Q$, and statement B is true. Therefore either $A$ or $B$ must be true (By law of the excluded middle).

Note that this does not tell us which of $A$ or $B$ is true, therefore it does not provide a proof of either individually

Answer 3

The following is a classical tautology

$$ (A \leftrightarrow B) \lor (B \leftrightarrow C) \lor (A \leftrightarrow C) $$

This is because $A,B,C$ have values in $\{{\sf true,false}\}$, and by the pidgeonhole principle two of them must share a value.

In intuitionistic logic, the formula above is not a tautology. If it were, one of the three subformulas should be a tautology on its own, and clearly none of them is such (they are not even classical ones).