[set theory] binary relationship (definition field | value field | inverse operation | inverse synthesis operation | restriction | image | single root | single value | nature of synthesis operation)

One 、 The domain of the relationship 、 range 、 Domain

---

R

R

R Is an arbitrary set

Domain of definition ( Domain ) :

d

o

m

R

=

{

x

∣

∃

y

(

x

R

y

)

}

dom R = \{ x | \exist y (xRy) \}

domR={ x∣∃y(xRy)}

There is

y

y

y ,

x

x

x And

y

y

y Yes

R

R

R Relationship ,

R

R

R A relationship is a collection , The elements in the set are ordered pairs ,

x

R

y

xRy

xRy yes

<

x

,

y

>

<x,y>

<x,y> Ordered pair ;

R

R

R Ordered pairs in , The first element is

x

x

x , The second element is

y

y

y , Then you can put the

x

x

x Put it into the definition field ;

R

R

R The first element of all ordered pairs in the relationship comes out , Form a domain ;

range ( Range ) :

r

a

n

R

=

{

y

∣

∃

y

(

x

R

y

)

}

ran R = \{ y | \exist y (xRy) \}

ranR={ y∣∃y(xRy)}

R

R

R The first element of all ordered pairs in the relationship comes out , Composition range ;

Domain ( Field ) :

f

l

d

R

=

d

o

m

R

∪

r

a

n

R

fld R = dom R \cup ran R

fldR=domR∪ranR

Domain yes Domain of definition and Union of ranges ;

Two 、 The domain of the relationship 、 range 、 Domain Example

---

1.

R

1

=

{

a

,

b

}

R_1 = \{a, b\}

R1​={ a,b}

R

1

R_1

R1​ There is no ordered pair in , Therefore, its Domain of definition , The value field is empty , Further its Domain Also empty ;

d

o

m

R

1

=

∅

dom R_1 = \varnothing

domR1​=∅

r

a

n

R

1

=

∅

ran R_1 = \varnothing

ranR1​=∅

f

l

d

R

1

=

∅

fld R_1 = \varnothing

fldR1​=∅

2.

R

2

=

{

a

,

b

,

<

c

,

d

>

,

<

e

,

f

>

}

R_2 = \{ a, b, <c, d> , <e,f> \}

R2​={ a,b,<c,d>,<e,f>}

d

o

m

R

2

=

{

c

,

e

}

dom R_2 = \{ c, e \}

domR2​={ c,e}

r

a

n

R

2

=

{

d

,

f

}

ran R_2 = \{ d, f \}

ranR2​={ d,f}

f

l

d

R

2

=

{

c

,

d

,

e

,

f

}

fld R_2 = \{ c, d, e , f\}

fldR2​={ c,d,e,f}

3.

R

3

=

{

<

1

,

2

>

,

<

3

,

4

>

,

<

5

,

6

>

}

R_3 = \{ <1,2>, <3, 4> , <5,6> \}

R3​={ <1,2>,<3,4>,<5,6>}

d

o

m

R

3

=

{

1

,

3

,

5

}

dom R_3 = \{ 1, 3, 5 \}

domR3​={ 1,3,5}

r

a

n

R

3

=

{

2

,

4

,

6

}

ran R_3 = \{ 2, 4, 6 \}

ranR3​={ 2,4,6}

f

l

d

R

3

=

{

1

,

2

,

3

,

4

,

5

,

6

}

fld R_3 = \{ 1, 2, 3, 4,5, 6\}

fldR3​={ 1,2,3,4,5,6}

3、 ... and 、 Inverse operation of relation

---

Any collection

F

,

G

F , G

F,G , The two sets here are relations , The elements in the set are ordered pairs

Inverse operation ( Inverse ) :

F

−

1

=

{

<

x

,

y

>

∣

y

F

x

}

F^{-1} = \{ <x, y> | yFx \}

F−1={ <x,y>∣yFx}

