Book of Proof
Page 44
we can find injections f : B → R2 and g : R2 → B. The function f : B → R2 defined
as f (x, y) = (x, y) is clearly injective. For g : R2 → B, consider the function
µ
x2 + y2
x2 + y2
¶
g(x, y) =
x,
y .
x2 + y2 + 1
x2 + y2 + 1
Verify that this is an injective function g : R2 → B.
300
Solutions
7. Prove or disprove: If there is a injection f : A → B and a surjection g : A → B,
then there is a bijection h : A → B.
This is true. Here is an outline of a proof. Define a function g0 : B → A as
follows. For each b ∈ B, choose an element xb ∈ g−1({x}). (That is, choose an
element xb ∈ A for which g(xb) = b.) Now let g0 : B → A be the function defined
as g0(b) = xb. Check that g0 is injective and apply the the Cantor-Bernstein-
Schröeder theorem.
Index
C(n, k), 74
difference of sets, 17
disproof, 146
absolute value, 6
divides, 90
addition principle, 82
division algorithm, 29, 91
and, 38
divisor, 90
axiom of foundation, 31
domain of a function, 198
Doxiadis, Apostolos, 32
basis step, 156
biconditional statement, 44
element of a set, 3
bijection, 218
empty set, 4
bijective function, 201
entries of a list, 63
byte, 64
equality of functions, 200
equality of lists, 64
Cantor, Georg, 219
equality of sets, 3
Cantor-Bernstein-Schröeder theorem, 234
equivalence class, 185
cardinality, 4, 217
equivalence relation, 184
Cartesian plane, 9
equivalent statements, 123
Cartesian power, 10
Euclid, 114, 140
Cartesian product, 8
Euler, Leonhard, 107, 142
closed interval, 6
existence theorem, 125
codomain of a function, 198
existential quantifier, 52
Cohen, Paul, 237
existential statement, 125
complement of a set, 19
composite number, 90
factorial, 70
composition of functions, 208
false, 34
conditional statement, 41
Fermat’s last theorem, 36
conjecture, 147
Fermat, Pierre de, 36
constructive proof, 128
Fibonacci sequence, 167
continuum hypothesis, 237
function, 197
contrapositive, 102
range of, 198
converse of a statement, 44, 102
bijective, 201, 217
corollary, 88
codomain of, 198
countable set, 223
composition of, 208
counterexample, 149
domain of, 198
counting, 63
equality, 200
injective, 201
definition, 87
inverse, 211
DeMorgan’s laws, 50, 57
notation, 199
302
Index
one-to-one, 201
entries, 63
onto, 201
equal, 64
surjective, 201
non-repetitive, 66
function notation, 199
order, 63
fundamental theorem of arithmetic, 166
repetition, 66
fundamental theorem of calculus, viii
logic, 33
contradiction, 111
gamma function, 73
equivalence, 49
gcd, 90
inference, 61
geometric sequence, 169
quantifier, 52
Goldbach’s conjecture, 36, 56
existential, 52
Goldbach, Christian, 36
universal, 52
golden ratio, 169
symbols, 46, 51
graph, 163
logical equivalence, 49
cycle, 163
logical inference, 61
edges, 163
vertices, 163
mean value theorem, 55
greatest common divisor, 90
Mersenne prime, 144
multiple, 90
Hagy, Jessica, 32
multiplication principle, 65
half-open interval, 6
natural numbers, 4
if-and-only-if theorem, 121
necessary condition, 43
image, 215
negation of a statement, 40
inclusion-exclusion formula, 81
non-constructive proof, 128
index set, 25
indexed set, 24
one-to-one function, 201
induction, 154
onto function, 201
strong, 161
open interval, 6
inductive hypothesis, 156
open sentence, 35, 54
inductive step, 156
or, 39
infinite interval, 6
ordered pair, 8
injection, 218
ordered triple, 9
injective function, 201
integers, 3, 4
Papadimitriou, Christos, 32
congruence, 105, 181
parity, 89
modulo n, 192
partition, 189
intersection of sets, 17
Pascal’s triangle, 79
interval, 6
Pascal, Blaise, 79
inverse of a function, 211
perfect number, 139, 142
inverse relation, 211
pigeonhole principle, 206
irrational number, 113
Pisano, Leonardo, 167
power set, 14
lcm, 90
power, Cartesian, 10
least common multiple, 90
preimage, 215
lemma, 88
prime number, 36, 90
length, 63
proof
list, 63
by cases, 98
empty, 64
by contradiction, 111
303
by induction, 154
sigma notation, 24
strong, 161
size, see cardinality
by smallest counterexample, 165
statement, 34
constructive, 128
biconditional, 44
contrapositive, 102
conditional, 41
direct, 87, 92
necessary, 43
existence, 124
sufficient, 43
involving sets, 131
converse, 44
non-constructive, 128
equivalent, 123
uniqueness, 124, 127
existential, 125
within-a-proof, 117
negation, 57
proposition, 88, 92
Stirling’s formula, 73
Pythagorean theorem, 36
strong induction, 161
subset, 11
quadratic formula, 36
sufficient condition, 43
quantifier, 52
surjection, 218
quotient, 29, 91
surjective function, 201
symmetric property of a relation, 179
range of a function, 198
rational numbers, 6, 113
theorem, 87
real numbers, 4
existence, 125
reflexive property of a relation, 179
if-and-only-if, 121
relations, 175
three-dimensional space, 10
between sets, 194
transitive property of a relation, 179
equivalence, 184
tree, 163
class, 185
triple, ordered, 9
inverse, 211
true, 34
reflexive, 179
truth
symmetric, 179
table, 38
transitive, 179
value, 38
remainder, 29, 91, 105
Russell’s paradox, 31
uncountable set, 223
Russell, Bertrand, 31
union of sets, 17
uniqueness proof, 127
set(s)
unit circle, 14, 19
builder-notation, 5, 131
universal quantifier, 52
cardinalities of
universal set, 19
comparison of, 228
equal, 217
variable, 35
unequal, 217
vector space, 131
cardinality of, 3, 217
Venn diagram, 21
complement, 19
countable, 223
well-ordering principle, 29
element of, 3
Wiles, Andrew, 36
empty, 4
WLOG, 99
equal, 3
partition of, 189
Zermelo-Fraenkel axioms, 31
subset of, 11
uncountable, 223