当前位置：网站首页>[set theory] order relation (chain | anti chain | chain and anti chain example | chain and anti chain theorem | chain and anti chain inference | good order relation)

[set theory] order relation (chain | anti chain | chain and anti chain example | chain and anti chain theorem | chain and anti chain inference | good order relation)

2022-07-03 09:16:00 【Programmer community】

List of articles

One 、 chain
Two 、 Anti chain
3、 ... and 、 Chain and anti chain examples
Four 、 Chain and anti chain theorem
5、 ... and 、 Chain and anti chain inference
6、 ... and 、 Examples of chain and anti chain inference
7、 ... and 、 Good order relationship

One 、 chain

≼

<A, \preccurlyeq>

$< A, ≼ >$ yes Posets ,

⊆

B \subseteq A

$B \subseteq A$ ,

A group of elements in a partial order set form a set

$B$ , If

$B$ Both elements in the set are comparable , said

$B$ The set is the partially ordered set

≼

<A, \preccurlyeq>

$< A, ≼ >$ Chain ;

Symbolize :

∀

(

∈

∧

∈

→

And

can

Than

)

\forall x \forall y ( x \in B \land y \in B \to x And y Comparable )

$\forall x \forall y (x \in B \land y \in B \to x And y can Than)$

The essence of a chain is a set

∣

|B|

$∣ B ∣$ Is the length of the chain

Two 、 Anti chain

≼

<A, \preccurlyeq>

$< A, ≼ >$ yes Posets ,

⊆

B \subseteq A

$B \subseteq A$ ,

A group of elements in a partial order set form a set

$B$ , If

$B$ Both elements in the set There is no comparison , said

$B$ The set is the partially ordered set

≼

<A, \preccurlyeq>

$< A, ≼ >$ Of Anti chain ;

Symbolize :

∀

(

∈

∧

∈

∧

≠

→

And

can

Than

)

\forall x \forall y ( x \in B \land y \in B \land x\not= y \to x And y There is no comparison )

$\forall x \forall y (x \in B \land y \in B \land x \neq = y \to x And y No can Than)$

The essence of anti chain is a set

∣

|B|

$∣ B ∣$ Is the length of the anti chain

3、 ... and 、 Chain and anti chain examples

Reference blog : 【 Set theory 】 Partial order relation Analysis of related topics ( Partial order relation Special elements in | Draw hastu | chain | Anti chain )

Four 、 Chain and anti chain theorem

≼

<A, \preccurlyeq>

$< A, ≼ >$ yes Posets ,

⊆

B \subseteq A

$B \subseteq A$ ,

$A$ The longest chain length in the set is

$n$ , The conclusion is as follows :

①

$A$ There are maximal elements in the set ;

$A$ The maximal element of a set is the largest element in the longest chain ;

②

$A$ Exists in collection

$n$ Partition blocks , Every partition is anti chain ;

take chain The maximal element in , Elements that are not comparable to this maximal element are placed in a set , Form a partition ; ( Note that the elements in the partition are not comparable to each other )

Among the remaining elements on the chain , Choose a very big yuan again , Then put the elements that are not comparable to the maximal element into a set , Form another partition ;

⋮

\vdots

$⋮$

The following example explains how to divide :

Insert picture description here

The above partial order set , The longest chain length is

$6$ ;

① Will be the largest yuan

g,h

$g, h$ , The remaining elements that are not comparable to this maximal element

$k$ Put in a collection ;

{

}

A_1 = \{ g , h , k \}

$A_{1} = {g, h, k}$

② Put the maximal elements of the remaining elements

$f$ , The remaining elements that are not comparable to this maximal element

$j$ Put in a collection ;

{

}

A_2 = \{ f,j \}

$A_{2} = {f, j}$

③ Put the maximal elements of the remaining elements

$e$ , The remaining elements that are not comparable to this maximal element

$i$ Put in a collection ;

{

}

A_3 = \{ e, i \}

$A_{3} = {e, i}$

④ Put the maximal elements of the remaining elements

$d$ , The rest of the elements are related to Kobe Bryant ;

{

}

A_4 = \{ d \}

