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.)