:: Finite Sequences and Tuples of Elements of a Non-empty Sets
:: by Czes{\l}aw Byli\'nski
::
:: Received March 1, 1990
:: Copyright (c) 1990-2021 Association of Mizar Users

theorem :: FINSEQ_2:1

canceled;

:: Auxiliary theorems
::$CT

theorem Th1: :: FINSEQ_2:2

for i, j, l being natural Number st l = min (i,j) holds
(Seg i) /\ (Seg j) = Seg l

proof end;

theorem Th2: :: FINSEQ_2:3

for i, j being natural Number st i <= j holds
max (0,(i - j)) = 0

proof end;

theorem Th3: :: FINSEQ_2:4

for i, j being natural Number st j <= i holds
max (0,(i - j)) = i - j

proof end;

theorem :: FINSEQ_2:5

for i, j being natural Number holds max (0,(i - j)) is Element of NAT

proof end;

theorem :: FINSEQ_2:6

canceled;

::$CT

theorem :: FINSEQ_2:7

for i, l being natural Number holds
( not i in Seg (l + 1) or i in Seg l or i = l + 1 )

proof end;

theorem :: FINSEQ_2:8

for i, j, l being natural Number st i in Seg l holds
i in Seg (l + j)

proof end;

:: Additional propositions related to Finite Sequences

theorem :: FINSEQ_2:9

for p, q being FinSequence st len p = len q & ( for j being Nat st j in dom p holds
p . j = q . j ) holds
p = q

proof end;

theorem Th8: :: FINSEQ_2:10

for b being object
for p being FinSequence st b in rng p holds
ex i being Nat st
( i in dom p & p . i = b )

proof end;

theorem Th9: :: FINSEQ_2:11

for i being natural Number
for D being set
for p being FinSequence of D st i in dom p holds
p . i in D

proof end;

theorem Th10: :: FINSEQ_2:12

for p being FinSequence
for D being set st ( for i being Nat st i in dom p holds
p . i in D ) holds
p is FinSequence of D

proof end;

Lm1: for x1, x2 being object holds rng <*x1,x2*> = {x1,x2}

proof end;

theorem Th11: :: FINSEQ_2:13

for D being non empty set
for d1, d2 being Element of D holds <*d1,d2*> is FinSequence of D

proof end;

Lm2: for x1, x2, x3 being object holds rng <*x1,x2,x3*> = {x1,x2,x3}

proof end;

theorem Th12: :: FINSEQ_2:14

for D being non empty set
for d1, d2, d3 being Element of D holds <*d1,d2,d3*> is FinSequence of D

proof end;

theorem Th13: :: FINSEQ_2:15

for i being natural Number
for p, q being FinSequence st i in dom p holds
i in dom (p ^ q)

proof end;

theorem Th14: :: FINSEQ_2:16

for a being object
for p being FinSequence holds len (p ^ <*a*>) = (len p) + 1

proof end;

theorem :: FINSEQ_2:17

for a, b being object
for p, q being FinSequence st p ^ <*a*> = q ^ <*b*> holds
( p = q & a = b )

proof end;

theorem :: FINSEQ_2:18

for i being natural Number
for p being FinSequence st len p = i + 1 holds
ex q being FinSequence ex a being object st p = q ^ <*a*> by CARD_1:27, FINSEQ_1:46;

theorem Th17: :: FINSEQ_2:19

for A being set
for p being FinSequence of A st len p <> 0 holds
ex q being FinSequence of A ex d being Element of A st p = q ^ <*d*>

proof end;

theorem Th18: :: FINSEQ_2:20

for i being natural Number
for p, q being FinSequence st q = p | (Seg i) & len p <= i holds
p = q

proof end;

theorem :: FINSEQ_2:21

for i being natural Number
for p, q being FinSequence st q = p | (Seg i) holds
len q = min (i,(len p))

proof end;

theorem Th20: :: FINSEQ_2:22

for i, j being natural Number
for r being FinSequence st len r = i + j holds
ex p, q being FinSequence st
( len p = i & len q = j & r = p ^ q )

proof end;

theorem Th21: :: FINSEQ_2:23

for i, j being natural Number
for D being non empty set
for r being FinSequence of D st len r = i + j holds
ex p, q being FinSequence of D st
( len p = i & len q = j & r = p ^ q )

proof end;

scheme :: FINSEQ_2:sch 1
SeqLambdaD{ F₁() -> Nat, F₂() -> non empty set , F₃( set ) -> Element of F₂() } :

