当前位置：网站首页>[set theory] order relation (partial order relation | partial order set | example of partial order set)
[set theory] order relation (partial order relation | partial order set | example of partial order set)
2022-07-03 07:22:00 【Programmer community】
List of articles
- One 、 Partial order relation
- Two 、 Posets
- 3、 ... and 、 Examples of partial order relationships ( Greater than or equal to 、 Less than or equal to 、 to be divisible by | Ordered pairs of elements are single values )
- Four 、 Examples of partial order relationships 2 ( Inclusion relation | An ordered pair of elements is a set )
- 5、 ... and 、 Examples of partial order relationships 3 ( Refinement relation | Order is a family of elements )
One 、 Partial order relation
Partial order relation :
Given a non empty set
A
A
A ,
A
≠
∅
A \not= \varnothing
A=∅ ,
R
R
R The relationship is
A
A
A Binary relations on sets ,
R
⊆
A
×
A
R \subseteq A \times A
R⊆A×A ,
If
R
R
R The relationship satisfies the following properties :
- introspect : All vertices in the graph They all have rings ;
- antisymmetric : Between two vertices Yes
0
0
0 Or
1
1
1 A directed edge ;
- Pass on : Premise
a
→
b
,
b
→
c
a \to b , b\to c
a→b,b→c Don't set up Default delivery ; Premise
a
→
b
,
b
→
c
a \to b , b\to c
a→b,b→c establish Must satisfy
a
→
c
a \to c
a→c There is ;
said
R
R
R The relationship is
A
A
A On the assembly Partial order relation ;
Partial order relation representation : Use
≼
\preccurlyeq
≼ Symbols indicate partial order relations , pronounce as “ Less than or equal to ” ;
Symbolize :
<
x
,
y
>
∈
R
⇔
x
R
y
⇔
x
≼
y
<x,y> \in R \Leftrightarrow xRy \Leftrightarrow x \preccurlyeq y
<x,y>∈R⇔xRy⇔x≼y , Reading :
<
x
,
y
>
<x,y>
<x,y> Ordered pairs are in partial order relation
R
R
R in , be
x
x
x And
y
y
y There are
R
R
R Relationship ,
x
x
x Less than or equal to
y
y
y ;
Equivalence relation Is used for classification Of , Partial order relation Is used for organization Of , Inside each class , Give a structure ;
Two 、 Posets
Posets :
≼
\preccurlyeq
≼ Relationship yes
A
A
A Partial order relations on sets , said aggregate
A
A
A And Partial order relation
≼
\preccurlyeq
≼ Composed of Ordered pair
<
A
,
≼
>
<A, \preccurlyeq>
<A,≼> It is called a poset ;
If there is a partial order relation on a set , Then this set is called a poset ;
3、 ... and 、 Examples of partial order relationships ( Greater than or equal to 、 Less than or equal to 、 to be divisible by | Ordered pairs of elements are single values )
Greater than or equal to 、 Less than or equal to 、 Division relations yes Ordered pair set , Each of them Elements of ordered pairs yes Single numeric element ;
1. Greater than or equal to 、 Less than or equal to
∅
≠
A
⊆
R
\varnothing \not=A \subseteq R
∅=A⊆R , Nonempty set
A
A
A , Is a set of real numbers
R
R
R Subset ;
aggregate
A
A
A The greater than or equal relationship on , Less than or equal to , Are partial order relations , Both relationships satisfy introspect , antisymmetric , Pass on Relationship ;
The poset is expressed as :
<
A
,
≤
>
,
<
A
,
≥
>
<A , \leq> , <A, \geq>
<A,≤>,<A,≥>
The greater than or equal relationship set represents :
≥
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
≥
y
}
\geq = \{<x, y>\ | x,y \in A \land x \geq y \}
≥={ <x,y> ∣x,y∈A∧x≥y}
The less than or equal relationship set represents :
≤
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
≤
y
}
\leq = \{<x, y>\ | x,y \in A \land x \leq y \}
≤={ <x,y> ∣x,y∈A∧x≤y}
2. Division relations
∅
≠
A
⊆
Z
+
=
{
x
∣
x
∈
Z
∧
x
>
0
}
\varnothing \not=A \subseteq Z_+ = \{ x | x \in Z \land x > 0 \}
∅=A⊆Z+={ x∣x∈Z∧x>0} , Nonempty set
A
A
A , Is a set of positive integers
Z
+
Z_+
Z+ Subset ;
aggregate
A
A
A Upper Division relations It's a partial order relationship , Divisible relations are all satisfied introspect , antisymmetric , Pass on Relationship ;
The poset is expressed as :
<
A
,
∣
>
<A , |>
<A,∣>
The set of divisible relations represents :
∣
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
∣
y
}
|= \{<x, y>\ | x,y \in A \land x | y \}
∣={ <x,y> ∣x,y∈A∧x∣y}
x
x
x to be divisible by
y
y
y ,
x
∣
y
x|y
x∣y ,
x
x
x It's a divisor ( molecular ) ,
y
y
y It's a dividend ( The denominator ) ;
y
x
\dfrac{y}{x}
xy
Reference resources : 【 Set theory 】 Binary relationship ( Special relationship types | Empty relation | Identity | Global relations | Division relations | Size relationship ) 3、 ... and 、 Division relations
Four 、 Examples of partial order relationships 2 ( Inclusion relation | An ordered pair of elements is a set )
Inclusion relation yes Ordered pair set , Each of them Elements of ordered pairs yes aggregate ;
Set family
A
\mathscr{A}
A Included in
A
A
A The power set of a set ,
A
⊆
P
(
A
)
\mathscr{A}\subseteq P(A)
A⊆P(A) ;
Inclusion relation ,
x
x
x Included in
y
y
y , Symbolize :
⊆
=
{
<
x
,
y
>
∣
x
,
y
∈
A
∧
x
⊆
y
}
\subseteq = \{<x,y> | x,y \in \mathscr{A} \land x \subseteq y \}
⊆={ <x,y>∣x,y∈A∧x⊆y}
Include examples of relationships :
Premise :
aggregate
A
=
{
a
,
b
}
A = \{ a, b \}
A={ a,b}
Set family
A
1
=
{
∅
,
{
a
}
,
{
b
}
}
\mathscr{A}_1 = \{ \varnothing , \{ a \} , \{ b \} \}
A1={ ∅,{ a},{ b}}
Set family
A
2
=
{
{
a
}
,
{
a
,
b
}
}
\mathscr{A}_2 = \{ \{ a \} , \{ a , b \} \}
A2={ { a},{ a,b}}
Set family
A
3
=
P
(
A
)
=
{
∅
,
{
a
}
,
{
b
}
,
{
a
,
b
}
}
\mathscr{A}_3 = P(A) = \{ \varnothing , \{ a \} , \{ b \} , \{ a , b \} \}
A3=P(A)={ ∅,{ a},{ b},{ a,b}} , This family is also
A
A
A Power set of ;
Use ordered pairs to represent the following containment relationships , Every element of an ordered pair is a set ;
① Set family
A
1
\mathscr{A}_1
A1 All inclusive relationships on :
⊆
1
=
I
A
1
∪
{
<
∅
,
{
a
}
>
,
<
∅
,
{
b
}
>
}
\subseteq_1 = I_{\mathscr{A}_1} \cup \{ <\varnothing , \{ a \}> , <\varnothing , \{ b \}> \}
⊆1=IA1∪{ <∅,{ a}>,<∅,{ b}>}
The identity relation on a set family is an inclusion relation , Any set is contained in the set itself ;
An empty set is contained in any non empty set ;
② Set family
A
2
\mathscr{A}_2
A2 All inclusive relationships on :
⊆
2
=
I
A
2
∪
{
<
{
a
}
,
{
a
,
b
}
>
}
\subseteq_2 = I_{\mathscr{A}_2} \cup \{ <\{ a \}, \{ a, b \}> \}
⊆2=IA2∪{ <{ a},{ a,b}>}
The identity relation on a set family is an inclusion relation , Any set is contained in the set itself ;
{
a
}
\{ a \}
{ a} Set contained in
{
a
,
b
}
\{ a, b \}
{ a,b} aggregate ;
③ Set family
A
3
\mathscr{A}_3
A3 All inclusive relationships on :
⊆
3
=
I
A
3
∪
{
<
∅
,
{
a
}
>
,
<
∅
,
{
b
}
>
,
<
∅
,
{
a
,
b
}
>
,
{
<
{
a
}
,
{
a
,
b
}
>
}
,
{
<
{
b
}
,
{
a
,
b
}
>
}
}
\subseteq_3 = I_{\mathscr{A}_3} \cup \{ <\varnothing , \{ a \}> , <\varnothing , \{ b \}> , <\varnothing , \{ a,b \}> , \{ <\{ a \}, \{ a, b \}> \} , \{ <\{ b \}, \{ a, b \}> \} \}
⊆3=IA3∪{ <∅,{ a}>,<∅,{ b}>,<∅,{ a,b}>,{ <{ a},{ a,b}>},{ <{ b},{ a,b}>}}
The identity relation on a set family is an inclusion relation ;
An empty set is contained in any non empty set ;
{
a
}
\{ a \}
{ a} Set contained in
{
a
,
b
}
\{ a, b \}
{ a,b} aggregate ;
{
b
}
\{ b \}
{ b} Set contained in
{
a
,
b
}
\{ a, b \}
{ a,b} aggregate ;
5、 ... and 、 Examples of partial order relationships 3 ( Refinement relation | Order is a family of elements )
Refinement relation yes Ordered pair set , Each of them Elements of ordered pairs yes Set family ;
aggregate
A
A
A Non empty ,
π
\pi
π yes
A
A
A Set divided into sets , Every partition is a set family ;
Divide reference : 【 Set theory 】 Divide ( Divide | Partition example | Partition and equivalence )
There is a relationship between sets , Refinement relation , Using symbols
≼
Add
fine
\preccurlyeq_{ Refine }
≼ Add fine Express ;
Refinement relation
≼
Add
fine
\preccurlyeq_{ Refine }
≼ Add fine Symbolize :
≼
Add
fine
=
{
<
x
,
y
>
∣
x
,
y
∈
π
∧
x
yes
y
Of
Add
fine
}
\preccurlyeq_{ Refine } = \{ <x, y> | x, y \in \pi \land x yes y The refinement of \}
≼ Add fine ={ <x,y>∣x,y∈π∧x yes y Of Add fine }
Premise :
aggregate
A
=
{
a
,
b
,
c
}
A = \{ a, b , c \}
A={ a,b,c}
Set family
A
1
=
{
{
a
,
b
,
c
}
}
\mathscr{A}_1 = \{ \{ a , b , c \} \}
A1={ { a,b,c}}
Set family
A
2
=
{
{
a
}
,
{
b
,
c
}
}
\mathscr{A}_2 = \{ \{ a \} , \{ b , c \} \}
A2={ { a},{ b,c}}
Set family
A
3
=
{
{
b
}
,
{
a
,
c
}
}
\mathscr{A}_3= \{ \{ b \} , \{ a , c \} \}
A3={ { b},{ a,c}}
Set family
A
4
=
{
{
c
}
,
{
a
,
b
}
}
\mathscr{A}_4= \{ \{ c \} , \{ a , b \} \}
A4={ { c},{ a,b}}
Set family
A
5
=
{
{
a
}
,
{
b
}
,
{
c
}
}
\mathscr{A}_5= \{ \{ a \} , \{ b \} , \{ c \} \}
A5={ { a},{ b},{ c}}
The above families are
A
A
A Partition of sets ;
Divide the set , Form a new set ;
π
1
=
{
A
1
,
A
2
}
\pi_1 = \{ \mathscr{A}_1 , \mathscr{A}_2 \}
π1={ A1,A2}
π
2
=
{
A
2
,
A
3
}
\pi_2 = \{ \mathscr{A}_2 , \mathscr{A}_3 \}
π2={ A2,A3}
π
3
=
{
A
1
,
A
2
,
A
3
,
A
4
,
A
5
}
\pi_3 = \{ \mathscr{A}_1 , \mathscr{A}_2 , \mathscr{A}_3 , \mathscr{A}_4, \mathscr{A}_5 \}
π3={ A1,A2,A3,A4,A5}
①
π
1
\pi_1
π1 The refinement relationship of partition elements in the set :
≼
1
=
I
π
1
∪
{
<
A
2
,
A
1
>
}
\preccurlyeq_1 = I_{\pi1} \cup \{<\mathscr{A}_2, \mathscr{A}_1>\}
≼1=Iπ1∪{ <A2,A1>}
Each division is its own refinement ;
A
2
\mathscr{A}_2
A2 yes
A
1
\mathscr{A}_1
A1 The refinement of ,
A
2
\mathscr{A}_2
A2 Less than or equal to
A
1
\mathscr{A}_1
A1 ;
②
π
2
\pi_2
π2 The refinement relationship of partition elements in the set :
≼
2
=
I
π
2
\preccurlyeq_2 = I_{\pi2}
≼2=Iπ2
Each division is its own refinement ;
A
2
,
A
3
\mathscr{A}_2 , \mathscr{A}_3
A2,A3 Neither of them is the refinement of the other ;
③
π
3
\pi_3
π3 The refinement relationship of partition elements in the set :
≼
3
=
I
π
3
∪
{
<
A
2
,
A
1
>
,
<
A
3
,
A
1
>
,
<
A
4
,
A
1
>
,
<
A
5
,
A
1
>
,
<
A
5
,
A
2
>
,
<
A
5
,
A
3
>
,
<
A
5
,
A
4
>
}
\preccurlyeq_3 = I_{\pi3} \cup \{<\mathscr{A}_2, \mathscr{A}_1> , <\mathscr{A}_3, \mathscr{A}_1> , <\mathscr{A}_4, \mathscr{A}_1> , <\mathscr{A}_5, \mathscr{A}_1> , <\mathscr{A}_5, \mathscr{A}_2> , <\mathscr{A}_5, \mathscr{A}_3> , <\mathscr{A}_5, \mathscr{A}_4> \}
≼3=Iπ3∪{ <A2,A1>,<A3,A1>,<A4,A1>,<A5,A1>,<A5,A2>,<A5,A3>,<A5,A4>}
Each division is its own refinement ;
Any division is
A
1
\mathscr{A}_1
A1 The refinement of ;
A
1
\mathscr{A}_1
A1 It's the biggest , Greater than or equal to any other partition ;
A
5
\mathscr{A}_5
A5 It is the refinement of any division ;
A
5
\mathscr{A}_5
A5 The smallest is the smallest , Less than or equal to any other partition ;
边栏推荐
- Take you through the whole process and comprehensively understand the software accidents that belong to testing
- [Fiddler problem] solve the problem about Fiddler's packet capturing. After the mobile network is configured with an agent, it cannot access the Internet
- LeetCode
- 【已解决】win10找不到本地组策略编辑器解决方法
- 你开发数据API最快多长时间？我1分钟就足够了
- Advanced APL (realize group chat room)
- Recursion, Fibonacci sequence
- [solved] sqlexception: invalid value for getint() - 'Tian Peng‘
- Win 10 find the port and close the port
- Advanced API (use of file class)
猜你喜欢
随机推荐
LeetCode
【最详细】最新最全Redis面试大全（50道）
Pits encountered in the use of El checkbox group
Jeecg data button permission settings
Crontab scheduled task
【CMake】CMake链接SQLite库
Split small interface
Interview questions about producers and consumers (important)
Upgrade CentOS php7.2.24 to php7.3
VMware virtual machine installation
7.2刷题两个
你开发数据API最快多长时间？我1分钟就足够了
IO stream system and FileReader, filewriter
[untitled]
Advanced API (multithreading 02)
docket
Visit Google homepage to display this page, which cannot be displayed
twenty million two hundred and twenty thousand three hundred and nineteen
Homology policy / cross domain and cross domain solutions /web security attacks CSRF and XSS
The underlying mechanism of advertising on websites