Enderton.Set.Chapter_3 #
Relations and Functions
Theorem 3G (i) #
Assume that F
is a one-to-one function. If x ∈ dom F
, then F⁻¹(F(x)) = x
.
Theorem 3G (ii) #
Assume that F
is a one-to-one function. If y ∈ ran F
, then F(F⁻¹(y)) = y
.
Theorem 3H #
Assume that F
and G
are functions. Then
dom (F ∘ G) = {x ∈ dom G | G(x) ∈ dom F}.
Theorem 3J (a) #
Assume that F : A → B
, and that A
is nonempty. There exists a function
G : B → A
(a "left inverse") such that G ∘ F
is the identity function on A
iff F
is one-to-one.
Theorem 3J (b) #
Assume that F : A → B
, and that A
is nonempty. There exists a function
H : B → A
(a "right inverse") such that F ∘ H
is the identity function on
B
only if F
maps A
onto B
.
Theorem 3K (a) #
The following hold for any sets. (F
need not be a function.)
The image of a union is the union of the images:
F⟦⋃ 𝓐⟧ = ⋃ {F⟦A⟧ | A ∈ 𝓐}
Theorem 3K (b) #
The following hold for any sets. (F
need not be a function.)
The image of an intersection is included in the intersection of the images:
F⟦⋂ 𝓐⟧ ⊆ ⋂ {F⟦A⟧ | A ∈ 𝓐}
Equality holds if F
is single-rooted.
Theorem 3K (c) #
The following hold for any sets. (F
need not be a function.)
The image of a difference includes the difference of the images:
F⟦A⟧ - F⟦B⟧ ⊆ F⟦A - B⟧.
Equality holds if F
is single-rooted.
Corollary 3L #
For any function G
and sets A
, B
, and 𝓐
:
G⁻¹⟦⋃ 𝓐⟧ = ⋃ {G⁻¹⟦A⟧ | A ∈ 𝓐},
G⁻¹⟦𝓐⟧ = ⋂ {G⁻¹⟦A⟧ | A ∈ 𝓐} for 𝓐 ≠ ∅,
G⁻¹⟦A - B⟧ = G⁻¹⟦A⟧ - G⁻¹⟦B⟧.
Theorem 3M #
If R
is a symmetric and transitive relation, then R
is an equivalence
relation on fld R
.
Theorem 3R #
Let R
be a linear ordering on A
.
(i) There is no x
for which xRx
.
(ii) For distinct x
and y
in A
, either xRy
or yRx
.
Exercise 3.1 #
Suppose that we attempted to generalize the Kuratowski definitions of ordered pairs to ordered triples by defining
⟨x, y, z⟩* = {{x}, {x, y}, {x, y, z}}.open Set
Show that this definition is unsuccessful by giving examples of objects u
,
v
, w
, x
, y
, z
with ⟨x, y, z⟩* = ⟨u, v, w⟩*
but with either y ≠ v
or z ≠ w
(or both).
Exercise 3.5a #
Assume that A
and B
are given sets, and show that there exists a set C
such that for any y
,
y ∈ C ↔ y = {x} × B for some x in A.
In other words, show that {{x} × B | x ∈ A}
is a set.
Exercise 3.6 #
Show that a set A
is a relation iff A ⊆ dom A × ran A
.
Exercise 3.7 #
Show that if R
is a relation, then fld R = ⋃ ⋃ R
.
Exercise 3.8 (i) #
Show that for any set 𝓐
:
dom ⋃ A = ⋃ { dom R | R ∈ 𝓐 }
Exercise 3.8 (ii) #
Show that for any set 𝓐
:
ran ⋃ A = ⋃ { ran R | R ∈ 𝓐 }
Exercise 3.9 (i) #
Discuss the result of replacing the union operation by the intersection operation in the preceding problem.
dom ⋃ A = ⋃ { dom R | R ∈ 𝓐 }
Exercise 3.9 (ii) #
Discuss the result of replacing the union operation by the intersection operation in the preceding problem.
ran ⋃ A = ⋃ { ran R | R ∈ 𝓐 }
Exercise 3.12 #
Assume that f
and g
are functions and show that
f ⊆ g ↔ dom f ⊆ dom g ∧ (∀ x ∈ dom f) f(x) = g(x).
Exercise 3.13 #
Assume that f
and g
are functions with f ⊆ g
and dom g ⊆ dom f
. Show
that f = g
.
Exercise 3.14 (a) #
Assume that f
and g
are functions. Show that f ∩ g
is a function.
Exercise 3.14 (b) #
Assume that f
and g
are functions. Show that f ∪ g
is a function iff
f(x) = g(x)
for every x
in (dom f) ∩ (dom g)
.
Exercise 3.15 #
Let 𝓐
be a set of functions such that for any f
and g
in 𝓐
, either
f ⊆ g
or g ⊆ f
. Show that ⋃ 𝓐
is a function.
Exercise 3.17 #
Show that the composition of two single-rooted sets is again single-rooted. Conclude that the composition of two one-to-one functions is again one-to-one.
Exercise 3.18 #
Let R
be the set
{⟨0, 1⟩, ⟨0, 2⟩, ⟨0, 3⟩, ⟨1, 2⟩, ⟨1, 3⟩, ⟨2, 3⟩}
Evaluate the following: R ∘ R
, R ↾ {1}
, R⁻¹ ↾ {1}
, R⟦{1}⟧
, and
R⁻¹⟦{1}⟧
.
Exercise 3.19 #
Let
A = {⟨∅, {∅, {∅}}⟩, ⟨{∅}, ∅⟩}.
Evaluate each of the following: A(∅)
, A⟦∅⟧
, A⟦{∅}⟧
, A⟦{∅, {∅}}⟧
,
A⁻¹
, A ∘ A
, A ↾ ∅
, A ↾ {∅, {∅}}
, ⋃ ⋃ A
.
Exercise 3.20 #
Show that F ↾ A = F ∩ (A × ran F)
.
Exercise 3.22 (a) #
Show that the following is correct for any sets.
A ⊆ B → F⟦A⟧ ⊆ F⟦B⟧
Exercise 3.22 (b) #
Show that the following is correct for any sets.
(F ∘ G)⟦A⟧ = F⟦G⟦A⟧⟧
Exercise 3.22 (c) #
Show that the following is correct for any sets.
Q ↾ (A ∪ B) = (Q ↾ A) ∪ (Q ↾ B)
Exercise 3.23 (i) #
Let I
be the identity function on the set A
. Show that for any sets B
and
C
, B ∘ I = B ↾ A
.
Exercise 3.23 (ii) #
Let I
be the identity function on the set A
. Show that for any sets B
and
C
, I⟦C⟧ = A ∩ C
.
Exercise 3.24 #
Show that for a function F
, F⁻¹⟦A⟧ = { x ∈ dom F | F(x) ∈ A }
.
Exercise 3.25 (b) #
Show that the result of part (a) holds for any function G
, not necessarily
one-to-one.
Exercise 3.25 (a) #
Assume that G
is a one-to-one function. Show that G ∘ G⁻¹
is the identity
function on ran G
.
Exercise 3.27 #
Show that dom (F ∘ G) = G⁻¹⟦dom F⟧
for any sets F
and G
. (F
and G
need
not be functions.)
Exercise 3.28 #
Assume that f
is a one-to-one function from A
into B
, and that G
is the
function with dom G = 𝒫 A
defined by the equation G(X) = f⟦X⟧
. Show that G
maps 𝒫 A
one-to-one into 𝒫 B
.
Exercise 3.29 #
Assume that f : A → B
and define a function G : B → 𝒫 A
by
G(b) = {x ∈ A | f(x) = b}
Show that if f
maps A
onto B
, then G
is one-to-one. Does the converse
hold?
Exercise 3.30 #
Assume that F : 𝒫 A → 𝒫 A
and that F
has the monotonicity property:
X ⊆ Y ⊆ A → F(X) ⊆ F(Y).
Define B = ⋂ {X ⊆ A | F(X) ⊆ X}
and C = ⋃ {X ⊆ A | X ⊆ F(X)}
.
Exercise 3.30 (a) #
Show that F(B) = B
and F(C) = C
.
Exercise 3.32 (a) #
Show that R
is symmetric iff R⁻¹ ⊆ R
.
Exercise 3.32 (b) #
Show that R
is transitive iff R ∘ R ⊆ R
.
Exercise 3.33 #
Show that R
is a symmetric and transitive relation iff R = R⁻¹ ∘ R
.
Exercise 3.34 (a) #
Assume that 𝓐
is a nonempty set, every member of which is a transitive
relation. Is the set ⋂ 𝓐
a transitive relation?
Exercise 3.34 (b) #
Assume that 𝓐
is a nonempty set, every member of which is a transitive
relation. Is ⋃ 𝓐
a transitive relation?
Exercise 3.35 #
Show that for any R
and x
, we have [x]_R = R⟦{x}⟧
.
Exercise 3.36 #
Assume that f : A → B
and that R
is an equivalence relation on B
. Define
Q
to be the set {⟨x, y⟩ ∈ A × A | ⟨f(x), f(y)⟩ ∈ R}
. Show that Q
is an
equivalence relation on A
.
Exercise 3.37 #
Assume that P
is a partition of a set A
. Define the relation Rₚ
as
follows:
xRₚy ↔ (∃ B ∈ Π)(x ∈ B ∧ y ∈ B).
Show that Rₚ
is an equivalence relation on A
. (This is a formalized version
of the discussion at the beginning of this section.)
Exercise 3.38 #
Theorem 3P shows that A / R
is a partition of A
whenever R
is an
equivalence relation on A
. Show that if we start with the equivalence relation
Rₚ
of the preceding exercise, then the partition A / Rₚ
is just P
.
Exercise 3.39 #
Assume that we start with an equivalence relation R
on A
and define P
to
be the partition A / R
. Show that Rₚ
, as defined in Exercise 37, is just
R
.
Exercise 3.41 (a) #
Let ℝ
be the set of real numbers and define the realtion Q
on ℝ × ℝ
by
⟨u, v⟩ Q ⟨x, y⟩
iff u + y = x + v
. Show that Q
is an equivalence
relation on ℝ × ℝ
.
Exercise 3.43 #
Assume that R
is a linear ordering on a set A
. Show that R⁻¹
is also a
linear ordering on A
.
Exercise 3.44 #
Assume that <
is a linear ordering on a set A
. Assume that f : A → A
and
that f
has the property that whenever x < y
, then f(x) < f(y)
. Show that
f
is one-to-one and that whenever f(x) < f(y)
, then x < y
.
Exercise 3.45 #
Assume that <_A
and <_B
are linear orderings on A
and B
, respectively.
Define the binary relation <_L
on the Cartesian product A × B
by:
⟨a₁, b₁⟩ <_L ⟨a₂, b₂⟩ iff either a₁ <_A a₂ or (a₁ = a₂ ∧ b₁ <_B b₂).
Show that <_L
is a linear ordering on A × B
. (The relation <_L
is called
lexicographic ordering, being the ordering used in making dictionaries.)