ex z being FinSequence of F₂() st
( len z = F₁() & ( for j being Nat st j in dom z holds
z . j = F₃(j) ) )

proof end;

scheme :: FINSEQ_2:sch 2
IndSeqD{ F₁() -> set , P₁[ set ] } :

for p being FinSequence of F₁() holds P₁[p]

provided

A1: P₁[ <*> F₁()] and
A2: for p being FinSequence of F₁()
for x being Element of F₁() st P₁[p] holds
P₁[p ^ <*x*>]

proof end;

theorem Th22: :: FINSEQ_2:24

for D being set
for D1 being Subset of D
for p being FinSequence of D1 holds p is FinSequence of D

proof end;

theorem Th23: :: FINSEQ_2:25

for i being natural Number
for D being non empty set
for f being Function of (Seg i),D holds f is FinSequence of D

proof end;

theorem :: FINSEQ_2:26

for D being non empty set
for p being FinSequence of D holds p is Function of (dom p),D

proof end;

theorem :: FINSEQ_2:27

for i being natural Number
for D being non empty set
for f being sequence of D holds f | (Seg i) is FinSequence of D

proof end;

theorem :: FINSEQ_2:28

for i being natural Number
for D being non empty set
for q being FinSequence
for f being sequence of D st q = f | (Seg i) holds
len q = i

proof end;

theorem Th27: :: FINSEQ_2:29

for p, q being FinSequence
for f being Function st rng p c= dom f & q = f * p holds
len q = len p

proof end;

theorem Th28: :: FINSEQ_2:30

for i being natural Number
for D being non empty set st D = Seg i holds
for p being FinSequence
for q being FinSequence of D st i <= len p holds
p * q is FinSequence

proof end;

theorem :: FINSEQ_2:31

for i being natural Number
for D, D9 being non empty set st D = Seg i holds
for p being FinSequence of D9
for q being FinSequence of D st i <= len p holds
p * q is FinSequence of D9

proof end;

theorem Th30: :: FINSEQ_2:32

for A, D being set
for p being FinSequence of A
for f being Function of A,D holds f * p is FinSequence of D

proof end;

theorem Th31: :: FINSEQ_2:33

for A being set
for D9 being non empty set
for q being FinSequence
for p being FinSequence of A
for f being Function of A,D9 st q = f * p holds
len q = len p

proof end;

theorem :: FINSEQ_2:34

for x being set
for f being Function st x in dom f holds
f * <*x*> = <*(f . x)*>

proof end;

theorem :: FINSEQ_2:35

for x1 being object
for D, D9 being non empty set
for p being FinSequence of D
for f being Function of D,D9 st p = <*x1*> holds
f * p = <*(f . x1)*>

proof end;

theorem Th34: :: FINSEQ_2:36

for x1, x2 being object
for D, D9 being non empty set
for p being FinSequence of D
for f being Function of D,D9 st p = <*x1,x2*> holds
f * p = <*(f . x1),(f . x2)*>

proof end;

theorem Th35: :: FINSEQ_2:37

for x1, x2, x3 being object
for D, D9 being non empty set
for p being FinSequence of D
for f being Function of D,D9 st p = <*x1,x2,x3*> holds
f * p = <*(f . x1),(f . x2),(f . x3)*>

proof end;

theorem Th36: :: FINSEQ_2:38

for i, j being natural Number
for p being FinSequence
for f being Function of (Seg i),(Seg j) st ( j = 0 implies i = 0 ) & j <= len p holds
p * f is FinSequence

proof end;

theorem :: FINSEQ_2:39

for i being natural Number
for p being FinSequence
for f being Function of (Seg i),(Seg i) st i <= len p holds
p * f is FinSequence by Th36;

theorem :: FINSEQ_2:40

for p being FinSequence
for f being Function of (dom p),(dom p) holds p * f is FinSequence

proof end;

theorem Th39: :: FINSEQ_2:41

for i being natural Number
for p, q being FinSequence
for f being Function of (Seg i),(Seg i) st rng f = Seg i & i <= len p & q = p * f holds
len q = i

proof end;

theorem Th40: :: FINSEQ_2:42

for p, q being FinSequence
for f being Function of (dom p),(dom p) st rng f = dom p & q = p * f holds
len q = len p

proof end;

theorem Th41: :: FINSEQ_2:43

for i being natural Number
for p, q being FinSequence
for f being Permutation of (Seg i) st i <= len p & q = p * f holds
len q = i

proof end;

theorem :: FINSEQ_2:44

