Book of Proof

Home > Other > Book of Proof > Page 44
Book of Proof Page 44

by Richard Hammack


  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

 

 

 


‹ Prev