Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

4. Sets
Stphane Bressan e

September 1, 2009

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

4.1. Introduction
A set is a Many that allows itself to be thought of as a One. by Georg Cantor

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Informal Denition A set is a collection of objects called elements (members) of the set. The following are denitions in extension (or comprehension) of various sets. They are given by enumerating the members of the set. {1, 2, 3}, {apple, orange, red, unicorn}, {1, {1, 2}}. is the empty set.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Intuitive Denition We say that an element e belongs to (or is a member of a set S, noted e S, i it is inside the set. We say that the set S contains the element e. e is not a member of S is noted e S. / 2 {1, 2, 3}, apple {apple, oranges, red, unicorn}, {1, 2} {1, {1, 2}}. 3 {1, 2}, / {1, 2} {1, 2, 3}. / 2 {1, {1, 2}}. /

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

{1, 1, 2, 2, 2} is not a correct representation. We cannot distinguish identical members in a set. There are no duplicates in a seta . We write {1, 2}. {1, 2} = {2, 1}. There is no order of elements in a setb .
a b

a set with duplicates is called a multi-set or a bag -see t-uples-. a set with order and duplicates is called a sequence or a list.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

A set can be dened in intention, i.e. by a property that characterizes the members of the set. This is called the set builder notation. {X | X N 1 < X X < 5}. {X N | 1 < X X < 5}, in this case N is called the domain.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

The property is dened by a formula in rst order logic. The constants that make the formula true when substituted to the free variablesa appearing in the head of the set denition (dene a model) are the members of the set. {X | X N 1 < X X < 5}. {X : X N 1 < X X < 5}. {X N | 1 < X X < 5}, in this case N is called the domain.
a Remember that in this context free variables have an existential interpretation.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition Two sets are equal i they have the same elementsa .
a

This is why there is neither duplicates nor order in a set.

{1, 2, 3} = {X N | 0 < X < 4}, {3, 7} = {X Z | X 2 10X + 21 = 0}.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition A set S is a subset of a set T (or S is included in T ), noted S T , i all the elements of S are elements of T . {1, 2} {1, 2, 3}, {3} {1, 2, 3}, {1, 2, 3}, {3, 4} {1, 2, 3}, {1, 2, 3} {X N | 0 X 4}, {0, 3, 7} {X Z | X 3 10X 2 + 21X = 0}. Warning Do not confuse T S with T S!

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition The union of a set S and a set T , noted S T , is the smallest set that contains the elements of S and the elements of T . {0, 1, 2, 3, 4, 7} = {0, 1, 2, 3, 4} {0, 3, 7}, {0, 1, 2, 3, 4, 5, 6, 7} = {0, 1, 2, 3, 4} {0, 3, 7}, {0, 1, 2, 3, 7} = {X N | 0 X 4} {X Z | X 3 10X 2 + 21X = 0}, {X N Z | (0 X 4) (X 3 10X 2 + 21X = 0)} = {X N | 0 X 4} {X Z | X 3 10X 2 + 21X = 0}.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition The intersection of a set S and a set T , noted S T , is the smallest set that contains the common elements of S and T . {0, 3} = {1, 2, 3, 4} {0, 3, 7}, {0, 3, 7} = {1, 2, 3, 4} {0, 3, 7}, {0, 3} = {X N | 0 X 4} {X Z | X 3 10X 2 + 21X = 0}, {X N Z | (0 X 4) (X 3 10X 2 + 21X = 0)} = {X N | 0 X 4} {X Z | X 3 10X 2 + 21X = 0}.

Introduction Introduction

Set Theory

ZFC

Operations on Sets

Venn Diagrams

To be Continued... We will see more operations on sets later.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Set Theory
Set theory refers to attempts to axiomatize the denition of a set. Set theory denes by axioms, i.e. the expected properties of sets and their elements. In the remainder of this section, the universe of discourse is composed of sets. If necessary we can also consider basic elements called urelements.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.2.1 (Extensionality) X Y ((Z (Z X Z Y )) X = Y ). Sets that have the same elements are equal.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.2.2 X Y (X Y (Z (Z X Z Y ))). We say that a set is a subseta of (included in) another set if and only if all its elements are in the other set. (X Y ) is noted X Y.
a

Some authors use X Y .

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.2.3 A set is a proper subseta of (strictly included in) another set if and only it is included in the other set but the two sets are dierent. We write X Y X = Y .
a

Some authors use X Y . Confusing!

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.2.4 X Y ((X Y Y X ) X = Y ).

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.2.5 (Empty Set) X (Y ((Y X ))).

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.2.6 (Empty is Subset of all Sets) X Z ((Y (Y X )) (X Z )). we want to write Z ( Z )) but we do not know yet that there is only one set X that veries axiom 4.2.5.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof. Let X be such that Y (Y X )

