We generated three hard problems for higher order theorem provers with first-order equality containing
 an axiomatization of if-then-else. We claim that there exists a function H which has a finite (small) number
 of approximation points and expect that the prover finds the if-then-else term to express H. To be
 sure this is possible, we also provide witnesses for the functions.

Formulas:
f1,f2       ... if-then-else axiomatizations
f3,f4       ... properties of the successor function (0 is no successor and
a number is always different from its successor)
conclusion0 ... there exists a function h s.t. h(0) = 1, h(1) = 0
conclusion1 ... there exists a function h s.t. h(0) = 1, h(1) = 0, h(2) = 0
conclusion2 ... there exists a function h s.t. h(0) = 1, h(1) = 0, h(2) = 1
w1          ... witness for conclusion0 and conclusion1 (no if-then-else nesting)
w2          ... witness for conclusion2 (no if-then-else nesting)
w3          ... alternative witness for conclusion2 (one if-then-else nesting)

The formulas are:
f1: (all X all u all v (X -> ite(X,u,v) = u))
f2: (all X all u all v (-X -> ite(X,u,v) = v))
f3: (all x -(s(x) = zero))
f4: (all x -(s(x) = x))
w1: (all x (h(x) = ite((x=zero), s(zero), zero) ))
w2: (all x (h(x) = ite((x=s(zero)), zero, s(zero)) ))
w3: (all x (h(x) = ite((x=zero), s(zero),
                                 ite((x=s(zero)), zero, s(zero)  ))))

conclusion0 = (exists H (H(zero)=s(zero) & H(s(zero))=zero ))
conclusion1 = (exists H (H(zero)=s(zero) & H(s(zero))=zero & H(s(s(zero))) = zero))
conclusion2 = (exists H (H(zero)=s(zero) & H(s(zero))=zero & H(s(s(zero))) = s(zero)))

Types:
The variable X is of type o and H is of type i>i. The constant ite is of
type o>i>i>i. Everything else is first-order: u,v,x are variables of type i, zero is a constant of
type i and h is a constant of type i>i.

The problems are (in sequent notation):

P0: f1, f2 :- conclusion0
P1: f1, f2, f3, f4 :- conclusion1
P2: f1, f2, f3, f4 :- conclusion2

To show that there are actual witnesses for the function h, we provide a witness, where the witness w1 can be used
for both W0 and W1:

W0: { w1 :- } x P0
W1: { w1 :- } x P1
W2: { w2 :- } x P2

The filenames are:

P0: ntape6-0-without-witness.tptp
P1: ntape6-1-without-witness.tptp
P2: ntape6-2-without-witness.tptp

W0: ntape6-0-with-witness.tptp
W1: ntape6-1-with-witness.tptp
W2: ntape6-2-with-witness.tptp
W3: ntape6-2-with-witness2.tptp

Contact information: riener (at) logic.at

