top | item 46522401

Show HN: Proof that any fixed-axis type system fails for some domain (Lean4)

3 points| trissim | 1 month ago |zenodo.org

I formalized a proof that the structural vs. nominal typing debate can't be won: any fixed-axis type system necessarily fails for some domain. The core result: for a type system with fixed axes (like structure, inheritance, hierarchy), there exists a domain whose requirements cannot be fully captured. This isn't a limitation of specific languages, it's a mathematical impossibility result.

What's in the zip

Full Lean 4 formalization (compiles with lake build) Instantiations for Python, TypeScript, Java, and Rust The axioms for type system structure are extracted from actual language specifications, not invented

Main theorem: For any fixed-axis type framework, there exists a domain D such that no complete typing is achievable.

Let me know there are any holes or if this ends the structural vs nominal typing debate.

discuss

order

No comments yet.