We will show this in the tutorial.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.2.7 (The Empty Set is Unique) X1 X2 Y ((Y X1 ) (Y X2 )). If two sets verify axiom 4.2.5 then they are the same set.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof. Let X1 and X2 be two sets such that Y ((Y X1 ) (Y X2 )).

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.2.8 The empty set (or null set), noted , is the set such that Y (Y ).

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.2.9 (No other Set than Empty is Subset of Empty) Z (Z Z = ).

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.2.10 (Power Set) X Y Z (Z X Z Y ).

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.2.11 (The Power Set is Unique) Y1 Y2 X Z (((Z X Z Y1 ) (Z X Z Y2 )) Y1 = Y2 ) Proof. The proof is omitted.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.2.12 The power set of a set S, noted P(S) or 2S , is the set of all subsets of S.

Introduction Set Theory

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.2.13 (Innity) X ( X (Y (Y X Y {Y } X ))). The axioms state the existence of an innity of sets: , {}, {, {}}, {, {}, {, {}}}, etc.

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

ZFC
The Cumulative Hierarchy A safe way (what is the danger?) to dene sets is to build layers starting from the urelements (or from the empty set).

{{{0}}}, {{{1}}}, {{{, 1}}}, {{}, {{0}}}, {}, {{1}}, {{0, 1}}, {{0}, {}}, {0, {{0}, {1}}, {{0}, {0, 1}}, {0, {0}}, , {0}, {1}, {0, 1} 0, 1

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

An axiomatization of set theory is Zermelo-Fraenkel axioms with the axiom of Choice (referred to as ZFC). This axiomatization uses rst order logic and axioms schemata (higher order logic). ZFC is consistent and non redundant. Every mathematical theorem about set can be proved with ZFC (ZFC is complete). Standard theorems of mathematics can be proved with ZFC.

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.3.1 (Union) X Y Z T ((T X Z T ) Z Y ).

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.3.2 (The Union is Unique) Y1 Y2 X Z forallT ((((T X Z T ) Z Y1 ) ((T X Z T ) Z Y2 )) Y1 = Y2 ). Proof. The proof is omitted.

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.3.3 The union set of a set S, noted X is the set of all elements of the elements of S.

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.3.4 (Pairing) X Y Z T ((T = X T = Y ) T Z ).

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.3.5 (The Pair is Unique) Z1 Z2 X Y T ((((T = X T = Y ) T Z1 ) ((T = X T = Y ) T Z2 )) Z1 = Z2 . Proof. The proof is omitted.

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.3.6 The pair of two sets S and T , noted {S, T } is the set that contains the two elements S and T .

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Axiom 4.3.7 (Regularity) X (X = (Y (Y X Z (Z X (Z Y ))))) Every non-empty set X contains a member Y such that X and Y are disjoint. This axioms forbids that X Y and Y X and similar cycles of membership. It also forbids innite descending chains (... X3 X2 X1 X0 ).

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.3.8 (Zermelo-Fraenkel with Choice) Axiom of Extensionality. Axiom of Empty Set. Axiom of Power Set. Axiom of Innity. Axiom of Union. Axiom of Pairing. Axiom of Regularity. Axiom Schema of Separation. (Not discussed here. About sets in intention.) Axiom Schema of Replacement. (Not discussed here. About functions.) Axiom of Choice. (Not discussed here. About functions.)

Introduction ZFC

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Russells Paradox There is only one barber in a town. The barber is a man. The barber shaves all and only those men who do not shave themselves. Does the barber shave himself? X = {Y | Y X }. Does X X ? / Russells paradox is prevented by the axiom schema of separation in ZFC.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Operations on Sets
Denition 4.4.1 Let S and T be two sets. The union of S and T , noted S T is the set such that: X (X S T (X S X T ))

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.2 Let S and T be two sets. The intersection of S and T , noted S T is the set such that: X (X S T (X S X T ))

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Big Operators We can now dene the big operators:

X.

X S X (this will also be used for generalized Cartesian product). X S X S

X. X.
X {1,2,3} X ? X {1,2,3} X ? X P(S) X ? X S

What is What is What is What is

X?

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.3 Let S and T be two sets. S and T are disjoint i S T = .

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.4 Let V be a set of sets. The sets T V are mutually disjoint i T1 V T2 V (T1 = T2 T1 T2 = ).

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.5 Let V be a set containing non empty sets if any. Let U be a set. V is a partition of U i (S V T V (S T = )) ( X V X = U).

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.6 Let S and T be two sets. The (non-symmetric) dierence of S and T , noted S \ T a is the set such that: X (X S \ T (X S (X T )))
a

Some authors use S T .

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.7 Let S and T be two sets. The symmetric dierence of S and T , noted S T a is the set such that: X (X S T (X S X T ))
a

Some authors use ST .

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.8 Let S and T be two sets. Let T S. The complement of T in S, S noted T or T a , if non ambiguous, is S \ T
a

Some authors use c T or T c .

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.4.9 Let S be a non-empty set. P(S) with , and algebra. is a Boolean

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof. Let x and y be two subsets of S (x P(S), y P(S)).

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.4.10 Let S be a non-empty set. Let x and y be two subsets of S (x P(S), y P(S)). x y =x y

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof. This is a law of Boolean algebra (De Morgans law) that we proved in chapter 2.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.11 A set that contains a single element is called a singleton.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.12 A set that contains two distincta elements is called a pair.
a This restriction is not necessary according to the axiom of pairing: a singleton is a pair.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.13 (by Kuratowski) Let S be a non-empty set. Let x and y be two subsets of S (x P(S), y P(S)). The set {{x}, {x, y }} is an ordered pair, noted < x, y >a .
a

Some authors use (x, y ).

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Notice that < x, x >= {{x}, {x}} = {{x}}.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proposition 4.4.14 (Characteristic Property) Let S be a non-empty set. Let x1 and y1 be two subsets of S. Let Let x2 and y2 be two subsets of S. < x1 , y1 >=< x2 , y2 > (x1 = x2 y1 = y2 )

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Proof.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Denition 4.4.15 Let S and T be two sets. The Cartesian product (or cross product) of S and T , noted S T is the set such that: X Y (< X , Y > S T (X S Y T )) Notice that Cartesian product is neither commutative nor associative.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Cartesian Product This is a tabular representation of the Cartesian product of S = {1, 2, 3} and T = {a, b}. S T = {< 1, a >, < 1, b >, < 2, a >, < 2, b >, < 3, a >, < 3, b >} 1 1 2 2 3 3 a b a b a b

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Generalized T-uple There are many ways to generalize ordered pairs. Informally, we say that a generalized t-uple is written as follows. < X1 , X2 , ..., Xn > A t-uple with three elements is a triple, with four elements is a quadruple, with ve elements is a quintuple, etc. a
a

Check online resources for t-uple or tuple.

Although < X1 , X2 , X3 >=<< X1 , X2 >, X3 >, for convenience they are often confused for the same mathematical object. It is not always the case.

Introduction Operations on Sets

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Generalized Cartesian Product Consequently there are many ways to generalize Cartesian product. Informally, we say that a generalized Cartesian Product is written as follows. S1 S2 ... Sn Although S1 S2 S3 = (S1 S2 ) S3 for convenience they are often confused for the same mathematical object. It is not always the case. Let V be a set of sets. We can write: S
SV

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Venn Diagrams
Informal Denition Venn Diagrams are informal graphical representations of sets.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Membership The general case of an element e and a set T such that e T , is represented by the following Venn diagram.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Two Sets The general case of two sets S and T is represented by the following Venn diagram.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Disjoint Sets The general case of two disjoint sets S and T is represented by the following Venn diagram.
S

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Inclusion The general case of two sets S and T such that T S, is represented by the following Venn diagram.

S T

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Union The union S T is represented by the blue hachured pattern.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Union The intersection S T is represented by the blue hachured pattern.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Union The dierence S \ T is represented by the blue hachured pattern.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Union The symmetric dierence S T is represented by the blue hachured pattern.

Introduction Venn Diagrams

Set Theory

ZFC

Operations on Sets

Venn Diagrams

Union The fact that the set of sets S1 , S2 , S3 , S4 , S5 , S6 is a partition of S is represented by the following Venn diagram.

S S1 S5 S4 S2 S6 S3