[FOM] An intuitionistic query

Arnold Neumaier Arnold.Neumaier at univie.ac.at
Thu Sep 17 08:57:10 EDT 2009


rgheck wrote:
> On 09/09/2009 10:12 AM, Arnold Neumaier wrote:

>> (*) is a special case of Dirichlet's pigeonhole principle.
>> Are there versions of the latter that are intuitionistically
>> undecidable? I found an infinite version in
>>      https://eprints.kfupm.edu.sa/60600/1/60600.pdf ,
>> but I am looking for a finite version.
>>    
> Each of the finite versions is certainly going to be provable by a 
> version of the argument you gave, and the uniformity of those arguments 
> is good intuitionistic reason to think the generalization holds. I.e, 
> the obvious argument by induction should work.

I am not so certain. I looked more deeply into the literature and
found that it apparently depends on the way the pigeonhole principle
is formulated.

For example, according to Theorem 4 in http://arxiv.org/pdf/math/9405204
the principle appears to be intuitionistically invalid when written in
a form generalizing
    (***) For every mapping f from {a,b,c} to {d,e},
    there are distinct x, y with  f(x)=f(y). 




Arnold Neumaier



More information about the FOM mailing list