for p, q being FinSequence
for f being Permutation of (dom p) st q = p * f holds
len q = len p

proof end;

theorem Th43: :: FINSEQ_2:45

for i, j being natural Number
for D being non empty set
for p being FinSequence of D
for f being Function of (Seg i),(Seg j) st ( j = 0 implies i = 0 ) & j <= len p holds
p * f is FinSequence of D

proof end;

theorem :: FINSEQ_2:46

for i being natural Number
for D being non empty set
for p being FinSequence of D
for f being Function of (Seg i),(Seg i) st i <= len p holds
p * f is FinSequence of D by Th43;

theorem Th45: :: FINSEQ_2:47

for D being non empty set
for p being FinSequence of D
for f being Function of (dom p),(dom p) holds p * f is FinSequence of D

proof end;

theorem Th46: :: FINSEQ_2:48

for k being natural Number holds id (Seg k) is FinSequence of NAT

proof end;

definition

let i be natural Number ;

func idseq i -> FinSequence equals :: FINSEQ_2:def 1
id (Seg i);

coherence
id (Seg i) is FinSequence by Th46;

end;

:: deftheorem defines idseq FINSEQ_2:def 1 :
for i being natural Number holds idseq i = id (Seg i);

registration

let k be natural Number ;

cluster idseq k -> k -element ;

coherence
idseq k is k -element

proof end;

end;

registration

cluster idseq 0 -> empty ;

coherence
idseq 0 is empty ;

end;

theorem :: FINSEQ_2:49

for i being natural Number
for k being Element of Seg i holds (idseq i) . k = k ;

theorem Th48: :: FINSEQ_2:50

idseq 1 = <*1*>

proof end;

theorem Th49: :: FINSEQ_2:51

for i being natural Number holds idseq (i + 1) = (idseq i) ^ <*(i + 1)*>

proof end;

theorem Th50: :: FINSEQ_2:52

idseq 2 = <*1,2*> by Th48, Th49;

theorem :: FINSEQ_2:53

idseq 3 = <*1,2,3*> by Th49, Th50;

theorem Th52: :: FINSEQ_2:54

for k being natural Number
for p being FinSequence st len p <= k holds
p * (idseq k) = p

proof end;

theorem :: FINSEQ_2:55

for k being natural Number holds idseq k is Permutation of (Seg k) ;

theorem Th54: :: FINSEQ_2:56

for a being object
for k being natural Number holds (Seg k) --> a is FinSequence

proof end;

registration

let i be natural Number ;
let a be object ;

cluster (Seg i) --> a -> FinSequence-like ;

coherence
(Seg i) --> a is FinSequence-like by Th54;

end;

definition

let i be natural Number ;
let a be object ;

func i |-> a -> FinSequence equals :: FINSEQ_2:def 2
(Seg i) --> a;

coherence
(Seg i) --> a is FinSequence ;

end;

:: deftheorem defines |-> FINSEQ_2:def 2 :
for i being natural Number
for a being object holds i |-> a = (Seg i) --> a;

registration

let k be natural Number ;
let a be object ;

cluster k |-> a -> k -element ;

coherence
k |-> a is k -element

proof end;

end;

theorem :: FINSEQ_2:57

for k being natural Number
for d being object
for w being set st w in Seg k holds
(k |-> d) . w = d by FUNCOP_1:7;

theorem :: FINSEQ_2:58

for a being object holds 0 |-> a = {} ;

theorem Th57: :: FINSEQ_2:59

for a being object holds 1 |-> a = <*a*>

proof end;

theorem Th58: :: FINSEQ_2:60

for i being natural Number
for a being object holds (i + 1) |-> a = (i |-> a) ^ <*a*>

proof end;

theorem Th59: :: FINSEQ_2:61

for a being object holds 2 |-> a = <*a,a*>

proof end;

theorem :: FINSEQ_2:62

for a being object holds 3 |-> a = <*a,a,a*>

proof end;

theorem Th61: :: FINSEQ_2:63

for D being non empty set
for d being Element of D
for k being natural Number holds k |-> d is FinSequence of D

proof end;

Lm3: for i being natural Number
for p, q being FinSequence
for F being Function st [:(rng p),(rng q):] c= dom F & i = min ((len p),(len q)) holds
dom (F .: (p,q)) = Seg i

proof end;

theorem Th62: :: FINSEQ_2:64

for p, q being FinSequence
for F being Function st [:(rng p),(rng q):] c= dom F holds
F .: (p,q) is FinSequence

proof end;

theorem Th63: :: FINSEQ_2:65

