Re: Question about proof by contradiction

In article <22002860.1205435339850.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
pn4039@xxxxxxxxxx <pn4039@xxxxxxxxxx> wrote:
Thanks Jack and F,

The examples of RAA that do and don't make use of LEM are good,
though I'm still wondering if you can construct two such examples that
are more mathematical in nature (quantitative that is: I study
mathematics, not logic).

I think the following two "work":

(1) RAA without LEM. There is no rational number whose square is
equal to 2.

Proof. Suppose a and b are integers such that (a/b)^2 = 2. We may
assume without loss of generality that a,b>0, and that
gcd(a,b)=1. Then a^2 = 2b^2. Since a^2 is even, a is even. Thus, a
= 2k for some k. Substituting in you have (2k)^2 = 2b^2, or 4k^2 =
2b^2. Cancelling we have b^2 = 2k^2, so b^2 is even, hence b is
even. Thus 2 divides both a and b, which is a
contradiction. Therefore, there is no rational number whose square
is equal to 2.


(2) RAA with LEM. Let A be the collection of all continuous functions
f:[0,1]-->R, R the real numbers, and make A into a ring by
pointwise addition and multiplication. Let I be a proper ideal of
A. Then there exists a point a in [0,1] such that f(a)=0 for all f
in I.

Proof. Suppose to the contrary that there is no such point a. Then
for every a in [0,1] there exists a continuous function g_a in I
such that g_a(a) =/= 0. Since g_a is continuous, there exists an
e_a>0 such that g_a(x) =/= 0 for every x in (a-e_a,
a+e_a)/\[0,1]. The intervals (a-e_a,a+e_a) form an open cover of
[0,1], so by compactness there exists e1,...,en>0 and a_1,...,a_n
in [0,1] such that

[0,1] is contained in (a1-e1,a1+e1) \/ ... \/ (an-en,an+en).

Let g_i be the function g_{a_i}, i=1,...,n. Let
f = g_1^2 + ... + g_n^2. Since I is an ideal of A and g_i is in I
for each i, it follows that f is in I. Moreover, for each x in
[0,1], there exists i such that x is in (ai-ei,ai+ei), and
therefore g_i(x)^2 > 0. Thus,

f(x) = g_1^2(x) + ... + g_n^2(x) >= g_i(x)^2 > 0.

That is, f(x) > 0 for every x in X. Let h(x) be given by h(x) =
1/f(x) for every x in [0,1]. Since f is continuous and always
positive, h is continuous. Therefore, h is in A. Since I is an
ideal, hf is in I. However, hf(x) = (1/f(x))f(x) = 1 for every x in
[0,1]. That is, the constant function 1 is in I. If g is any
function of A, then g(hf) = g is in I, so A is contained in I. This
contradicts the fact that I is a proper ideal of A.

Thus, the assumption that there does not exist any point a in
[0,1] such that f(a)=0 for all f in I leads to a contradiction, so
we conclude (from LEM) that there must exist an a in [0,1] for
which f(a) = 0 for all f in I.


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: Question about proof by contradiction
    ... All the math books that I have constantly remind that RAA may or may ... not make use of LEM, and yet they never give examples to distinguish. ... We just may call both rules of derivation "RAA": ... B & ~B Contradiction ...
    (sci.math)
  • Re: arithmetic in ZF
    ... > Let's take the contrapositive of that "shared first link" ... > Classically we get there trivially by LEM, ... > The q arose out of a non-constructive proof and we begin ... > The classical proof didn't produce Just Any old contradiction; ...
    (sci.logic)
  • Re: A question about Caontors proof of the uncountability of the reals
    ... All the constructivists I know accept the rule: ... both LNC and LEM). ... So I guess some forms of proof by contradiction are ... acceptable even to intuitionists. ...
    (sci.math)
  • Re: Question about proof by contradiction
    ... What are RAA and LEM? ... The phrase "LEM" makes me think of the Lunar Excursion Module. ...
    (sci.math)