[FOM] a very exciting claim

Andrej Bauer Andrej.Bauer at andrej.com
Thu Mar 23 04:00:13 EST 2006


On Wednesday 22 March 2006 14:36, Eray Ozkural wrote:
> Excuse my ignorance. Is this also why in many definitions, the
> properties relating to an object of type X, P1, P2, .., PN are given, and
> there is an additional property that says "No other object is X"? I am
> just trying to understand, because (naively) if I give an
> algorithm that enumerates all X, there is no need to make the claim
> of negating the rest. Can you please expand on these claims a little
> further?

I think you are referring to inductive defnitions, for example when we define 
a well-formed formula X to be a string of symbols following some rules 
P1, ..., Pn on how to make new formulas. Books in logic like to add "and no 
other string is a well-formed formula".

This is just a clumsy way of explaining inductive definitions. There are many 
better ways of doing it: to programmers explain them using inductive 
datatypes or grammars, to logicians explain them with 
introduction/elimination rules or induction principles, to mathematicians 
explain them with free algebras.

I am somewhat surprised at what Gabriel is saying:
> Finally, some things are shorter and nicer in a constructive
> mindset yet disturb the classical mind.  E.g., the definition of
> |x|.  Constructively: x if x is at least 0, -x if x is at most 0.
> Period. But a classical mathematical can't stop there.  He feels a need
> to say that |x| is defined for all x.  On the other hand, in a
> constructive mindset, one does not feel such a need.  Nothing is
> missing.

Irrespective of whether you're classical or constructive, if you want to 
define absolute value as a function R --> R in the way you suggest above, 
then you should first prove a pasting lemma which says that you can paste 
together f_1 : (-infinity, 0] --> R and f_2 : [0, infinity) into f : R --> R, 
provided they agree at 0. Classically this is rather easy since

  R = (-infinity, 0] union [0, infinity)

But constructively the above equation cannot be proved, so you need to worry 
_more_. I do not find it self-evident at all (with my constructive hat on) 
that the above definition of |x| defines a function for all real x (I know it 
does).

Or to put it another way, suppose you define |x| as you said:

  if x <= 0 then |x| = -x,
  if x >= 0 then |x| = x.

Why is |x| defined for all x, constructively?

I personally prefer the definition |x| = max(-x,x), where max comes from a 
proof that (R, <=) is a lattice.

Andrej


More information about the FOM mailing list