for p, q, r being FinSequence
for F being Function st [:(rng p),(rng q):] c= dom F & r = F .: (p,q) holds
len r = min ((len p),(len q))

proof end;

Lm4: for a being object
for p being FinSequence
for F being Function st [:{a},(rng p):] c= dom F holds
dom (F [;] (a,p)) = dom p

proof end;

theorem Th64: :: FINSEQ_2:66

for a being object
for p being FinSequence
for F being Function st [:{a},(rng p):] c= dom F holds
F [;] (a,p) is FinSequence

proof end;

theorem Th65: :: FINSEQ_2:67

for a being object
for p, r being FinSequence
for F being Function st [:{a},(rng p):] c= dom F & r = F [;] (a,p) holds
len r = len p

proof end;

Lm5: for a being object
for p being FinSequence
for F being Function st [:(rng p),{a}:] c= dom F holds
dom (F [:] (p,a)) = dom p

proof end;

theorem Th66: :: FINSEQ_2:68

for a being object
for p being FinSequence
for F being Function st [:(rng p),{a}:] c= dom F holds
F [:] (p,a) is FinSequence

proof end;

theorem Th67: :: FINSEQ_2:69

for a being object
for p, r being FinSequence
for F being Function st [:(rng p),{a}:] c= dom F & r = F [:] (p,a) holds
len r = len p

proof end;

theorem Th68: :: FINSEQ_2:70

for D, D9, E being non empty set
for F being Function of [:D,D9:],E
for p being FinSequence of D
for q being FinSequence of D9 holds F .: (p,q) is FinSequence of E

proof end;

theorem Th69: :: FINSEQ_2:71

for D, D9, E being non empty set
for r being FinSequence
for F being Function of [:D,D9:],E
for p being FinSequence of D
for q being FinSequence of D9 st r = F .: (p,q) holds
len r = min ((len p),(len q))

proof end;

theorem Th70: :: FINSEQ_2:72

for D, D9, E being non empty set
for r being FinSequence
for F being Function of [:D,D9:],E
for p being FinSequence of D
for q being FinSequence of D9 st len p = len q & r = F .: (p,q) holds
( len r = len p & len r = len q )

proof end;

theorem :: FINSEQ_2:73

for D, D9, E being non empty set
for F being Function of [:D,D9:],E
for p being FinSequence of D
for p9 being FinSequence of D9 holds
( F .: ((<*> D),p9) = <*> E & F .: (p,(<*> D9)) = <*> E )

proof end;

theorem :: FINSEQ_2:74

for D, D9, E being non empty set
for d1 being Element of D
for d19 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D
for q being FinSequence of D9 st p = <*d1*> & q = <*d19*> holds
F .: (p,q) = <*(F . (d1,d19))*>

proof end;

theorem :: FINSEQ_2:75

for D, D9, E being non empty set
for d1, d2 being Element of D
for d19, d29 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D
for q being FinSequence of D9 st p = <*d1,d2*> & q = <*d19,d29*> holds
F .: (p,q) = <*(F . (d1,d19)),(F . (d2,d29))*>

proof end;

theorem :: FINSEQ_2:76

for D, D9, E being non empty set
for d1, d2, d3 being Element of D
for d19, d29, d39 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D
for q being FinSequence of D9 st p = <*d1,d2,d3*> & q = <*d19,d29,d39*> holds
F .: (p,q) = <*(F . (d1,d19)),(F . (d2,d29)),(F . (d3,d39))*>

proof end;

theorem Th75: :: FINSEQ_2:77

for D, D9, E being non empty set
for d being Element of D
for F being Function of [:D,D9:],E
for p being FinSequence of D9 holds F [;] (d,p) is FinSequence of E

proof end;

theorem Th76: :: FINSEQ_2:78

for D, D9, E being non empty set
for d being Element of D
for r being FinSequence
for F being Function of [:D,D9:],E
for p being FinSequence of D9 st r = F [;] (d,p) holds
len r = len p

proof end;

theorem :: FINSEQ_2:79

for D, D9, E being non empty set
for d being Element of D
for F being Function of [:D,D9:],E holds F [;] (d,(<*> D9)) = <*> E

proof end;

theorem :: FINSEQ_2:80

for D, D9, E being non empty set
for d being Element of D
for d19 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D9 st p = <*d19*> holds
F [;] (d,p) = <*(F . (d,d19))*>

proof end;

theorem :: FINSEQ_2:81

