A set is a (possibly infinite) collection of distinct objects.
- The empty set: ∅={}∅={} (plays a role akin to zero)
- Binary numbers: {0,1}{0,1}
- Natural numbers: N={1,2,3,...}N={1,2,3,...}
- Integers: Z={...,-2,-1,0,1,2,...}Z={...,-2,-1,0,1,2,...} (ZZ is short for “Zahlen”, German for “numbers”)
- Rational numbers: QQ (QQ for “quotient”)
- Real numbers: RR
- Complex numbers: CC
In this course we will assume familiarity with a number of common set operations. In particular, for the sets A={0,1}A={0,1}, B={1}B={1}, C={2}C={2}, we have the operations of:
- Union: A∪B={0,1}A∪B={0,1}, B∪C={1,2}B∪C={1,2}
- Intersection: A∩B={1}A∩B={1}, B∩C=∅B∩C=∅
- Exclusion:
A
∖
B
=
{
0
}
A
∖
B
=
{
0
}
- Complement: Ac=U∖AAc=U∖A, Ac={2}Ac={2}
- Cartesian Product:
A
2
=
A
×
A
=
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
,
(
1
,
1
)
}
A
2
=
A
×
A
=
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
,
(
1
,
1
)
}
In order to be useful a set must typically satisfy some additional structure. We begin by defining a notion of distance.
A metric space is a set MM together with a metric (distance function)
d:M×M→Rd:M×M→R such that for all x,y,z∈Mx,y,z∈M
- M1. d(x,y)=d(y,x)d(x,y)=d(y,x) (symmetry)
- M2. d(x,y)≥0d(x,y)≥0 (non-negative)
- M3. d(x,y)=0d(x,y)=0 iff x=yx=y (positive semi-definite)
- M4. d(x,z)≤d(x,y)+d(y,z)d(x,z)≤d(x,y)+d(y,z) (triangle inequality).
- Trivial metric: (MM is arbitrary)
d(x,y)=0 if x=y,1 if x≠y.d(x,y)=0 if x=y,1 if x≠y.
- Standard metric: (M=RM=R)
d(x,y)=|x-y|d(x,y)=|x-y|
- Euclidean (ℓ2)(ℓ2) metric: (M=RNM=RN)
d(x,y)=∑i=1N|xi-yi|2d(x,y)=∑i=1N|xi-yi|2
- ℓ1ℓ1 metric: (M=RNM=RN)
d(x,y)=∑i=1N|xi-yi|d(x,y)=∑i=1N|xi-yi|
- ℓpℓp metric, 1≤p<∞1≤p<∞: (M=RNM=RN)
d(x,y)=∑i=1N|xi-yi|p1/pd(x,y)=∑i=1N|xi-yi|p1/p
- ℓ∞ℓ∞ metric: (M=RNM=RN)
d(x,y)=maxi=1,...,N|xi-yi|d(x,y)=maxi=1,...,N|xi-yi|
- LpLp metric: (MM = real (or complex) valued functions defined on [a,b][a,b])
dp(x,y)=∫ab|x(t)-y(t)|pdt1/pdp(x,y)=∫ab|x(t)-y(t)|pdt1/p
