Interpretation Representation and Model Verification

Background

Why is Model Finding Useful?

• Checking the consistency of an axiomatization. [Sutcliffe]
• Finding the countermodel for a conjecture [Claessen], in particular ...
• In fault finding applications, e.g., in software verification, a countermodel for a proof obligation points to the location of the fault. [Sutcliffe]
• Finding a solution to a problem that is coded as a model finding problem. [Claessen]
• In teaching it is really useful to inspecting outcomes of student's experiments. [Steen]

1. Give only a "yes", indicating that there is a model.
   • In an (industrial) application where models indicate bugs, users would probably get very frustrated. [McCune]
   • Acceptable, but a model is preferred. [Claessen]
   • As part of a decision procedure, sat/unsat could be used as a yes/no subroutine. I do use this for my I/O logic reasoner. [Steen]
2. Give only a "yes, finite", indicating that there is a finite model.
3. Output a model in some form
   • In the case of a countermodel for a conjecture, one would like to have some concrete representation of it to see why the theorem cannot be proved. [Claessen]
   • Sometimes it is very easy to find satisfiability (a saturation) with ordered resolution even if there is a finite model. [Tammet]
   • Regardless of the cardinalities, applications that use ATP systems to find models typically need an explicit model with a domain and symbol mapping. [Sutcliffe]
4. Output a finite model in some form
   • Finite models are used to evaluate other clauses. [McCune]
   • It's better to require the output of a finite model as this can be easily checked by other systems. [Zhang]
   • It is not enough to know that there is a solution; one would like to know what the solution is. [Claessen]

Representation of Interpretations

• Classical interpretations
  • Interpretations with a finite domain, and the symbol interpretations. These are called finite interpretations. The finite domain can be:
    • Explicitly enumerated.
    • The finite Herbrand Universe of a Herbrand interpretation.
  • Interpretations with an infinite domain, and the symbol interpretations. These are called infinite interpretations. The infinite domain can be:
    • Explicitly generated, e.g., Peano arithmetic terms.
    • Explicitly specified, e.g., the integers.
    • Algebraic numbers (real closed fields)
    • The infinite Herbrand Universe of a Herbrand interpretation.
    • One can explicitly state that it's infinite while leaving open how this is realized, e.g., "in all infinite domains, it holds that ..."
    • Any others?
  • Saturations. Saturations embody a Herbrand interpretation.
  • Models that are nearly constant everywhere, as used in the SMT world for model-based quantifier instantiation.
  • Consistent sets of formulae represent families of interpretations. [Steen]
  • +You can read off a satisfying assignment from a non-closable tableau, right? [Steen]
  • Any others?
• Non-classical Kripke interpretations
  • Kripke interpretations with a finite number of worlds.
  • Kripke interpretations with an infinite number of worlds. Infinite worlds are necessary when there are, e.g., in alethic modal logic, an infinite number of possibilities; in temporal logics, R is serial (always has a successor) and non-circular etc., so there have to be infinitely many worlds (points in time). [Steen]
  • Within each world of a Kripke interpretation there is a classical interpretation, with the options as above.

Properties of Different Representations

• A finite model with an enumerated domain, and the symbol interpretations.
  • My experience suggests that one would prefer a finite model over a saturation. [Claessen]
  • A finite model can be abbreviated in some way, e.g., if a 30-ary predicate is true for all but three cases, it is enough to mention those 3 cases and a default case. A large predicate table can be expressed in terms of a few smaller ones, e.g., p(X,Y) := q(X) & r(Y). [Claessen]
• A definition of an infinite domain, and the symbol interpretations.
  • The domain must be adequate for interpreting all formulae. [Sutcliffe]
  • I hope it will be OK to specify the interpretation for that subset of an infinite domain that is used, for which the range coincides with the domain. The subset is induced by interpretation of terms, first constants, then inductively by functions. But what if no constants ... add a new constant as done for the Herbrand Universe in a Herbrand interpretation? [Sutcliffe]
  • There are uncountably many interpretations: whatever the language, it will be possible to represent only a small (negligible) subset of all models.
  • The only ATP systems I know of that can produce an explicit infinite domain model are Z3 (Pascal says) and cvc5 (I think!). [Sutcliffe]