for D, D9, E being non empty set
for d being Element of D
for d19, d29 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D9 st p = <*d19,d29*> holds
F [;] (d,p) = <*(F . (d,d19)),(F . (d,d29))*>

proof end;

theorem :: FINSEQ_2:82

for D, D9, E being non empty set
for d being Element of D
for d19, d29, d39 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D9 st p = <*d19,d29,d39*> holds
F [;] (d,p) = <*(F . (d,d19)),(F . (d,d29)),(F . (d,d39))*>

proof end;

theorem Th81: :: FINSEQ_2:83

for D, D9, E being non empty set
for d9 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D holds F [:] (p,d9) is FinSequence of E

proof end;

theorem Th82: :: FINSEQ_2:84

for D, D9, E being non empty set
for d9 being Element of D9
for r being FinSequence
for F being Function of [:D,D9:],E
for p being FinSequence of D st r = F [:] (p,d9) holds
len r = len p

proof end;

theorem :: FINSEQ_2:85

for D, D9, E being non empty set
for d9 being Element of D9
for F being Function of [:D,D9:],E holds F [:] ((<*> D),d9) = <*> E

proof end;

theorem :: FINSEQ_2:86

for D, D9, E being non empty set
for d1 being Element of D
for d9 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D st p = <*d1*> holds
F [:] (p,d9) = <*(F . (d1,d9))*>

proof end;

theorem :: FINSEQ_2:87

for D, D9, E being non empty set
for d1, d2 being Element of D
for d9 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D st p = <*d1,d2*> holds
F [:] (p,d9) = <*(F . (d1,d9)),(F . (d2,d9))*>

proof end;

theorem :: FINSEQ_2:88

for D, D9, E being non empty set
for d1, d2, d3 being Element of D
for d9 being Element of D9
for F being Function of [:D,D9:],E
for p being FinSequence of D st p = <*d1,d2,d3*> holds
F [:] (p,d9) = <*(F . (d1,d9)),(F . (d2,d9)),(F . (d3,d9))*>

proof end;

:: Tuples

definition

let D be set ;

mode FinSequenceSet of D -> set means :Def3: :: FINSEQ_2:def 3
for a being object st a in it holds
a is FinSequence of D;

existence
ex b₁ being set st
for a being object st a in b₁ holds
a is FinSequence of D

proof end;

end;

:: deftheorem Def3 defines FinSequenceSet FINSEQ_2:def 3 :
for D, b₂ being set holds
( b₂ is FinSequenceSet of D iff for a being object st a in b₂ holds
a is FinSequence of D );

definition

let D be set ;
let S be FinSequenceSet of D;
:: original: Element
redefine mode Element of S -> FinSequence of D;
coherence
for b₁ being Element of S holds b₁ is FinSequence of D

proof end;

end;

registration

let D be set ;

cluster non empty for FinSequenceSet of D;

existence
not for b₁ being FinSequenceSet of D holds b₁ is empty

proof end;

end;

theorem Th87: :: FINSEQ_2:89

for D being set holds D * is FinSequenceSet of D

proof end;

definition

let D be set ;
:: original: *
redefine func D * -> FinSequenceSet of D;
coherence
D * is FinSequenceSet of D by Th87;

end;

theorem :: FINSEQ_2:90

for D being set
for D9 being FinSequenceSet of D holds D9 c= D *

proof end;

theorem :: FINSEQ_2:91

for D being non empty set
for D9 being Subset of D
for S being FinSequenceSet of D9 holds S is FinSequenceSet of D

proof end;

registration

let i be natural Number ;
let D be non empty set ;

cluster Relation-like omega -defined D -valued Function-like V49() i -element FinSequence-like FinSubsequence-like countable for FinSequence of D;

existence
ex b₁ being FinSequence of D st b₁ is i -element

proof end;

end;

definition

let i be natural Number ;
let D be non empty set ;
mode Tuple of i,D is i -element FinSequence of D;

end;

definition

let i be natural Number ;
let D be set ;

func i -tuples_on D -> FinSequenceSet of D equals :: FINSEQ_2:def 4
{ s where s is Element of D * : len s = i } ;

coherence
{ s where s is Element of D * : len s = i } is FinSequenceSet of D

proof end;

end;

:: deftheorem defines -tuples_on FINSEQ_2:def 4 :
for i being natural Number
for D being set holds i -tuples_on D = { s where s is Element of D * : len s = i } ;

registration

let i be natural Number ;
let D be non empty set ;

cluster i -tuples_on D -> non empty ;

coherence
not i -tuples_on D is empty

proof end;

end;

registration