$A_{4} = {d}$

⑤ Put the maximal elements of the remaining elements

$c$ , The rest of the elements are related to Kobe Bryant ;

{

}

A_5 = \{ c\}

$A_{5} = {c}$

⑥ Put the maximal elements of the remaining elements

a,b

$a, b$ , There are no remaining elements ;

{

}

A_6 = \{ a,b \}

$A_{6} = {a, b}$

The whole is divided into :

{

}

{

}

{

}

{

}

{

}

{

}

\mathscr{A} = \{ \{ g , h , k \} ,\{ f,j \} , \{ e, i \} , \{ d \} , \{ c\} , \{ a,b \} \}

$A = {{g, h, k}, {f, j}, {e, i}, {d}, {c}, {a, b}}$

Remove one layer of the longest chain every time , Finally, remove the longest chain , obtain

$n$ Partition blocks ;

5、 ... and 、 Chain and anti chain inference

≼

<A, \preccurlyeq>

$< A, ≼ >$ yes Posets ,

⊆

B \subseteq A

$B \subseteq A$ ,

$A$ Set size is

mn + 1

$m n + 1$ ,

∣

|A| = mn + 1

$∣ A ∣ = m n + 1$ , The conclusion is as follows :

$A$ Either exists in the set

m+1

$m + 1$ Anti chain of , Or there is

n + 1

$n + 1$ Chain ;

Use the counter evidence to prove :

If neither

m+1

$m + 1$ Anti connection of , There is no

n + 1

$n + 1$ Chain ,

Suppose you have a length of

$n$ Chain , The length is

$m$ Anti connection of ,

$A$ The set is divided at most

$n$ Partition blocks , Each partition has at most

$m$ Elements , The set has at most

m n

$m n$ Elements , And

∣

|A| = mn + 1

$∣ A ∣ = m n + 1$ contradiction ;

6、 ... and 、 Examples of chain and anti chain inference

Insert picture description here

The above partial order set , The longest chain length is

$6$ ;

{

}

A = \{ a,b,c,d,e,f,g,h,k,j,i \}

$A = {a, b, c, d, e, f, g, h, k, j, i}$ Collection , The number of elements is

$11$ individual ,

$A$ There are

The length is
6
6
$6$ Chain ,
{
a
,
c
,
d
,
e
,
f
,
g
}
\{ a, c,d, e,f, g \}
${a, c, d, e, f, g}$ ,
{
b
,
c
,
d
,
e
,
f
,
h
}
\{ b, c,d, e,f, h \}
${b, c, d, e, f, h}$
The length is
3
3
$3$ Anti chain of ,
{
g
,
h
,
k
}
\{ g,h,k \}
${g, h, k}$ ,
{
a
,
b
,
i
}
\{ a,b,i \}
${a, b, i}$ ,
{
g
,
h
,
i
}
\{ g,h,i \}
${g, h, i}$ ,
{
a
,
b
,
k
}
\{ a,b,k \}
${a, b, k}$

∣

|A| = 11 = 2 \times 5 + 1

$∣ A ∣ = 11 = 2 \times 5 + 1$

$A$ The set either has a length of

2 + 1 = 3

$2 + 1 = 3$ Anti chain of , Or there is a length of

5 + 1 = 6

$5 + 1 = 6$ Chain ; ( Both are satisfied )
or

$A$ The set either has a length of

5 + 1 = 6

$5 + 1 = 6$ Anti chain of , Or there is a length of

2 + 1 = 3

$2 + 1 = 3$ Chain ; ( The satisfying length is

$3$ Chain )

$A$ Partition on set :

$\mathscr{A} = \{ \{ g , h , k \} ,\{ f,j \} , \{ e, i \} , \{ d \} , \{ c\} , \{ a,b \} \}A={ { g,h,k},{ f,j},{ e,i},{ d},{ c},{ a,b}}$
$\mathscr{A} = \{ \{ g , h \} ,\{ f \} , \{ e \} , \{ d \} , \{ c, j\} , \{ a,b , i \} \}A={ { g,h},{ f},{ e},{ d},{ c,j},{ a,b,i}}$