:: Dilworth's Decomposition Theorem for Posets
:: by Piotr Rudnicki
::
:: Received September 17, 2009
:: Copyright (c) 2009-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, FINSET_1, XBOOLE_0, CARD_1, XXREAL_0, SUBSET_1, TARSKI,
ORDINAL1, SETFAM_1, ZFMISC_1, EQREL_1, NAT_1, FUNCT_1, FINSEQ_1, ARYTM_3,
RELAT_1, ORDERS_2, RELAT_2, COMBGRAS, STRUCT_0, ORDERS_1, CIRCUIT2,
GROUP_10, RAMSEY_1, JORDAN4, WAYBEL_0, WAYBEL_4, YELLOW_0, FUNCT_2,
LEXBFS, ARYTM_1, UPROOTS, CARD_3, FINSEQ_2, VALUED_0, SQUARE_1, ORDINAL2,
DILWORTH, REAL_1;
notations TARSKI, RELAT_1, RELAT_2, RELSET_1, FINSET_1, SETFAM_1, XBOOLE_0,
SUBSET_1, CARD_1, STRUCT_0, WAYBEL_0, WAYBEL_4, ORDERS_2, ORDINAL1,
EQREL_1, FUNCT_1, FUNCT_2, NUMBERS, XREAL_0, XXREAL_0, NAT_1, YELLOW_0,
XCMPLX_0, ZFMISC_1, LEXBFS, FINSEQ_1, SQUARE_1, UPROOTS, RVSUM_1, INT_5,
FINSEQ_2, VALUED_0, GROUP_10, RAMSEY_1, DOMAIN_1;
constructors DOMAIN_1, LEXBFS, WAYBEL_4, SQUARE_1, UPROOTS, WSIERP_1, INT_5,
RAMSEY_1, RELSET_1, BINOP_2, NUMBERS;
registrations STRUCT_0, XXREAL_0, RELSET_1, CARD_1, YELLOW_0, XREAL_0,
FINSET_1, XBOOLE_0, NAT_1, INT_1, YELLOW_2, EQREL_1, FINSEQ_1, FUNCT_1,
SUBSET_1, ORDINAL1, PEPIN, RVSUM_1, FUNCT_2, FINSEQ_2, NUMBERS, RELAT_1,
VALUED_0, ORDERS_2;
requirements ARITHM, SUBSET, BOOLE, NUMERALS, REAL;
begin :: Preliminaries
:: Facts that I could not find in MML.
scheme :: DILWORTH:sch 1
FraenkelFinCard1 { A() -> finite non empty set, P[set],
Y() -> finite set, F(set) -> set }:
card Y() <= card A()
provided
Y() = { F(w) where w is Element of A(): P[w] };
theorem :: DILWORTH:1 :: set00:
for X, Y, x being set st not x in X holds X \ (Y \/ {x}) = X \ Y;
theorem :: DILWORTH:2 :: ssf0:
for X, Y being set, F being Subset-Family of X, G being Subset-Family of Y
holds F \/ G is Subset-Family of X \/ Y;
theorem :: DILWORTH:3 :: SPpart0:
for X, Y being set, F being a_partition of X, G being a_partition of Y
st X misses Y holds F \/ G is a_partition of X \/ Y;
theorem :: DILWORTH:4 :: SPpart:
for X, Y being set, F being a_partition of Y
st Y c< X holds F \/ { X \ Y } is a_partition of X;
theorem :: DILWORTH:5 :: Sinfset:
for X being infinite set, n being Nat
ex Y being finite Subset of X st card Y > n;
begin :: Cliques and stable sets
definition
let R be RelStr, S be Subset of R;
attr S is connected means
:: DILWORTH:def 1
the InternalRel of R is_connected_in S;
end;
notation
let R be RelStr, S be Subset of R;
synonym S is clique for S is connected;
end;
registration
let R be RelStr;
cluster trivial -> clique for Subset of R;
end;
registration
let R be RelStr;
cluster clique for Subset of R;
end;
definition
let R be RelStr;
mode Clique of R is clique Subset of R;
end;
theorem :: DILWORTH:6 :: DClique:
for R being RelStr, S being Subset of R holds S is Clique of R iff
for a, b being Element of R st a in S & b in S & a <> b holds a <= b or b <= a;
registration
let R be RelStr;
cluster finite for Clique of R;
end;
registration
let R be reflexive RelStr;
cluster connected -> strongly_connected for Subset of R;
end;
registration
let R be non empty RelStr;
cluster finite non empty for Clique of R;
end;
theorem :: DILWORTH:7 :: Clique36a:
for R being non empty RelStr, a1,a2 being Element of R
st a1 <> a2 & {a1,a2} is Clique of R holds a1 <= a2 or a2 <= a1;
theorem :: DILWORTH:8 :: Clique36b:
for R being non empty RelStr, a1,a2 being Element of R
st a1 <= a2 or a2 <= a1 holds {a1,a2} is Clique of R;
theorem :: DILWORTH:9 :: Clique37:
for R being RelStr, C being Clique of R, S being Subset of C
holds S is Clique of R;
theorem :: DILWORTH:10 :: Clique1:
for R being RelStr, C being finite Clique of R, n being Nat
st n <= card C ex B being finite Clique of R st B c= C & card B = n;
theorem :: DILWORTH:11 :: ExtClique
for R being transitive RelStr, C being Clique of R, x, y being Element of R
st x is_maximal_in C & x <= y holds C \/ {y} is Clique of R;
theorem :: DILWORTH:12 :: ExtCliquemin
for R being transitive RelStr, C being Clique of R, x, y being Element of R
st x is_minimal_in C & y <= x holds C \/ {y} is Clique of R;
definition
let R be RelStr, S be Subset of R;
attr S is stable means
:: DILWORTH:def 2
for x, y being Element of R st x in S & y in S & x <> y
holds not x <= y & not y <= x;
end;
registration
let R be RelStr;
cluster trivial -> stable for Subset of R;
end;
registration
let R be RelStr;
cluster stable for Subset of R;
end;
definition
let R be RelStr;
mode StableSet of R is stable Subset of R;
:: other possible names: AntiChain of R, IndependentSet of R
end;
registration
let R be RelStr;
cluster finite for StableSet of R;
end;
registration
let R be non empty RelStr;
cluster finite non empty for StableSet of R;
end;
theorem :: DILWORTH:13 :: AChain36a:
for R being non empty RelStr, a1, a2 being Element of R
st a1 <> a2 & {a1,a2} is StableSet of R holds not (a1 <= a2 or a2 <= a1);
theorem :: DILWORTH:14 :: AChain36b:
for R being non empty RelStr, a1, a2 being Element of R
st not (a1 <= a2 or a2 <= a1) holds {a1,a2} is StableSet of R;
theorem :: DILWORTH:15 :: ACClique:
for R being RelStr, C being Clique of R, A being StableSet of R, a, b being set
st a in A & b in A & a in C & b in C holds a = b;
theorem :: DILWORTH:16 :: AChain0:
for R being RelStr, A being StableSet of R, B being Subset of A
holds B is StableSet of R;
theorem :: DILWORTH:17 :: AChain1:
for R being RelStr, A being finite StableSet of R, n being Nat
st n <= card A ex B being finite StableSet of R st card B = n;
begin :: Clique number and stability number
definition
let R be RelStr;
attr R is with_finite_clique# means
:: DILWORTH:def 3
ex C being finite Clique of R
st for D being finite Clique of R holds card D <= card C;
end;
registration
cluster finite -> with_finite_clique# for RelStr;
end;
registration
let R be with_finite_clique# RelStr;
cluster -> finite for Clique of R;
end;
definition
let R be with_finite_clique# RelStr;
func clique# R -> Nat means
:: DILWORTH:def 4
(ex C being finite Clique of R st card C = it)
& for T being finite Clique of R holds card T <= it;
end;
registration
let R be empty RelStr;
cluster clique# R -> empty;
end;
registration
let R be with_finite_clique# non empty RelStr;
cluster clique# R -> positive;
end;
theorem :: DILWORTH:18 :: Height3:
for R being with_finite_clique# non empty RelStr
st [#]R is StableSet of R holds clique# R = 1;
theorem :: DILWORTH:19 :: Height4:
for R being with_finite_clique# RelStr st clique# R = 1
holds [#]R is StableSet of R;
definition
let R be RelStr;
attr R is with_finite_stability# means
:: DILWORTH:def 5
ex A being finite StableSet of R
st for B being finite StableSet of R holds card B <= card A;
end;
registration
cluster finite -> with_finite_stability# for RelStr;
end;
registration
let R be with_finite_stability# RelStr;
cluster -> finite for StableSet of R;
end;
definition
let R be with_finite_stability# RelStr;
func stability# R -> Nat means
:: DILWORTH:def 6
(ex A being finite StableSet of R st card(A) = it)
& for T being finite StableSet of R holds card T <= it;
end;
registration
let R be empty RelStr;
cluster stability# R -> empty;
end;
registration
let R be with_finite_stability# non empty RelStr;
cluster stability# R -> positive;
end;
theorem :: DILWORTH:20 :: Width3:
for R being with_finite_stability# non empty RelStr
st [#]R is Clique of R holds stability# R = 1;
theorem :: DILWORTH:21 :: Width4:
for R being with_finite_stability# RelStr st stability# R = 1
holds [#]R is Clique of R;
registration
:: I have done it through Ramsey. How else to prove it?
:: For posets one gets it directly from Dilworth.
:: Related: how big the gap between (clique# * stability#) and
:: card of the carrier can be?
cluster with_finite_clique# with_finite_stability# -> finite for RelStr;
end;
begin :: Lower and upper sets, minimal and maximal elements
definition
let R be RelStr, X be Subset of R;
func Lower X -> Subset of R equals
:: DILWORTH:def 7
X \/ downarrow X;
func Upper X -> Subset of R equals
:: DILWORTH:def 8
X \/ uparrow X;
end;
theorem :: DILWORTH:22 :: ABAC0:
for R being antisymmetric transitive RelStr, A being StableSet of R,
z being set
st z in Upper A & z in Lower A holds z in A;
theorem :: DILWORTH:23 :: ABunion:
for R being with_finite_stability# RelStr, A being StableSet of R
st card A = stability# R holds Upper A \/ Lower A = [#]R;
theorem :: DILWORTH:24 :: Pminmin:
for R being transitive RelStr, x being Element of R, S being Subset of R
st x is_minimal_in Lower S holds x is_minimal_in [#]R;
theorem :: DILWORTH:25 :: Pmaxmax:
for R being transitive RelStr, x being Element of R, S being Subset of R
st x is_maximal_in Upper S holds x is_maximal_in [#]R;
definition
let R be RelStr;
func minimals R -> Subset of R means
:: DILWORTH:def 9
for x being Element of R holds x in it iff x is_minimal_in [#]R
if R is non empty
otherwise it = {};
func maximals R -> Subset of R means
:: DILWORTH:def 10
for x being Element of R holds x in it iff x is_maximal_in [#]R
if R is non empty
otherwise it = {};
end;
registration
let R be with_finite_clique# non empty antisymmetric transitive RelStr;
cluster maximals R -> non empty;
cluster minimals R -> non empty;
end;
registration let R be RelStr;
cluster minimals R -> stable;
cluster maximals R -> stable;
end;
theorem :: DILWORTH:26 :: PCAamin:
for R being RelStr, A being StableSet of R
st not minimals R c= A holds not minimals R c= Upper A;
theorem :: DILWORTH:27 :: PCAbmax:
for R being RelStr, A being StableSet of R
st not maximals R c= A holds not maximals R c= Lower A;
begin :: Substructures
registration
let R be RelStr, X be finite Subset of R;
cluster subrelstr X -> finite;
end;
theorem :: DILWORTH:28 :: SPClique:
for R being RelStr, S being Subset of R, C being Clique of subrelstr S
holds C is Clique of R;
theorem :: DILWORTH:29 :: SPClique1:
for R being RelStr, S being Subset of R, C being Clique of R
holds C /\ S is Clique of subrelstr S;
theorem :: DILWORTH:30 :: SPAChain1:
for R being RelStr, S being Subset of R, A being StableSet of subrelstr S
holds A is StableSet of R;
theorem :: DILWORTH:31 :: SPAChain:
for R being RelStr, S being Subset of R, A being StableSet of R
holds A /\ S is StableSet of subrelstr S;
theorem :: DILWORTH:32 :: SPmax
for R being RelStr, S being Subset of R, B being Subset of subrelstr S,
x being Element of subrelstr S, y being Element of R
st x = y & x is_maximal_in B holds y is_maximal_in B;
theorem :: DILWORTH:33 :: SPmin
for R being RelStr, S being Subset of R, B being Subset of subrelstr S,
x being Element of subrelstr S, y being Element of R
st x = y & x is_minimal_in B holds y is_minimal_in B;
theorem :: DILWORTH:34 :: PbeSmax:
for R being transitive RelStr, A being StableSet of R,
C being Clique of subrelstr Lower A, a, b being Element of R
st a in A & a in C & b in C holds a = b or b <= a;
theorem :: DILWORTH:35 :: PabSmin:
for R being transitive RelStr, A being StableSet of R,
C being Clique of subrelstr Upper A, a, b being Element of R
st a in A & a in C & b in C holds a = b or a <= b;
registration
let R be with_finite_clique# RelStr, S be Subset of R;
cluster subrelstr S -> with_finite_clique#;
end;
registration
let R be with_finite_stability# RelStr, S be Subset of R;
cluster subrelstr S -> with_finite_stability#;
end;
theorem :: DILWORTH:36 :: Pmaxmin:
for R being with_finite_clique# non empty antisymmetric transitive RelStr,
x being Element of R
holds ex y being Element of R st y is_minimal_in [#]R & (y = x or y < x);
theorem :: DILWORTH:37 :: Pam:
for R being with_finite_clique# antisymmetric transitive RelStr
holds Upper minimals R = [#]R;
theorem :: DILWORTH:38 :: Pminmax
for R being with_finite_clique# non empty antisymmetric transitive RelStr,
x being Element of R
ex y being Element of R st y is_maximal_in [#]R & (y = x or x < y);
theorem :: DILWORTH:39 :: Pbm:
for R being with_finite_clique# antisymmetric transitive RelStr
holds Lower maximals R = [#]R;
theorem :: DILWORTH:40 :: PCAmin:
for R being with_finite_clique# antisymmetric transitive RelStr,
A being StableSet of R
st minimals R c= A holds A = minimals R;
theorem :: DILWORTH:41 :: PCAmax:
for R being with_finite_clique# antisymmetric transitive RelStr,
A being StableSet of R
st maximals R c= A holds A = maximals R;
theorem :: DILWORTH:42 :: Hsubp0:
for R being with_finite_clique# RelStr, S being Subset of R
holds clique# subrelstr S <= clique# R;
theorem :: DILWORTH:43 :: Hsubp1:
for R being with_finite_clique# RelStr, C being Clique of R,
S being Subset of R st card C = clique# R & C c= S
holds clique# subrelstr S = clique# R;
theorem :: DILWORTH:44 :: Wsubp0:
for R being with_finite_stability# RelStr, S being Subset of R
holds stability# subrelstr S <= stability# R;
theorem :: DILWORTH:45 :: Wsubp1:
for R being with_finite_stability# RelStr, A being StableSet of R,
S being Subset of R st card A = stability# R & A c= S
holds stability# subrelstr S = stability# R;
begin :: Partitions into cliques and stable sets
definition
let R be RelStr, P be a_partition of the carrier of R;
attr P is Clique-wise means
:: DILWORTH:def 11
for x being set st x in P holds x is Clique of R;
end;
registration let R be RelStr;
cluster Clique-wise for a_partition of the carrier of R;
end;
definition
let R be RelStr;
mode Clique-partition of R is Clique-wise a_partition of the carrier of R;
end;
registration let R be empty RelStr;
cluster empty -> Clique-wise for a_partition of the carrier of R;
end;
theorem :: DILWORTH:46 :: Chpw:
for R being finite RelStr, C being Clique-partition of R
holds card C >= stability# R;
theorem :: DILWORTH:47 :: ACpart1:
for R being with_finite_stability# RelStr, A being StableSet of R,
C being Clique-partition of R st card C = card A
ex f being Function of A, C st f is bijective &
for x being set st x in A holds x in f.x;
theorem :: DILWORTH:48 :: ACpart2:
for R being finite RelStr, A being StableSet of R,
C being Clique-partition of R st card C = card A
for c being set st c in C ex a being Element of A st c /\ A = {a};
theorem :: DILWORTH:49 :: Glueing lemma:
for R being with_finite_stability# antisymmetric transitive non empty RelStr,
A being StableSet of R,
U being Clique-partition of subrelstr Upper A,
L being Clique-partition of subrelstr Lower A
st card A = stability# R & card U = stability# R & card L = stability# R
ex C being Clique-partition of R st card C = stability# R;
definition
let R be RelStr, P be a_partition of the carrier of R;
attr P is StableSet-wise means
:: DILWORTH:def 12
for x being set st x in P holds x is StableSet of R;
end;
registration
let R be RelStr;
cluster StableSet-wise for a_partition of the carrier of R;
end;
definition
let R be RelStr;
mode Coloring of R is StableSet-wise a_partition of the carrier of R;
end;
registration let R be empty RelStr;
cluster -> StableSet-wise for a_partition of the carrier of R;
end;
theorem :: DILWORTH:50 :: ColClique:
for R being finite RelStr, C being Coloring of R holds card C >= clique# R;
begin :: Dilworth's theorem and a dual
:: There seems to be little theory of antisymmetric transitive relations.
:: Posets are required to be reflexive and antisymmetric while
:: strict posets to be irreflexive and asymmetric (and both are
:: required to be transitive.) Since asymmetric implies antisymmetric,
:: it seems that the common ground would be antisymmetric and transitive
:: relations.
::$N Dilworth's Decomposition Theorem
theorem :: DILWORTH:51 :: Dilworth: Finite case
for R being finite antisymmetric transitive RelStr
ex C being Clique-partition of R st card(C) = stability# R;
definition
let R be with_finite_stability# non empty RelStr, C be Subset of R;
attr C is strong-chain means
:: DILWORTH:def 13
for S being finite non empty Subset of R
ex P being Clique-partition of subrelstr S
st card P <= stability# R &
ex c being set st c in P & S /\ C c= c &
for d being set st d in P & d <> c holds C /\ d = {};
end;
registration let R be with_finite_stability# non empty RelStr;
cluster strong-chain -> clique for Subset of R;
end;
registration
let R be with_finite_stability# antisymmetric transitive non empty RelStr;
cluster 1-element -> strong-chain for Subset of R;
end;
theorem :: DILWORTH:52 :: Maxsc:
for R being with_finite_stability# non empty antisymmetric transitive RelStr
ex S being non empty Subset of R
st S is strong-chain &
not ex D being Subset of R st D is strong-chain & S c< D;
theorem :: DILWORTH:53 :: Dilworth: General case
for R being with_finite_stability# antisymmetric transitive RelStr
ex C being Clique-partition of R st card C = stability# R;
theorem :: DILWORTH:54 :: A dual of Dilworth's theorem
for R being with_finite_clique# antisymmetric transitive RelStr
ex A being Coloring of R st card A = clique# R;
begin :: Erdos-Szekeres theorem
::$N Erdos-Szekeres Theorem
theorem :: DILWORTH:55 :: CSR
for R being finite antisymmetric transitive RelStr, r, s being Nat
st card R = r*s+1
holds (ex C being Clique of R st card C >= r+1) or
(ex A being StableSet of R st card A >= s+1);
:: In a sequence of n^2+1 (distinct) real numbers there is a monotone
:: subsequence of length at least n+1.
:: Let F be the sequence. Define a RelStr with the carrier equal F (a set
:: of ordered pairs) and the relation defined as: if a = [i,F.i] in F and
:: b = [j,F.j] in F, for some i and j, then a < b iff i < j & F.i < F.j.
:: The relation is asymmetric and transitive.
:: Considered defining FinSubsequence of f but have given up.
:: There is not much gain from having FinSubsequence of f instead of
:: FinSubsequence st g c= f
theorem :: DILWORTH:56
for f being real-valued FinSequence, n being Nat
st card f = n^2+1 & f is one-to-one
ex g being real-valued FinSubsequence
st g c= f & card g >= n+1 & (g is increasing or g is decreasing);