文档介绍：Algeb ra of Sets
Y u Jiangsheng
c
Institute putational Linguistics
P eking Universit y
General Union Axiom
Axiom 1 F o r any set A , there exists a set B
whose elements a re exactly the memb ers of
the memb ers of A :
8 x [ x 2 B $ ( 9 b 2 A ) x 2 b ]
S
W e de ne A as follo ws:
[
x 2 A $ ( 9 b 2 A ) x 2 b
1
Examples of General Union
S
Example 1 If A = f b ;b ;b ; g ,then A =
0 1 2
S
b = f x j x b elongs to some memb er b of A g
i i
i
Example 2 Supp ose that a; b a re t w o given
sets
S
f a; b g = f x j x b elongs to some of f a; b gg
= f x j x b elongs to a o r to b g
= a [ b
2
General Intersection
Theo rem 1 F o r any nonempt y set A , there
T
exists a unique set B (denoted b y A ). fo r
any x , x 2 B $ x b elongs to every memb er
of A .
Pro of Let c 2 A be some xed memb er, b y
the Subset Axiom there exists a set B . fo r
any x ,
x 2 B $ x 2 c and x bo x belongs to
every other memeb er of A
$ x b elongs to every memeb er of A
3
Some Prop erties
Prop ert y 1 Let f ; g = f[ ; \g :
Commutative La w : A B = B A
Asso ciative La w : A ( B C )= ( A B ) C
Distributive La w : A ( B C )= ( A B ) ( A C )
De Mo rgan's La w : C
( A B ) = ( C
A )
( C
B )
4
Mo re Prop erties
Prop ert y 2 Mo re general cases:
General Distributi ve La w
T T
1. A [ B = f A [ X j X 2Bg
S S
2. A \ B = f A \ X j X 2Bg
General De Mo rgan's La w (fo r A6 = ; )
S T
1. C
A = f C
A j X 2Ag
T S
2. C
A = f C
A j X 2Ag
5
Prop erties ab out Empt yset
Prop ert y 3 V ery intuitive:
1. A [; = A and A \; = ;
2. A \ ( C
A )= ; and A [ ( C
A )= A [ C
A C
descib es the second p rop ert y .
6
What's a map?
De nition 1 Given t w o classes A and B , a
map (function) f from A to B (denoted b y
f : A ! B ) is a co rresp ondence that fo r any
a 2 A , there exists an element b = f ( a ) 2 B .
f
a
z
A
b
B
7
Some Notes on Map
De