let D be non empty set ;
let i be natural Number ;

cluster -> i -element for Element of i -tuples_on D;

coherence
for b₁ being Element of i -tuples_on D holds b₁ is i -element

proof end;

end;

theorem Th90: :: FINSEQ_2:92

for D being set
for z being FinSequence of D holds z is Element of (len z) -tuples_on D

proof end;

theorem :: FINSEQ_2:93

for i being natural Number
for D being set holds i -tuples_on D = Funcs ((Seg i),D)

proof end;

theorem :: FINSEQ_2:94

for D being set holds 0 -tuples_on D = {(<*> D)}

proof end;

theorem :: FINSEQ_2:95

for i being natural Number
for D being non empty set
for z being Tuple of 0 ,D
for t being Tuple of i,D holds
( z ^ t = t & t ^ z = t ) by FINSEQ_1:34;

theorem Th94: :: FINSEQ_2:96

for D being non empty set holds 1 -tuples_on D = { <*d*> where d is Element of D : verum }

proof end;

Lm6: for i being natural Number
for D being non empty set
for z being Tuple of i,D holds z in i -tuples_on D

proof end;

theorem Th95: :: FINSEQ_2:97

for D being non empty set
for z being Tuple of 1,D ex d being Element of D st z = <*d*>

proof end;

theorem Th96: :: FINSEQ_2:98

for D being non empty set
for d being Element of D holds <*d*> in 1 -tuples_on D

proof end;

theorem Th97: :: FINSEQ_2:99

for D being non empty set holds 2 -tuples_on D = { <*d1,d2*> where d1, d2 is Element of D : verum }

proof end;

theorem :: FINSEQ_2:100

for D being non empty set
for z being Tuple of 2,D ex d1, d2 being Element of D st z = <*d1,d2*>

proof end;

theorem Th99: :: FINSEQ_2:101

for D being non empty set
for d1, d2 being Element of D holds <*d1,d2*> in 2 -tuples_on D

proof end;

theorem Th100: :: FINSEQ_2:102

for D being non empty set holds 3 -tuples_on D = { <*d1,d2,d3*> where d1, d2, d3 is Element of D : verum }

proof end;

theorem :: FINSEQ_2:103

for D being non empty set
for z being Tuple of 3,D ex d1, d2, d3 being Element of D st z = <*d1,d2,d3*>

proof end;

theorem Th102: :: FINSEQ_2:104

for D being non empty set
for d1, d2, d3 being Element of D holds <*d1,d2,d3*> in 3 -tuples_on D

proof end;

theorem Th103: :: FINSEQ_2:105

for i, j being natural Number
for D being non empty set holds (i + j) -tuples_on D = { (z ^ t) where z is Tuple of i,D, t is Tuple of j,D : verum }

proof end;

theorem Th104: :: FINSEQ_2:106

for i, j being natural Number
for D being non empty set
for s being Tuple of i + j,D ex z being Element of i -tuples_on D ex t being Element of j -tuples_on D st s = z ^ t

proof end;

theorem :: FINSEQ_2:107

for i, j being natural Number
for D being non empty set
for z being Tuple of i,D
for t being Tuple of j,D holds z ^ t is Tuple of i + j,D ;

theorem :: FINSEQ_2:108

for D being non empty set holds D * = union { (i -tuples_on D) where i is Nat : verum }

proof end;

theorem :: FINSEQ_2:109

for i being natural Number
for D being non empty set
for D9 being non empty Subset of D
for z being Tuple of i,D9 holds z is Element of i -tuples_on D

proof end;

Lm7: for i being natural Number
for A being set
for x being object st x in i -tuples_on A holds
x is b₁ -element FinSequence

proof end;

theorem :: FINSEQ_2:110

for i, j being natural Number
for A being set
for D being non empty set st i -tuples_on D = j -tuples_on A holds
i = j

proof end;

theorem :: FINSEQ_2:111

for i being natural Number holds idseq i is Element of i -tuples_on NAT

proof end;

theorem Th110: :: FINSEQ_2:112

for i being natural Number
for D being non empty set
for d being Element of D holds i |-> d is Element of i -tuples_on D

proof end;

theorem :: FINSEQ_2:113

for i being natural Number
for D, D9 being non empty set
for z being Tuple of i,D
for f being Function of D,D9 holds f * z is Element of i -tuples_on D9

proof end;

theorem Th112: :: FINSEQ_2:114

for i being natural Number
for D being non empty set
for z being Tuple of i,D
for f being Function of (Seg i),(Seg i) st rng f = Seg i holds
z * f is Element of i -tuples_on D

