:: Combinatorial {G}rassmannians
:: by Andrzej Owsiejczuk
::
:: Received April 16, 2007
:: Copyright (c) 2007-2016 Association of Mizar Users
:: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland).
:: This code can be distributed under the GNU General Public Licence
:: version 3.0 or later, or the Creative Commons Attribution-ShareAlike
:: License version 3.0 or later, subject to the binding interpretation
:: detailed in file COPYING.interpretation.
:: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these
:: licenses, or see http://www.gnu.org/licenses/gpl.html and
:: http://creativecommons.org/licenses/by-sa/3.0/.
environ
vocabularies NUMBERS, INCSP_1, SUBSET_1, CARD_1, XBOOLE_0, ARYTM_3, TARSKI,
ORDINAL1, FINSET_1, RELAT_1, ARYTM_1, NAT_1, FUNCT_1, XXREAL_0, FDIFF_1,
WELLORD2, ZFMISC_1, ANPROJ_2, AFF_2, MOD_4, FUNCT_2, PRE_POLY, SETFAM_1,
COMBGRAS;
notations TARSKI, XBOOLE_0, CARD_1, SUBSET_1, ORDINAL1, ENUMSET1, ZFMISC_1,
SETFAM_1, DOMAIN_1, FINSET_1, RELAT_1, RELSET_1, WELLORD2, NUMBERS,
INCSP_1, XXREAL_0, XCMPLX_0, REAL_1, FUNCT_1, FUNCT_2, INCPROJ, NAT_1;
constructors SETFAM_1, WELLORD2, DOMAIN_1, REAL_1, NAT_1, BINOP_2, INCPROJ,
RELSET_1, XREAL_0, INT_1;
registrations XBOOLE_0, SUBSET_1, FUNCT_1, ORDINAL1, FUNCT_2, FINSET_1,
XREAL_0, NAT_1, CARD_1, INCSP_1, RELSET_1;
requirements BOOLE, SUBSET, NUMERALS, ARITHM, REAL;
begin :: Preliminaries
reserve
k,n for Nat,
x,y,X,Y,Z for set;
theorem :: COMBGRAS:1
for a,b being set st a <> b & card a = n & card b = n holds card
(a /\ b) in n & n + 1 c= card (a \/ b);
theorem :: COMBGRAS:2
for a,b being set st card a = n + k & card b = n + k holds card(a
/\ b) = n iff card(a \/ b) = n + 2*k;
theorem :: COMBGRAS:3
card X c= card Y iff ex f being Function st f is one-to-one & X
c= dom f & f.:X c= Y;
theorem :: COMBGRAS:4
for f being Function st f is one-to-one & X c= dom f holds card(f
.:X) = card X;
theorem :: COMBGRAS:5
X \ Y = X \ Z & Y c= X & Z c= X implies Y = Z;
theorem :: COMBGRAS:6
for Y being non empty set for p being Function of X,Y st p is
one-to-one for x1,x2 being Subset of X holds x1 <> x2 implies p.:x1 <> p.:x2;
theorem :: COMBGRAS:7
for a,b,c being set st card a = n - 1 & card b = n - 1 & card c =
n - 1 & card(a /\ b) = n - 2 & card(a /\ c) = n - 2 & card(b /\ c) = n - 2 & 2
<= n holds (3 <= n implies card(a /\ b /\ c) = n - 2 & card(a \/ b \/ c) = n +
1 or card(a /\ b /\ c) = n - 3 & card(a \/ b \/ c) = n ) & (n = 2 implies card(
a /\ b /\ c) = n - 2 & card(a \/ b \/ c) = n + 1 );
theorem :: COMBGRAS:8
for P1,P2 being IncProjStr st the IncProjStr of P1 = the
IncProjStr of P2 for A1 being POINT of P1, A2 being POINT of P2 st A1 = A2 for
L1 being LINE of P1, L2 being LINE of P2 st L1 = L2 holds A1 on L1 implies A2
on L2;
theorem :: COMBGRAS:9
for P1,P2 being IncProjStr st the IncProjStr of P1 = the
IncProjStr of P2 for A1 being Subset of the Points of P1 for A2 being Subset of
the Points of P2 st A1 = A2 for L1 being LINE of P1, L2 being LINE of P2 st L1
= L2 holds A1 on L1 implies A2 on L2;
registration
cluster with_non-trivial_lines linear up-2-rank strict for IncProjStr;
end;
begin :: Configuration G
definition
mode PartialLinearSpace is with_non-trivial_lines up-2-rank IncProjStr;
end;
definition
let k be Nat;
let X be non empty set such that
0 < k and
k + 1 c= card X;
func G_(k,X) -> strict PartialLinearSpace means
:: COMBGRAS:def 1
the Points of it = {A
where A is Subset of X: card A = k} & the Lines of it = {L where L is Subset of
X: card L = k + 1} & the Inc of it = (RelIncl bool X) /\ [:the Points of it,
the Lines of it:];
end;
theorem :: COMBGRAS:10
for k being Nat for X being non empty set st 0 < k &
k + 1 c= card X for A being POINT of G_(k,X) for L being LINE of G_(k,X) holds
A on L iff A c= L;
theorem :: COMBGRAS:11
for k being Element of NAT for X being non empty set st 0 < k &
k + 1 c= card X holds G_(k,X) is Vebleian;
theorem :: COMBGRAS:12
for k being Element of NAT for X being non empty set st 0 < k &
k + 1 c= card X holds for A1,A2,A3,A4,A5,A6 being POINT of G_(k,X) for L1,L2,L3
,L4 being LINE of G_(k,X) st A1 on L1 & A2 on L1 & A3 on L2 & A4 on L2 & A5 on
L1 & A5 on L2 & A1 on L3 & A3 on L3 & A2 on L4 & A4 on L4 & not A5 on L3 & not
A5 on L4 & L1 <> L2 & L3 <> L4 holds ex A6 being POINT of G_(k,X) st A6 on L3 &
A6 on L4 & A6 = (A1 /\ A2) \/ (A3 /\ A4);
theorem :: COMBGRAS:13
for k being Element of NAT for X being non empty set st 0 < k & k + 1
c= card X holds G_(k,X) is Desarguesian;
definition
let S be IncProjStr;
let K be Subset of the Points of S;
attr K is clique means
:: COMBGRAS:def 2
for A,B being POINT of S st A in K & B in K ex
L being LINE of S st {A,B} on L;
end;
definition
let S be IncProjStr;
let K be Subset of the Points of S;
attr K is maximal_clique means
:: COMBGRAS:def 3
K is clique & for U being Subset of
the Points of S st U is clique & K c= U holds U = K;
end;
definition
let k be Nat;
let X be non empty set;
let T be Subset of the Points of G_(k,X);
attr T is STAR means
:: COMBGRAS:def 4
ex S being Subset of X st card S = k - 1 & T = {
A where A is Subset of X: card A = k & S c= A};
attr T is TOP means
:: COMBGRAS:def 5
ex S being Subset of X st card S = k + 1 & T = {A
where A is Subset of X: card A = k & A c= S};
end;
theorem :: COMBGRAS:14
for k being Element of NAT for X being non empty set st 2 <= k &
k + 2 c= card X for K being Subset of the Points of G_(k,X) holds K is STAR or
K is TOP implies K is maximal_clique;
theorem :: COMBGRAS:15
for k being Element of NAT for X being non empty set st 2 <= k &
k + 2 c= card X for K being Subset of the Points of G_(k,X) holds K is
maximal_clique implies K is STAR or K is TOP;
begin :: Automorphisms
definition
let S1,S2 be IncProjStr;
struct IncProjMap over S1,S2 (#point-map -> Function of the Points of S1,
the Points of S2, line-map -> Function of the Lines of S1, the Lines of S2#);
end;
definition
let S1,S2 be IncProjStr;
let F be IncProjMap over S1,S2;
let a be POINT of S1;
func F.a -> POINT of S2 equals
:: COMBGRAS:def 6
(the point-map of F).a;
end;
definition
let S1,S2 be IncProjStr;
let F be IncProjMap over S1,S2;
let L be LINE of S1;
func F.L -> LINE of S2 equals
:: COMBGRAS:def 7
(the line-map of F).L;
end;
theorem :: COMBGRAS:16
for S1,S2 being IncProjStr for F1,F2 being IncProjMap over S1,S2
st (for A being POINT of S1 holds F1.A = F2.A) & (for L being LINE of S1 holds
F1.L = F2.L) holds the IncProjMap of F1 = the IncProjMap of F2;
definition
let S1,S2 be IncProjStr;
let F be IncProjMap over S1,S2;
attr F is incidence_preserving means
:: COMBGRAS:def 8
for A1 being POINT of S1 for L1
being LINE of S1 holds (A1 on L1 iff F.A1 on F.L1);
end;
theorem :: COMBGRAS:17
for S1,S2 being IncProjStr for F1,F2 being IncProjMap over S1,S2 st
the IncProjMap of F1 = the IncProjMap of F2 holds F1 is incidence_preserving
implies F2 is incidence_preserving;
definition
let S be IncProjStr;
let F be IncProjMap over S,S;
attr F is automorphism means
:: COMBGRAS:def 9
the line-map of F is bijective & the
point-map of F is bijective & F is incidence_preserving;
end;
definition
let S1,S2 be IncProjStr;
let F be IncProjMap over S1,S2;
let K be Subset of the Points of S1;
func F.:K -> Subset of the Points of S2 equals
:: COMBGRAS:def 10
(the point-map of F).:K;
end;
definition
let S1,S2 be IncProjStr;
let F be IncProjMap over S1,S2;
let K be Subset of the Points of S2;
func F"K -> Subset of the Points of S1 equals
:: COMBGRAS:def 11
(the point-map of F)"K;
end;
definition
let X be set;
let A be finite set;
func ^^(A,X) -> Subset of bool X equals
:: COMBGRAS:def 12
{B where B is Subset of X: card B =
(card A)+1 & A c= B};
end;
definition
let k be Nat;
let X be non empty set such that
0 < k & k + 1 c= card X;
let A be finite set such that
card A = k - 1;
func ^^(A,X,k) -> Subset of the Points of G_(k,X) equals
:: COMBGRAS:def 13
^^(A,X);
end;
theorem :: COMBGRAS:18
for S1,S2 being IncProjStr for F being IncProjMap over S1,S2 for
K being Subset of the Points of S1 holds F.:K = {B where B is POINT of S2:ex A
being POINT of S1 st (A in K & F.A = B)};
theorem :: COMBGRAS:19
for S1,S2 being IncProjStr for F being IncProjMap over S1,S2 for K
being Subset of the Points of S2 holds F"K = {A where A is POINT of S1:ex B
being POINT of S2 st (B in K & F.A = B)};
theorem :: COMBGRAS:20
for S being IncProjStr for F being IncProjMap over S,S for K
being Subset of the Points of S holds F is incidence_preserving & K is clique
implies F.:K is clique;
theorem :: COMBGRAS:21
for S being IncProjStr for F being IncProjMap over S,S for K
being Subset of the Points of S holds F is incidence_preserving & the line-map
of F is onto & K is clique implies F"K is clique;
theorem :: COMBGRAS:22
for S being IncProjStr for F being IncProjMap over S,S for K
being Subset of the Points of S holds F is automorphism & K is maximal_clique
implies F.:K is maximal_clique & F"K is maximal_clique;
theorem :: COMBGRAS:23
for k being Element of NAT for X being non empty set st 2 <= k &
k + 2 c= card X for F being IncProjMap over G_(k,X), G_(k,X) st F is
automorphism for K being Subset of the Points of G_(k,X) holds K is STAR
implies F.:K is STAR & F"K is STAR;
definition
let k be Nat;
let X be non empty set such that
0 < k & k + 1 c= card X;
let s be Permutation of X;
func incprojmap(k,s) -> strict IncProjMap over G_(k,X), G_(k,X) means
:: COMBGRAS:def 14
(for A being POINT of G_(k,X) holds it.A = s.:A) & for L being LINE of G_(k,X
) holds it.L = s.:L;
end;
theorem :: COMBGRAS:24
for k being Nat for X being non empty set st k = 1 &
k + 1 c= card X for F being IncProjMap over G_(k,X), G_(k,X) st F is
automorphism holds ex s being Permutation of X st the IncProjMap of F =
incprojmap(k,s);
theorem :: COMBGRAS:25
for k being Nat for X being non empty set st 1 < k &
card X = k + 1 for F being IncProjMap over G_(k,X), G_(k,X) st F is
automorphism holds ex s being Permutation of X st the IncProjMap of F =
incprojmap(k,s);
theorem :: COMBGRAS:26
for k being Element of NAT for X being non empty set st 0 < k &
k + 1 c= card X for T being Subset of the Points of G_(k,X) for S being Subset
of X holds card S = k - 1 & T = {A where A is Subset of X: card A = k & S c= A}
implies S = meet T;
theorem :: COMBGRAS:27 ::LemStarb:
for k being Element of NAT for X being non empty set st 0 < k & k + 1
c= card X for T being Subset of the Points of G_(k,X) st T is STAR for S being
Subset of X holds S = meet T implies card S = k - 1 & T = {A where A is Subset
of X: card A = k & S c= A};
theorem :: COMBGRAS:28
for k being Element of NAT for X being non empty set st 0 < k &
k + 1 c= card X for T1,T2 being Subset of the Points of G_(k,X) st T1 is STAR &
T2 is STAR & meet T1 = meet T2 holds T1 = T2;
theorem :: COMBGRAS:29
for k being Element of NAT for X being non empty set st k + 1 c=
card X for A being finite Subset of X st card A = k-1 holds ^^(A,X,k) is STAR
;
theorem :: COMBGRAS:30
for k being Element of NAT for X being non empty set st k + 1 c=
card X for A being finite Subset of X st card A = k-1 holds meet ^^(A,X,k) = A;
theorem :: COMBGRAS:31
for k being Nat for X being non empty set st 0 < k &
k + 3 c= card X for F being IncProjMap over G_(k+1,X), G_(k+1,X) st F is
automorphism ex H being IncProjMap over G_(k,X), G_(k,X) st H is automorphism &
the line-map of H = the point-map of F & for A being POINT of G_(k,X), B being
finite set st B = A holds H.A = meet(F.:(^^(B,X,k+1)));
theorem :: COMBGRAS:32
for k being Nat for X being non empty set st 0 < k &
k + 3 c= card X for F being IncProjMap over G_(k+1,X), G_(k+1,X) st F is
automorphism for H being IncProjMap over G_(k,X), G_(k,X) st the line-map of H
= the point-map of F for f being Permutation of X st the IncProjMap of H =
incprojmap(k,f) holds the IncProjMap of F = incprojmap(k+1,f);
theorem :: COMBGRAS:33
for k being Nat for X being non empty set st 2 <= k &
k + 2 c= card X for F being IncProjMap over G_(k,X), G_(k,X) st F is
automorphism holds ex s being Permutation of X st the IncProjMap of F =
incprojmap(k,s);
theorem :: COMBGRAS:34
for k being Nat for X being non empty set st 0 < k &
k + 1 c= card X for s being Permutation of X holds incprojmap(k,s) is
automorphism;
theorem :: COMBGRAS:35
for X being non empty set st 0 < k & k + 1 c= card X for F being
IncProjMap over G_(k,X), G_(k,X) holds F is automorphism iff ex s being
Permutation of X st the IncProjMap of F = incprojmap(k,s);