take

F

F

F All elements of the ordered alignment in the relationship , Change direction back and forth , The first element in the ordered alignment becomes the second element , The second element becomes the first element ;

Such as : take

y

F

x

yFx

yFx , yes

<

y

,

x

>

<y, x>

<y,x> Ordered pair , become

<

x

,

y

>

<x, y>

<x,y> Ordered pair ;

Four 、 Inverse composition operation of relation

---

Reverse order synthesis ( Composite ) :

F

o

G

=

{

<

x

,

y

>

∣

∃

z

(

x

G

z

∧

z

F

y

)

}

FoG = \{ <x, y> | \exist z ( xGz \land zFy ) \}

FoG={ <x,y>∣∃z(xGz∧zFy)}

If Relationship

G

G

G There is

<

x

,

z

>

<x,z>

<x,z> Ordered pair , Relationship

F

F

F There is

<

z

,

y

>

<z, y>

<z,y> Ordered pair , You can get a new ordered pair

<

x

,

y

>

<x,y>

<x,y> , The new order pair is Relationship

F

F

F and Relationship

G

G

G Synthesis In the result of the calculation ;

This synthesis is Reverse order synthesis , First use

F

o

G

FoG

FoG In the back

G

G

G The order of the relationship is right , And then use The former

F

F

F Ordered pairs in ;

Reverse order synthesis The corresponding is sequential synthesis , Generally, reverse order synthesis is used , Its nature is convenient to use ;

5、 ... and 、 Relationship constraints

---

For any set

F

,

A

F, A

F,A , Can define

F

F

F Assemble in

A

A

A On the assembly Limit ( Restriction ) :

F

↾

A

=

{

<

x

,

y

>

∣

x

F

y

∧

x

∈

A

}

F \upharpoonright A = \{ <x, y> | xFy \land x \in A \}

F↾A={ <x,y>∣xFy∧x∈A}

analysis :

F

F

F A set is a relation , Its element is Ordered pair

A

A

A Sets are ordinary sets , Its elements are simply single elements ;

F

F

F In the collection Ordered pair In the elements , If Ordered right First element stay

A

A

A Collection , Then pick out this ordered pair , Put it in a new collection , This new set is called

F

F

F Assemble in

A

A

A On the assembly Limit , Write it down as

F

↾

A

F \upharpoonright A

F↾A ;

Above Limit ( Restriction ) It's a limitation The first element in an ordered pair ;

If you want to Limit the second element , take

F

F

F Orderly aligned in a set The second element belongs to

A

A

A Select the ordered pairs of the set of , Can be

F

F

F Inverse the relation , then seek

F

−

1

F^{-1}

F−1 The limitation of ;

The result of restriction is still a relationship , The elements in its set are ordered pairs ;

6、 ... and 、 Image of relationship

---

For any set

F

,

A

F, A

F,A , Can define

F

F

F Assemble in

A

A

A On the assembly image ( Image ) :

F

(

A

)

=

r

a

n

(

F

↾

A

)

F(A) = ran(F \upharpoonright A)

F(A)=ran(F↾A)

namely ,

F

F

F stay

A

A

A On the assembly Limit ( Restriction ) Range of values ;

Another way to express :

F

[

A

]

=

{

y

∣

∃

x

(

x

∈

A

)

∧

x

F

y

}

F [A] = \{ y | \exist x ( x \in A ) \land xFy \}

F[A]={ y∣∃x(x∈A)∧xFy}

take

F

F

F Medium Ordered pair Pick out , Then pick out the first element of the ordered alignment in

A

A

A Ordered pairs in sets , Put the above Pick out the second element of the ordered pair , Put it into a new set , This set is yes

F

F

F stay

A

A

A On the assembly image ;

image The result is not a relationship , It is Meeting specific requirements Ordered pair set A set consisting of the second element of an ordered pair in ;

7、 ... and 、 Single root