proof end;

theorem :: FINSEQ_2:115

for i being natural Number
for D being non empty set
for z being Tuple of i,D
for f being Permutation of (Seg i) holds z * f is Tuple of i,D

proof end;

theorem :: FINSEQ_2:116

for i being natural Number
for D being non empty set
for z being Tuple of i,D
for d being Element of D holds (z ^ <*d*>) . (i + 1) = d

proof end;

theorem :: FINSEQ_2:117

for i being natural Number
for D being non empty set
for z being Tuple of i + 1,D ex t being Element of i -tuples_on D ex d being Element of D st z = t ^ <*d*>

proof end;

theorem :: FINSEQ_2:118

for i being natural Number
for D being non empty set
for z being Tuple of i,D holds z * (idseq i) = z

proof end;

theorem :: FINSEQ_2:119

for i being natural Number
for D being non empty set
for z1, z2 being Tuple of i,D st ( for j being Nat st j in Seg i holds
z1 . j = z2 . j ) holds
z1 = z2

proof end;

theorem :: FINSEQ_2:120

for i being natural Number
for D, D9, E being non empty set
for F being Function of [:D,D9:],E
for z1 being Tuple of i,D
for z2 being Tuple of i,D9 holds F .: (z1,z2) is Element of i -tuples_on E

proof end;

theorem :: FINSEQ_2:121

for i being natural Number
for D, D9, E being non empty set
for d being Element of D
for F being Function of [:D,D9:],E
for z being Tuple of i,D9 holds F [;] (d,z) is Element of i -tuples_on E

proof end;

theorem :: FINSEQ_2:122

for i being natural Number
for D, D9, E being non empty set
for d9 being Element of D9
for F being Function of [:D,D9:],E
for z being Tuple of i,D holds F [:] (z,d9) is Element of i -tuples_on E

proof end;

theorem :: FINSEQ_2:123

for i, j being natural Number
for x being object holds (i + j) |-> x = (i |-> x) ^ (j |-> x)

proof end;

:: Addendum, 2002.07.08

theorem :: FINSEQ_2:124

for D being non empty set
for i being natural Number
for x being Tuple of i,D holds dom x = Seg i

proof end;

theorem :: FINSEQ_2:125

for f being Function
for x, y being set st x in dom f & y in dom f holds
f * <*x,y*> = <*(f . x),(f . y)*>

proof end;

theorem :: FINSEQ_2:126

for f being Function
for x, y, z being set st x in dom f & y in dom f & z in dom f holds
f * <*x,y,z*> = <*(f . x),(f . y),(f . z)*>

proof end;

theorem :: FINSEQ_2:127

for x1, x2 being object holds rng <*x1,x2*> = {x1,x2} by Lm1;

theorem :: FINSEQ_2:128

for x1, x2, x3 being object holds rng <*x1,x2,x3*> = {x1,x2,x3} by Lm2;

:: from SCMFSA_7, 2005.11.21, A.T.

theorem :: FINSEQ_2:129

for p1, p2, q being FinSequence st p1 c= q & p2 c= q & len p1 = len p2 holds
p1 = p2

proof end;

theorem :: FINSEQ_2:130

for D being non empty set
for s being FinSequence of D st s <> {} holds
ex w being FinSequence of D ex n being Element of D st s = <*n*> ^ w

proof end;

:: Moved from AMISTD_2 by AK, 2008.02.02

registration

let D be set ;

cluster -> functional for FinSequenceSet of D;

coherence
for b₁ being FinSequenceSet of D holds b₁ is functional by Def3;

end;

:: from FINSOP_1, 2009.05.23, AT

definition

let D be non empty set ;
let n be natural Number ;
let d be Element of D;
:: original: |->
redefine func n |-> d -> Element of n -tuples_on D;
coherence
n |-> d is Element of n -tuples_on D by Th110;

end;

:: new, 2009.08.15, A.T.

theorem :: FINSEQ_2:131

for i being natural Number
for D being non empty set
for z being set holds
( z is Tuple of i,D iff z in i -tuples_on D )

proof end;

:: from CATALG_1, 2009.09.08, A.T.

theorem Th130: :: FINSEQ_2:132

for A being set
for i being Element of NAT
for p being FinSequence holds
( p in i -tuples_on A iff ( len p = i & rng p c= A ) )

proof end;

theorem :: FINSEQ_2:133

for A being set
for i being Element of NAT
for p being FinSequence of A holds
( p in i -tuples_on A iff len p = i )

