Solucionario-Set..Teiria

Introduction to Set Theory
A Solution Manual for Hrbacek and Jech (1999)

Jianfei Shen
School of Economics, The University of New South Wales

Sydney, Australia

The Lord by wisdom founded the earth, by understanding he established the heavens. — Proverbs 3:19

Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . vii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Sets 1.1 1.2 1.3 1.4 ............................................................... Introduction to Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Properties . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Elementary Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 1 1 1 3

2

Relations, Functions, and Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1Ordered Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Equivalences And Partitions . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5 Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Introduction to Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2Properties of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 The Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Arithmetic of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Operations and Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Finite, Countable, and Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Finite Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Countable Sets . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . 4.4 Linear Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Complete Linear Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 31 31 34 38 41 45 4551 54 59 64 68

3

4

v

vi 5

CONTENTS

Cardinal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.1 Cardinal Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 The Cardinality of the Continuum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Ordinal Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.1 Well-Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2 Ordinal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6

References . . . . . . . . . . . . . . . . . . . . . . ....