Ordered Sets | PDF Textbook

This PDF textbook provides a systematic introduction to ordered sets, covering partial orders, total orders, Hasse diagrams, greatest and maximal elements, upper and lower bounds, suprema and infima, as well as well-ordered sets, the well-ordering principle, the minimal counterexample method, transfinite induction, and Zorn's lemma. The material is developed through numerous concrete examples, proofs, and exercises. Available for Premium and Supporter members.

Basic Information

  • Pages: 267
  • Format: PDF
  • Version: October 7, 2026
  • Membership: Premium and Supporter members

This PDF textbook is based on the Web materials published on WIIS and has been reorganized so that propositional logic can be studied systematically as a single textbook.

It provides a systematic introduction to propositions, logical connectives, truth tables, tautologies, logical equivalences, inference, and proof, with the aim of helping readers acquire the foundations of logic studied at the university level.

Rather than emphasizing elegance, the textbook places priority on clarity and carefully explains why each idea works the way it does. It is suitable both for readers studying propositional logic for the first time and for those who wish to review the foundations of university mathematics, information science, or economics.

This textbook systematically covers the following topics:

  • Propositions and logical formulas
  • Logical connectives (negation, conjunction, disjunction, implication, equivalence, etc.)
  • Truth tables
  • Tautologies and contradictions
  • Necessary conditions, sufficient conditions, and necessary and sufficient conditions
  • Logical equivalences and equivalent transformations
  • Rules of inference
  • Methods of proof, including conditional proof, proof by contradiction, and proof by contraposition
  • Review tests

Definitions, theorems, proofs, examples, and exercises are arranged in a balanced way so that readers can build their understanding step by step.

This textbook is not a one-time publication.

At WIIS, the PDF textbook is continuously updated in conjunction with improvements to the Web materials. Updates include not only corrections of typographical errors but also improvements to explanations and the addition of new examples and exercises.

Premium and Supporter members may download the latest version as many times as they wish during their membership period.

This PDF textbook is based on the web materials published on WIIS and has been reorganized so that the fundamental theory of ordered sets can be studied systematically in a single volume.

The book begins with the definition of partial orders and systematically develops strict partial orders, total orders, strict total orders, and the relationships among them. It then introduces key concepts for understanding ordered sets, including Hasse diagrams for visualizing finite ordered sets, adjacency matrices for representing order relations, ordered subsets, greatest and least elements, maximal and minimal elements, upper and lower bounds, and suprema and infima. In the latter half of the book, the discussion extends to well-ordered sets, the well-ordering principle, the principle of transfinite induction, and Zorn’s lemma.

An order is a mathematical structure used to describe relationships such as precedence, magnitude, inclusion, and divisibility among the elements of a set. In some cases, as with the usual order on the real numbers, any two elements can be compared. In other cases, such as set inclusion or divisibility among natural numbers, some pairs of elements may be incomparable. The theory of ordered sets provides a unified framework for analyzing these different order structures through properties such as reflexivity, antisymmetry, and transitivity.

The book first examines the definitions of partial orders and strict partial orders in detail. A partial order is defined by reflexivity, antisymmetry, and transitivity, whereas a strict partial order is characterized by asymmetry and transitivity. These are not unrelated concepts: each can be derived from the other under the appropriate correspondence. For this reason, the relationship between partial and strict partial orders is also treated carefully.

The discussion then turns to total orders, which satisfy completeness. In a totally ordered set, any two elements are comparable, whereas this need not be true in a general partially ordered set. After clarifying this distinction, the book examines the relationship between total orders and strict total orders, restrictions of orders, ordered subsets, and totally ordered subsets.

Hasse diagrams and adjacency matrices are also introduced as concrete methods for representing ordered sets. Hasse diagrams visualize the structure of finite ordered sets through cover relations. Adjacency matrices, on the other hand, represent order relations by matrices whose entries are 0 or 1, making it possible to analyze properties such as reflexivity, antisymmetry, and transitivity from a matrix representation.

The book also examines in detail greatest and least elements, maximal and minimal elements, all of which are defined for ordered subsets. Although these terms are similar, a greatest element and a maximal element are different concepts, as are a least element and a minimal element. Greatest and least elements are defined through comparison with every element of the set, while maximal and minimal elements are defined by the absence of strictly larger or smaller elements. Numerous examples and proofs are used to clarify these distinctions.

Upper and lower bounds, as well as suprema and infima, are treated systematically. Even when a subset has no greatest or least element, it may still have upper or lower bounds within a larger ordered set. The least upper bound is the supremum, and the greatest lower bound is the infimum. Because these concepts appear frequently in analysis, optimization, economics, and other fields, it is important to understand their definitions and basic properties precisely within the framework of ordered sets.

The latter half of the book focuses on well-ordered sets. A well-ordered set is a totally ordered set in which every nonempty subset has a least element. The natural numbers provide the standard example, and the well-ordering principle for the natural numbers plays an important role in many mathematical proofs. In addition to the principle itself, the book covers its use in the minimal counterexample method, its relationship with mathematical induction and strong induction, and applications in number theory.

