leanprover / leanprover/reference-manual

The description of why strict posivity is needed is wrong

Open
#124 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Lean
Stars
129
Forks
67
Avg merge
1d 15h
Merged PRs (30d)
16

Description

Describe the bug
This came up on Zulip:

at the explanation for the requirements for inductive types, the example claims that the defined Fix (fun a => a -> a) would be equivalent to Bad... i've given a shot, but i couldn't seem to prove that you can construct Bad.rec function from Fix.rec? Maybe it would be easier to say that Fix (. -> Empty) is an inconsistent type (as you're creating a fixpoint for negation)?

And later in the thread:

at the explanation for the requirements for inductive types, the example claims that the defined Fix (fun a => a -> a) would be equivalent to Bad... i've given a shot, but i couldn't seem to prove that you can construct Bad.rec function from Fix.rec? Maybe it would be easier to say that Fix (. -> False) is an inconsistent type (as you're creating a fixpoint for negation)?

I looked into this and indeed Lean generates a recursor without an induction hypothesis for Fix.rec:

unsafe inductive Fix (f : Type u → Type u) where
  | fix : f (Fix f) → Fix f

#check Fix.rec
-- Fix.rec.{u_1, u} {f : Type u → Type u} {motive : Fix f → Sort u_1}
--   (fix : (a : f (Fix f)) → motive (Fix.fix a))
--   (t : Fix f) : motive t

So I guess the Fix that comes out of the unsafe inductive declaration is an accidentally consistent but non-inductive type.

And the the answer:

it's still not consistent, using f := (. -> Empty)

my point is that the argument as to why it isn't consistent is wrong (or at least not clear)

This should be investigated and fixed.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Open the linked Well-formed inductives section and compare the Fix (fun a => a -> a) explanation with the Zulip discussion, especially Fix.rec and the f := (. -> Empty) case. Clarify the consistency argument in the documentation and verify the revised explanation against the surrounding requirements text; no specific test is named.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.