Asynchronous Circuit Design

Appendix B

Sets and Relations

Your theory is crazy, but it's not crazy enough to be true.

—Niels Bohr, to a young physicist

First things first, but not necessarily in that order.

—Doctor Who

What we imagine is order is merely the prevailing form of chaos.

—Kerry Thornley, Principia Discordia, 5th edition

The art of progress is to preserve order amid change.

—A. N. Whitehead

Confusion is a word we have invented for an order which is not understood.

—Henry Miller (1891 – 1980)

Not till we are lost, in other words, not till we have lost the world, do we begin to find ourselves, and realize the infinite extent of our relations.

—Henry David Thoreau (1817 – 1862)

Throughout the book we have assumed a basic knowledge of set theory. This appendix provides a brief review of some of the basic concepts of set theory used in this book.

B.1 BASIC SET THEORY

A set S is any collection of objects that can be distinguished. Each object x which is in S is called a member of S (denoted x ∈ S). When an object x is not a member of S, it is denoted by x ∉ S. A set is determined by its members. Therefore, two sets X and Y are equal when they consist of the same members (denoted X = Y). This means that if X = Y and a ∈ X, then a ∈ Y. This is known as the principle of extension. If two sets are not equal, it is denoted X ≠ Y. There are three basic properties of equality:

1. X = X (reflexive)
2. X = Y implies Y = X (symmetric)
3. X = Y and Y = Z then X = Z (transitive)

Example B.1.1 The set {1, 2, 3, 5, 6, 10, ...