当前位置：网站首页>[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 ;
边栏推荐
- [set theory] partition (partition | partition example | partition and equivalence relationship)
- 带你全流程，全方位的了解属于测试的软件事故
- Split small interface
- Thoughts on project development
- IP home online query platform
- New stills of Lord of the rings: the ring of strength: the caster of the ring of strength appears
- JUC forkjoinpool branch merge framework - work theft
- TreeMap
- Recursion, Fibonacci sequence
- Longest common prefix and
猜你喜欢
【已解决】Unknown error 1146
Common APIs
Homology policy / cross domain and cross domain solutions /web security attacks CSRF and XSS
![[HCAI] learning summary OSI model](/img/90/66505b22e32aa00b26886a9d5c5e4c.jpg)
[HCAI] learning summary OSI model
Pits encountered in the use of El checkbox group
![PdfWriter. GetInstance throws system Nullreferenceexception [en] pdfwriter GetInstance throws System. NullRef](/img/65/1f28071fc15e76abb37f1b128e1d90.jpg)
PdfWriter. GetInstance throws system Nullreferenceexception [en] pdfwriter GetInstance throws System. NullRef
JUC forkjoinpool branch merge framework - work theft
High concurrency memory pool
691. 立方体IV
Store WordPress media content on 4everland to complete decentralized storage
随机推荐
Pits encountered in the use of El checkbox group
The embodiment of generics in inheritance and wildcards
Shim and Polyfill in [concept collection]
OSI knowledge sorting
Upgrade CentOS php7.2.24 to php7.3
“百度杯”CTF比赛 2017 二月场，Web：爆破-1
Arduino Serial系列函数 有关print read 的总结
PdfWriter. GetInstance throws system Nullreferenceexception [en] pdfwriter GetInstance throws System. NullRef
Dora (discover offer request recognition) process of obtaining IP address
你开发数据API最快多长时间？我1分钟就足够了
《指环王：力量之戒》新剧照 力量之戒铸造者亮相
VMWare网络模式-桥接，Host-Only，NAT网络
Margin left: -100% understanding in the Grail layout
The underlying mechanism of advertising on websites
Laravel frame step pit (I)
Talk about floating
Win 2008 R2 crashed at the final installation stage
LeetCode
[attribute comparison] defer and async
High concurrency memory pool