The book then introduces the principle of transfinite induction for general well-ordered sets. In ordinary mathematical induction on the natural numbers, one proves statements by passing from one natural number to the next. In a general well-ordered set, however, there may be elements with no immediate predecessor. Transfinite induction addresses such cases by assuming that a proposition holds for all elements smaller than a given element and then proving it for that element itself. The logical structure of this method is explained carefully, with particular attention to how it differs from induction on the natural numbers.

Finally, the book covers Zorn’s lemma, an important theorem that guarantees the existence of maximal elements in partially ordered sets. Zorn’s lemma states that if every totally ordered subset of a partially ordered set has an upper bound, then the partially ordered set has a maximal element. Although abstract, it is a powerful tool for proving the existence of maximal structures and is widely used in set theory, linear algebra, algebra, analysis, and many other areas of mathematics. The book discusses not only the statement of Zorn’s lemma, but also the ideas behind its proof and concrete applications.

This textbook systematically covers the following topics:

  • Partial orders and the axioms of order
  • Strict partial orders
  • The relationship between partial and strict partial orders
  • Total orders
  • Strict total orders
  • The relationship between total and strict total orders
  • Hasse diagrams and cover relations
  • Representation of order relations by adjacency matrices
  • Ordered subsets
  • Totally ordered subsets
  • Greatest and least elements
  • Maximal and minimal elements
  • The distinction between greatest and maximal elements
  • Upper and lower bounds
  • Suprema and infima
  • Well-ordered sets
  • Initial segments and well-order structures
  • The well-ordering principle for the natural numbers
  • The minimal counterexample method
  • The relationship among mathematical induction, strong induction, and the well-ordering principle
  • The principle of transfinite induction
  • Successor stages and limit stages
  • Zorn’s lemma
  • Existence proofs for maximal elements
  • The axiom of choice and Zorn’s lemma
  • Review tests

Definitions, propositions, proofs, concrete examples, and exercises are arranged in a balanced way so that readers can build their understanding step by step. For order relations, familiar examples such as the usual order on the real numbers, set inclusion, and divisibility among natural numbers are used to examine which axioms of order are satisfied in each case. The book also illustrates how different order structures can arise on the same underlying set depending on which binary relation is defined.

The distinction between partial and total orders is organized around the question of whether every pair of elements is comparable. In a general partially ordered set, there may be multiple maximal or minimal elements, whereas a greatest or least element, when it exists, is unique. Through these distinctions, the everyday notions of “largest” and “smallest” are refined into more precise mathematical concepts.

Upper and lower bounds, as well as suprema and infima, are discussed not only in relation to the subset under consideration but also in relation to the larger ordered set that contains it. The book distinguishes cases in which a greatest element coincides with a supremum, or a least element with an infimum, from cases in which they do not, and clarifies how the relevant definitions are related.

For well-ordered sets, the emphasis is not merely on the definition, but on how the property that every nonempty subset has a least element leads to powerful proof techniques. The minimal counterexample method is derived from the well-ordering principle and compared with mathematical induction and strong induction, showing how these different proof methods exploit the same underlying structure in different forms.

In well-ordered sets more general than the natural numbers, an element need not have an immediate predecessor. To handle such situations, the book introduces transfinite induction and explains both its similarities to and differences from induction on the natural numbers. In particular, concrete examples are used to illustrate limit stages that cannot be reached by successor steps alone.

The treatment of Zorn’s lemma emphasizes a practical way of thinking about applications: which collection should be regarded as the partially ordered set, what should count as a totally ordered subset, how an upper bound should be constructed, and what the resulting maximal element means in the original problem. This approach is intended to help readers acquire the basic skills needed to apply Zorn’s lemma in existence proofs.

Three review tests are included at the end of the book. They cover topics ranging from basic concepts such as partial orders, total orders, adjacency matrices, greatest and maximal elements, upper and lower bounds, and suprema and infima, to proofs using the well-ordering principle, the minimal counterexample method, the structure of well-ordered sets, and existence proofs for maximal structures using Zorn’s lemma.

This textbook is suitable not only as an introduction for readers studying ordered sets seriously for the first time, but also as preparation for further study in set theory, analysis, topology, linear algebra, abstract algebra, optimization theory, and related subjects. It can also be used to develop the ability to read and write abstract definitions, propositions, and proofs in university-level mathematics.

Study Guide

Related Books

Propositional Logic | PDF Textbook

This is a PDF textbook on propositional logic. It systematically covers propositions, logical formulas, truth tables, tautologies, logical equivalences, inference, and proof. Through numerous examples and exercises, you can learn the foundations of logic used in university mathematics, information science, and computer science. This material is available to Premium and Supporter members.

Table of Contents

ログイン

アカウントにログインして、学習ノートやブックマーク、投稿記事などを管理できます。