当前位置：网站首页>[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 ;
边栏推荐
- [plus de détails] dernière entrevue complète redis (50)
- 1. E-commerce tool cefsharp autojs MySQL Alibaba cloud react C RPA automated script, open source log
- Summary of abnormal mechanism of interview
- Margin left: -100% understanding in the Grail layout
- OSI knowledge sorting
- Wireshark software usage
- 【已解决】SQLException: Invalid value for getInt() - ‘田鹏‘
- Split small interface
- Discussion on some problems of array
- Use of file class
猜你喜欢
Mise en place d'un environnement de développement de fonctions personnalisées
The embodiment of generics in inheritance and wildcards
高并发内存池
POI excel percentage
SecureCRT取消Session记录的密码
为什么说数据服务化是下一代数据中台的方向？
New stills of Lord of the rings: the ring of strength: the caster of the ring of strength appears
Wireshark software usage
“百度杯”CTF比赛 2017 二月场，Web：爆破-1
3311. Longest arithmetic
随机推荐
[set theory] equivalence classes (concept of equivalence classes | examples of equivalence classes | properties of equivalence classes | quotient sets | examples of quotient sets)*
Custom generic structure
Specified interval inversion in the linked list
Inno Setup 制作安装包
Longest common prefix and
"Baidu Cup" CTF game 2017 February, Web: blast-1
Chrome 98 Private Network Access problem w/ disabled web security: Request had no target IP address
POI excel percentage
How to specify the execution order for multiple global exception handling classes
[HCAI] learning summary OSI model
Dora (discover offer request recognition) process of obtaining IP address
LeetCode
[solved] sqlexception: invalid value for getint() - 'Tian Peng‘
Basic knowledge about SQL database
Hash table, generic
Talk about floating
在 4EVERLAND 上存储 WordPress 媒体内容，完成去中心化存储
691. 立方体IV
7.2刷题两个
Margin left: -100% understanding in the Grail layout