title: Coq: Prop versus Set in Type(n)
body: <p>I want to consider the following three (related?) Coq definitions.</p>
  
  <pre><code>Inductive nat1: Prop :=
    | z1 : nat1
    | s1 : nat1 -&gt; nat1.
  
  Inductive nat2 : Set := 
    | z2 : nat2
    | s2 : nat2 -&gt; nat2.
  
  Inductive nat3 : Type :=
    | z3 : nat3
    | s3 : nat3 -&gt; nat3.
  </code></pre>
  
  <p>All three types give induction principles to prove a proposition holds.</p>
  
  <pre><code>nat1_ind
       : forall P : Prop, P -&gt; (nat1 -&gt; P -&gt; P) -&gt; nat1 -&gt; P
  
  nat2_ind
       : forall P : nat2 -&gt; Prop,
         P z2 -&gt; (forall n : nat2, P n -&gt; P (s2 n)) -&gt; forall n : nat2, P n
  
  nat3_ind
       : forall P : nat3 -&gt; Prop,
         P z3 -&gt; (forall n : nat3, P n -&gt; P (s3 n)) -&gt; forall n : nat3, P n
  </code></pre>
  
  <p>The set and type versions also contain induction principles for definitions over set and type (rec and rect respectively).  This is the extent of my knowledge about the difference between Prop and Set; Prop has a weaker induction.</p>
  
  <p>I have also read that Prop is impredicative while Set is predicative, but this seems like a property rather than a defining quality.</p>
  
  <p>While some practical (moral?) differences between Set and Prop are clear, the exact, defining differences between Set and Prop, as well as where they fit into the universe of types is unclear (running check on Prop and Set gives Type (* (Set) + 1*)), and I'm not exactly sure how to interpret this...</p>