2
$\begingroup$

To represent finite sets within coq, we either use something like ListSet, which are just definitions on top of list, or we build something like Compcert.Map, and then we define a set A as a map from A to ().

However, neither of these approaches manage to define sets inductively. What I want to know is a way to define a set type in the form of:

Inductive set (A: Type) : Type := 
 nil: set A | add: A -> set A -> <fill in the blanks> -> set A

Is it possible to have such an "inductive definition" for finite sets? If not, can I be supplied with a proof of why not?

My intuition is that such a thing is not possible, because an inductive type allows for equational reasoning, while sets cannot be equationally reasoned with:

$$ \texttt{add}~(1, \emptyset) = \texttt{add}(1, \texttt{add}(1, \emptyset)) \quad \text{(union is idempotent.)} $$

however:

add 1 (add 1 nil) <> add 1 nil 

So we will always have to go through some "extensional interface". Unfortunately, I don't know how to prove such a thing!

$\endgroup$
  • $\begingroup$ You might like to look into "quotient types" (and higher-inductive types, which are a kind of generalization of quotients). Another approach might be to make your add constructor take a proof that the new element is not yet in the set (which you might be able to define as an inductive-recursive definition). $\endgroup$ – Stefan May 4 at 14:22
  • $\begingroup$ Can you show me how to write the inductive-recursive definition? I'd be glad if you could. Regarding quotient types: Right, I'd forgotten about their existence! I guess I can encode this in cubical agda? (cubical so the quotients are computable) $\endgroup$ – Siddharth Bhat May 4 at 15:18
5
$\begingroup$

There are many variants of finite sets in constructive mathematics. One that can be defined using just inductive definitions, and is therefore amenable to formalization in type theory, is the Notherian finiteness by Thierry Coquand and Arnaud Spiwack. The idea is to define a set or a type $A$ to be finite if the following holds: every sequence $a : \mathbb{N} \to A$ contains a duplicate. The trick is to express an equivalent condition using inductive definitions, so that we get an induction principle for reasoning about such sets.

The definition of Notherian finiteness from section 2.3 of the linked paper can be translated to Coq like this:

(* [occurs x l] states that x appears in the list l *)
Inductive occurs {A : Type} : A -> list A -> Type :=
  | occurs_head : forall x k, occurs x (cons x k)
  | occurs_tail : forall x y k, occurs x k -> occurs x (cons y k).

(* [has_duplicates l] states that [l] has a duplicate, i.e., that an element appears in it twice. *)
Inductive has_duplicates {A : Type} : list A -> Type :=
  | has_duplicates_head : forall x l, occurs x l -> has_duplicates (cons x l)
  | has_duplicates_tail : forall x l, has_duplicates l -> has_duplicates (cons x l).

(* An auxiliary definition: a list `l` is said to be `notherian` if it contains a duplicate, or if every extension of `l` by one element is `notherian`. *)
Inductive notherian (A : Type) : list A -> Type :=
  | N_duplicates : forall l, has_duplicates l -> notherian A l
  | N_step : forall l, (forall a, notherian A (cons a l)) -> notherian A l.

Definition NotherianFinite A := notherian A nil.

If you're willing to use quotient types or the higher inductive types from homotopy type theory, then you can have a look at the defintion of finite sets Finite in the HoTT library. It says that a type X is finite if there is a number n such that X is merely equivalent to the standard finite set {0, 1, ..., n-1}. The word "merely" here means that we truncate the existence, i.e., $$\textstyle\mathsf{Finite}\, X \mathrel{{:}{=}} \sum_{n : \mathbb{N}} \left\| X \simeq \mathsf{Fin}\,n\right\|$$ where $\mathsf{Fin}\,n$ is the standard finite set $\sum_{k : \mathbb{N}} (k < n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the pointers to both the Coq definition and the HoTT based definition. Can you give me some intuition about where my intuition that "(a)sets cannot be equationally reasoned with but (b) inductive definiitions can" breaks? Does (a) break, or (b), or both? $\endgroup$ – Siddharth Bhat May 5 at 13:49
  • 1
    $\begingroup$ Finite sets can be equationally reasoned about because the finite subsets of a type $A$ are the commutative monoid freely generated by $A$. So there will be equations (of the commutative monoid) and an induction principle (the free generation). $\endgroup$ – Andrej Bauer May 5 at 18:02
  • $\begingroup$ It is unclear to me why they correspond to the free commutative monoid. Won't the free commutative monoid of a type $S$ with inhabitants $a:S, b:S$ contain terms such as $\epsilon, a, b, ab, a^2, b^2, a^2b^2\dots$, while the subsets of $S$ are only $\epsilon, a, b, ab$? $\endgroup$ – Siddharth Bhat May 5 at 19:55
  • 1
    $\begingroup$ Oops, its the free idempotent commutative monoid, i.e., $x^2 = x$ for all $x$. Without idempotence we get mutisets. $\endgroup$ – Andrej Bauer May 6 at 8:54
  • 1
    $\begingroup$ You asked if there are reasoning principles. The answer is "yes, the equations of a semilattice (which is what an idempotent commutative monoid is), and an induction principle". If a given framework can't handle the reasoning, that's the problem for the framework, the reasoning principles still are there. $\endgroup$ – Andrej Bauer May 6 at 18:03

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.