• A saturation.
  • Hardly a useful artifact. [Sutcliffe]
  • Saturations are pretty much impossible to interpret explicitly in a way that can be used constructively by users. [Sutcliffe]
  • A saturation is not a direct representation of a finite model. [Tammet]
  • A saturation tells you only that models exist, but very little about what they might look like. Take some equational axioms for a group plus a denial of commutativity; the typical saturation gives the complete set of reductions for free groups plus the denial of commutativity, which does help finding an example of a non-commutative group. [McCune]
  • There are classes of problem (including problems where all models are infinite) in which saturation can tell you everything about the models. [McCune]
  • A saturated set of clauses at the end doesn't mean much for other systems. [Zhang]
  • I have never been able to make use of a saturated clause set. [Claessen]
  • The clauses of a saturation could in principle be used for checking whether some later presented finite part of an infinite model is OK. [Tammet]
  • In some sense the saturation does not differ very much from the original clause set: the saturation is also just a clause set, and is typically not a fixpoint for other search strategies. [Tammet]
  • Given a saturation and the system search control, it's sometimes possible to decide if a ground atom is TRUE or FALSE. [Schulz] In the general case you cannot even decide ground atoms. [Tammet]
  • There have been several attempts to improve the representation (Viennese ATP researchers (Leitsch, Baaz, Fermüller etc.), but the improvements are basically still the fixpoint set of clauses. [Tammet]
  • I have never read the proof of completeness of superposition but isn't it the case that a saturation allows to build a model? [Fontaine]
  • An email exchange with Joe Schoisswohl and Cezary Kaliszyk

    A Saturation (S) is a way of writing a Herbrand interpretation
    (HI) of input formulae (I). I learned that a HI consists of:
    
    Domain (D) = The Herbrand Universe (HU), and if the HU is empty add a new
               constant.
    Function map (F) = Identity
    Predicate map (P) = Some way of saying which elements of the Herbrand
               Base (HB) are true/false.
    
    So, simplistically, S can be represented in the TPTP format by providing
    the conjunction of the universally quantified formulae of S. Yeah, I know
    a saturation is modulo the ATP system's ordering, so it might not be
    possible to prove S |= I, but let's gloss over that for now. There might
    be a deeper issue: In the CNF context, S can contain symbols not in I
    (e.g., Skolems), and hence not part of the HU. So formally, S might not
    be an interpretation of I. What problems might arise? I'm thinking of an
    example like ...
    
    Axioms
        ? [X] : p(X)
    HI
        D = {a}
        F = id
        P = p(a) == true
    But ...
        S = {p(sk)}
    
    Here p(sk) |= ? [X] : p(X). Are there any weird cases where things break?
    Can we say that an S that contains symbols not from the I really represents
    a HI of I? Or only a HI of CNF(I), then lean on equisatisfiability to prove
    that "if S |= I then HI |- I" where HI is somehow constructed from S?
    

Representation of FOF Finite Interpretations

Representation of TFF/TXF Interpretations

%--------------------------------------------------------
tff(human_type,type,      human: $tType ).
tff(cat_type,type,        cat: $tType ).
tff(jon_decl,type,        jon: human ).
tff(garfield_decl,type,   garfield: cat ).
tff(arlene_decl,type,     arlene: cat ).
tff(nermal_decl,type,     nermal: cat ).
tff(loves_decl,type,      loves: cat > cat ).
tff(owns_decl,type,       owns: ( human * cat ) > $o ).

tff(only_jon,axiom, ! [H: human] : H = jon ).

tff(only_garfield_and_arlene_and_nermal,axiom,
    ! [C: cat] : 
      ( C = garfield | C = arlene | C = nermal ) ).

tff(distinct_cats,axiom,
    ( garfield != arlene & arlene != nermal 
    & nermal != garfield ) ).

tff(jon_owns_garfield_not_arlene,axiom,
    ( owns(jon,garfield) & ~ owns(jon,arlene) ) ).

tff(all_cats_love_garfield,axiom,
    ! [C: cat] : ( loves(C) = garfield ) ).

tff(jon_owns_garfields_lovers,conjecture,
    ! [C: cat] :
      ( ( loves(C) = garfield & C != arlene ) 
       => owns(jon,C) ) ).
%--------------------------------------------------------

%--------------------------------------------------------
tff(human_type,type,      human: $tType ).
tff(cat_type,type,        cat: $tType ).
tff(jon_decl,type,        jon: human ).
tff(garfield_decl,type,   garfield: cat ).
tff(arlene_decl,type,     arlene: cat ).
tff(nermal_decl,type,     nermal: cat ).
tff(loves_decl,type,      loves: cat > cat ).
tff(owns_decl,type,       owns: ( human * cat ) > $o ).

%----Types of the domains
tff(d_human_type,type,    d_human: $tType ).
tff(d_cat_type,type,      d_cat: $tType ).
%----Types of the promotion functions
tff(d2human_decl,type,    d2human: d_human > human ).
tff(d2cat_decl,type,      d2cat: d_cat > cat ).
%----Types of the domain elements
tff(d_jon_decl,type,      d_jon: d_human ).
tff(d_garfield_decl,type, d_garfield: d_cat ).
tff(d_arlene_decl,type,   d_arlene: d_cat ).
tff(d_nermal_decl,type,   d_nermal: d_cat ).

tff(garfield,interpretation,
%----The domain for human is d_human
    ( ( ! [H: human] : ? [DH: d_human] : H = d2human(DH)
%----The d_human elements are {d_jon}
      & ! [DH: d_human] : ( DH = d_jon )
%----The type-promoter is a bijection
      & ! [DH1: d_human,DH2: d_human] :
          ( d2human(DH1) = d2human(DH2) => DH1 = DH2 )
%----The domain for cat is d_cat
      & ! [C: cat] : ? [DC: d_cat] : C = d2cat(DC)
%----The d_cat elements are {d_garfield,d_arlene,d_nermal}
      & ! [DC: d_cat]: 
          ( DC = d_garfield | DC = d_arlene | DC = d_nermal )
      & $distinct(d_garfield,d_arlene,d_nermal)
%----The type-promoter is a bijection
      & ! [DC1: d_cat,DC2: d_cat] : 
          ( d2cat(DC1) = d2cat(DC2) => DC1 = DC2 ) )
%----Interpret terms via the type-promoted domain
    & ( jon = d2human(d_jon)
      & garfield = d2cat(d_garfield)
      & arlene = d2cat(d_arlene)
      & nermal = d2cat(d_nermal)
      & loves(d2cat(d_garfield)) = d2cat(d_garfield)
      & loves(d2cat(d_arlene)) = d2cat(d_garfield)
      & loves(d2cat(d_nermal)) = d2cat(d_garfield) )
%----Interpret atoms as true or false
    & ( owns(d2human(d_jon),d2cat(d_garfield))
      & ~ owns(d2human(d_jon),d2cat(d_arlene))
      & ~ owns(d2human(d_jon),d2cat(d_nermal)) ) ) ).
%--------------------------------------------------------

Representation of TXF Interpretations

Representation of THF Interpretations

Representation of Infinite Interpretations

%------------------------------------------------------------------------------
tff(person_type,type,        person: $tType ).
tff(bob_decl,type,           bob: person ).
tff(child_of_decl,type,      child_of: person > person ).
tff(is_descendant_decl,type, is_descendant: ( person * person ) > $o ).

tff(descendents_different,axiom,
    ! [A: person,D: person] : ( is_descendant(A,D) => ( A != D ) ) ).

tff(descendent_transitive,axiom,
    ! [A: person,C: person,G: person] :
      ( ( is_descendant(A,C) & is_descendant(C,G) ) => is_descendant(A,G) ) ).

tff(child_is_descendant,axiom,
    ! [P: person] : is_descendant(P,child_of(P)) ).

tff(all_have_child,axiom,
    ! [P: person] : ? [C: person] : C = child_of(P) ).

%------------------------------------------------------------------------------

%------------------------------------------------------------------------------
tff(person_type,type,         person: $tType ).
tff(bob_decl,type,            bob: person ).
tff(child_of_decl,type,       child_of: person > person ).
tff(is_descendant_decl,type,  is_descendant: ( person * person ) > $o ).

tff(peano_type,type,          peano: $tType).
tff(zero_decl,type,           zero: peano ).
tff(s_decl,type,              s: peano > peano ).
tff(peano2person_decl,type,peano2person: peano > person ).
tff(peano_less_decl,type,     peano_less: ( peano * peano ) > $o ).

tff(people,interpretation,
%----Domain for type person is the Peano numbers
    ( ( ! [P: person] : ? [I: peano] : ( P = peano2person(I) )
      & ! [I: peano] : ( I = zero | ? [P: peano] : I = s(P) )
%----The type promoter is a bijection (injective and surjective)
      & ! [I1: peano,I2: peano] :
          ( peano2person(I1) = peano2person(I2) => I1 = I2 )
%----Relationships between Peano numbers
      & ! [I1: peano,I2: peano,I3: peano] :
          ( peano_less(I1,s(I1))
          & ( ( peano_less(I1,I2)
              & peano_less(I2,I3) )
           => peano_less(I1,I3) )
          & ( peano_less(I1,I2)
           => I1 != I2 ) ) )
%----Mapping people to integers. Note that Bob's ancestors will be interpreted
%----as negative integers.
    & ( bob = peano2person(zero)
      & ! [I: peano] :
          child_of(peano2person(I)) = peano2person(s(I)) )
%----Interpretation of descendancy
    & ( ! [A: peano,D: peano] :
          ( is_descendant(peano2person(A),peano2person(D))
        <=> peano_less(A,D) ) ) ) ).

%------------------------------------------------------------------------------

%------------------------------------------------------------------------------
tff(person_type,type,        person: $tType ).
tff(bob_decl,type,           bob: person ).
tff(child_of_decl,type,      child_of: person > person ).
tff(is_descendant_decl,type, is_descendant: ( person * person ) > $o ).

tff(int2person_decl,type,    int2person: $int > person ).

tff(people,interpretation,
%----Domain for type person is the integers
    ( ( ! [P: person] : ? [I: $int] : int2person(I) = P
%----The type promoter is a bijection (injective and surjective)
      & ! [I1: $int,I2: $int] : 
          ( int2person(I1) = int2person(I2) => I1 = I2 ) )
%----Mapping people to integers. Note that Bob's ancestors will be interpreted 
%----as negative integers.
    & ( bob = int2person(0)
      & ! [I: $int] : child_of(int2person(I)) = int2person($sum(I,1)) )
%----Interpretation of descendancy
    & ! [A: $int,D: $int] : 
        ( is_descendant(int2person(A),int2person(D)) <=> $less(A,D) ) ) ).

%------------------------------------------------------------------------------

Representation of Kripke Interpretations

Record world information in one formula, using a new defined type $ki_world, a new defined predicate $ki_world_is with type $ki_world > $o, a new defined predicate $ki_accessible with type ($ki_world * $ki_world) > $o, and a new defined constant $ki_local_world with type $ki_world. Syntactically distinct constants of type $ki_world are known to be unequal. The interpretation in a world is represented as above, with guards used to specify the worlds in which the interpretation is used.

Representation of Finite-Finite Kripke Interpretations - Local Axioms

%------------------------------------------------------------------------------
tff(semantics,logic,
    $alethic_modal ==
      [ $domains == $constant,
        $rigidity == $rigid,
        $locality == $local,
        $modalities == $modal_system_M ] ).

tff(person_decl,type,person: $tType).
tff(product_decl,type,product: $tType).
tff(alex_decl,type,alex: person).
tff(chris_decl,type,chris: person).
tff(leo_decl,type,leo: product).
tff(work_hard_decl,type,work_hard: (person * product) > $o).
tff(gets_rich_decl,type,gets_rich: person > $o).

%----If there is a product that a person works hard on, then it's possible
%----that the person will get rich.
tff(work_hard_to_get_rich,axiom,
    ! [P: person] :
      ( ? [R: product] : work_hard(P,R)
     => {$possible} @ ( gets_rich(P) ) ) ).

%----Nobody necessarily gets rich.
tff(not_all_get_rich,axiom,
    ~ ? [P: person] : ({$necessary} @ (gets_rich(P)) ) ).

%----Alex and Chris work hard on Leo-III.
tff(alex_works_on_leo,axiom,
    work_hard(alex,leo) ).

tff(chris_works_on_leo,axiom,
    work_hard(chris,leo) ).

%----It's possible that Alex gets rich but Chris does not.
tff(only_alex_gets_rich,conjecture,
    ( {$possible} @ (gets_rich(alex) & ~ gets_rich(chris)) ) ).
%------------------------------------------------------------------------------

Representation of Finite-Finite Kripke Interpretations

Representation of Finite-Infinite Kripke Interpretations

Representation of Infinite-Finite Kripke Interpretations

%------------------------------------------------------------------------------
tff(simple_spec,logic,
    $alethic_modal == [
      $constants == $rigid,
      $quantification == $constant,
      $modalities == $modal_system_M ] ).

tff(person_type,type, person: $tType).
tff(geoff_decl,type,  geoff: person).
tff(alive_decl,type,  alive: (person * $int) > $o).
tff(age_decl,type,    age: (person * $int) > $int).

tff(born_by_1961,axiom,
    ? [BirthYear: $int] :
      ( $lesseq(BirthYear,1961)
      & ! [PreBirthYear: $int] :
          ( $less(PreBirthYear,BirthYear)
         => ( ~ alive(geoff,PreBirthYear)
            & ( age(geoff,PreBirthYear) = -1 ) ) )
      & ! [FromBirthYear: $int] :
          ( $greatereq(FromBirthYear,BirthYear)
         => ( alive(geoff,FromBirthYear)
            & ( age(geoff,FromBirthYear) = $difference(FromBirthYear,BirthYear)) ) ) ) ).

tff(necessarily_alive_between,axiom,
    ! [StartYear: $int,EndYear: $int] :
      ( ( $less(StartYear,EndYear)
        & alive(geoff,StartYear)
        & alive(geoff,EndYear) )
     => ( {$necessary} 
        @ (! [BetweenYear: $int] :
             ( ( $greatereq(BetweenYear,StartYear)
               & $lesseq(BetweenYear,EndYear) )
            => alive(geoff,BetweenYear) )) ) ) ).

tff(necessarily_dead_after,axiom,
    ! [DeathYear: $int] :
      ( ( alive(geoff,DeathYear)
        & ~ alive(geoff,$sum(DeathYear,1)) )
     => ( {$necessary}
        @ (! [Year: $int] :
             ( $greater(Year,DeathYear)
            => ~ alive(geoff,Year) ) ) ) ) ).

tff(might_live_another_year,axiom,
    ! [Year: $int] :
      ( alive(geoff,Year)
     => ( {$possible} @ (alive(geoff,$sum(Year,1))) ) ) ).

%----Adding this should make the axioms contradictory
% tff(must_die,axiom,
%     {$necessary} @
%       ( ? [Year: $int] :
%           ( $greater(Year,1961)
%           & ~ alive(geoff,Year ) ) ).

%----This should be provable
% tff(might_live_long,conjecture,
%     {$possible} @
%       ( ? [Year: $int] :
%           ( age(geoff,Year) = 120
%           & alive(geoff,Year) ) ) ).

%------------------------------------------------------------------------------

%------------------------------------------------------------------------------
%----Declarations to fool Vampire when processing this file directly
% tff('$ki_world_type',type,$ki_world: $tType).
% tff('$ki_local_world_decl',type,$ki_local_world: $ki_world).
% tff('$ki_accessible_decl',type,$ki_accessible: ($ki_world * $ki_world) > $o).
% tff('$ki_world_is_decl',type,$ki_world_is: ($ki_world * $o) > $o).

tff(person_type,type, person: $tType).
tff(geoff_decl,type,geoff: person).
tff(alive_decl,type,alive: (person * $int) > $o).
tff(age_decl,type,age: (person * $int) > $int).

tff(int2ki_world_decl,type,int2ki_world: $int > $ki_world ).
tff(d_person_type,type,d_person: $tType).
tff(d_geoff_decl,type,d_geoff: d_person).
tff(d2person_decl,type,d2person: d_person > person).

tff(long_live_geoff,interpretation,
%----An infinite number of worlds, numbered by naturals
    ( ( ! [I: $int] : ? [W: $ki_world] : int2ki_world(I) = W
%----The type promoter is a bijection (injective and surjective)
      & ! [I1: $int,I2: $int] : 
          ( int2ki_world(I1) = int2ki_world(I2) => I1 = I2 )
      & ! [W: $ki_world] : ? [I: $int] : int2ki_world(I) = W
%----Worlds can access themselves and greater indexed worlds (worlds in the future)
      & ! [P: $int,F: $int] : 
          ( $greatereq(F,P)
         => $ki_accessible(int2ki_world(P),int2ki_world(F)) ) )

%----Worlds before 1961 all think geoff was born that year
    & ! [IW: $int] :
        ( $less(IW,1961)
       => ( '$ki_world_is'(int2ki_world(IW),
%----Only one domain element for person
              ( ( ! [P: person] : ? [DP: d_person] : P = d2person(DP)
                & ! [DP: d_person] : DP = d_geoff
                & ? [DP: d_person] : DP = d_geoff
%----The type promoter is a bijection (injective and surjective)
                & ! [X: d_person,Y: d_person] :
                    ( d2person(X) = d2person(Y) => X = Y ) )
              & geoff = d2person(d_geoff)
%----Alive and age interpretation
              & ! [Y: $int] :
                  ( $less(Y,IW)
                 => ( ~ alive(d2person(d_geoff),Y)
                    & age(d2person(d_geoff),Y) = -1 ) )
              & alive(d2person(d_geoff),IW)
              & age(d2person(d_geoff),IW) = 0
              & ! [Y: $int] :
                  ( $greater(Y,IW)
                 => ( alive(d2person(d_geoff),Y)
                    & age(d2person(d_geoff),Y) = $difference(Y,IW) ) ) ) ) ) )

%----Worlds from 1961 know geoff was born in 1961. geoff lives forever!
    & ! [IW: $int] :
        ( $greatereq(IW,1961)
       => ( '$ki_world_is'(int2ki_world(IW),
              ( ( ! [P: person] : ? [DP: d_person] : P = d2person(DP)
                & ! [DP: d_person] : DP = d_geoff
                & ? [DP: d_person] : DP = d_geoff
                & ! [X: d_person,Y: d_person] :
                    ( d2person(X) = d2person(Y) => X = Y ) )
              & geoff = d2person(d_geoff)
              & ! [Y: $int] :
                  ( ( $less(Y,1961)
                   => ( ~ alive(d2person(d_geoff),Y)
                      & age(d2person(d_geoff),Y) = -1 ) )
                  & ( ( $greatereq(Y,1961)
                      & $less(Y,IW) )
                   => ( alive(d2person(d_geoff),Y)
                      & age(d2person(d_geoff),Y) = $difference(Y,1961) ) ) )
              & alive(d2person(d_geoff),IW)
              & age(d2person(d_geoff),IW) = $difference(IW,1961)
              & ! [Y: $int] :
                  ( $greater(Y,IW)
                 => ( alive(d2person(d_geoff),Y)
                    & age(d2person(d_geoff),Y) = $difference(Y,1961) ) ) ) ) ) ) ) ).

%------------------------------------------------------------------------------

• The consistency of the interpretation formula cannot be confirmed by any ATP system I have.

Representation of Infinite-Infinite Kripke Interpretations