---

Any collection

F

F

F , Single root ( Single Rooted ) Definition :

F

F

F It's single

⇔

\Leftrightarrow

⇔

∀

y

(

y

∈

r

a

n

F

→

∃

!

x

(

x

∈

d

o

m

F

∧

x

F

y

)

)

\forall y ( y \in ran F \to \exist ! x( x \in domF \land xFy ) )

∀y(y∈ranF→∃!x(x∈domF∧xFy))

⇔

\Leftrightarrow

⇔

(

∀

y

∈

r

a

n

F

)

(

∃

!

x

∈

d

o

m

F

)

(

x

F

y

)

( \forall y \in ran F )( \exist ! x \in domF )(xFy)

(∀y∈ranF)(∃!x∈domF)(xFy)

Any one of them

y

y

y ,

y

y

y Is the element in the value range of the ordered alignment , Orderly alignment and

y

y

y Corresponding value

x

x

x Elements , namely

<

x

,

y

>

<x, y>

<x,y> Form an ordered pair , The

x

x

x Exist and unique ;

Ordered pair

<

x

,

y

>

<x, y>

<x,y> Each of them

y

y

y All correspond to different

x

x

x

Some predicate formula descriptions :

∃

!

\exist !

∃! Express Only exist ;

∀

x

(

(

x

∈

A

→

B

(

x

)

)

\forall x ( (x \in A \to B(x) )

∀x((x∈A→B(x)) Can be abbreviated to

(

∀

x

∈

A

)

B

(

x

)

(\forall x \in A)B(x)

(∀x∈A)B(x)

∃

x

(

x

∈

A

∧

B

(

x

)

)

\exist x ( x \in A \land B(x) )

∃x(x∈A∧B(x)) Can be abbreviated to

(

∃

x

∈

A

)

B

(

x

)

(\exist x \in A)B(x)

(∃x∈A)B(x)

8、 ... and 、 Single value

---

Any collection

F

F

F , Single value ( Single Value ) Definition :

F

F

F It is single valued

⇔

\Leftrightarrow

⇔

∀

x

(

x

∈

d

o

m

F

→

∃

!

y

(

y

∈

r

a

n

F

∧

x

F

y

)

)

\forall x ( x \in dom F \to \exist ! y( y \in ranF \land xFy ) )

∀x(x∈domF→∃!y(y∈ranF∧xFy))

⇔

\Leftrightarrow

⇔

(

∀

x

∈

d

o

m

F

)

(

∃

!

y

∈

r

a

n

F

)

(

x

F

y

)

( \forall x \in dom F )( \exist ! y \in ranF )(xFy)

(∀x∈domF)(∃!y∈ranF)(xFy)

Any one of them

x

x

x ,

x

x

x Is the definition field in the ordered pair, and the elements in the field , Orderly alignment and

x

x

x Corresponding value

y

y

y Elements , namely

<

x

,

y

>

<x, y>

<x,y> Form an ordered pair , The

y

y

y Exist and unique ;

Ordered pair

<

x

,

y

>

<x, y>

<x,y> Each of them

x

x

x All correspond to different

y

y

y

Nine 、 The nature of composition operation

---

R

1

,

R

2

,

R

3

R_1, R_2, R_3

R1​,R2​,R3​ It's three sets , It has the following properties :

(

R

1

o

R

2

)

o

R

3

=

(

R

1

o

(

R

2

o

R

3

)

)

(R_1 o R_2) o R_3 = (R_1 o ( R_2 o R_3 ))

(R1​oR2​)oR3​=(R1​o(R2​oR3​))

F

,

G

F, G

F,G It's two sets , It has the following properties :

(

F

o

G

)

−

1

=

G

−

1

o

F

−

1

(F o G)^{-1} = G^{-1} o F^{-1}

(FoG)−1=G−1oF−1

Inverse of composition operation be equal to The composition of the inverse of two sets ;