proof end;

theorem :: FINSEQ_2:134

for A being set
for i being Element of NAT holds i -tuples_on A c= A *

proof end;

theorem Th133: :: FINSEQ_2:135

for A being set
for x being object holds
( x in 1 -tuples_on A iff ex a being set st
( a in A & x = <*a*> ) )

proof end;

theorem :: FINSEQ_2:136

for A being set
for a being object st <*a*> in 1 -tuples_on A holds
a in A

proof end;

theorem Th135: :: FINSEQ_2:137

for A being set
for x being object holds
( x in 2 -tuples_on A iff ex a, b being object st
( a in A & b in A & x = <*a,b*> ) )

proof end;

theorem :: FINSEQ_2:138

for A being set
for a, b being object st <*a,b*> in 2 -tuples_on A holds
( a in A & b in A )

proof end;

theorem Th137: :: FINSEQ_2:139

for A being set
for x being object holds
( x in 3 -tuples_on A iff ex a, b, c being object st
( a in A & b in A & c in A & x = <*a,b,c*> ) )

proof end;

theorem :: FINSEQ_2:140

for A being set
for a, b, c being object st <*a,b,c*> in 3 -tuples_on A holds
( a in A & b in A & c in A )

proof end;

theorem :: FINSEQ_2:141

for i being natural Number
for A being set
for x being object st x in i -tuples_on A holds
x is b₁ -element FinSequence by Lm7;

:: from MSUALG_1, 2009.09.18, A.T.

theorem :: FINSEQ_2:142

for A being non empty set
for n being Nat holds n -tuples_on A c= A *

proof end;

:: from AMISTD_3, 2010.01.10, A.T.

theorem :: FINSEQ_2:143

for x being object
for m, n being Nat st n |-> x = m |-> x holds
n = m

proof end;

definition

let I be set ;
let M be ManySortedSet of I;

func M # -> ManySortedSet of I * means :Def5: :: FINSEQ_2:def 5
for i being Element of I * holds it . i = product (M * i);

existence
ex b₁ being ManySortedSet of I * st
for i being Element of I * holds b₁ . i = product (M * i)

proof end;

uniqueness
for b₁, b₂ being ManySortedSet of I * st ( for i being Element of I * holds b₁ . i = product (M * i) ) & ( for i being Element of I * holds b₂ . i = product (M * i) ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def5 defines # FINSEQ_2:def 5 :
for I being set
for M being ManySortedSet of I
for b₃ being ManySortedSet of I * holds
( b₃ = M # iff for i being Element of I * holds b₃ . i = product (M * i) );

registration

let I be set ;
let M be V2() ManySortedSet of I;

cluster M # -> V2() ;

coherence
M # is non-empty

proof end;

end;

definition

let a be set ;

func *--> a -> sequence of ({a} *) means :Def6: :: FINSEQ_2:def 6
for n being Nat holds it . n = n |-> a;

existence
ex b₁ being sequence of ({a} *) st
for n being Nat holds b₁ . n = n |-> a

proof end;

uniqueness
for b₁, b₂ being sequence of ({a} *) st ( for n being Nat holds b₁ . n = n |-> a ) & ( for n being Nat holds b₂ . n = n |-> a ) holds
b₁ = b₂

proof end;

end;

:: deftheorem Def6 defines *--> FINSEQ_2:def 6 :
for a being set
for b₂ being sequence of ({a} *) holds
( b₂ = *--> a iff for n being Nat holds b₂ . n = n |-> a );

theorem Th142: :: FINSEQ_2:144

for n being Nat
for a, b being set holds (a .--> b) * (n |-> a) = n |-> b

proof end;

theorem :: FINSEQ_2:145

for D being non empty set
for n being Nat
for a being set
for M being ManySortedSet of {a} st M = a .--> D holds
((M #) * (*--> a)) . n = Funcs ((Seg n),D)

proof end;

registration

let i be natural Number ;

cluster i |-> 0 -> empty-yielding ;

coherence
i |-> 0 is empty-yielding ;

end;

:: new, 2011.10.03, A.K.

registration

let D be set ;

cluster -> FinSequence-membered for FinSequenceSet of D;

coherence
for b₁ being FinSequenceSet of D holds b₁ is FinSequence-membered

proof end;

end;

definition

let D be set ;
let F be FinSequenceSet of D;
let f be sequence of F;
let n be natural Number ;
:: original: .
redefine func f . n -> FinSequence of D;
coherence
f . n is FinSequence of D

proof end;

end;