Sets: Summary
Sets: Introduction
German mathematician Georg Cantor (1845-1918) has introduced sets. His work from 1874 to 1884 is the origin of set theory. Cantor's definition: "A set is a gathering together into a whole of definite distinct objects of our perception or thought, called the set elements".
Sets are ubiquitous in mathematics, with many math objects resabling a set of some kind.
Sets are introduced in theories without a proof: as a primitive or axiom.
Zermelo-Fraenkel (ZF) set theory is considered the foundation of modern math.
Initially, naïve set theory was developed that treated sets as collections of objects without imposing any restriction as to what can consitute a set. This has led to some paradoxes, with Russell's paradox being the most famous.
Naïve set theory is an informal approach to set theory.
Axiomatic set theory, such as ZF, is a formal system based on a set of axioms.
Sets: Elements
objects that belong to a set are called set elements or set members
Sets: inclusion
subset is an example of inclusion relation
inclusion relation is reflexive, transitive, and anti-symmetric
proper inclusion relation is irreflexive, transitive, and asymmetric.
inclusion and proper inclusion relations have natural converses;
A (properly) includes B iff B is (properly) included in A;
alternatively, A is a (proper) superset of B
exclusion relation is symmetric and anti-reflexive
inclusion relation is antisymmetric
set membership (belonging) is an example of membership relation
membership (elementhood) relation is reflexive
inclusion relation is transitive, membership relation is not
Sets: Cardinality
standard set notation: curly braces for listing the elements explicitly
comprehensions:
{x ∈ S |...}
∅
for the empty setS \ T
for the set difference ofS
andT
cardinality of a set
S
is|S|
powerset of
S
i.e. the set of all the subsets ofS
, isP(S)
the set
{0,1,2,3,4,5,...}
of natural numbers is denoted by the symbolN
a set is countable if its elements can be placed in one-to-one correspondence with the natural numbers
Relations
An n-place relation on a collection of sets
S1,S2,...,Sn
is a set
R ⊆ S1 × S2 ×...× Sn
of tuples of elementsS1 - Sn
the elements
s1 ∈ S1
throughsn ∈ Sn
are related byR
if(s1,...,sn)
is an element ofR
A one-place relation on a set
S
is called a predicate onS
P is true of an element
s ∈ S
ifs ∈ P
we write
P(s)
instead ofs ∈ P
, regardingP
as a function mapping elements ofS
to truth valuesA two-place relation
R
on setsS
andT
is a binary relationWe write
sRt
instead of(s, t) ∈ R
if
S
andT
are the same setU
, thenR
is a binary relation onU
3-place or more place relations are often written using a mixfix concrete syntax, where the elements in the relation are separated by a sequence of symbols that jointly constitute the name of the relation. For example, for the typing relation for the simply typed lambda calculus, we write
Γ ⊢ s : T
to mean the triple(Γ,s,T)
is in the typing relation.The domain of a relation R on sets S and T, written
dom(R)
, is the set of elementss ∈ S
such that(s, t) ∈ R
for somet
.The codomain or range of
R
, writtenrange(R)
, is the set of elementst ∈ T
such that(s, t) ∈ R
for some s
Functions
A relation R on sets S and T is called a partial function from S to T if, whenever
(s, t1) ∈ R
and(s, t2) ∈ R
, we havet1 = t2
.If, in addition,
dom(R) = S
, then R is called a total function (or just function) from S to T.A partial function R from S to T is said to be defined on an argument
s ∈ S
ifs ∈ dom(R)
, and undefined otherwise.We write
f (x) ↑
, orf (x) =↑
, to mean f is undefined on x, andf (x)↓
to mean f is defined on xwe also need to define functions that may fail on some inputs, so it is important to distinguish failure (which is a legitimate, observable result) from divergence
a function that may fail can be either partial, i.e. it may also diverge, or total (it must always return a result or explicitly fail)
We write
f(x)=fail
when f returns a failure result on the input x.Formally, a function from S to T that may also fail is actually a function
from S to
T ∪ {fail}
, where we assume thatfail
does not belong to T.Suppose R is a binary relation on a set S and P is a predicate on S. P is preserved by R if whenever we have
sRs'
andP(s)
, we also haveP(s0)
.
Ordered Sets
a binary relation R on a set S is reflexive if R relates every element of S to itself i.e.
sRs
or(s,s) ∈ R
for alls ∈ S
.R is symmetric if
sRt
impliestRs
, for all s and t in S.R is transitive if
sRt
ANDtRu
implysRu
.R is antisymmetric if
sRt
andtRs
imply thats = t
A reflexive and transitive relation R on a set S is called a preorder on S.
We denote a preorder by
s < t
"s is strictly less than t" to means ≤ t ∧ s ≠ t
.A preorder (on a set S) that is also antisymmetric is called a partial order
on S.
A partial order ≤ is called a total order if it also has the property that,
for each s and t in S, either
s ≤ t
ort ≤ s
.Suppose that ≤ is a partial order on a set S and s and t are elements of S. An element
j ∈ S
is said to be a join (or least upper bound) of s and t ifs ≤ j
andt ≤ j
, AND for any elementk ∈ S
withs ≤ k
andt ≤ k
, we havej ≤ k
.an element
m ∈ S
is a meet (or greatest lower bound) of s and t ifm ≤ s
andm ≤ t
, AND for any elementn ∈ S
withn ≤ s
andn ≤ t
, we haven ≤ m
a reflexive, transitive, and symmetric relation on a set S is called
an equivalence on S.
let R is a binary relation on a set S. The reflexive closure of R is the smallest reflexive relation R' that contains R. "Smallest" in the sense that if R'' is some other reflexive relation that contains all the pairs in R, then we have
R' ⊆ R''
the transitive closure of R is the smallest transitive relation R' that contains R
The transitive closure of R is often written R+
The reflexive and transitive closure of R is the smallest reflexive and transitive relation that contains R, often written R∗.
Let preorder ≤ on a set S. A decreasing chain in ≤ is a sequence s1,s2,s3,... of elements of S such that each member of the sequence is strictly less than its predecessor:
si+1 < si
for every i.Chains can be either finite or infinite
Suppose we have a set S with a preorder ≤. We say that ≤ is well
founded if it contains no infinite decreasing chains. For example, the usual order on the natural numbers, with
0 < 1 < ...
, is well founded, but the same order on the integers,...< −1 < 0 < 1 <...
is not. We sometimes omit mentioning ≤ explicitly and simply speak of S as a well-founded set.
Last updated