2
$\begingroup$

After looking at Can a computer determine whether a mathematical statement is true or not? for a while, I worry we may be into incompleteness/halting problem territory with this question, so an answer on that front, while disappointing, would also be acceptable

I've been interested by ADT equations since I read the linked post, and I've started thinking about them in the context of Coq's inductive types (which essentially permit the usual sum, product, and unitary type constructors).

In particular, I've been considering the correspondence between type definitions and the number of elements inhabiting the type. In particular, solving the type's equation yields the number of elements inhabiting the type, and it seems reasonable to me that, for any so-definded type, this number is at most $\aleph_0$. That is, for any ADT or inductively defined type, the number of inhabitants is at most countably infinite. I'm thinking about how to formulate or prove such a statement in Coq, and in the meantime had some questions. (It seems further natural that such types and numbers are in one-to-one correspondence up to isomorphism between types of the same cardinality, but that might be a step too far).

It seems easy enough to show a type definition containing exactly $n$ elements for any natural $n$, so that gives one direction of a theorem connecting the two. Going the other way, though, seems more difficult, and in either case it woudl be natural to me to rely on a function $C$ from types $\tau$ to numbers (what class of numbers?) $n$ where $C(\tau) = n$ means there are $n$ elements inhabiting the type.

The trouble is, this function doesn't seem computable. If we take the naturals as

Inductive nat: Type :=
  | O
  | S: nat -> nat.

such a function would be required to produce an infinity (namely $\aleph_0$), and thus I don't think Coq could accept such a definition. (Worse, how would the definition know when to return 0?)

So I've come back around to equations. I wondered if I could formulate this idea by constructing for each type $\tau$ (possibly parameterized on other types $\alpha, \beta, \dots$) a polynomial (is this the right term, since it may really be a recurrence?) in the same class of numbers $\tau(\alpha, \beta, \dots) = P(\tau, \alpha, \beta, \dots)$ and proving that all such equations have a unique solution (and herein lies my concern above: would this even be provable?).

This brings me to my main question: I believe that the above statement is true in the absence of mutually recursive types. But mutually recursive types suggest systems of equations, rather than a single equation, and it is well-known that systems do not always have a solution.

But these systems would have some (possibly unique) properties:

  • they would be polynomial in this class of numbers
  • each would have the form $\tau_i = P(\tau_1, \dots, \tau_n)$
  • there would be exactly $n$ equations for $n$ mutually recursive types

Is it possible to prove (or already proven) that such systems are always uniquely solvable in the naturals? I suspect it might be easier to formulate in Linear algebra, but I'm a bit rusty on what it takes to do that here.

$\endgroup$
4
  • $\begingroup$ If this more appropriate on one of the math stacks, let me know. $\endgroup$ Feb 12 at 17:12
  • $\begingroup$ Do you have examples of the equations you're talking about? For instance, the 'obvious' (to me) equation for nat is $x = 1 + x$, which has no solution in the naturals. There are also definitions of empty types with equations $x = x$ and $x = x×x$, which do not have unique solutions. On another tack, I might recommend reading this article $\endgroup$
    – Dan Doel
    Feb 12 at 21:38
  • $\begingroup$ @DanDoel I suppose "in the naturals" is a bit misleading, I'm a bit new to this stuff too. The solution there would have to be $x = \aleph_0$, but I'm not sure how to characterize that sort of thing. Thanks for the feedback $\endgroup$ Feb 12 at 22:19
  • $\begingroup$ I've edited to suggest that I really don't what this class of numbers is, as it includes both $\aleph_0$ and all the naturals @DanDoel $\endgroup$ Feb 12 at 22:23
3
$\begingroup$

The initial assumption about such types having at most countably many elements is false. We can use inductive types to define a non-countable type, namely the countably branching trees:

(* Countably branching trees. *)
Inductive Tree : Type :=
  | Leaf : Tree
  | Node : (nat -> Tree) -> Tree.

Lemma nocycle (t : Tree) : forall (f : nat -> Tree), t = Node f -> forall a, f a <> t.
Proof.
  induction t as [? | f H].
  - easy.
  - intros g E n.
    injection E.
    intro E'; destruct E'.
    intro gN.
    now elim (H n f gN n).
Qed.

Corollary uncountable_Tree :
  ~ exists (f : nat -> Tree), forall t : Tree, exists n, f n = t.
Proof.
  intros [f H].
  destruct (H (Node f)) as [n ?].
  now pose (nocycle (Node f) f eq_refl n).
Qed.

In any case, counting elements of types is a tricky business. Consider the following inductive type:

Inductive cow (P : Prop) : Type :=
  | moo : P -> cow P.

Consider any propostion Q : Prop. If cow Q has zero elements then Q is false, and if it has an element then Q is true. So if we could count the elements of cow, we could also tell whether it has zero elements, and would be able to decide an arbitrary proposition, which would give us excluded middle.

You need to restrict the inductive types quite severaly to obtain a small enough family of them whose sizes can actually be counted.

$\endgroup$
2
  • $\begingroup$ Absolutely fascinating... thanks for the concrete examples, which I’m looking forward to playing with and understanding. In the cow section, did you mean if cow Q has 0 elements? And is the idea that having an element of that type means we showed evidence (from moo’s constructor) of the prop? And having no elements means there was no way to make a moo, so there is no way to get evidence of the prop? $\endgroup$ Feb 13 at 14:21
  • 1
    $\begingroup$ @D.BenKnoble: Yes, cow Q, fixed it. Thanks. Your thinking is correct regarding evidence. $\endgroup$ Feb 13 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.