[Agda] ℕ ⊆ P U Q -> ¬ isFinite P or ...
Sergei Meshveliani
mechvel at botik.ru
Mon Oct 27 09:17:57 CET 2014
On Sat, 2014-10-25 at 17:51 +0100, Paolo Capriotti wrote:
> On Sat, Oct 25, 2014 at 4:18 PM, Sergei Meshveliani <mechvel at botik.ru> wrote:
> > And I have an impression that the statement
> >
> > question : {P Q : NSet} → setℕ ⊆ (P ⋃ Q) →
> > (¬ isFinite P) ⊎ (¬ isFinite Q)
> >
> > has not a constructive proof.
> >
> > Has it?
>
> You're right, it's unprovable. In fact, from `question` above you can distill a
> function:
>
> h : (ℕ → 2) → 2
>
> such that
>
> ∀ f : ℕ → 2, ¬ isFinite (f⁻¹ (h f))
>
> Now, `h` cannot be continuous. In fact, let `m` be the modulus of continuity of
> `h` at `λ _ → 0`, and let `f : ℕ → 2` be defined by:
>
> f n = 0 if n ≤ m
> f n = 1 otherwise
>
> then
>
> 0 = h (λ _ → 0) = h f = 1.
>
> Discontinuous functions are taboo, hence `question` cannot be proved.
Thanks to people for explanations.
I understand the Abhishek's idea about the Turing machine halt
resolution.
As to your explanation with the continuity matters, I fear of that I am
not aware of notions.
Is "2" a set of two elements?
What topology or metric on ℕ → 2 and 2 is used in a notion of
continuity for a map in (ℕ → 2) → 2 ?
What does it mean that m is a modulus of continuity for h at
g : ℕ → 2 ?
If it is \forall g ( |h(g') - h(g)| <= m * |g' - g| ),
then what does it mean |g' - g| ?
Also g, g' map only into a two-value domain ...
Regards,
------
Sergei
More information about the Agda
mailing list