当前位置：网站首页>[set theory] partial order relation (partial order relation definition | partial order set definition | greater than or equal to relation | less than or equal to relation | integer division relation |

[set theory] partial order relation (partial order relation definition | partial order set definition | greater than or equal to relation | less than or equal to relation | integer division relation |

2022-07-03 03:20:00 【Programmer community】

List of articles

One . Partial order relation
- 1. Partial order relation definition
- - ( 1 ) Partial order relation definition ( introspect | antisymmetric | Pass on )
  - ( 2 ) Partial order relation And Equivalence relation ( Equivalence relation Used for classification | Partial order relation Used to organize )
- 2. Poset definition
- - ( 1 ) Poset definition
Two . Partial order relation Example
- 1. Less than or equal to
- - ( 1 ) Less than or equal to explain
  - ( 2 ) Less than or equal to analysis
- 2. Relationship greater than or equal to
- - ( 1 ) Relationship greater than or equal to explain
  - ( 2 ) Relationship greater than or equal to analysis
- 3. Division relations
- - ( 1 ) Division relations explain
  - ( 2 ) Division relations analysis
- 4. Inclusion relation
- - ( 1 ) Inclusion relation explain
  - ( 2 ) Inclusion relation analysis
- 5. Refinement relation
- - ( 1 ) Refinement relation explain
  - ( 2 ) Refinement relation analysis

One . Partial order relation

1. Partial order relation definition

( 1 ) Partial order relation definition ( introspect | antisymmetric | Pass on )

Partial order relation Definition :

1. precondition 1 :
A
̸
=
∅
A \not= \varnothing
$A ̸ = \emptyset$ , also
R
⊆
A
×
A
R \subseteq A \times A
$R \subseteq A \times A$ ;
2. precondition 2 : If
R
R
$R$ yes introspect , antisymmetric , Delivered ;
- ① introspect : Every element own and own Have a relationship ,
  $x R x$ ;
- ② antisymmetric : If $x R y xRy also y R x yRx be x = y x=y x ̸ = y x \not=y , x R y xRy and y R x yRx Can't exist at the same time ; There can be no , But it must not happen at the same time ;$
  $x = y$ , namely
- ③ Pass on : If Yes
  $x R z$ , If the premise does not hold , Then it is also reluctantly called transmission ;
3. Conclusion : call
R
R
$R$ by
A
A
$A$ The partial order relations on the ;
4. Express : Use
⪯
\preceq
$⪯$ Indicates a partial order relation ;
5. How to read :
⪯
\preceq
$⪯$ pronounce as " Less than or equal to " ;
6. Use a formula to express :
<
x
,
y
>
∈
R
*
x
R
y
*
x
⪯
y
<x, y> \in R \Longleftrightarrow xRy \Longleftrightarrow x \preceq y
$< x, y > \in R * x R y * x ⪯ y$
7. Formula interpretation : If
x
x
$x$ ,
y
y
$y$ Two elements constitute Ordered pair
<
x
,
y
>
<x,y>
$< x, y >$ , And in partial order
R
R
$R$ in ,
x
x
$x$ and
y
y
$y$ have
R
R
$R$ Relationship , Or you could write it as
x
x
$x$ Less than or equal to ( Partial order symbol )
y
y
$y$ ;
8. Common partial order relations : Trees On Of Less than or equal to , Containment relationships on sets , Not
0
0
$0$ The integer division relationship between natural numbers , Are common partial order relations ;

( 2 ) Partial order relation And Equivalence relation ( Equivalence relation Used for classification | Partial order relation Used to organize )

Partial order relation And Equivalence relation :

1. Represents the hierarchy : Partial order relation is a very common binary relation , Usually used for Express hierarchy ;
2. Equivalence relation : Equivalence relation yes Used for classification , Will a aggregate It is divided into Several equivalence classes ;
3. Partial order relation : Partial order relation Usually Used to organize , Inside each class , Give it a structure , Especially the hierarchy , There are upper and lower levels ,

2. Poset definition

( 1 ) Poset definition

Posets Definition :

1. precondition 1 : $\preceq⪯ yes A A$
$A$ Upper Partial order relation ;
2. Conclusion : $\preceq>$
$< A, ⪯ >$ Is a partially ordered set ;
3. Reading : aggregate $\preceq$
$⪯$ The order of composition is right , be called Posets ;

Two . Partial order relation Example

1. Less than or equal to

( 1 ) Less than or equal to explain

Examples of posets 1 ( Less than or equal to

≤

\leq

$\leq$ yes Partial order relation ) :

1. The formula says : $\varnothing \not= A \subseteq R , <A , \leq >$
$\emptyset ̸ = A \subseteq R, < A, \leq >$
2. Language description : If $A A yes Set of real numbers R R A A You can't yes An empty set ∅ \varnothing , aggregate A A$
$R$ Of A subset of , also
$A$ Medium Less than or equal to , It's a partial order relationship ;
3. Express relationships in the form of sets : $\leq = \{ <x,y> | x,y \in A \land x \leq y \}$
$\leq = {< x, y > ∣ x, y \in A \land x \leq y}$

( 2 ) Less than or equal to analysis

Set of real numbers

$A$ Upper Less than or equal to (

≤

\leq

$\leq$ ) analysis :

1. Reflexive property analysis : $\leq x$
$x \leq x$ , Is established , Less than or equal to yes Reflexive ;
2. Analysis of antisymmetric properties :
$x = y$ , accord with Antisymmetric property Of Definition , therefore Less than or equal to Relationship yes Antisymmetric ,
3. Transitive property analysis :
$z$ , Is established , therefore Less than or equal to yes Delivered ;
4. summary : in summary , Less than or equal to Relationship yes Partial order relation ;

2. Relationship greater than or equal to

( 1 ) Relationship greater than or equal to explain

Examples of posets 2 ( Relationship greater than or equal to

≥

\geq

$\geq$ yes Partial order relation ) :

1. The formula says : $\varnothing \not= A \subseteq R , <A , \geq >$
$\emptyset ̸ = A \subseteq R, < A, \geq >$
2. Language description : If $A A yes Set of real numbers R R A A You can't yes An empty set ∅ \varnothing , aggregate A A Medium Relationship greater than or equal to ( ≥ \geq$
$R$ Of A subset of , also
$\geq$ ) , It's a partial order relationship ;
3. Express relationships in the form of sets : $\geq = \{ <x,y> | x,y \in A \land x \geq y \}$
$\geq = {< x, y > ∣ x, y \in A \land x \geq y}$

( 2 ) Relationship greater than or equal to analysis

Set of real numbers

$A$ Upper Relationship greater than or equal to (

≥

\geq

$\geq$ ) analysis :

1. Reflexive property analysis : $\geq x$
$x \geq x$ , Is established , Relationship greater than or equal to yes Reflexive ;
2. Analysis of antisymmetric properties :
$x = y$ , accord with Antisymmetric property Of Definition , therefore Greater than or equal to Relationship yes Antisymmetric ,
3. Transitive property analysis :
$z$ , Is established , therefore Relationship greater than or equal to yes Delivered ;
4. summary : in summary , Greater than or equal to Relationship yes Partial order relation ;

3. Division relations

( 1 ) Division relations explain

Examples of posets 3 ( Division relations yes Partial order relation ) :

1. The formula says : $\varnothing \not= A \subseteq Z_+ = \{ x | x \in Z \land x > 0 \}<A , | >$
$\emptyset ̸ = A \subseteq Z_{+} = {x ∣ x \in Z \land x > 0} < A, ∣ >$
2. Language description : If $Z_+$
$Z_{+}$ Of A subset of , also
3. Express relationships in the form of sets : $\{ <x,y> | x,y \in A \land x | y \}$
$∣ = {< x, y > ∣ x, y \in A \land x ∣ y}$
4. Division relations : $x x x yes y y y Factor of, or y y y yes x x x Multiple;$
$x ∣ y$ ,

( 2 ) Division relations analysis

Positive integer set

$A$ Upper Division relations (

∣

$∣$ ) analysis :

1. Reflexive property analysis :
$x ∣ x$ , Is established , Division relations ( | ) yes Reflexive ;
2. Analysis of antisymmetric properties :
$x = y$ , accord with Antisymmetric property Of Definition , therefore to be divisible by Relationship yes Antisymmetric ,
3. Transitive property analysis :
$z$ , Is established , therefore Division relations yes Delivered ;
4. summary : in summary , to be divisible by Relationship yes Partial order relation ;

4. Inclusion relation

( 1 ) Inclusion relation explain

Examples of posets 4 ( Inclusion relation

⊆

\subseteq

$\subseteq$ yes Partial order relation ) :

1. The formula says : $\mathscr{A} \subseteq P(A) , \subseteq = \{<x , y> | x , y \in \mathscr{A} \land x \subseteq y \}$
$A \subseteq P (A), \subseteq = {< x, y > ∣ x, y \in A \land x \subseteq y}$
2. Language description : aggregate $A A The power set on P ( A ) P(A) P ( A ) P(A) Subsets of constitute Set family A \mathscr{A} , This set family A \mathscr{A}$
$P (A)$ ,
$A$ Inclusion relation on , It's a partial order relationship ;

( 2 ) Inclusion relation analysis

analysis A collection of Subset Family The inclusive relationship between :

① Suppose a relatively simple set

{

}

A=\{a, b\}

$A = {a, b}$

② analysis below

$A$ Of 3 Subset family ;

{

∅

{

}

{

}

\mathscr{A}_1 = \{ \varnothing , \{a\} , \{b\} \}

$A_{1} = {\emptyset, {a}, {b}}$

Set family

\mathscr{A}_1

$A_{1}$ contain An empty set

∅

\varnothing

$\emptyset$ , Unit set

{

}

\{a\}

${a}$ , Unit set

{

}

\{b\}

${b}$ ;

{

}

{

}

\mathscr{A}_2 = \{ \{a\} , \{a, b\} \}

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

Set family

\mathscr{A}_2

$A_{2}$ contain Unit set

{

}

\{a\}

${a}$ , 2 Meta set

{

}

\{a, b\}

${a, b}$ ;

(

)

{

∅

{

}

{

}

{

}

\mathscr{A}_3 = P(A) = \{ \varnothing , \{a\} , \{b\} , \{a, b\} \}

$A_{3} = P (A) = {\emptyset, {a}, {b}, {a, b}}$

Set family

\mathscr{A}_3

$A_{3}$ contain An empty set

∅

\varnothing

$\emptyset$ , Unit set

{

}

\{a\}

${a}$ , Unit set

{

}

\{b\}

${b}$ , 2 Meta set

{

}

\{a, b\}

${a, b}$ ; This is a aggregate

$A$ Of Power set ;

③ List the set family

\mathscr{A}_1

$A_{1}$ Inclusion relation on :

⊆

∪

{

∅

{

}

∅

{

}

\subseteq_1 = I_{\mathscr{A}1} \cup \{ <\varnothing , \{a\}> , <\varnothing , \{b\}> \}

$\subseteq_{1} = I_{A 1} \cup {< \emptyset, {a} >, < \emptyset, {b} >}$

⊆

\subseteq_1

$\subseteq_{1}$ Is a collection

\mathscr{A}1

$A 1$ The partial order relations on the ;

namely analysis An empty set

∅

\varnothing

$\emptyset$ , Unit set

{

}

\{a\}

${a}$ , Unit set

{

}

\{b\}

${b}$ Three The containment relationship between sets :

1. Identity $I_{\mathscr{A}1}$
$I_{A 1}$ :
2. $<\varnothing , \{a\}>$
$< \emptyset, {a} >$ : An empty set sure Included in aggregate
3. $<\varnothing , \{b\}>$
$< \emptyset, {b} >$ : An empty set sure Included in aggregate
4. summary : These include relationships Property analysis of :
- ① introspect : Each element itself contain own , $\subseteq A$
  $A \subseteq A$ , The containment relationship has Reflexive nature ;
- ② antisymmetric : If aggregate $\subseteq BA⊆B , B ⊆ A B \subseteq AB⊆A , that A = B A = B$
  $A = B$ , obviously Inclusion relation Have antisymmetric properties ;
- ③ Pass on : If $\subseteq BA⊆B , also A ⊆ C A \subseteq CA⊆C , So there are A ⊆ C A \subseteq C$
  $A \subseteq C$ , Inclusion relation It has transitive property ;

④ List the set family

\mathscr{A}_2

$A_{2}$ Inclusion relation on :

⊆

∪

{

}

{

}

\subseteq_2 = I_{\mathscr{A}2} \cup \{ <\{a\} , \{a, b\}>

$\subseteq_{2} = I_{A 2} \cup {< {a}, {a, b} >$

⊆

\subseteq_2

$\subseteq_{2}$ Is a collection

\mathscr{A}2

$A 2$ The partial order relations on the ;

⑤ List the set family

\mathscr{A}_3

$A_{3}$ Inclusion relation on :

⊆

∪

{

∅

{

}

∅

{

}

∅

{

}

{

}

{

}

{

}

{

}

\subseteq_3 = I_{\mathscr{A}3} \cup \{ <\varnothing , \{a\}> , <\varnothing , \{b\}>, <\varnothing , \{a, b\}> , <\{a\} , \{a, b\}> , <\{b\} , \{a, b\}> \}

$\subseteq_{3} = I_{A 3} \cup {< \emptyset, {a} >, < \emptyset, {b} >, < \emptyset, {a, b} >, < {a}, {a, b} >, < {b}, {a, b} >}$

⊆

\subseteq_3

$\subseteq_{3}$ Is a collection

\mathscr{A}_3

$A_{3}$ The partial order relations on the ;

5. Refinement relation

( 1 ) Refinement relation explain

Examples of posets 5 ( Refinement relation

⪯

Add

fine

\preceq_{ Refine }

$⪯_{Add fine}$ yes Partial order relation ) :

1. Detailed relationship description : $\not= \varnothingA̸=∅ , π \piπ yes from A A$
$A$ Of Some divisions Set of components ;

⪯

Add

fine

{

∣

∈

∧

yes

Add

fine

}

\preceq_{ Refine } = \{<x , y> | x , y \in \pi \land x yes y Of Refine \}

$⪯_{Add fine} = {< x, y > ∣ x, y \in π \land x yes y Of Add fine}$

2. Divide : Divide yes One Set family ( A collection of collections ) , Its elements are collections Also called Fast division , among Every element ( Elements in the set family ) aggregate Medium Elements yes Nonempty set
$A$ The elements of ;
- ① The set family does not contain empty sets ;
- ② Any two sets in this set family do not want to intersect ;
- ③ In this set family all Elements Union and collection , obtain aggregate
  $A$ ;

( 2 ) Refinement relation analysis

analysis A collection of Between divisions Of Refine Relationship :

① aggregate

{

}

A = \{a, b, c\}

$A = {a, b, c}$ , Below Divide and Refine Are based on The aggregate Analyze ;

② below List the set

$A$ Of 5 A division :

Divide 1 : Corresponding 1 An equivalence relation , Divide into 1 class ;

{

}

\mathscr{A}_1 =\{ \{ a, b, c \} \}

$A_{1} = {{a, b, c}}$

Divide 2 : Corresponding 2 An equivalence relation , Divide into 2 class ;

{

}

{

}

\mathscr{A}_2 = \{ \{ a \} , \{ b, c \} \}

$A_{2} = {{a}, {b, c}}$

Divide 3 : Corresponding 2 An equivalence relation , Divide into 2 class ;

{

}

{

}

\mathscr{A}_3 = \{ \{ b \} , \{ a, c \} \}

$A_{3} = {{b}, {a, c}}$

Divide 4 : Corresponding 2 An equivalence relation , Divide into 2 class ;

{

}

{

}

\mathscr{A}_4 = \{ \{ c \} , \{ a, b \}\}

$A_{4} = {{c}, {a, b}}$

Divide 5 : Corresponding 3 An equivalence relation , Divide into 3 class ; Each element has its own kind

{

}

{

}

{

}

\mathscr{A}_5 = \{ \{ a \} , \{ b \}, \{ c \} \}

$A_{5} = {{a}, {b}, {c}}$

③ below List several sets composed of partitions to be analyzed :

aggregate 1 :

{

}

\pi_1 = \{ \mathscr{A}_1, \mathscr{A}_2 \}

$π_{1} = {A_{1}, A_{2}}$

aggregate 2 :

{

}

\pi_2 = \{ \mathscr{A}_2, \mathscr{A}_3 \}

$π_{2} = {A_{2}, A_{3}}$

aggregate 3 :

{

}

\pi_3 = \{ \mathscr{A}_1, \mathscr{A}_2, \mathscr{A}_3, \mathscr{A}_4, \mathscr{A}_5 \}

$π_{3} = {A_{1}, A_{2}, A_{3}, A_{4}, A_{5}}$

④ aggregate

\pi_1

$π_{1}$ Analysis of refinement relationship on :

1. You are your own refinement : Each division , You are your own refinement , therefore Refining the relationship Yes $I_{\pi 1}Iπ1 , < A 1 , A 1 > <\mathscr{A}_1 , \mathscr{A}_1><A1,A1> , < A 2 , A 2 > <\mathscr{A}_2 , \mathscr{A}_2>$
$< A_{2}, A_{2} >$ ;
2. Other details : $\mathscr{A}_2A2 Divided Each partition , All are A 1 \mathscr{A}_1$
$A_{1}$ Divide Middle block A subset of a partitioned block of , So there is
3. Refined definition : $\mathscr{A}_1A1 and A 2 \mathscr{A}_2A2 It's all a collection A A$
$A$ Division ,
$A_{1}$ The refinement of ;

- 4. List the detailed Relations :

⪯

∪

{

}

\preceq_1 = I_{\pi 1} \cup \{ <\mathscr{A}_2, \mathscr{A}_1> \}

$⪯_{1} = I_{π 1} \cup {< A_{2}, A_{1} >}$

⑤ aggregate

\pi_2

$π_{2}$ Analysis of refinement relationship on :

1. You are your own refinement : Each division , You are your own refinement , therefore Refining the relationship Yes $I_{\pi 2}Iπ2 , < A 3 , A 3 > <\mathscr{A}_3 , \mathscr{A}_3><A3,A3> , < A 2 , A 2 > <\mathscr{A}_2 , \mathscr{A}_2>$
$< A_{2}, A_{2} >$ ;
2. Other details : $\mathscr{A}_2A2 and A 3 \mathscr{A}_3$
$A_{3}$ These two divisions are not refinement of each other , therefore There are no other refinements in this set ;

- 4. List the detailed Relations :

⪯

\preceq_2 = I_{\pi 2}

$⪯_{2} = I_{π 2}$

⑥ aggregate

\pi_3

$π_{3}$ Analysis of refinement relationship on :

1. You are your own refinement : Each division , You are your own refinement , therefore Refining the relationship Yes $I_{\pi 3}Iπ3 , < A 1 , A 1 > <\mathscr{A}_1 , \mathscr{A}_1><A1,A1> , < A 2 , A 2 > <\mathscr{A}_2 , \mathscr{A}_2><A2,A2>, < A 3 , A 3 > <\mathscr{A}_3 , \mathscr{A}_3><A3,A3>, < A 4 , A 4 > <\mathscr{A}_4 , \mathscr{A}_4><A4,A4>, < A 5 , A 5 > <\mathscr{A}_5 , \mathscr{A}_5>$
$< A_{5}, A_{5} >$ ;
2. Other details :
- ① And $\mathscr{A}_5$
  $A_{5}$ Divide related refinements :
- ② And $\mathscr{A}_1$
  $A_{1}$ Divide related refinements :
4. List the detailed Relations :

⪯

∪

{

}

\preceq_3 = I_{\pi 3} \cup \{ <\mathscr{A}_5 , \mathscr{A}_4> , <\mathscr{A}_5 , \mathscr{A}_3> , <\mathscr{A}_5 , \mathscr{A}_2> , <\mathscr{A}_5 , \mathscr{A}_1> , <\mathscr{A}_4 , \mathscr{A}_1>, <\mathscr{A}_3 , \mathscr{A}_1>, <\mathscr{A}_2 , \mathscr{A}_1> \}

$⪯_{3} = I_{π 3} \cup {< A_{5}, A_{4} >, < A_{5}, A_{3} >, < A_{5}, A_{2} >, < A_{5}, A_{1} >, < A_{4}, A_{1} >, < A_{3}, A_{1} >, < A_{2}, A_{1} >}$