TPTP Problem File: COM174^1.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : COM174^1 : TPTP v9.0.0. Released v7.0.0.
% Domain : Computing Theory
% Problem : Koenig's lemma 94
% Version : [Bla16] axioms : Especial.
% English :
% Refs : [Loc10] Lochbihler (2010), Coinductive
% : [RB15] Reynolds & Blanchette (2015), A Decision Procedure for
% : [Bla16] Blanchette (2016), Email to Geoff Sutcliffe
% Source : [Bla16]
% Names : koenigslemma__94.p [Bla16]
% Status : Theorem
% Rating : 0.33 v9.0.0, 0.67 v8.1.0, 0.75 v7.5.0, 1.00 v7.1.0
% Syntax : Number of formulae : 314 ( 152 unt; 56 typ; 0 def)
% Number of atoms : 621 ( 413 equ; 0 cnn)
% Maximal formula atoms : 11 ( 2 avg)
% Number of connectives : 3774 ( 113 ~; 20 |; 79 &;3323 @)
% ( 0 <=>; 239 =>; 0 <=; 0 <~>)
% Maximal formula depth : 22 ( 7 avg)
% Number of types : 2 ( 1 usr)
% Number of type conns : 185 ( 185 >; 0 *; 0 +; 0 <<)
% Number of symbols : 58 ( 55 usr; 10 con; 0-5 aty)
% Number of variables : 1031 ( 17 ^; 883 !; 84 ?;1031 :)
% ( 47 !>; 0 ?*; 0 @-; 0 @+)
% SPC : TH1_THM_EQU_NAR
% Comments : This file was generated by Isabelle (most likely Sledgehammer)
% 2016-07-13 14:46:08.257
%------------------------------------------------------------------------------
%----Could-be-implicit typings (5)
thf(ty_t_Coinductive__List_Ollist,type,
coinductive_llist: $tType > $tType ).
thf(ty_t_List_Olist,type,
list: $tType > $tType ).
thf(ty_t_Set_Oset,type,
set: $tType > $tType ).
thf(ty_t_itself,type,
itself: $tType > $tType ).
thf(ty_tf_a,type,
a: $tType ).
%----Explicit typings (51)
thf(sy_c_Coinductive__List_Ofinite__lprefix,type,
coindu328551480prefix:
!>[A: $tType] : ( ( coinductive_llist @ A ) > ( coinductive_llist @ A ) > $o ) ).
thf(sy_c_Coinductive__List_Olappend,type,
coinductive_lappend:
!>[A: $tType] : ( ( coinductive_llist @ A ) > ( coinductive_llist @ A ) > ( coinductive_llist @ A ) ) ).
thf(sy_c_Coinductive__List_Olfinite,type,
coinductive_lfinite:
!>[A: $tType] : ( ( coinductive_llist @ A ) > $o ) ).
thf(sy_c_Coinductive__List_Olist__of,type,
coinductive_list_of:
!>[A: $tType] : ( ( coinductive_llist @ A ) > ( list @ A ) ) ).
thf(sy_c_Coinductive__List_Olist__of__aux,type,
coindu1384447384of_aux:
!>[A: $tType] : ( ( list @ A ) > ( coinductive_llist @ A ) > ( list @ A ) ) ).
thf(sy_c_Coinductive__List_Ollast,type,
coinductive_llast:
!>[A: $tType] : ( ( coinductive_llist @ A ) > A ) ).
thf(sy_c_Coinductive__List_Ollist_OLCons,type,
coinductive_LCons:
!>[A: $tType] : ( A > ( coinductive_llist @ A ) > ( coinductive_llist @ A ) ) ).
thf(sy_c_Coinductive__List_Ollist_OLNil,type,
coinductive_LNil:
!>[A: $tType] : ( coinductive_llist @ A ) ).
thf(sy_c_Coinductive__List_Ollist_Olnull,type,
coinductive_lnull:
!>[A: $tType] : ( ( coinductive_llist @ A ) > $o ) ).
thf(sy_c_Coinductive__List_Ollist_Olset,type,
coinductive_lset:
!>[A: $tType] : ( ( coinductive_llist @ A ) > ( set @ A ) ) ).
thf(sy_c_Coinductive__List_Ollist__of,type,
coinductive_llist_of:
!>[A: $tType] : ( ( list @ A ) > ( coinductive_llist @ A ) ) ).
thf(sy_c_Coinductive__List_Olstrict__prefix,type,
coindu1478340336prefix:
!>[A: $tType] : ( ( coinductive_llist @ A ) > ( coinductive_llist @ A ) > $o ) ).
thf(sy_c_HOL_Oundefined,type,
undefined:
!>[A: $tType] : A ).
thf(sy_c_If,type,
if:
!>[A: $tType] : ( $o > A > A > A ) ).
thf(sy_c_Koenigslemma__Mirabelle__aepjeeakgn_Oconnected,type,
koenig793108494nected:
!>[Node: $tType] : ( ( Node > Node > $o ) > $o ) ).
thf(sy_c_Koenigslemma__Mirabelle__aepjeeakgn_Opaths,type,
koenig916195507_paths:
!>[Node: $tType] : ( ( Node > Node > $o ) > ( set @ ( coinductive_llist @ Node ) ) ) ).
thf(sy_c_List_Oappend,type,
append:
!>[A: $tType] : ( ( list @ A ) > ( list @ A ) > ( list @ A ) ) ).
thf(sy_c_List_Obind,type,
bind:
!>[A: $tType,B: $tType] : ( ( list @ A ) > ( A > ( list @ B ) ) > ( list @ B ) ) ).
thf(sy_c_List_Obutlast,type,
butlast:
!>[A: $tType] : ( ( list @ A ) > ( list @ A ) ) ).
thf(sy_c_List_Ocan__select,type,
can_select:
!>[A: $tType] : ( ( A > $o ) > ( set @ A ) > $o ) ).
thf(sy_c_List_Oinsert,type,
insert:
!>[A: $tType] : ( A > ( list @ A ) > ( list @ A ) ) ).
thf(sy_c_List_Olast,type,
last:
!>[A: $tType] : ( ( list @ A ) > A ) ).
thf(sy_c_List_Olist_OCons,type,
cons:
!>[A: $tType] : ( A > ( list @ A ) > ( list @ A ) ) ).
thf(sy_c_List_Olist_ONil,type,
nil:
!>[A: $tType] : ( list @ A ) ).
thf(sy_c_List_Olist_Omap,type,
map:
!>[A: $tType,Aa: $tType] : ( ( A > Aa ) > ( list @ A ) > ( list @ Aa ) ) ).
thf(sy_c_List_Olist_Oset,type,
set2:
!>[A: $tType] : ( ( list @ A ) > ( set @ A ) ) ).
thf(sy_c_List_Olist__ex1,type,
list_ex1:
!>[A: $tType] : ( ( A > $o ) > ( list @ A ) > $o ) ).
thf(sy_c_List_Omap__tailrec,type,
map_tailrec:
!>[A: $tType,B: $tType] : ( ( A > B ) > ( list @ A ) > ( list @ B ) ) ).
thf(sy_c_List_Omap__tailrec__rev,type,
map_tailrec_rev:
!>[A: $tType,B: $tType] : ( ( A > B ) > ( list @ A ) > ( list @ B ) > ( list @ B ) ) ).
thf(sy_c_List_Omaps,type,
maps:
!>[A: $tType,B: $tType] : ( ( A > ( list @ B ) ) > ( list @ A ) > ( list @ B ) ) ).
thf(sy_c_List_Oproduct__lists,type,
product_lists:
!>[A: $tType] : ( ( list @ ( list @ A ) ) > ( list @ ( list @ A ) ) ) ).
thf(sy_c_List_Orev,type,
rev:
!>[A: $tType] : ( ( list @ A ) > ( list @ A ) ) ).
thf(sy_c_List_Orotate1,type,
rotate1:
!>[A: $tType] : ( ( list @ A ) > ( list @ A ) ) ).
thf(sy_c_List_Osublists,type,
sublists:
!>[A: $tType] : ( ( list @ A ) > ( list @ ( list @ A ) ) ) ).
thf(sy_c_Pure_Otype,type,
type:
!>[A: $tType] : ( itself @ A ) ).
thf(sy_c_Set_OCollect,type,
collect:
!>[A: $tType] : ( ( A > $o ) > ( set @ A ) ) ).
thf(sy_c_Set_Othe__elem,type,
the_elem:
!>[A: $tType] : ( ( set @ A ) > A ) ).
thf(sy_c_Sublist_Oprefixes,type,
prefixes:
!>[A: $tType] : ( ( list @ A ) > ( list @ ( list @ A ) ) ) ).
thf(sy_c_Sublist_Oprefixes__rel,type,
prefixes_rel:
!>[A: $tType] : ( ( list @ A ) > ( list @ A ) > $o ) ).
thf(sy_c_Sublist_Ostrict__suffix,type,
strict_suffix:
!>[A: $tType] : ( ( list @ A ) > ( list @ A ) > $o ) ).
thf(sy_c_Wellfounded_Oaccp,type,
accp:
!>[A: $tType] : ( ( A > A > $o ) > A > $o ) ).
thf(sy_c_member,type,
member:
!>[A: $tType] : ( A > ( set @ A ) > $o ) ).
thf(sy_v_XS_H____,type,
xs: list @ a ).
thf(sy_v_graph,type,
graph: a > a > $o ).
thf(sy_v_n,type,
n: a ).
thf(sy_v_x,type,
x: a ).
thf(sy_v_xs,type,
xs2: coinductive_llist @ a ).
thf(sy_v_xs_H_H____,type,
xs3: coinductive_llist @ a ).
thf(sy_v_xs_H____,type,
xs4: coinductive_llist @ a ).
thf(sy_v_ys____,type,
ys: list @ a ).
thf(sy_v_zs____,type,
zs: list @ a ).
%----Relevant facts (254)
thf(fact_0_xs_H,axiom,
( xs4
= ( coinductive_llist_of @ a @ xs ) ) ).
% xs'
thf(fact_1_n__neq__x,axiom,
n != x ).
% n_neq_x
thf(fact_2__092_060open_062_092_060And_062thesis_O_A_I_092_060And_062XS_H_O_Axs_H_A_061_Allist__of_AXS_H_A_092_060Longrightarrow_062_Athesis_J_A_092_060Longrightarrow_062_Athesis_092_060close_062,axiom,
~ ! [XS: list @ a] :
( xs4
!= ( coinductive_llist_of @ a @ XS ) ) ).
% \<open>\<And>thesis. (\<And>XS'. xs' = llist_of XS' \<Longrightarrow> thesis) \<Longrightarrow> thesis\<close>
thf(fact_3_path,axiom,
member @ ( coinductive_llist @ a ) @ ( coinductive_LCons @ a @ n @ xs2 ) @ ( koenig916195507_paths @ a @ graph ) ).
% path
thf(fact_4_xs,axiom,
( xs2
= ( coinductive_lappend @ a @ xs4 @ ( coinductive_LCons @ a @ x @ xs3 ) ) ) ).
% xs
thf(fact_5_XS_H,axiom,
( xs
= ( append @ a @ ys @ ( cons @ a @ n @ zs ) ) ) ).
% XS'
thf(fact_6__092_060open_062n_A_092_060notin_062_Aset_Azs_092_060close_062,axiom,
~ ( member @ a @ n @ ( set2 @ a @ zs ) ) ).
% \<open>n \<notin> set zs\<close>
thf(fact_7_paths_OEmpty,axiom,
! [Node: $tType,Graph: Node > Node > $o] : ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LNil @ Node ) @ ( koenig916195507_paths @ Node @ Graph ) ) ).
% paths.Empty
thf(fact_8_paths_OLCons,axiom,
! [Node: $tType,Graph: Node > Node > $o,X: Node,Y: Node,Xs: coinductive_llist @ Node] :
( ( Graph @ X @ Y )
=> ( ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LCons @ Node @ Y @ Xs ) @ ( koenig916195507_paths @ Node @ Graph ) )
=> ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LCons @ Node @ X @ ( coinductive_LCons @ Node @ Y @ Xs ) ) @ ( koenig916195507_paths @ Node @ Graph ) ) ) ) ).
% paths.LCons
thf(fact_9_paths_Ocases,axiom,
! [Node: $tType,A2: coinductive_llist @ Node,Graph: Node > Node > $o] :
( ( member @ ( coinductive_llist @ Node ) @ A2 @ ( koenig916195507_paths @ Node @ Graph ) )
=> ( ( A2
!= ( coinductive_LNil @ Node ) )
=> ( ! [X2: Node] :
( A2
!= ( coinductive_LCons @ Node @ X2 @ ( coinductive_LNil @ Node ) ) )
=> ~ ! [X2: Node,Y2: Node,Xs2: coinductive_llist @ Node] :
( ( A2
= ( coinductive_LCons @ Node @ X2 @ ( coinductive_LCons @ Node @ Y2 @ Xs2 ) ) )
=> ( ( Graph @ X2 @ Y2 )
=> ~ ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LCons @ Node @ Y2 @ Xs2 ) @ ( koenig916195507_paths @ Node @ Graph ) ) ) ) ) ) ) ).
% paths.cases
thf(fact_10_paths_Osimps,axiom,
! [Node: $tType,A2: coinductive_llist @ Node,Graph: Node > Node > $o] :
( ( member @ ( coinductive_llist @ Node ) @ A2 @ ( koenig916195507_paths @ Node @ Graph ) )
= ( ( A2
= ( coinductive_LNil @ Node ) )
| ? [X3: Node] :
( A2
= ( coinductive_LCons @ Node @ X3 @ ( coinductive_LNil @ Node ) ) )
| ? [X3: Node,Y3: Node,Xs3: coinductive_llist @ Node] :
( ( A2
= ( coinductive_LCons @ Node @ X3 @ ( coinductive_LCons @ Node @ Y3 @ Xs3 ) ) )
& ( Graph @ X3 @ Y3 )
& ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LCons @ Node @ Y3 @ Xs3 ) @ ( koenig916195507_paths @ Node @ Graph ) ) ) ) ) ).
% paths.simps
thf(fact_11_paths_OSingle,axiom,
! [Node: $tType,X: Node,Graph: Node > Node > $o] : ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LCons @ Node @ X @ ( coinductive_LNil @ Node ) ) @ ( koenig916195507_paths @ Node @ Graph ) ) ).
% paths.Single
thf(fact_12_paths__LConsD,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A,Graph: A > A > $o] :
( ( member @ ( coinductive_llist @ A ) @ ( coinductive_LCons @ A @ X @ Xs ) @ ( koenig916195507_paths @ A @ Graph ) )
=> ( member @ ( coinductive_llist @ A ) @ Xs @ ( koenig916195507_paths @ A @ Graph ) ) ) ).
% paths_LConsD
thf(fact_13_paths_Ocoinduct,axiom,
! [Node: $tType,X4: ( coinductive_llist @ Node ) > $o,X: coinductive_llist @ Node,Graph: Node > Node > $o] :
( ( X4 @ X )
=> ( ! [X2: coinductive_llist @ Node] :
( ( X4 @ X2 )
=> ( ( X2
= ( coinductive_LNil @ Node ) )
| ? [Xa: Node] :
( X2
= ( coinductive_LCons @ Node @ Xa @ ( coinductive_LNil @ Node ) ) )
| ? [Xa: Node,Y4: Node,Xs4: coinductive_llist @ Node] :
( ( X2
= ( coinductive_LCons @ Node @ Xa @ ( coinductive_LCons @ Node @ Y4 @ Xs4 ) ) )
& ( Graph @ Xa @ Y4 )
& ( ( X4 @ ( coinductive_LCons @ Node @ Y4 @ Xs4 ) )
| ( member @ ( coinductive_llist @ Node ) @ ( coinductive_LCons @ Node @ Y4 @ Xs4 ) @ ( koenig916195507_paths @ Node @ Graph ) ) ) ) ) )
=> ( member @ ( coinductive_llist @ Node ) @ X @ ( koenig916195507_paths @ Node @ Graph ) ) ) ) ).
% paths.coinduct
thf(fact_14_paths__lappendD1,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A,Graph: A > A > $o] :
( ( member @ ( coinductive_llist @ A ) @ ( coinductive_lappend @ A @ Xs @ Ys ) @ ( koenig916195507_paths @ A @ Graph ) )
=> ( member @ ( coinductive_llist @ A ) @ Xs @ ( koenig916195507_paths @ A @ Graph ) ) ) ).
% paths_lappendD1
thf(fact_15_set,axiom,
member @ a @ x @ ( coinductive_lset @ a @ xs2 ) ).
% set
thf(fact_16__092_060open_062x_A_092_060notin_062_Alset_Axs_H_092_060close_062,axiom,
~ ( member @ a @ x @ ( coinductive_lset @ a @ xs4 ) ) ).
% \<open>x \<notin> lset xs'\<close>
thf(fact_17_True,axiom,
member @ a @ n @ ( coinductive_lset @ a @ xs4 ) ).
% True
thf(fact_18_calculation,axiom,
coinductive_lfinite @ a @ ( coinductive_LCons @ a @ n @ ( coinductive_llist_of @ a @ ys ) ) ).
% calculation
thf(fact_19_lappend__code_I1_J,axiom,
! [A: $tType,Ys: coinductive_llist @ A] :
( ( coinductive_lappend @ A @ ( coinductive_LNil @ A ) @ Ys )
= Ys ) ).
% lappend_code(1)
thf(fact_20_lappend__LNil2,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ( coinductive_lappend @ A @ Xs @ ( coinductive_LNil @ A ) )
= Xs ) ).
% lappend_LNil2
thf(fact_21_lappend__code_I2_J,axiom,
! [A: $tType,Xa2: A,X: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coinductive_lappend @ A @ ( coinductive_LCons @ A @ Xa2 @ X ) @ Ys )
= ( coinductive_LCons @ A @ Xa2 @ ( coinductive_lappend @ A @ X @ Ys ) ) ) ).
% lappend_code(2)
thf(fact_22_lappend__snocL1__conv__LCons2,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Y: A,Ys: coinductive_llist @ A] :
( ( coinductive_lappend @ A @ ( coinductive_lappend @ A @ Xs @ ( coinductive_LCons @ A @ Y @ ( coinductive_LNil @ A ) ) ) @ Ys )
= ( coinductive_lappend @ A @ Xs @ ( coinductive_LCons @ A @ Y @ Ys ) ) ) ).
% lappend_snocL1_conv_LCons2
thf(fact_23_llist__of__inject,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( coinductive_llist_of @ A @ Xs )
= ( coinductive_llist_of @ A @ Ys ) )
= ( Xs = Ys ) ) ).
% llist_of_inject
thf(fact_24_llist_Oinject,axiom,
! [A: $tType,X21: A,X22: coinductive_llist @ A,Y21: A,Y22: coinductive_llist @ A] :
( ( ( coinductive_LCons @ A @ X21 @ X22 )
= ( coinductive_LCons @ A @ Y21 @ Y22 ) )
= ( ( X21 = Y21 )
& ( X22 = Y22 ) ) ) ).
% llist.inject
thf(fact_25_lappend__LNil__LNil,axiom,
! [A: $tType] :
( ( coinductive_lappend @ A @ ( coinductive_LNil @ A ) @ ( coinductive_LNil @ A ) )
= ( coinductive_LNil @ A ) ) ).
% lappend_LNil_LNil
thf(fact_26_LNil__eq__lappend__iff,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( ( coinductive_LNil @ A )
= ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( ( Xs
= ( coinductive_LNil @ A ) )
& ( Ys
= ( coinductive_LNil @ A ) ) ) ) ).
% LNil_eq_lappend_iff
thf(fact_27__092_060open_062lfinite_Axs_H_092_060close_062,axiom,
coinductive_lfinite @ a @ xs4 ).
% \<open>lfinite xs'\<close>
thf(fact_28__092_060open_062n_A_092_060in_062_Aset_AXS_H_092_060close_062,axiom,
member @ a @ n @ ( set2 @ a @ xs ) ).
% \<open>n \<in> set XS'\<close>
thf(fact_29_lfinite__LCons,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ ( coinductive_LCons @ A @ X @ Xs ) )
= ( coinductive_lfinite @ A @ Xs ) ) ).
% lfinite_LCons
thf(fact_30_lfinite__code_I2_J,axiom,
! [B: $tType,X: B,Xs: coinductive_llist @ B] :
( ( coinductive_lfinite @ B @ ( coinductive_LCons @ B @ X @ Xs ) )
= ( coinductive_lfinite @ B @ Xs ) ) ).
% lfinite_code(2)
thf(fact_31_lfinite__code_I1_J,axiom,
! [A: $tType] : ( coinductive_lfinite @ A @ ( coinductive_LNil @ A ) ) ).
% lfinite_code(1)
thf(fact_32_lfinite__lappend,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( ( coinductive_lfinite @ A @ Xs )
& ( coinductive_lfinite @ A @ Ys ) ) ) ).
% lfinite_lappend
thf(fact_33__092_060open_062_092_060And_062thesis_O_A_I_092_060And_062ys_Azs_O_A_092_060lbrakk_062XS_H_A_061_Ays_A_064_An_A_D_Azs_059_An_A_092_060notin_062_Aset_Azs_092_060rbrakk_062_A_092_060Longrightarrow_062_Athesis_J_A_092_060Longrightarrow_062_Athesis_092_060close_062,axiom,
~ ! [Ys2: list @ a,Zs: list @ a] :
( ( xs
= ( append @ a @ Ys2 @ ( cons @ a @ n @ Zs ) ) )
=> ( member @ a @ n @ ( set2 @ a @ Zs ) ) ) ).
% \<open>\<And>thesis. (\<And>ys zs. \<lbrakk>XS' = ys @ n # zs; n \<notin> set zs\<rbrakk> \<Longrightarrow> thesis) \<Longrightarrow> thesis\<close>
thf(fact_34__092_060open_062_092_060exists_062ys_Azs_O_AXS_H_A_061_Ays_A_064_An_A_D_Azs_A_092_060and_062_An_A_092_060notin_062_Aset_Azs_092_060close_062,axiom,
? [Ys2: list @ a,Zs: list @ a] :
( ( xs
= ( append @ a @ Ys2 @ ( cons @ a @ n @ Zs ) ) )
& ~ ( member @ a @ n @ ( set2 @ a @ Zs ) ) ) ).
% \<open>\<exists>ys zs. XS' = ys @ n # zs \<and> n \<notin> set zs\<close>
thf(fact_35__092_060open_062_092_060And_062thesis_O_A_I_092_060And_062xs_H_Axs_H_H_O_A_092_060lbrakk_062lfinite_Axs_H_059_Axs_A_061_Alappend_Axs_H_A_ILCons_Ax_Axs_H_H_J_059_Ax_A_092_060notin_062_Alset_Axs_H_092_060rbrakk_062_A_092_060Longrightarrow_062_Athesis_J_A_092_060Longrightarrow_062_Athesis_092_060close_062,axiom,
~ ! [Xs5: coinductive_llist @ a] :
( ( coinductive_lfinite @ a @ Xs5 )
=> ( ? [Xs6: coinductive_llist @ a] :
( xs2
= ( coinductive_lappend @ a @ Xs5 @ ( coinductive_LCons @ a @ x @ Xs6 ) ) )
=> ( member @ a @ x @ ( coinductive_lset @ a @ Xs5 ) ) ) ) ).
% \<open>\<And>thesis. (\<And>xs' xs''. \<lbrakk>lfinite xs'; xs = lappend xs' (LCons x xs''); x \<notin> lset xs'\<rbrakk> \<Longrightarrow> thesis) \<Longrightarrow> thesis\<close>
thf(fact_36_lset__llist__of,axiom,
! [A: $tType,Xs: list @ A] :
( ( coinductive_lset @ A @ ( coinductive_llist_of @ A @ Xs ) )
= ( set2 @ A @ Xs ) ) ).
% lset_llist_of
thf(fact_37_in__lset__lappend__iff,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) ) )
= ( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
| ( ( coinductive_lfinite @ A @ Xs )
& ( member @ A @ X @ ( coinductive_lset @ A @ Ys ) ) ) ) ) ).
% in_lset_lappend_iff
thf(fact_38_lfinite__LConsI,axiom,
! [A: $tType,Xs: coinductive_llist @ A,X: A] :
( ( coinductive_lfinite @ A @ Xs )
=> ( coinductive_lfinite @ A @ ( coinductive_LCons @ A @ X @ Xs ) ) ) ).
% lfinite_LConsI
thf(fact_39_lfinite__LNil,axiom,
! [A: $tType] : ( coinductive_lfinite @ A @ ( coinductive_LNil @ A ) ) ).
% lfinite_LNil
thf(fact_40_llist_Oset__induct,axiom,
! [A: $tType,X: A,A2: coinductive_llist @ A,P: A > ( coinductive_llist @ A ) > $o] :
( ( member @ A @ X @ ( coinductive_lset @ A @ A2 ) )
=> ( ! [Z1: A,Z2: coinductive_llist @ A] : ( P @ Z1 @ ( coinductive_LCons @ A @ Z1 @ Z2 ) )
=> ( ! [Z1: A,Z2: coinductive_llist @ A,Xa3: A] :
( ( member @ A @ Xa3 @ ( coinductive_lset @ A @ Z2 ) )
=> ( ( P @ Xa3 @ Z2 )
=> ( P @ Xa3 @ ( coinductive_LCons @ A @ Z1 @ Z2 ) ) ) )
=> ( P @ X @ A2 ) ) ) ) ).
% llist.set_induct
thf(fact_41_llist_Oset__cases,axiom,
! [A: $tType,E: A,A2: coinductive_llist @ A] :
( ( member @ A @ E @ ( coinductive_lset @ A @ A2 ) )
=> ( ! [Z2: coinductive_llist @ A] :
( A2
!= ( coinductive_LCons @ A @ E @ Z2 ) )
=> ~ ! [Z1: A,Z2: coinductive_llist @ A] :
( ( A2
= ( coinductive_LCons @ A @ Z1 @ Z2 ) )
=> ~ ( member @ A @ E @ ( coinductive_lset @ A @ Z2 ) ) ) ) ) ).
% llist.set_cases
thf(fact_42_lset__induct_H,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A,P: ( coinductive_llist @ A ) > $o] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
=> ( ! [Xs2: coinductive_llist @ A] : ( P @ ( coinductive_LCons @ A @ X @ Xs2 ) )
=> ( ! [X5: A,Xs2: coinductive_llist @ A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs2 ) )
=> ( ( P @ Xs2 )
=> ( P @ ( coinductive_LCons @ A @ X5 @ Xs2 ) ) ) )
=> ( P @ Xs ) ) ) ) ).
% lset_induct'
thf(fact_43_lset__induct,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A,P: ( coinductive_llist @ A ) > $o] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
=> ( ! [Xs2: coinductive_llist @ A] : ( P @ ( coinductive_LCons @ A @ X @ Xs2 ) )
=> ( ! [X5: A,Xs2: coinductive_llist @ A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs2 ) )
=> ( ( X != X5 )
=> ( ( P @ Xs2 )
=> ( P @ ( coinductive_LCons @ A @ X5 @ Xs2 ) ) ) ) )
=> ( P @ Xs ) ) ) ) ).
% lset_induct
thf(fact_44_lset__cases,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
=> ( ! [Xs5: coinductive_llist @ A] :
( Xs
!= ( coinductive_LCons @ A @ X @ Xs5 ) )
=> ~ ! [X5: A,Xs5: coinductive_llist @ A] :
( ( Xs
= ( coinductive_LCons @ A @ X5 @ Xs5 ) )
=> ~ ( member @ A @ X @ ( coinductive_lset @ A @ Xs5 ) ) ) ) ) ).
% lset_cases
thf(fact_45_mem__Collect__eq,axiom,
! [A: $tType,A2: A,P: A > $o] :
( ( member @ A @ A2 @ ( collect @ A @ P ) )
= ( P @ A2 ) ) ).
% mem_Collect_eq
thf(fact_46_Collect__mem__eq,axiom,
! [A: $tType,A3: set @ A] :
( ( collect @ A
@ ^ [X3: A] : ( member @ A @ X3 @ A3 ) )
= A3 ) ).
% Collect_mem_eq
thf(fact_47_Collect__cong,axiom,
! [A: $tType,P: A > $o,Q: A > $o] :
( ! [X2: A] :
( ( P @ X2 )
= ( Q @ X2 ) )
=> ( ( collect @ A @ P )
= ( collect @ A @ Q ) ) ) ).
% Collect_cong
thf(fact_48_ext,axiom,
! [B: $tType,A: $tType,F: A > B,G: A > B] :
( ! [X2: A] :
( ( F @ X2 )
= ( G @ X2 ) )
=> ( F = G ) ) ).
% ext
thf(fact_49_llist_Oset__intros_I1_J,axiom,
! [A: $tType,A1: A,A22: coinductive_llist @ A] : ( member @ A @ A1 @ ( coinductive_lset @ A @ ( coinductive_LCons @ A @ A1 @ A22 ) ) ) ).
% llist.set_intros(1)
thf(fact_50_llist_Oset__intros_I2_J,axiom,
! [A: $tType,X: A,A22: coinductive_llist @ A,A1: A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ A22 ) )
=> ( member @ A @ X @ ( coinductive_lset @ A @ ( coinductive_LCons @ A @ A1 @ A22 ) ) ) ) ).
% llist.set_intros(2)
thf(fact_51_lset__intros_I1_J,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A] : ( member @ A @ X @ ( coinductive_lset @ A @ ( coinductive_LCons @ A @ X @ Xs ) ) ) ).
% lset_intros(1)
thf(fact_52_lset__intros_I2_J,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A,X6: A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
=> ( member @ A @ X @ ( coinductive_lset @ A @ ( coinductive_LCons @ A @ X6 @ Xs ) ) ) ) ).
% lset_intros(2)
thf(fact_53_lappend__inf,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ~ ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_lappend @ A @ Xs @ Ys )
= Xs ) ) ).
% lappend_inf
thf(fact_54_lfinite__llist__of,axiom,
! [A: $tType,Xs: list @ A] : ( coinductive_lfinite @ A @ ( coinductive_llist_of @ A @ Xs ) ) ).
% lfinite_llist_of
thf(fact_55_split__llist__first,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
=> ? [Ys2: coinductive_llist @ A,Zs: coinductive_llist @ A] :
( ( Xs
= ( coinductive_lappend @ A @ Ys2 @ ( coinductive_LCons @ A @ X @ Zs ) ) )
& ( coinductive_lfinite @ A @ Ys2 )
& ~ ( member @ A @ X @ ( coinductive_lset @ A @ Ys2 ) ) ) ) ).
% split_llist_first
thf(fact_56_split__llist,axiom,
! [A: $tType,X: A,Xs: coinductive_llist @ A] :
( ( member @ A @ X @ ( coinductive_lset @ A @ Xs ) )
=> ? [Ys2: coinductive_llist @ A,Zs: coinductive_llist @ A] :
( ( Xs
= ( coinductive_lappend @ A @ Ys2 @ ( coinductive_LCons @ A @ X @ Zs ) ) )
& ( coinductive_lfinite @ A @ Ys2 ) ) ) ).
% split_llist
thf(fact_57_lfinite_Oinducts,axiom,
! [A: $tType,X: coinductive_llist @ A,P: ( coinductive_llist @ A ) > $o] :
( ( coinductive_lfinite @ A @ X )
=> ( ( P @ ( coinductive_LNil @ A ) )
=> ( ! [Xs2: coinductive_llist @ A,X2: A] :
( ( coinductive_lfinite @ A @ Xs2 )
=> ( ( P @ Xs2 )
=> ( P @ ( coinductive_LCons @ A @ X2 @ Xs2 ) ) ) )
=> ( P @ X ) ) ) ) ).
% lfinite.inducts
thf(fact_58_lfinite_Osimps,axiom,
! [A: $tType] :
( ( coinductive_lfinite @ A )
= ( ^ [A4: coinductive_llist @ A] :
( ( A4
= ( coinductive_LNil @ A ) )
| ? [Xs3: coinductive_llist @ A,X3: A] :
( ( A4
= ( coinductive_LCons @ A @ X3 @ Xs3 ) )
& ( coinductive_lfinite @ A @ Xs3 ) ) ) ) ) ).
% lfinite.simps
thf(fact_59_lfinite_Ocases,axiom,
! [A: $tType,A2: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ A2 )
=> ( ( A2
!= ( coinductive_LNil @ A ) )
=> ~ ! [Xs2: coinductive_llist @ A] :
( ? [X2: A] :
( A2
= ( coinductive_LCons @ A @ X2 @ Xs2 ) )
=> ~ ( coinductive_lfinite @ A @ Xs2 ) ) ) ) ).
% lfinite.cases
thf(fact_60_lfinite__rev__induct,axiom,
! [A: $tType,Xs: coinductive_llist @ A,P: ( coinductive_llist @ A ) > $o] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( P @ ( coinductive_LNil @ A ) )
=> ( ! [X2: A,Xs2: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ Xs2 )
=> ( ( P @ Xs2 )
=> ( P @ ( coinductive_lappend @ A @ Xs2 @ ( coinductive_LCons @ A @ X2 @ ( coinductive_LNil @ A ) ) ) ) ) )
=> ( P @ Xs ) ) ) ) ).
% lfinite_rev_induct
thf(fact_61_paths__lappendD2,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A,Graph: A > A > $o] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( member @ ( coinductive_llist @ A ) @ ( coinductive_lappend @ A @ Xs @ Ys ) @ ( koenig916195507_paths @ A @ Graph ) )
=> ( member @ ( coinductive_llist @ A ) @ Ys @ ( koenig916195507_paths @ A @ Graph ) ) ) ) ).
% paths_lappendD2
thf(fact_62_lappend__assoc,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A,Zs2: coinductive_llist @ A] :
( ( coinductive_lappend @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) @ Zs2 )
= ( coinductive_lappend @ A @ Xs @ ( coinductive_lappend @ A @ Ys @ Zs2 ) ) ) ).
% lappend_assoc
thf(fact_63_llist__of__eq__LCons__conv,axiom,
! [A: $tType,Xs: list @ A,Y: A,Ys: coinductive_llist @ A] :
( ( ( coinductive_llist_of @ A @ Xs )
= ( coinductive_LCons @ A @ Y @ Ys ) )
= ( ? [Xs7: list @ A] :
( ( Xs
= ( cons @ A @ Y @ Xs7 ) )
& ( Ys
= ( coinductive_llist_of @ A @ Xs7 ) ) ) ) ) ).
% llist_of_eq_LCons_conv
thf(fact_64_llist__of_Osimps_I2_J,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( coinductive_llist_of @ A @ ( cons @ A @ X @ Xs ) )
= ( coinductive_LCons @ A @ X @ ( coinductive_llist_of @ A @ Xs ) ) ) ).
% llist_of.simps(2)
thf(fact_65_lappend__llist__of__llist__of,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( coinductive_lappend @ A @ ( coinductive_llist_of @ A @ Xs ) @ ( coinductive_llist_of @ A @ Ys ) )
= ( coinductive_llist_of @ A @ ( append @ A @ Xs @ Ys ) ) ) ).
% lappend_llist_of_llist_of
thf(fact_66_neq__LNil__conv,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ( Xs
!= ( coinductive_LNil @ A ) )
= ( ? [X3: A,Xs7: coinductive_llist @ A] :
( Xs
= ( coinductive_LCons @ A @ X3 @ Xs7 ) ) ) ) ).
% neq_LNil_conv
thf(fact_67_llist_Oexhaust,axiom,
! [A: $tType,Y: coinductive_llist @ A] :
( ( Y
!= ( coinductive_LNil @ A ) )
=> ~ ! [X212: A,X222: coinductive_llist @ A] :
( Y
!= ( coinductive_LCons @ A @ X212 @ X222 ) ) ) ).
% llist.exhaust
thf(fact_68_llist_Odistinct_I1_J,axiom,
! [A: $tType,X21: A,X22: coinductive_llist @ A] :
( ( coinductive_LNil @ A )
!= ( coinductive_LCons @ A @ X21 @ X22 ) ) ).
% llist.distinct(1)
thf(fact_69_lappend__eq__LNil__iff,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( ( coinductive_lappend @ A @ Xs @ Ys )
= ( coinductive_LNil @ A ) )
= ( ( Xs
= ( coinductive_LNil @ A ) )
& ( Ys
= ( coinductive_LNil @ A ) ) ) ) ).
% lappend_eq_LNil_iff
thf(fact_70_split__list,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
=> ? [Ys2: list @ A,Zs: list @ A] :
( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X @ Zs ) ) ) ) ).
% split_list
thf(fact_71_split__list__last,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
=> ? [Ys2: list @ A,Zs: list @ A] :
( ( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X @ Zs ) ) )
& ~ ( member @ A @ X @ ( set2 @ A @ Zs ) ) ) ) ).
% split_list_last
thf(fact_72_split__list__prop,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ? [X7: A] :
( ( member @ A @ X7 @ ( set2 @ A @ Xs ) )
& ( P @ X7 ) )
=> ? [Ys2: list @ A,X2: A] :
( ? [Zs: list @ A] :
( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X2 @ Zs ) ) )
& ( P @ X2 ) ) ) ).
% split_list_prop
thf(fact_73_split__list__first,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
=> ? [Ys2: list @ A,Zs: list @ A] :
( ( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X @ Zs ) ) )
& ~ ( member @ A @ X @ ( set2 @ A @ Ys2 ) ) ) ) ).
% split_list_first
thf(fact_74_split__list__propE,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ? [X7: A] :
( ( member @ A @ X7 @ ( set2 @ A @ Xs ) )
& ( P @ X7 ) )
=> ~ ! [Ys2: list @ A,X2: A] :
( ? [Zs: list @ A] :
( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X2 @ Zs ) ) )
=> ~ ( P @ X2 ) ) ) ).
% split_list_propE
thf(fact_75_in__set__conv__decomp,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
= ( ? [Ys3: list @ A,Zs3: list @ A] :
( Xs
= ( append @ A @ Ys3 @ ( cons @ A @ X @ Zs3 ) ) ) ) ) ).
% in_set_conv_decomp
thf(fact_76_split__list__last__prop,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ? [X7: A] :
( ( member @ A @ X7 @ ( set2 @ A @ Xs ) )
& ( P @ X7 ) )
=> ? [Ys2: list @ A,X2: A,Zs: list @ A] :
( ( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X2 @ Zs ) ) )
& ( P @ X2 )
& ! [Xa: A] :
( ( member @ A @ Xa @ ( set2 @ A @ Zs ) )
=> ~ ( P @ Xa ) ) ) ) ).
% split_list_last_prop
thf(fact_77_split__list__first__prop,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ? [X7: A] :
( ( member @ A @ X7 @ ( set2 @ A @ Xs ) )
& ( P @ X7 ) )
=> ? [Ys2: list @ A,X2: A] :
( ? [Zs: list @ A] :
( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X2 @ Zs ) ) )
& ( P @ X2 )
& ! [Xa: A] :
( ( member @ A @ Xa @ ( set2 @ A @ Ys2 ) )
=> ~ ( P @ Xa ) ) ) ) ).
% split_list_first_prop
thf(fact_78_split__list__last__propE,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ? [X7: A] :
( ( member @ A @ X7 @ ( set2 @ A @ Xs ) )
& ( P @ X7 ) )
=> ~ ! [Ys2: list @ A,X2: A,Zs: list @ A] :
( ( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X2 @ Zs ) ) )
=> ( ( P @ X2 )
=> ~ ! [Xa: A] :
( ( member @ A @ Xa @ ( set2 @ A @ Zs ) )
=> ~ ( P @ Xa ) ) ) ) ) ).
% split_list_last_propE
thf(fact_79_list_Oinject,axiom,
! [A: $tType,X21: A,X22: list @ A,Y21: A,Y22: list @ A] :
( ( ( cons @ A @ X21 @ X22 )
= ( cons @ A @ Y21 @ Y22 ) )
= ( ( X21 = Y21 )
& ( X22 = Y22 ) ) ) ).
% list.inject
thf(fact_80_same__append__eq,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A,Zs2: list @ A] :
( ( ( append @ A @ Xs @ Ys )
= ( append @ A @ Xs @ Zs2 ) )
= ( Ys = Zs2 ) ) ).
% same_append_eq
thf(fact_81_append__same__eq,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ A,Zs2: list @ A] :
( ( ( append @ A @ Ys @ Xs )
= ( append @ A @ Zs2 @ Xs ) )
= ( Ys = Zs2 ) ) ).
% append_same_eq
thf(fact_82_append__assoc,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A,Zs2: list @ A] :
( ( append @ A @ ( append @ A @ Xs @ Ys ) @ Zs2 )
= ( append @ A @ Xs @ ( append @ A @ Ys @ Zs2 ) ) ) ).
% append_assoc
thf(fact_83_not__Cons__self2,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( cons @ A @ X @ Xs )
!= Xs ) ).
% not_Cons_self2
thf(fact_84_append__eq__append__conv2,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A,Zs2: list @ A,Ts: list @ A] :
( ( ( append @ A @ Xs @ Ys )
= ( append @ A @ Zs2 @ Ts ) )
= ( ? [Us: list @ A] :
( ( ( Xs
= ( append @ A @ Zs2 @ Us ) )
& ( ( append @ A @ Us @ Ys )
= Ts ) )
| ( ( ( append @ A @ Xs @ Us )
= Zs2 )
& ( Ys
= ( append @ A @ Us @ Ts ) ) ) ) ) ) ).
% append_eq_append_conv2
thf(fact_85_append__eq__appendI,axiom,
! [A: $tType,Xs: list @ A,Xs1: list @ A,Zs2: list @ A,Ys: list @ A,Us2: list @ A] :
( ( ( append @ A @ Xs @ Xs1 )
= Zs2 )
=> ( ( Ys
= ( append @ A @ Xs1 @ Us2 ) )
=> ( ( append @ A @ Xs @ Ys )
= ( append @ A @ Zs2 @ Us2 ) ) ) ) ).
% append_eq_appendI
thf(fact_86_list_Oset__cases,axiom,
! [A: $tType,E: A,A2: list @ A] :
( ( member @ A @ E @ ( set2 @ A @ A2 ) )
=> ( ! [Z2: list @ A] :
( A2
!= ( cons @ A @ E @ Z2 ) )
=> ~ ! [Z1: A,Z2: list @ A] :
( ( A2
= ( cons @ A @ Z1 @ Z2 ) )
=> ~ ( member @ A @ E @ ( set2 @ A @ Z2 ) ) ) ) ) ).
% list.set_cases
thf(fact_87_set__ConsD,axiom,
! [A: $tType,Y: A,X: A,Xs: list @ A] :
( ( member @ A @ Y @ ( set2 @ A @ ( cons @ A @ X @ Xs ) ) )
=> ( ( Y = X )
| ( member @ A @ Y @ ( set2 @ A @ Xs ) ) ) ) ).
% set_ConsD
thf(fact_88_list_Oset__intros_I1_J,axiom,
! [A: $tType,A1: A,A22: list @ A] : ( member @ A @ A1 @ ( set2 @ A @ ( cons @ A @ A1 @ A22 ) ) ) ).
% list.set_intros(1)
thf(fact_89_list_Oset__intros_I2_J,axiom,
! [A: $tType,X: A,A22: list @ A,A1: A] :
( ( member @ A @ X @ ( set2 @ A @ A22 ) )
=> ( member @ A @ X @ ( set2 @ A @ ( cons @ A @ A1 @ A22 ) ) ) ) ).
% list.set_intros(2)
thf(fact_90_append__Cons,axiom,
! [A: $tType,X: A,Xs: list @ A,Ys: list @ A] :
( ( append @ A @ ( cons @ A @ X @ Xs ) @ Ys )
= ( cons @ A @ X @ ( append @ A @ Xs @ Ys ) ) ) ).
% append_Cons
thf(fact_91_Cons__eq__appendI,axiom,
! [A: $tType,X: A,Xs1: list @ A,Ys: list @ A,Xs: list @ A,Zs2: list @ A] :
( ( ( cons @ A @ X @ Xs1 )
= Ys )
=> ( ( Xs
= ( append @ A @ Xs1 @ Zs2 ) )
=> ( ( cons @ A @ X @ Xs )
= ( append @ A @ Ys @ Zs2 ) ) ) ) ).
% Cons_eq_appendI
thf(fact_92_split__list__first__prop__iff,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ( ? [X3: A] :
( ( member @ A @ X3 @ ( set2 @ A @ Xs ) )
& ( P @ X3 ) ) )
= ( ? [Ys3: list @ A,X3: A] :
( ? [Zs3: list @ A] :
( Xs
= ( append @ A @ Ys3 @ ( cons @ A @ X3 @ Zs3 ) ) )
& ( P @ X3 )
& ! [Y3: A] :
( ( member @ A @ Y3 @ ( set2 @ A @ Ys3 ) )
=> ~ ( P @ Y3 ) ) ) ) ) ).
% split_list_first_prop_iff
thf(fact_93_split__list__last__prop__iff,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ( ? [X3: A] :
( ( member @ A @ X3 @ ( set2 @ A @ Xs ) )
& ( P @ X3 ) ) )
= ( ? [Ys3: list @ A,X3: A,Zs3: list @ A] :
( ( Xs
= ( append @ A @ Ys3 @ ( cons @ A @ X3 @ Zs3 ) ) )
& ( P @ X3 )
& ! [Y3: A] :
( ( member @ A @ Y3 @ ( set2 @ A @ Zs3 ) )
=> ~ ( P @ Y3 ) ) ) ) ) ).
% split_list_last_prop_iff
thf(fact_94_in__set__conv__decomp__first,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
= ( ? [Ys3: list @ A,Zs3: list @ A] :
( ( Xs
= ( append @ A @ Ys3 @ ( cons @ A @ X @ Zs3 ) ) )
& ~ ( member @ A @ X @ ( set2 @ A @ Ys3 ) ) ) ) ) ).
% in_set_conv_decomp_first
thf(fact_95_in__set__conv__decomp__last,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
= ( ? [Ys3: list @ A,Zs3: list @ A] :
( ( Xs
= ( append @ A @ Ys3 @ ( cons @ A @ X @ Zs3 ) ) )
& ~ ( member @ A @ X @ ( set2 @ A @ Zs3 ) ) ) ) ) ).
% in_set_conv_decomp_last
thf(fact_96_split__list__first__propE,axiom,
! [A: $tType,Xs: list @ A,P: A > $o] :
( ? [X7: A] :
( ( member @ A @ X7 @ ( set2 @ A @ Xs ) )
& ( P @ X7 ) )
=> ~ ! [Ys2: list @ A,X2: A] :
( ? [Zs: list @ A] :
( Xs
= ( append @ A @ Ys2 @ ( cons @ A @ X2 @ Zs ) ) )
=> ( ( P @ X2 )
=> ~ ! [Xa: A] :
( ( member @ A @ Xa @ ( set2 @ A @ Ys2 ) )
=> ~ ( P @ Xa ) ) ) ) ) ).
% split_list_first_propE
thf(fact_97_bind__simps_I2_J,axiom,
! [A: $tType,B: $tType,X: B,Xs: list @ B,F: B > ( list @ A )] :
( ( bind @ B @ A @ ( cons @ B @ X @ Xs ) @ F )
= ( append @ A @ ( F @ X ) @ ( bind @ B @ A @ Xs @ F ) ) ) ).
% bind_simps(2)
thf(fact_98_llast__lappend__LCons,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Y: A,Ys: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_llast @ A @ ( coinductive_lappend @ A @ Xs @ ( coinductive_LCons @ A @ Y @ Ys ) ) )
= ( coinductive_llast @ A @ ( coinductive_LCons @ A @ Y @ Ys ) ) ) ) ).
% llast_lappend_LCons
thf(fact_99_lappend__llist__of__LCons,axiom,
! [A: $tType,Xs: list @ A,Y: A,Ys: coinductive_llist @ A] :
( ( coinductive_lappend @ A @ ( coinductive_llist_of @ A @ Xs ) @ ( coinductive_LCons @ A @ Y @ Ys ) )
= ( coinductive_lappend @ A @ ( coinductive_llist_of @ A @ ( append @ A @ Xs @ ( cons @ A @ Y @ ( nil @ A ) ) ) ) @ Ys ) ) ).
% lappend_llist_of_LCons
thf(fact_100_list__of__aux__code_I2_J,axiom,
! [A: $tType,Xs: list @ A,Y: A,Ys: coinductive_llist @ A] :
( ( coindu1384447384of_aux @ A @ Xs @ ( coinductive_LCons @ A @ Y @ Ys ) )
= ( coindu1384447384of_aux @ A @ ( cons @ A @ Y @ Xs ) @ Ys ) ) ).
% list_of_aux_code(2)
thf(fact_101_llimit__induct,axiom,
! [A: $tType,P: ( coinductive_llist @ A ) > $o,Xs: coinductive_llist @ A] :
( ( P @ ( coinductive_LNil @ A ) )
=> ( ! [X2: A,Xs2: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ Xs2 )
=> ( ( P @ Xs2 )
=> ( P @ ( coinductive_LCons @ A @ X2 @ Xs2 ) ) ) )
=> ( ( ! [Ys4: coinductive_llist @ A] :
( ( coindu1478340336prefix @ A @ Ys4 @ Xs )
=> ( P @ Ys4 ) )
=> ( P @ Xs ) )
=> ( P @ Xs ) ) ) ) ).
% llimit_induct
thf(fact_102_set__list__of,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( set2 @ A @ ( coinductive_list_of @ A @ Xs ) )
= ( coinductive_lset @ A @ Xs ) ) ) ).
% set_list_of
thf(fact_103_append__Nil2,axiom,
! [A: $tType,Xs: list @ A] :
( ( append @ A @ Xs @ ( nil @ A ) )
= Xs ) ).
% append_Nil2
thf(fact_104_append__self__conv,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( append @ A @ Xs @ Ys )
= Xs )
= ( Ys
= ( nil @ A ) ) ) ).
% append_self_conv
thf(fact_105_self__append__conv,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( Xs
= ( append @ A @ Xs @ Ys ) )
= ( Ys
= ( nil @ A ) ) ) ).
% self_append_conv
thf(fact_106_append__self__conv2,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( append @ A @ Xs @ Ys )
= Ys )
= ( Xs
= ( nil @ A ) ) ) ).
% append_self_conv2
thf(fact_107_self__append__conv2,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ A] :
( ( Ys
= ( append @ A @ Xs @ Ys ) )
= ( Xs
= ( nil @ A ) ) ) ).
% self_append_conv2
thf(fact_108_Nil__is__append__conv,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( nil @ A )
= ( append @ A @ Xs @ Ys ) )
= ( ( Xs
= ( nil @ A ) )
& ( Ys
= ( nil @ A ) ) ) ) ).
% Nil_is_append_conv
thf(fact_109_append__is__Nil__conv,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( append @ A @ Xs @ Ys )
= ( nil @ A ) )
= ( ( Xs
= ( nil @ A ) )
& ( Ys
= ( nil @ A ) ) ) ) ).
% append_is_Nil_conv
thf(fact_110_llast__LCons2,axiom,
! [A: $tType,X: A,Y: A,Xs: coinductive_llist @ A] :
( ( coinductive_llast @ A @ ( coinductive_LCons @ A @ X @ ( coinductive_LCons @ A @ Y @ Xs ) ) )
= ( coinductive_llast @ A @ ( coinductive_LCons @ A @ Y @ Xs ) ) ) ).
% llast_LCons2
thf(fact_111_list__of__llist__of,axiom,
! [A: $tType,Xs: list @ A] :
( ( coinductive_list_of @ A @ ( coinductive_llist_of @ A @ Xs ) )
= Xs ) ).
% list_of_llist_of
thf(fact_112_lstrict__prefix__code_I4_J,axiom,
! [B: $tType,X: B,Xs: coinductive_llist @ B,Y: B,Ys: coinductive_llist @ B] :
( ( coindu1478340336prefix @ B @ ( coinductive_LCons @ B @ X @ Xs ) @ ( coinductive_LCons @ B @ Y @ Ys ) )
= ( ( X = Y )
& ( coindu1478340336prefix @ B @ Xs @ Ys ) ) ) ).
% lstrict_prefix_code(4)
thf(fact_113_lstrict__prefix__code_I1_J,axiom,
! [A: $tType] :
~ ( coindu1478340336prefix @ A @ ( coinductive_LNil @ A ) @ ( coinductive_LNil @ A ) ) ).
% lstrict_prefix_code(1)
thf(fact_114_bind__simps_I1_J,axiom,
! [B: $tType,A: $tType,F: B > ( list @ A )] :
( ( bind @ B @ A @ ( nil @ B ) @ F )
= ( nil @ A ) ) ).
% bind_simps(1)
thf(fact_115_append1__eq__conv,axiom,
! [A: $tType,Xs: list @ A,X: A,Ys: list @ A,Y: A] :
( ( ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) )
= ( append @ A @ Ys @ ( cons @ A @ Y @ ( nil @ A ) ) ) )
= ( ( Xs = Ys )
& ( X = Y ) ) ) ).
% append1_eq_conv
thf(fact_116_list__of__LNil,axiom,
! [A: $tType] :
( ( coinductive_list_of @ A @ ( coinductive_LNil @ A ) )
= ( nil @ A ) ) ).
% list_of_LNil
thf(fact_117_llast__singleton,axiom,
! [A: $tType,X: A] :
( ( coinductive_llast @ A @ ( coinductive_LCons @ A @ X @ ( coinductive_LNil @ A ) ) )
= X ) ).
% llast_singleton
thf(fact_118_lstrict__prefix__code_I2_J,axiom,
! [B: $tType,Y: B,Ys: coinductive_llist @ B] : ( coindu1478340336prefix @ B @ ( coinductive_LNil @ B ) @ ( coinductive_LCons @ B @ Y @ Ys ) ) ).
% lstrict_prefix_code(2)
thf(fact_119_lstrict__prefix__code_I3_J,axiom,
! [B: $tType,X: B,Xs: coinductive_llist @ B] :
~ ( coindu1478340336prefix @ B @ ( coinductive_LCons @ B @ X @ Xs ) @ ( coinductive_LNil @ B ) ) ).
% lstrict_prefix_code(3)
thf(fact_120_llist__of__list__of,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_llist_of @ A @ ( coinductive_list_of @ A @ Xs ) )
= Xs ) ) ).
% llist_of_list_of
thf(fact_121_list__of__LCons,axiom,
! [A: $tType,Xs: coinductive_llist @ A,X: A] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_list_of @ A @ ( coinductive_LCons @ A @ X @ Xs ) )
= ( cons @ A @ X @ ( coinductive_list_of @ A @ Xs ) ) ) ) ).
% list_of_LCons
thf(fact_122_transpose_Ocases,axiom,
! [A: $tType,X: list @ ( list @ A )] :
( ( X
!= ( nil @ ( list @ A ) ) )
=> ( ! [Xss: list @ ( list @ A )] :
( X
!= ( cons @ ( list @ A ) @ ( nil @ A ) @ Xss ) )
=> ~ ! [X2: A,Xs2: list @ A,Xss: list @ ( list @ A )] :
( X
!= ( cons @ ( list @ A ) @ ( cons @ A @ X2 @ Xs2 ) @ Xss ) ) ) ) ).
% transpose.cases
thf(fact_123_llist__less__induct,axiom,
! [A: $tType,P: ( coinductive_llist @ A ) > $o,Xs: coinductive_llist @ A] :
( ! [Xs2: coinductive_llist @ A] :
( ! [Ys4: coinductive_llist @ A] :
( ( coindu1478340336prefix @ A @ Ys4 @ Xs2 )
=> ( P @ Ys4 ) )
=> ( P @ Xs2 ) )
=> ( P @ Xs ) ) ).
% llist_less_induct
thf(fact_124_list__of__code,axiom,
! [A: $tType] :
( ( coinductive_list_of @ A )
= ( coindu1384447384of_aux @ A @ ( nil @ A ) ) ) ).
% list_of_code
thf(fact_125_list_Odistinct_I1_J,axiom,
! [A: $tType,X21: A,X22: list @ A] :
( ( nil @ A )
!= ( cons @ A @ X21 @ X22 ) ) ).
% list.distinct(1)
thf(fact_126_list_OdiscI,axiom,
! [A: $tType,List: list @ A,X21: A,X22: list @ A] :
( ( List
= ( cons @ A @ X21 @ X22 ) )
=> ( List
!= ( nil @ A ) ) ) ).
% list.discI
thf(fact_127_list_Oexhaust,axiom,
! [A: $tType,Y: list @ A] :
( ( Y
!= ( nil @ A ) )
=> ~ ! [X212: A,X222: list @ A] :
( Y
!= ( cons @ A @ X212 @ X222 ) ) ) ).
% list.exhaust
thf(fact_128_list_Oinducts,axiom,
! [A: $tType,P: ( list @ A ) > $o,List: list @ A] :
( ( P @ ( nil @ A ) )
=> ( ! [X1: A,X23: list @ A] :
( ( P @ X23 )
=> ( P @ ( cons @ A @ X1 @ X23 ) ) )
=> ( P @ List ) ) ) ).
% list.inducts
thf(fact_129_neq__Nil__conv,axiom,
! [A: $tType,Xs: list @ A] :
( ( Xs
!= ( nil @ A ) )
= ( ? [Y3: A,Ys3: list @ A] :
( Xs
= ( cons @ A @ Y3 @ Ys3 ) ) ) ) ).
% neq_Nil_conv
thf(fact_130_list__induct2_H,axiom,
! [A: $tType,B: $tType,P: ( list @ A ) > ( list @ B ) > $o,Xs: list @ A,Ys: list @ B] :
( ( P @ ( nil @ A ) @ ( nil @ B ) )
=> ( ! [X2: A,Xs2: list @ A] : ( P @ ( cons @ A @ X2 @ Xs2 ) @ ( nil @ B ) )
=> ( ! [Y2: B,Ys2: list @ B] : ( P @ ( nil @ A ) @ ( cons @ B @ Y2 @ Ys2 ) )
=> ( ! [X2: A,Xs2: list @ A,Y2: B,Ys2: list @ B] :
( ( P @ Xs2 @ Ys2 )
=> ( P @ ( cons @ A @ X2 @ Xs2 ) @ ( cons @ B @ Y2 @ Ys2 ) ) )
=> ( P @ Xs @ Ys ) ) ) ) ) ).
% list_induct2'
thf(fact_131_splice_Oinduct,axiom,
! [A: $tType,P: ( list @ A ) > ( list @ A ) > $o,A0: list @ A,A1: list @ A] :
( ! [X1: list @ A] : ( P @ ( nil @ A ) @ X1 )
=> ( ! [V: A,Va: list @ A] : ( P @ ( cons @ A @ V @ Va ) @ ( nil @ A ) )
=> ( ! [X2: A,Xs2: list @ A,Y2: A,Ys2: list @ A] :
( ( P @ Xs2 @ Ys2 )
=> ( P @ ( cons @ A @ X2 @ Xs2 ) @ ( cons @ A @ Y2 @ Ys2 ) ) )
=> ( P @ A0 @ A1 ) ) ) ) ).
% splice.induct
thf(fact_132_remdups__adj_Ocases,axiom,
! [A: $tType,X: list @ A] :
( ( X
!= ( nil @ A ) )
=> ( ! [X2: A] :
( X
!= ( cons @ A @ X2 @ ( nil @ A ) ) )
=> ~ ! [X2: A,Y2: A,Xs2: list @ A] :
( X
!= ( cons @ A @ X2 @ ( cons @ A @ Y2 @ Xs2 ) ) ) ) ) ).
% remdups_adj.cases
thf(fact_133_remdups__adj_Oinduct,axiom,
! [A: $tType,P: ( list @ A ) > $o,A0: list @ A] :
( ( P @ ( nil @ A ) )
=> ( ! [X2: A] : ( P @ ( cons @ A @ X2 @ ( nil @ A ) ) )
=> ( ! [X2: A,Y2: A,Xs2: list @ A] :
( ( ( X2 = Y2 )
=> ( P @ ( cons @ A @ X2 @ Xs2 ) ) )
=> ( ( ( X2 != Y2 )
=> ( P @ ( cons @ A @ Y2 @ Xs2 ) ) )
=> ( P @ ( cons @ A @ X2 @ ( cons @ A @ Y2 @ Xs2 ) ) ) ) )
=> ( P @ A0 ) ) ) ) ).
% remdups_adj.induct
thf(fact_134_list__nonempty__induct,axiom,
! [A: $tType,Xs: list @ A,P: ( list @ A ) > $o] :
( ( Xs
!= ( nil @ A ) )
=> ( ! [X2: A] : ( P @ ( cons @ A @ X2 @ ( nil @ A ) ) )
=> ( ! [X2: A,Xs2: list @ A] :
( ( Xs2
!= ( nil @ A ) )
=> ( ( P @ Xs2 )
=> ( P @ ( cons @ A @ X2 @ Xs2 ) ) ) )
=> ( P @ Xs ) ) ) ) ).
% list_nonempty_induct
thf(fact_135_map__tailrec__rev_Oinduct,axiom,
! [A: $tType,B: $tType,P: ( A > B ) > ( list @ A ) > ( list @ B ) > $o,A0: A > B,A1: list @ A,A22: list @ B] :
( ! [F2: A > B,X1: list @ B] : ( P @ F2 @ ( nil @ A ) @ X1 )
=> ( ! [F2: A > B,A5: A,As: list @ A,Bs: list @ B] :
( ( P @ F2 @ As @ ( cons @ B @ ( F2 @ A5 ) @ Bs ) )
=> ( P @ F2 @ ( cons @ A @ A5 @ As ) @ Bs ) )
=> ( P @ A0 @ A1 @ A22 ) ) ) ).
% map_tailrec_rev.induct
thf(fact_136_eq__Nil__appendI,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( Xs = Ys )
=> ( Xs
= ( append @ A @ ( nil @ A ) @ Ys ) ) ) ).
% eq_Nil_appendI
thf(fact_137_append__Nil,axiom,
! [A: $tType,Ys: list @ A] :
( ( append @ A @ ( nil @ A ) @ Ys )
= Ys ) ).
% append_Nil
thf(fact_138_lstrict__prefix__lfinite1,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coindu1478340336prefix @ A @ Xs @ Ys )
=> ( coinductive_lfinite @ A @ Xs ) ) ).
% lstrict_prefix_lfinite1
thf(fact_139_rev__induct,axiom,
! [A: $tType,P: ( list @ A ) > $o,Xs: list @ A] :
( ( P @ ( nil @ A ) )
=> ( ! [X2: A,Xs2: list @ A] :
( ( P @ Xs2 )
=> ( P @ ( append @ A @ Xs2 @ ( cons @ A @ X2 @ ( nil @ A ) ) ) ) )
=> ( P @ Xs ) ) ) ).
% rev_induct
thf(fact_140_rev__exhaust,axiom,
! [A: $tType,Xs: list @ A] :
( ( Xs
!= ( nil @ A ) )
=> ~ ! [Ys2: list @ A,Y2: A] :
( Xs
!= ( append @ A @ Ys2 @ ( cons @ A @ Y2 @ ( nil @ A ) ) ) ) ) ).
% rev_exhaust
thf(fact_141_Cons__eq__append__conv,axiom,
! [A: $tType,X: A,Xs: list @ A,Ys: list @ A,Zs2: list @ A] :
( ( ( cons @ A @ X @ Xs )
= ( append @ A @ Ys @ Zs2 ) )
= ( ( ( Ys
= ( nil @ A ) )
& ( ( cons @ A @ X @ Xs )
= Zs2 ) )
| ? [Ys5: list @ A] :
( ( ( cons @ A @ X @ Ys5 )
= Ys )
& ( Xs
= ( append @ A @ Ys5 @ Zs2 ) ) ) ) ) ).
% Cons_eq_append_conv
thf(fact_142_append__eq__Cons__conv,axiom,
! [A: $tType,Ys: list @ A,Zs2: list @ A,X: A,Xs: list @ A] :
( ( ( append @ A @ Ys @ Zs2 )
= ( cons @ A @ X @ Xs ) )
= ( ( ( Ys
= ( nil @ A ) )
& ( Zs2
= ( cons @ A @ X @ Xs ) ) )
| ? [Ys5: list @ A] :
( ( Ys
= ( cons @ A @ X @ Ys5 ) )
& ( ( append @ A @ Ys5 @ Zs2 )
= Xs ) ) ) ) ).
% append_eq_Cons_conv
thf(fact_143_rev__nonempty__induct,axiom,
! [A: $tType,Xs: list @ A,P: ( list @ A ) > $o] :
( ( Xs
!= ( nil @ A ) )
=> ( ! [X2: A] : ( P @ ( cons @ A @ X2 @ ( nil @ A ) ) )
=> ( ! [X2: A,Xs2: list @ A] :
( ( Xs2
!= ( nil @ A ) )
=> ( ( P @ Xs2 )
=> ( P @ ( append @ A @ Xs2 @ ( cons @ A @ X2 @ ( nil @ A ) ) ) ) ) )
=> ( P @ Xs ) ) ) ) ).
% rev_nonempty_induct
thf(fact_144_llist__of__eq__LNil__conv,axiom,
! [A: $tType,Xs: list @ A] :
( ( ( coinductive_llist_of @ A @ Xs )
= ( coinductive_LNil @ A ) )
= ( Xs
= ( nil @ A ) ) ) ).
% llist_of_eq_LNil_conv
thf(fact_145_llist__of_Osimps_I1_J,axiom,
! [A: $tType] :
( ( coinductive_llist_of @ A @ ( nil @ A ) )
= ( coinductive_LNil @ A ) ) ).
% llist_of.simps(1)
thf(fact_146_list__bind__cong,axiom,
! [B: $tType,A: $tType,Xs: list @ A,Ys: list @ A,F: A > ( list @ B ),G: A > ( list @ B )] :
( ( Xs = Ys )
=> ( ! [X2: A] :
( ( member @ A @ X2 @ ( set2 @ A @ Xs ) )
=> ( ( F @ X2 )
= ( G @ X2 ) ) )
=> ( ( bind @ A @ B @ Xs @ F )
= ( bind @ A @ B @ Ys @ G ) ) ) ) ).
% list_bind_cong
thf(fact_147_list__of__lappend,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_lfinite @ A @ Ys )
=> ( ( coinductive_list_of @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( append @ A @ ( coinductive_list_of @ A @ Xs ) @ ( coinductive_list_of @ A @ Ys ) ) ) ) ) ).
% list_of_lappend
thf(fact_148_Koenigslemma__Mirabelle__aepjeeakgn_Oconnected__def,axiom,
! [Node: $tType] :
( ( koenig793108494nected @ Node )
= ( ^ [Graph2: Node > Node > $o] :
! [N: Node,N2: Node] :
? [Xs3: list @ Node] : ( member @ ( coinductive_llist @ Node ) @ ( coinductive_llist_of @ Node @ ( cons @ Node @ N @ ( append @ Node @ Xs3 @ ( cons @ Node @ N2 @ ( nil @ Node ) ) ) ) ) @ ( koenig916195507_paths @ Node @ Graph2 ) ) ) ) ).
% Koenigslemma_Mirabelle_aepjeeakgn.connected_def
thf(fact_149_Koenigslemma__Mirabelle__aepjeeakgn_OconnectedD,axiom,
! [A: $tType,Graph: A > A > $o,N3: A,N4: A] :
( ( koenig793108494nected @ A @ Graph )
=> ? [Xs2: list @ A] : ( member @ ( coinductive_llist @ A ) @ ( coinductive_llist_of @ A @ ( cons @ A @ N3 @ ( append @ A @ Xs2 @ ( cons @ A @ N4 @ ( nil @ A ) ) ) ) ) @ ( koenig916195507_paths @ A @ Graph ) ) ) ).
% Koenigslemma_Mirabelle_aepjeeakgn.connectedD
thf(fact_150_the__elem__set,axiom,
! [A: $tType,X: A] :
( ( the_elem @ A @ ( set2 @ A @ ( cons @ A @ X @ ( nil @ A ) ) ) )
= X ) ).
% the_elem_set
thf(fact_151_longest__common__prefix_Oinduct,axiom,
! [A: $tType,P: ( list @ A ) > ( list @ A ) > $o,A0: list @ A,A1: list @ A] :
( ! [X2: A,Xs2: list @ A,Y2: A,Ys2: list @ A] :
( ( ( X2 = Y2 )
=> ( P @ Xs2 @ Ys2 ) )
=> ( P @ ( cons @ A @ X2 @ Xs2 ) @ ( cons @ A @ Y2 @ Ys2 ) ) )
=> ( ! [X1: list @ A] : ( P @ ( nil @ A ) @ X1 )
=> ( ! [Uu: list @ A] : ( P @ Uu @ ( nil @ A ) )
=> ( P @ A0 @ A1 ) ) ) ) ).
% longest_common_prefix.induct
thf(fact_152_prefixes_Oinduct,axiom,
! [A: $tType,P: ( list @ A ) > $o,A0: list @ A] :
( ( P @ ( nil @ A ) )
=> ( ! [X2: A,Xs2: list @ A] :
( ( P @ Xs2 )
=> ( P @ ( cons @ A @ X2 @ Xs2 ) ) )
=> ( P @ A0 ) ) ) ).
% prefixes.induct
thf(fact_153_prefixes_Ocases,axiom,
! [A: $tType,X: list @ A] :
( ( X
!= ( nil @ A ) )
=> ~ ! [X2: A,Xs2: list @ A] :
( X
!= ( cons @ A @ X2 @ Xs2 ) ) ) ).
% prefixes.cases
thf(fact_154_prefixes__snoc,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( prefixes @ A @ ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) ) )
= ( append @ ( list @ A ) @ ( prefixes @ A @ Xs ) @ ( cons @ ( list @ A ) @ ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) ) @ ( nil @ ( list @ A ) ) ) ) ) ).
% prefixes_snoc
thf(fact_155_prefixes__eq__Snoc,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ ( list @ A ),X: list @ A] :
( ( ( prefixes @ A @ Ys )
= ( append @ ( list @ A ) @ Xs @ ( cons @ ( list @ A ) @ X @ ( nil @ ( list @ A ) ) ) ) )
= ( ( ( ( Ys
= ( nil @ A ) )
& ( Xs
= ( nil @ ( list @ A ) ) ) )
| ? [Z: A,Zs3: list @ A] :
( ( Ys
= ( append @ A @ Zs3 @ ( cons @ A @ Z @ ( nil @ A ) ) ) )
& ( Xs
= ( prefixes @ A @ Zs3 ) ) ) )
& ( X = Ys ) ) ) ).
% prefixes_eq_Snoc
thf(fact_156_sublists_Osimps_I1_J,axiom,
! [A: $tType] :
( ( sublists @ A @ ( nil @ A ) )
= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( nil @ ( list @ A ) ) ) ) ).
% sublists.simps(1)
thf(fact_157_prefixes_Osimps_I1_J,axiom,
! [A: $tType] :
( ( prefixes @ A @ ( nil @ A ) )
= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( nil @ ( list @ A ) ) ) ) ).
% prefixes.simps(1)
thf(fact_158_product__lists_Osimps_I1_J,axiom,
! [A: $tType] :
( ( product_lists @ A @ ( nil @ ( list @ A ) ) )
= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( nil @ ( list @ A ) ) ) ) ).
% product_lists.simps(1)
thf(fact_159_prefixes_Oelims,axiom,
! [A: $tType,X: list @ A,Y: list @ ( list @ A )] :
( ( ( prefixes @ A @ X )
= Y )
=> ( ( ( X
= ( nil @ A ) )
=> ( Y
!= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( nil @ ( list @ A ) ) ) ) )
=> ~ ! [X2: A,Xs2: list @ A] :
( ( X
= ( cons @ A @ X2 @ Xs2 ) )
=> ( Y
!= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( map @ ( list @ A ) @ ( list @ A ) @ ( cons @ A @ X2 ) @ ( prefixes @ A @ Xs2 ) ) ) ) ) ) ) ).
% prefixes.elims
thf(fact_160_maps__simps_I1_J,axiom,
! [A: $tType,B: $tType,F: B > ( list @ A ),X: B,Xs: list @ B] :
( ( maps @ B @ A @ F @ ( cons @ B @ X @ Xs ) )
= ( append @ A @ ( F @ X ) @ ( maps @ B @ A @ F @ Xs ) ) ) ).
% maps_simps(1)
thf(fact_161_list_Omap__disc__iff,axiom,
! [B: $tType,A: $tType,F: A > B,A2: list @ A] :
( ( ( map @ A @ B @ F @ A2 )
= ( nil @ B ) )
= ( A2
= ( nil @ A ) ) ) ).
% list.map_disc_iff
thf(fact_162_map__is__Nil__conv,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B] :
( ( ( map @ B @ A @ F @ Xs )
= ( nil @ A ) )
= ( Xs
= ( nil @ B ) ) ) ).
% map_is_Nil_conv
thf(fact_163_Nil__is__map__conv,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B] :
( ( ( nil @ A )
= ( map @ B @ A @ F @ Xs ) )
= ( Xs
= ( nil @ B ) ) ) ).
% Nil_is_map_conv
thf(fact_164_map__eq__conv,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B,G: B > A] :
( ( ( map @ B @ A @ F @ Xs )
= ( map @ B @ A @ G @ Xs ) )
= ( ! [X3: B] :
( ( member @ B @ X3 @ ( set2 @ B @ Xs ) )
=> ( ( F @ X3 )
= ( G @ X3 ) ) ) ) ) ).
% map_eq_conv
thf(fact_165_map__append,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B,Ys: list @ B] :
( ( map @ B @ A @ F @ ( append @ B @ Xs @ Ys ) )
= ( append @ A @ ( map @ B @ A @ F @ Xs ) @ ( map @ B @ A @ F @ Ys ) ) ) ).
% map_append
thf(fact_166_list_Oinj__map__strong,axiom,
! [B: $tType,A: $tType,X: list @ A,Xa2: list @ A,F: A > B,Fa: A > B] :
( ! [Z3: A,Za: A] :
( ( member @ A @ Z3 @ ( set2 @ A @ X ) )
=> ( ( member @ A @ Za @ ( set2 @ A @ Xa2 ) )
=> ( ( ( F @ Z3 )
= ( Fa @ Za ) )
=> ( Z3 = Za ) ) ) )
=> ( ( ( map @ A @ B @ F @ X )
= ( map @ A @ B @ Fa @ Xa2 ) )
=> ( X = Xa2 ) ) ) ).
% list.inj_map_strong
thf(fact_167_list_Omap__cong0,axiom,
! [B: $tType,A: $tType,X: list @ A,F: A > B,G: A > B] :
( ! [Z3: A] :
( ( member @ A @ Z3 @ ( set2 @ A @ X ) )
=> ( ( F @ Z3 )
= ( G @ Z3 ) ) )
=> ( ( map @ A @ B @ F @ X )
= ( map @ A @ B @ G @ X ) ) ) ).
% list.map_cong0
thf(fact_168_list_Omap__cong,axiom,
! [B: $tType,A: $tType,X: list @ A,Ya: list @ A,F: A > B,G: A > B] :
( ( X = Ya )
=> ( ! [Z3: A] :
( ( member @ A @ Z3 @ ( set2 @ A @ Ya ) )
=> ( ( F @ Z3 )
= ( G @ Z3 ) ) )
=> ( ( map @ A @ B @ F @ X )
= ( map @ A @ B @ G @ Ya ) ) ) ) ).
% list.map_cong
thf(fact_169_ex__map__conv,axiom,
! [A: $tType,B: $tType,Ys: list @ B,F: A > B] :
( ( ? [Xs3: list @ A] :
( Ys
= ( map @ A @ B @ F @ Xs3 ) ) )
= ( ! [X3: B] :
( ( member @ B @ X3 @ ( set2 @ B @ Ys ) )
=> ? [Y3: A] :
( X3
= ( F @ Y3 ) ) ) ) ) ).
% ex_map_conv
thf(fact_170_map__cong,axiom,
! [B: $tType,A: $tType,Xs: list @ A,Ys: list @ A,F: A > B,G: A > B] :
( ( Xs = Ys )
=> ( ! [X2: A] :
( ( member @ A @ X2 @ ( set2 @ A @ Ys ) )
=> ( ( F @ X2 )
= ( G @ X2 ) ) )
=> ( ( map @ A @ B @ F @ Xs )
= ( map @ A @ B @ G @ Ys ) ) ) ) ).
% map_cong
thf(fact_171_map__idI,axiom,
! [A: $tType,Xs: list @ A,F: A > A] :
( ! [X2: A] :
( ( member @ A @ X2 @ ( set2 @ A @ Xs ) )
=> ( ( F @ X2 )
= X2 ) )
=> ( ( map @ A @ A @ F @ Xs )
= Xs ) ) ).
% map_idI
thf(fact_172_map__ext,axiom,
! [B: $tType,A: $tType,Xs: list @ A,F: A > B,G: A > B] :
( ! [X2: A] :
( ( member @ A @ X2 @ ( set2 @ A @ Xs ) )
=> ( ( F @ X2 )
= ( G @ X2 ) ) )
=> ( ( map @ A @ B @ F @ Xs )
= ( map @ A @ B @ G @ Xs ) ) ) ).
% map_ext
thf(fact_173_list_Osimps_I9_J,axiom,
! [B: $tType,A: $tType,F: A > B,X21: A,X22: list @ A] :
( ( map @ A @ B @ F @ ( cons @ A @ X21 @ X22 ) )
= ( cons @ B @ ( F @ X21 ) @ ( map @ A @ B @ F @ X22 ) ) ) ).
% list.simps(9)
thf(fact_174_Cons__eq__map__D,axiom,
! [A: $tType,B: $tType,X: A,Xs: list @ A,F: B > A,Ys: list @ B] :
( ( ( cons @ A @ X @ Xs )
= ( map @ B @ A @ F @ Ys ) )
=> ? [Z3: B,Zs: list @ B] :
( ( Ys
= ( cons @ B @ Z3 @ Zs ) )
& ( X
= ( F @ Z3 ) )
& ( Xs
= ( map @ B @ A @ F @ Zs ) ) ) ) ).
% Cons_eq_map_D
thf(fact_175_map__eq__Cons__D,axiom,
! [B: $tType,A: $tType,F: B > A,Xs: list @ B,Y: A,Ys: list @ A] :
( ( ( map @ B @ A @ F @ Xs )
= ( cons @ A @ Y @ Ys ) )
=> ? [Z3: B,Zs: list @ B] :
( ( Xs
= ( cons @ B @ Z3 @ Zs ) )
& ( ( F @ Z3 )
= Y )
& ( ( map @ B @ A @ F @ Zs )
= Ys ) ) ) ).
% map_eq_Cons_D
thf(fact_176_Cons__eq__map__conv,axiom,
! [A: $tType,B: $tType,X: A,Xs: list @ A,F: B > A,Ys: list @ B] :
( ( ( cons @ A @ X @ Xs )
= ( map @ B @ A @ F @ Ys ) )
= ( ? [Z: B,Zs3: list @ B] :
( ( Ys
= ( cons @ B @ Z @ Zs3 ) )
& ( X
= ( F @ Z ) )
& ( Xs
= ( map @ B @ A @ F @ Zs3 ) ) ) ) ) ).
% Cons_eq_map_conv
thf(fact_177_map__eq__Cons__conv,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B,Y: A,Ys: list @ A] :
( ( ( map @ B @ A @ F @ Xs )
= ( cons @ A @ Y @ Ys ) )
= ( ? [Z: B,Zs3: list @ B] :
( ( Xs
= ( cons @ B @ Z @ Zs3 ) )
& ( ( F @ Z )
= Y )
& ( ( map @ B @ A @ F @ Zs3 )
= Ys ) ) ) ) ).
% map_eq_Cons_conv
thf(fact_178_list_Osimps_I8_J,axiom,
! [A: $tType,B: $tType,F: A > B] :
( ( map @ A @ B @ F @ ( nil @ A ) )
= ( nil @ B ) ) ).
% list.simps(8)
thf(fact_179_maps__simps_I2_J,axiom,
! [B: $tType,A: $tType,F: B > ( list @ A )] :
( ( maps @ B @ A @ F @ ( nil @ B ) )
= ( nil @ A ) ) ).
% maps_simps(2)
thf(fact_180_prefixes_Osimps_I2_J,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( prefixes @ A @ ( cons @ A @ X @ Xs ) )
= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( map @ ( list @ A ) @ ( list @ A ) @ ( cons @ A @ X ) @ ( prefixes @ A @ Xs ) ) ) ) ).
% prefixes.simps(2)
thf(fact_181_prefixes_Opelims,axiom,
! [A: $tType,X: list @ A,Y: list @ ( list @ A )] :
( ( ( prefixes @ A @ X )
= Y )
=> ( ( accp @ ( list @ A ) @ ( prefixes_rel @ A ) @ X )
=> ( ( ( X
= ( nil @ A ) )
=> ( ( Y
= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( nil @ ( list @ A ) ) ) )
=> ~ ( accp @ ( list @ A ) @ ( prefixes_rel @ A ) @ ( nil @ A ) ) ) )
=> ~ ! [X2: A,Xs2: list @ A] :
( ( X
= ( cons @ A @ X2 @ Xs2 ) )
=> ( ( Y
= ( cons @ ( list @ A ) @ ( nil @ A ) @ ( map @ ( list @ A ) @ ( list @ A ) @ ( cons @ A @ X2 ) @ ( prefixes @ A @ Xs2 ) ) ) )
=> ~ ( accp @ ( list @ A ) @ ( prefixes_rel @ A ) @ ( cons @ A @ X2 @ Xs2 ) ) ) ) ) ) ) ).
% prefixes.pelims
thf(fact_182_Coinductive__List_Ofinite__lprefix__nitpick__simps_I3_J,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Y: A,Ys: coinductive_llist @ A] :
( ( coindu328551480prefix @ A @ Xs @ ( coinductive_LCons @ A @ Y @ Ys ) )
= ( ( Xs
= ( coinductive_LNil @ A ) )
| ? [Xs7: coinductive_llist @ A] :
( ( Xs
= ( coinductive_LCons @ A @ Y @ Xs7 ) )
& ( coindu328551480prefix @ A @ Xs7 @ Ys ) ) ) ) ).
% Coinductive_List.finite_lprefix_nitpick_simps(3)
thf(fact_183_not__in__set__insert,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ~ ( member @ A @ X @ ( set2 @ A @ Xs ) )
=> ( ( insert @ A @ X @ Xs )
= ( cons @ A @ X @ Xs ) ) ) ).
% not_in_set_insert
thf(fact_184_in__set__insert,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ Xs ) )
=> ( ( insert @ A @ X @ Xs )
= Xs ) ) ).
% in_set_insert
thf(fact_185_insert__Nil,axiom,
! [A: $tType,X: A] :
( ( insert @ A @ X @ ( nil @ A ) )
= ( cons @ A @ X @ ( nil @ A ) ) ) ).
% insert_Nil
thf(fact_186_Coinductive__List_Ofinite__lprefix__nitpick__simps_I1_J,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ( coindu328551480prefix @ A @ Xs @ ( coinductive_LNil @ A ) )
= ( Xs
= ( coinductive_LNil @ A ) ) ) ).
% Coinductive_List.finite_lprefix_nitpick_simps(1)
thf(fact_187_Coinductive__List_Ofinite__lprefix__nitpick__simps_I2_J,axiom,
! [A: $tType,Xs: coinductive_llist @ A] : ( coindu328551480prefix @ A @ ( coinductive_LNil @ A ) @ Xs ) ).
% Coinductive_List.finite_lprefix_nitpick_simps(2)
thf(fact_188_List_Oinsert__def,axiom,
! [A: $tType] :
( ( insert @ A )
= ( ^ [X3: A,Xs3: list @ A] : ( if @ ( list @ A ) @ ( member @ A @ X3 @ ( set2 @ A @ Xs3 ) ) @ Xs3 @ ( cons @ A @ X3 @ Xs3 ) ) ) ) ).
% List.insert_def
thf(fact_189_rotate1_Osimps_I2_J,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( rotate1 @ A @ ( cons @ A @ X @ Xs ) )
= ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) ) ) ).
% rotate1.simps(2)
thf(fact_190_map__eq__map__tailrec,axiom,
! [B: $tType,A: $tType] :
( ( map @ A @ B )
= ( map_tailrec @ A @ B ) ) ).
% map_eq_map_tailrec
thf(fact_191_last__snoc,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( last @ A @ ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) ) )
= X ) ).
% last_snoc
thf(fact_192_rotate1__is__Nil__conv,axiom,
! [A: $tType,Xs: list @ A] :
( ( ( rotate1 @ A @ Xs )
= ( nil @ A ) )
= ( Xs
= ( nil @ A ) ) ) ).
% rotate1_is_Nil_conv
thf(fact_193_set__rotate1,axiom,
! [A: $tType,Xs: list @ A] :
( ( set2 @ A @ ( rotate1 @ A @ Xs ) )
= ( set2 @ A @ Xs ) ) ).
% set_rotate1
thf(fact_194_last__appendR,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ A] :
( ( Ys
!= ( nil @ A ) )
=> ( ( last @ A @ ( append @ A @ Xs @ Ys ) )
= ( last @ A @ Ys ) ) ) ).
% last_appendR
thf(fact_195_last__appendL,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ A] :
( ( Ys
= ( nil @ A ) )
=> ( ( last @ A @ ( append @ A @ Xs @ Ys ) )
= ( last @ A @ Xs ) ) ) ).
% last_appendL
thf(fact_196_llast__llist__of,axiom,
! [A: $tType,Xs: list @ A] :
( ( coinductive_llast @ A @ ( coinductive_llist_of @ A @ Xs ) )
= ( last @ A @ Xs ) ) ).
% llast_llist_of
thf(fact_197_rotate1_Osimps_I1_J,axiom,
! [A: $tType] :
( ( rotate1 @ A @ ( nil @ A ) )
= ( nil @ A ) ) ).
% rotate1.simps(1)
thf(fact_198_last__ConsR,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( Xs
!= ( nil @ A ) )
=> ( ( last @ A @ ( cons @ A @ X @ Xs ) )
= ( last @ A @ Xs ) ) ) ).
% last_ConsR
thf(fact_199_last__ConsL,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( Xs
= ( nil @ A ) )
=> ( ( last @ A @ ( cons @ A @ X @ Xs ) )
= X ) ) ).
% last_ConsL
thf(fact_200_last_Osimps,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( ( Xs
= ( nil @ A ) )
=> ( ( last @ A @ ( cons @ A @ X @ Xs ) )
= X ) )
& ( ( Xs
!= ( nil @ A ) )
=> ( ( last @ A @ ( cons @ A @ X @ Xs ) )
= ( last @ A @ Xs ) ) ) ) ).
% last.simps
thf(fact_201_last__in__set,axiom,
! [A: $tType,As2: list @ A] :
( ( As2
!= ( nil @ A ) )
=> ( member @ A @ ( last @ A @ As2 ) @ ( set2 @ A @ As2 ) ) ) ).
% last_in_set
thf(fact_202_last__map,axiom,
! [B: $tType,A: $tType,Xs: list @ A,F: A > B] :
( ( Xs
!= ( nil @ A ) )
=> ( ( last @ B @ ( map @ A @ B @ F @ Xs ) )
= ( F @ ( last @ A @ Xs ) ) ) ) ).
% last_map
thf(fact_203_longest__common__suffix,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
? [Ss: list @ A,Xs5: list @ A,Ys6: list @ A] :
( ( Xs
= ( append @ A @ Xs5 @ Ss ) )
& ( Ys
= ( append @ A @ Ys6 @ Ss ) )
& ( ( Xs5
= ( nil @ A ) )
| ( Ys6
= ( nil @ A ) )
| ( ( last @ A @ Xs5 )
!= ( last @ A @ Ys6 ) ) ) ) ).
% longest_common_suffix
thf(fact_204_last__append,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ A] :
( ( ( Ys
= ( nil @ A ) )
=> ( ( last @ A @ ( append @ A @ Xs @ Ys ) )
= ( last @ A @ Xs ) ) )
& ( ( Ys
!= ( nil @ A ) )
=> ( ( last @ A @ ( append @ A @ Xs @ Ys ) )
= ( last @ A @ Ys ) ) ) ) ).
% last_append
thf(fact_205_append__butlast__last__id,axiom,
! [A: $tType,Xs: list @ A] :
( ( Xs
!= ( nil @ A ) )
=> ( ( append @ A @ ( butlast @ A @ Xs ) @ ( cons @ A @ ( last @ A @ Xs ) @ ( nil @ A ) ) )
= Xs ) ) ).
% append_butlast_last_id
thf(fact_206_snoc__eq__iff__butlast,axiom,
! [A: $tType,Xs: list @ A,X: A,Ys: list @ A] :
( ( ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) )
= Ys )
= ( ( Ys
!= ( nil @ A ) )
& ( ( butlast @ A @ Ys )
= Xs )
& ( ( last @ A @ Ys )
= X ) ) ) ).
% snoc_eq_iff_butlast
thf(fact_207_butlast__snoc,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( butlast @ A @ ( append @ A @ Xs @ ( cons @ A @ X @ ( nil @ A ) ) ) )
= Xs ) ).
% butlast_snoc
thf(fact_208_butlast_Osimps_I1_J,axiom,
! [A: $tType] :
( ( butlast @ A @ ( nil @ A ) )
= ( nil @ A ) ) ).
% butlast.simps(1)
thf(fact_209_in__set__butlastD,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( member @ A @ X @ ( set2 @ A @ ( butlast @ A @ Xs ) ) )
=> ( member @ A @ X @ ( set2 @ A @ Xs ) ) ) ).
% in_set_butlastD
thf(fact_210_map__butlast,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B] :
( ( map @ B @ A @ F @ ( butlast @ B @ Xs ) )
= ( butlast @ A @ ( map @ B @ A @ F @ Xs ) ) ) ).
% map_butlast
thf(fact_211_butlast_Osimps_I2_J,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( ( Xs
= ( nil @ A ) )
=> ( ( butlast @ A @ ( cons @ A @ X @ Xs ) )
= ( nil @ A ) ) )
& ( ( Xs
!= ( nil @ A ) )
=> ( ( butlast @ A @ ( cons @ A @ X @ Xs ) )
= ( cons @ A @ X @ ( butlast @ A @ Xs ) ) ) ) ) ).
% butlast.simps(2)
thf(fact_212_butlast__append,axiom,
! [A: $tType,Ys: list @ A,Xs: list @ A] :
( ( ( Ys
= ( nil @ A ) )
=> ( ( butlast @ A @ ( append @ A @ Xs @ Ys ) )
= ( butlast @ A @ Xs ) ) )
& ( ( Ys
!= ( nil @ A ) )
=> ( ( butlast @ A @ ( append @ A @ Xs @ Ys ) )
= ( append @ A @ Xs @ ( butlast @ A @ Ys ) ) ) ) ) ).
% butlast_append
thf(fact_213_in__set__butlast__appendI,axiom,
! [A: $tType,X: A,Xs: list @ A,Ys: list @ A] :
( ( ( member @ A @ X @ ( set2 @ A @ ( butlast @ A @ Xs ) ) )
| ( member @ A @ X @ ( set2 @ A @ ( butlast @ A @ Ys ) ) ) )
=> ( member @ A @ X @ ( set2 @ A @ ( butlast @ A @ ( append @ A @ Xs @ Ys ) ) ) ) ) ).
% in_set_butlast_appendI
thf(fact_214_list__ex1__simps_I1_J,axiom,
! [A: $tType,P: A > $o] :
~ ( list_ex1 @ A @ P @ ( nil @ A ) ) ).
% list_ex1_simps(1)
thf(fact_215_list__of__LCons__conv,axiom,
! [A: $tType,Xs: coinductive_llist @ A,X: A] :
( ( ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_list_of @ A @ ( coinductive_LCons @ A @ X @ Xs ) )
= ( cons @ A @ X @ ( coinductive_list_of @ A @ Xs ) ) ) )
& ( ~ ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_list_of @ A @ ( coinductive_LCons @ A @ X @ Xs ) )
= ( undefined @ ( list @ A ) ) ) ) ) ).
% list_of_LCons_conv
thf(fact_216_llast__LNil,axiom,
! [A: $tType] :
( ( coinductive_llast @ A @ ( coinductive_LNil @ A ) )
= ( undefined @ A ) ) ).
% llast_LNil
thf(fact_217_llast__linfinite,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ~ ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_llast @ A @ Xs )
= ( undefined @ A ) ) ) ).
% llast_linfinite
thf(fact_218_list__ex1__iff,axiom,
! [A: $tType] :
( ( list_ex1 @ A )
= ( ^ [P2: A > $o,Xs3: list @ A] :
? [X3: A] :
( ( member @ A @ X3 @ ( set2 @ A @ Xs3 ) )
& ( P2 @ X3 )
& ! [Y3: A] :
( ( ( member @ A @ Y3 @ ( set2 @ A @ Xs3 ) )
& ( P2 @ Y3 ) )
=> ( Y3 = X3 ) ) ) ) ) ).
% list_ex1_iff
thf(fact_219_can__select__set__list__ex1,axiom,
! [A: $tType,P: A > $o,A3: list @ A] :
( ( can_select @ A @ P @ ( set2 @ A @ A3 ) )
= ( list_ex1 @ A @ P @ A3 ) ) ).
% can_select_set_list_ex1
thf(fact_220_list__of__aux__def,axiom,
! [A: $tType] :
( ( coindu1384447384of_aux @ A )
= ( ^ [Xs3: list @ A,Ys3: coinductive_llist @ A] : ( if @ ( list @ A ) @ ( coinductive_lfinite @ A @ Ys3 ) @ ( append @ A @ ( rev @ A @ Xs3 ) @ ( coinductive_list_of @ A @ Ys3 ) ) @ ( undefined @ ( list @ A ) ) ) ) ) ).
% list_of_aux_def
thf(fact_221_rev__is__rev__conv,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( rev @ A @ Xs )
= ( rev @ A @ Ys ) )
= ( Xs = Ys ) ) ).
% rev_is_rev_conv
thf(fact_222_rev__rev__ident,axiom,
! [A: $tType,Xs: list @ A] :
( ( rev @ A @ ( rev @ A @ Xs ) )
= Xs ) ).
% rev_rev_ident
thf(fact_223_Nil__is__rev__conv,axiom,
! [A: $tType,Xs: list @ A] :
( ( ( nil @ A )
= ( rev @ A @ Xs ) )
= ( Xs
= ( nil @ A ) ) ) ).
% Nil_is_rev_conv
thf(fact_224_rev__is__Nil__conv,axiom,
! [A: $tType,Xs: list @ A] :
( ( ( rev @ A @ Xs )
= ( nil @ A ) )
= ( Xs
= ( nil @ A ) ) ) ).
% rev_is_Nil_conv
thf(fact_225_set__rev,axiom,
! [A: $tType,Xs: list @ A] :
( ( set2 @ A @ ( rev @ A @ Xs ) )
= ( set2 @ A @ Xs ) ) ).
% set_rev
thf(fact_226_rev__append,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( rev @ A @ ( append @ A @ Xs @ Ys ) )
= ( append @ A @ ( rev @ A @ Ys ) @ ( rev @ A @ Xs ) ) ) ).
% rev_append
thf(fact_227_singleton__rev__conv,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( ( cons @ A @ X @ ( nil @ A ) )
= ( rev @ A @ Xs ) )
= ( Xs
= ( cons @ A @ X @ ( nil @ A ) ) ) ) ).
% singleton_rev_conv
thf(fact_228_rev__singleton__conv,axiom,
! [A: $tType,Xs: list @ A,X: A] :
( ( ( rev @ A @ Xs )
= ( cons @ A @ X @ ( nil @ A ) ) )
= ( Xs
= ( cons @ A @ X @ ( nil @ A ) ) ) ) ).
% rev_singleton_conv
thf(fact_229_rev__eq__Cons__iff,axiom,
! [A: $tType,Xs: list @ A,Y: A,Ys: list @ A] :
( ( ( rev @ A @ Xs )
= ( cons @ A @ Y @ Ys ) )
= ( Xs
= ( append @ A @ ( rev @ A @ Ys ) @ ( cons @ A @ Y @ ( nil @ A ) ) ) ) ) ).
% rev_eq_Cons_iff
thf(fact_230_list__of__aux__code_I1_J,axiom,
! [A: $tType,Xs: list @ A] :
( ( coindu1384447384of_aux @ A @ Xs @ ( coinductive_LNil @ A ) )
= ( rev @ A @ Xs ) ) ).
% list_of_aux_code(1)
thf(fact_231_rev_Osimps_I1_J,axiom,
! [A: $tType] :
( ( rev @ A @ ( nil @ A ) )
= ( nil @ A ) ) ).
% rev.simps(1)
thf(fact_232_rev__swap,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A] :
( ( ( rev @ A @ Xs )
= Ys )
= ( Xs
= ( rev @ A @ Ys ) ) ) ).
% rev_swap
thf(fact_233_can__select__def,axiom,
! [A: $tType] :
( ( can_select @ A )
= ( ^ [P2: A > $o,A6: set @ A] :
? [X3: A] :
( ( member @ A @ X3 @ A6 )
& ( P2 @ X3 )
& ! [Y3: A] :
( ( ( member @ A @ Y3 @ A6 )
& ( P2 @ Y3 ) )
=> ( Y3 = X3 ) ) ) ) ) ).
% can_select_def
thf(fact_234_rev__map,axiom,
! [A: $tType,B: $tType,F: B > A,Xs: list @ B] :
( ( rev @ A @ ( map @ B @ A @ F @ Xs ) )
= ( map @ B @ A @ F @ ( rev @ B @ Xs ) ) ) ).
% rev_map
thf(fact_235_rev_Osimps_I2_J,axiom,
! [A: $tType,X: A,Xs: list @ A] :
( ( rev @ A @ ( cons @ A @ X @ Xs ) )
= ( append @ A @ ( rev @ A @ Xs ) @ ( cons @ A @ X @ ( nil @ A ) ) ) ) ).
% rev.simps(2)
thf(fact_236_map__tailrec__def,axiom,
! [B: $tType,A: $tType] :
( ( map_tailrec @ A @ B )
= ( ^ [F3: A > B,As3: list @ A] : ( rev @ B @ ( map_tailrec_rev @ A @ B @ F3 @ As3 @ ( nil @ B ) ) ) ) ) ).
% map_tailrec_def
thf(fact_237_map__tailrec__rev,axiom,
! [A: $tType,B: $tType] :
( ( map_tailrec_rev @ B @ A )
= ( ^ [F3: B > A,As3: list @ B] : ( append @ A @ ( rev @ A @ ( map @ B @ A @ F3 @ As3 ) ) ) ) ) ).
% map_tailrec_rev
thf(fact_238_map__tailrec__rev_Osimps_I2_J,axiom,
! [A: $tType,B: $tType,F: A > B,A2: A,As2: list @ A,Bs2: list @ B] :
( ( map_tailrec_rev @ A @ B @ F @ ( cons @ A @ A2 @ As2 ) @ Bs2 )
= ( map_tailrec_rev @ A @ B @ F @ As2 @ ( cons @ B @ ( F @ A2 ) @ Bs2 ) ) ) ).
% map_tailrec_rev.simps(2)
thf(fact_239_map__tailrec__rev_Osimps_I1_J,axiom,
! [A: $tType,B: $tType,F: A > B,Bs2: list @ B] :
( ( map_tailrec_rev @ A @ B @ F @ ( nil @ A ) @ Bs2 )
= Bs2 ) ).
% map_tailrec_rev.simps(1)
thf(fact_240_map__tailrec__rev_Oelims,axiom,
! [A: $tType,B: $tType,X: A > B,Xa2: list @ A,Xb: list @ B,Y: list @ B] :
( ( ( map_tailrec_rev @ A @ B @ X @ Xa2 @ Xb )
= Y )
=> ( ( ( Xa2
= ( nil @ A ) )
=> ( Y != Xb ) )
=> ~ ! [A5: A,As: list @ A] :
( ( Xa2
= ( cons @ A @ A5 @ As ) )
=> ( Y
!= ( map_tailrec_rev @ A @ B @ X @ As @ ( cons @ B @ ( X @ A5 ) @ Xb ) ) ) ) ) ) ).
% map_tailrec_rev.elims
thf(fact_241_llast__lappend,axiom,
! [A: $tType,Ys: coinductive_llist @ A,Xs: coinductive_llist @ A] :
( ( ( coinductive_lnull @ A @ Ys )
=> ( ( coinductive_llast @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( coinductive_llast @ A @ Xs ) ) )
& ( ~ ( coinductive_lnull @ A @ Ys )
=> ( ( ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_llast @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( coinductive_llast @ A @ Ys ) ) )
& ( ~ ( coinductive_lfinite @ A @ Xs )
=> ( ( coinductive_llast @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( undefined @ A ) ) ) ) ) ) ).
% llast_lappend
thf(fact_242_strict__suffix__def,axiom,
! [A: $tType] :
( ( strict_suffix @ A )
= ( ^ [Xs3: list @ A,Ys3: list @ A] :
? [Us: list @ A] :
( ( Ys3
= ( append @ A @ Us @ Xs3 ) )
& ( Us
!= ( nil @ A ) ) ) ) ) ).
% strict_suffix_def
thf(fact_243_lappend_Odisc__iff_I2_J,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( ~ ( coinductive_lnull @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) ) )
= ( ~ ( coinductive_lnull @ A @ Xs )
| ~ ( coinductive_lnull @ A @ Ys ) ) ) ).
% lappend.disc_iff(2)
thf(fact_244_lnull__lappend,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coinductive_lnull @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) )
= ( ( coinductive_lnull @ A @ Xs )
& ( coinductive_lnull @ A @ Ys ) ) ) ).
% lnull_lappend
thf(fact_245_lnull__llist__of,axiom,
! [A: $tType,Xs: list @ A] :
( ( coinductive_lnull @ A @ ( coinductive_llist_of @ A @ Xs ) )
= ( Xs
= ( nil @ A ) ) ) ).
% lnull_llist_of
thf(fact_246_llast__LCons,axiom,
! [A: $tType,Xs: coinductive_llist @ A,X: A] :
( ( ( coinductive_lnull @ A @ Xs )
=> ( ( coinductive_llast @ A @ ( coinductive_LCons @ A @ X @ Xs ) )
= X ) )
& ( ~ ( coinductive_lnull @ A @ Xs )
=> ( ( coinductive_llast @ A @ ( coinductive_LCons @ A @ X @ Xs ) )
= ( coinductive_llast @ A @ Xs ) ) ) ) ).
% llast_LCons
thf(fact_247_strict__suffix__trans,axiom,
! [A: $tType,Xs: list @ A,Ys: list @ A,Zs2: list @ A] :
( ( strict_suffix @ A @ Xs @ Ys )
=> ( ( strict_suffix @ A @ Ys @ Zs2 )
=> ( strict_suffix @ A @ Xs @ Zs2 ) ) ) ).
% strict_suffix_trans
thf(fact_248_lappend_Odisc_I2_J,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( ~ ( coinductive_lnull @ A @ Xs )
| ~ ( coinductive_lnull @ A @ Ys ) )
=> ~ ( coinductive_lnull @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) ) ) ).
% lappend.disc(2)
thf(fact_249_lappend_Odisc_I1_J,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coinductive_lnull @ A @ Xs )
=> ( ( coinductive_lnull @ A @ Ys )
=> ( coinductive_lnull @ A @ ( coinductive_lappend @ A @ Xs @ Ys ) ) ) ) ).
% lappend.disc(1)
thf(fact_250_lappend__lnull1,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( coinductive_lnull @ A @ Xs )
=> ( ( coinductive_lappend @ A @ Xs @ Ys )
= Ys ) ) ).
% lappend_lnull1
thf(fact_251_lappend__lnull2,axiom,
! [A: $tType,Ys: coinductive_llist @ A,Xs: coinductive_llist @ A] :
( ( coinductive_lnull @ A @ Ys )
=> ( ( coinductive_lappend @ A @ Xs @ Ys )
= Xs ) ) ).
% lappend_lnull2
thf(fact_252_lnull__imp__lfinite,axiom,
! [A: $tType,Xs: coinductive_llist @ A] :
( ( coinductive_lnull @ A @ Xs )
=> ( coinductive_lfinite @ A @ Xs ) ) ).
% lnull_imp_lfinite
thf(fact_253_lappend_Oexhaust,axiom,
! [A: $tType,Xs: coinductive_llist @ A,Ys: coinductive_llist @ A] :
( ( ( coinductive_lnull @ A @ Xs )
=> ~ ( coinductive_lnull @ A @ Ys ) )
=> ( ~ ( coinductive_lnull @ A @ Xs )
| ~ ( coinductive_lnull @ A @ Ys ) ) ) ).
% lappend.exhaust
%----Helper facts (3)
thf(help_If_3_1_T,axiom,
! [P: $o] :
( ( P = $true )
| ( P = $false ) ) ).
thf(help_If_2_1_T,axiom,
! [A: $tType,X: A,Y: A] :
( ( if @ A @ $false @ X @ Y )
= Y ) ).
thf(help_If_1_1_T,axiom,
! [A: $tType,X: A,Y: A] :
( ( if @ A @ $true @ X @ Y )
= X ) ).
%----Conjectures (1)
thf(conj_0,conjecture,
member @ ( coinductive_llist @ a ) @ ( coinductive_lappend @ a @ ( coinductive_LCons @ a @ n @ ( coinductive_llist_of @ a @ ys ) ) @ ( coinductive_lappend @ a @ ( coinductive_LCons @ a @ n @ ( coinductive_lappend @ a @ ( coinductive_llist_of @ a @ zs ) @ ( coinductive_LCons @ a @ x @ ( coinductive_LNil @ a ) ) ) ) @ xs3 ) ) @ ( koenig916195507_paths @ a @ graph ) ).
%------------------------------------------------------------------------------