Lesson 14 Sets, Relations, and Functions

“The only way to learn mathematics is to do mathematics.” Paul R. Halmos

“Pure mathematics is, in its way, the poetry of logical ideas.” Albert Einstein

Introduction

We now enter the precise language that underlies all of modern physics and mathematics.

The collections of objects we study are sets, the ways objects are connected are relations, and the rules that assign one quantity to another are functions.

Everything we have done so far—points in space, physical quantities, units, scaling laws—can be described more powerfully and more generally with these three ideas.

A set is simply a collection of distinct objects. For example, the set of all points on a line, the set of all possible energies of a system, the set of all outcomes of an experiment.

A relation tells us how two objects are linked. For example, “Point A is to the left of point B,” “Particle X exerts a force on particle Y,” “Temperature is greater than temperature .”

A function is a special relation that assigns exactly one output to each input. For example, distance as a function of time, force as a function of position, energy as a function of velocity.

These concepts are not abstract decorations—they are the working tools of mathematics and theoretical physics.  The state space of a system is the set of all possible states it can be in.  Forces are binary relations between objects (“A pushes B”).

We will prove classic results (De Morgan’s laws, properties of power sets, injectivity, surjectivity, bijectivity) not because they are “math for math’s sake,” but because they give us the logical precision to say exactly what we mean when we write a physical equation.

By the end of this lesson, you will see every physical law as a function, every conservation law as an equivalence relation, and every possible configuration of the universe as an element of a set.

Basic Concepts of Sets

If we take an abstract point of view, something important in theoretical physics, we can treat a unit of measurement as if it were an abstract box within which we could put anything at all for the purpose of counting similar objects. We can call such a box a cardinal number. This comes from the Latin, “cardinalis”, which means something pivotal or fundamental. Thus a cardinal number is the foundation of all of arithmetic. In this sense a cardinal number is a fundamental object of mathematics.

In general, in mathematics, we call a collection of mathematical objects a set. There is a vast literature about sets, and we will only use what we need of it. I recommend studying set theory beyond this lesson, as it is the basic language of modern mathematics. We have, in fact, just established a set, the set of all cardinals. We could also say that a cardinal number, say c, is a member or element of some set, say S. We would write this using the ∈ symbol for, “...is an element of the set...”, c∈S. We could also say that, “a is not an element of S,” a∉S. The number of elements that a set has is said to be the cardinal number of that set. A set having no elements is called the empty set or the null set; this is denoted Ø. A set having only one element is called a singleton set, you can represent it as the list of the single element, for example if the element is a we write {a}.

There are two ways to specify a set. The first way is to list all of its elements. For example, the set A is made up of the cardinal numbers 1, 2, and 3, we would write A={1,2,3}.

The second way of specifying a set is to write out the properties that are required for something to be considered a member of the set. We can symbolize such a property of an element of A by writing, p(a).  Then we can construct the set by saying that A consists of all elements a such that p(a) is true. We can symbolize this using what is called set-builder notation.

(14.1)

Where the symbol of the vertical line represents the phrase, “...such that...”. We can have more than one property that defines the elements of a set. Say that we have both the property p(a) and the property q(a), then we can write the set

(14.2)

You can have as many properties as necessary. For example, we could say that we are considering all of the letters in the word "that":

(14.3)

here we are saying that there is some element that we label l that is an element of the word “that”. This does not mean that we are saying the letter l is part of the word “that”, it is only a label. This label can take on any of the elements of the set.

As another example, say that we have a set consisting of all counting numbers less than 5:

(14.4)

You will see that a lot mathematics involves developing new ways of writing things so they do not take up lots of space and time.

If you have two sets, A and B, and the set A is composed entirely of elements of the set B, then we say that set A is a subset of set B, we write this, A ⊆ B. Formally we write,

(14.5)

We can also say that B is the superset of A, and we can write B⊇A. If we can write A ⊆ B and B ⊆ A, then we say that the set A is equal to the set B, A=B. This means they have the same elements. If we impose the condition that a subset not be equal to the larger set, A≠B, then we say that the set A is a proper subset of the set B, A ⊂ B.

(14.6)

We can draw a picture where sets are represented by closed figures, and subsets are represented by intersecting closed figures. Such a representation is called a Venn Diagram.

Note that we are including intersection ∩ in this diagram, and we will not explain this until the next section.

There is a concept that we will discard in time. If we have a superset of all sets that we will consider, we can call that the Universe of Discourse, or just the universal set, we denote this as U.

Undefined Terms

Term 14.1 Set – A well-defined collection of distinct objects.

Term 14.2 Element / Member – An object that belongs to a set (∈).

Formal Definitions

Definition 14.1 Empty set / Null set – The unique set with no elements (Ø).

Definition 14.2 Singleton set – A set with exactly one element ({a}).

Definition 14.3 Set equality – Two sets are equal iff they have exactly the same elements. This is actually a statement of the Axiom of Extensionality.

Definition 14.4 Subset – A ⊆ B iff every element of A is in B (⊆). We can say that A is an inclusion of B.

Definition 14.5 Superset – A ⊇ B iff B contains every element of A (⊇).

Definition 14.6 Proper subset – A ⊂ B iff A ⊆ B and A ≠ B.

Definition 14.7 Venn diagram – Pictorial representation of sets and their relationships.  

Definition 14.8 Universe of Discourse/Universal set – The superset of all sets you can consider.  

Axioms

Axiom 14.1: The Axiom of Extensionality. Two sets are equal iff they have exactly the same elements. Formally, we write,

(14.7)

Principles

Principle 14.1: Any collection of distinct mathematical objects (numbers, points, physical quantities, cardinal numbers, etc.) can be regarded as a single unified entity called a set. Sets are the basic building blocks of modern mathematics and provide the language for all rigorous theoretical physics.

Principle 14.2: For any object x and any set S, exactly one of the following is true: x is a member (element) of S (written x ∈ S), or x is not a member of S (written x ∉ S). There is no third possibility—membership is definite and unambiguous.

Principle 14.3: The cardinal number of a set is the fundamental measure of its “size” by which we mean the number of distinct elements it contains. The empty set Ø has cardinal number 0 (the smallest cardinal), singleton sets have cardinal number 1, and so on. Cardinal numbers are themselves elements of sets and form the foundation of arithmetic.

Principle 14.4: A set can be defined in exactly two equivalent ways:

By explicit listing of its elements (called roster notation): A = {1, 2, 3}

By stating the defining property or properties that all elements must satisfy (called set-builder notation): A = {x | P(x)} or A = {x | P(x) ∧ Q(x)}.

These two descriptions always describe the same collection.

Principle 14.5 (Order and Repetition Do Not Matter) In a set, the order in which elements are listed is irrelevant, and no element is repeated. Thus {1, 2, 3}, {3, 1, 2}, and {1, 2, 2, 3} all represent exactly the same set.

Principle 14.6 (The Empty Set is Unique and Universal) There is exactly one empty set Ø — the set that contains no elements at all. It is a valid set in every context and serves as the starting point for constructing all other finite sets.

Principle 14.7 (Subset Relation is Hierarchical and Reflexive) If every element of set A is also an element of set B, then A is a subset of B (A ⊆ B). This includes the case A = B (every set is a subset of itself). If A ⊆ B and A ≠ B, then A is a proper subset of B (A ⊂ B). The subset relation organizes sets into a partial order.

Principle 14.8 (Equality of Sets is Determined by Elements Alone) Two sets A and B are equal (A = B) if and only if they have exactly the same elements — that is, A ⊆ B and B ⊆ A. No other property (order, labeling, or how the sets were constructed) matters.

Principle 14.9 (The Universe of Discourse is Context-Dependent) When working with sets in a particular problem, we often implicitly or explicitly restrict attention to a universal set U (the “universe of discourse”) that contains all elements we are willing to consider. All sets under discussion are understood to be subsets of this U. The choice of U is conventional and problem-specific.

Theorems

Theorem 14.1 The Empty Set is Unique

Proof of Theorem 14.1: Suppose there exist two empty sets, call them and . By definition, both have no elements. There is no x such that .There is also no x such that . Now apply the Axiom of Extensionality so that for every x,

(14.8)

in other words, both sides are false for any x. Therefore, by Extensionality, . Thus, any two empty sets must be equal, therefore the empty set is unique. QED.

Theorem 14.2 The Empty Set is a Subset of All Sets

Proof of Theorem 14.2: Recall the definition of subset: A set A is a subset of B (written A ⊆ B) iff

(14.9)

Now let A = Ø. We must show,

(14.10)

The implication P ⇒ Q is true whenever P is false, recall this from the truth table of the implication. Here, the premise x ∈ Ø is always false (by the definition of the empty set). Therefore, the implication x ∈ Ø ⇒ x ∈ B is true for every x, regardless of B.Thus,

(14.11)

for any set B. QED.

Theorem 14.3 The Reflexivity of Subsets, A⊆A.

Proof of Theorem 14.3: Recall the definition of subset,

(14.12)

Now apply this to B = A. We need to show,

(14.13)

Let x be an arbitrary object. Consider the implication x ∈ A ⇒ x ∈ A. This statement is a tautology — it is always true, because the premise and conclusion are identical. If x ∈ A is true, then the conclusion x ∈ A is true.  If x ∈ A is false, the implication is vacuously true (false premise). In either case, the implication holds. Since the implication is true for every x, the universal statement is true. Therefore A ⊆ A. QED

Theorem 14.4 The Transitivity of Subsets, If A⊆B∧B⊆C, then A⊆C.

Proof of Theorem 14.4: We use the definition of subset three times. By definition A⊆B  means

(14.14)

and B⊆C means

(14.15)

We need to show that A⊆C,

(14.16)

Let x be an arbitrary object such that x ∈ A. From (14.14) we can say that x∈A⇒x∈B, so x∈B. From (14.15) we can say that x∈B⇒x∈C, so x ∈ C. Therefore x∈A→x∈C. Since this holds for every x, we have A⊆C. QED

Theorem 14.5 Antisymmetry of Subsets, If A⊆B and B⊆A, then A=B.

Sketch of the Proof of Theorem 14.5: By assumption:  A⊆B ⇒ ∀x (x ∈ A ⇒ x ∈ B) and B⊆A ⇒  ∀x (x ∈ B ⇒ x ∈ A). Now take any x. If x ∈ A, ⇒ x ∈ B. If x ∈ B ⇒ x ∈ A. So x ∈ A ⇔ x ∈ B for every x. By the Axiom of Extensionality, A = B. QED

Exercise 14.1: Begin with Term 14.1 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, axiom, principle, theorem, and proof.

Exercise 14.2:
a) Give the details for the proof of the antisymmetry of sub sets.
b) Empty Set and Singleton Set:
    1) Write the empty set in two different notations.
    2) Write three different singleton sets that contain the number 5, a letter, and a point P.
    3) Is {Ø} the same as Ø? Explain.
c) Subset vs Element: Let A = {1, 2, 3}. For each of the following, say whether it is an element of A or a subset of A (or both/neither):
    2  
    {2}  
    Ø  
    {1, 3}  
    A itself.
d) Proper Subsets and Venn Diagrams: Let U = {1, 2, 3, 4, 5, 6, 7, 8} (the universal set). Let A = {1, 2, 3, 4}, B = {1, 3, 5}, C = {1, 3}.
    1) List all proper subsets of C.
    2) Draw a Venn diagram showing U, A, B, and C.
    3) Which sets satisfy A ⊆ U, C ⊆ A, and C ⊂ B?

The Element-Chasing Method of Proof

This is the most common and most reliable way to prove almost anything about sets. To prove: Set A equals set B (or A ⊆ B, or any set equality/inclusion) you always do two things in this exact order:

Show A ⊆ B. Take an arbitrary element a that belongs to A.

Using the definitions and given facts, show that a must belong to B.

Show B ⊆ A. Take an arbitrary element b that belongs to B.

Using the definitions and given facts, show that b must belong to A.

When both directions are done, A = B (by extensionality).

If you only need A ⊆ B, you stop after step 2

For example, given   and B={x∣∣x∣≤1} be subsets of the real numbers. We will use element-chasing to prove that B⊆A.

Proof: Take an arbitrary element b∈B. By our definition of B, b∈B ⇒ {b}<=1.We can rewrite this -1<=b<=1. If we square these, we get, or . This also tells us that . By definition, this implies that b∈A. Since b is arbitrary, this implies that every element of B is also an element of A. Hence B⊆A. QED

Exercise 14.3:
a) Let and B={x∈R∣∣x∣≤2}. Prove by element chasing that B⊆A.
b) Let C={x∈Z∣x is divisible by 6}  and D={x∈Z∣x is divisible by 2}. Prove by element chasing that C⊆D.
c) Let E={x∈R∣−3≤x≤5} and . Prove by element chasing that E⊆F.

Set Operations

With the basic notion of sets now established, we introduce the ways to combine and compare them. These are the building blocks we will later use to describe the mathematical structures that make up all of theoretical physics.

If there is a set A, a rule, denoted *, that assigns to every pair of element a and b another element a*b is called a binary operation on A.

When we want to put together everything that belongs to either of two sets, we form their union. If we have sets A and B, their union is denoted with the symbol ∪, so we write A∪B. Formally we write,

(14.17)

We can visualize this with a Venn Diagram. Here we use the command to call a function from the online Function Repository, in this case we use VennDiagram.

When we want only what belongs to both sets at the same time, we form the intersection. We denote an intersection with the symbol ∩, so we write A∩B. Formally we write,

(14.18)

We can visualize it in a Venn diagram. Here we use the

Two sets whose intersection is the empty set are called disjoint.

The part of one set that is left after we remove everything that also belongs to another set is the difference. We  denote the difference using the symbol -, so the difference of A from B is B - A. Formally, we write,

(14.19)

The elements that belong to exactly one of two sets (but not both) form the symmetric difference. We denote this with thew Δ symbol, se we write the difference of A from  B, B Δ A, Formally we write

(14.20)

The Venn diagram looks like this.

When we have a fixed “everything” we are considering (thus we have established the universal set) and we want everything that is not in a given set, we take the complement. We denote this by an upper index c, for example, the complement of A is . Formally we write,

(14.21)

Changing the order of two sets does not change the result of union or intersection — we say they are commutative.

(14.22)

(14.23)

Grouping three sets in different ways does not matter for union or intersection—we say they are associative.

(14.24)

(14.25)

Union distributes over intersection and intersection distributes over union — this is distributivity.

(14.26)

(14.27)

Including the empty set changes nothing in union, and taking everything with the universal set changes nothing in intersection — these are the identity laws.

A set together with its complement gives everything, and a collection together with its complement gives nothing — these are the complement laws.

Doing the same operation twice on a set gives the same set—these are the idempotent laws.

The complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements—these are De Morgan’s laws.

When order matters in pairing elements from two sets, the corresponding elements form a set of ordered pairs.

The collection of all possible ordered pairs from two sets is the set called the Cartesian product. We write,

(14.28)

For example, a Venn diagram might show this situation,

where this would be written symbolically,

(14.29)

The Cartesian product of n sets is the set called the n-fold Cartesian product, its elements are called ordered n-tuples.

Definitions

Definition 14.9 Union: The collection of all elements that belong to at least one of two sets (A ∪ B).

Definition 14.10 Intersection: The collection of all elements that belong to both collections (A ∩ B).

Definition 14.11 Disjoint sets: Two collections with no elements in common (A ∩ B = Ø).  

Definition 14.12 Set difference: Elements that belong to one collection but not another (A - B).

Definition 14.13 Symmetric difference: Elements that belong to exactly one of two collections (A △ B).

Definition 14.14 Complement: Everything (in the universal set) that is not in a given collection ).

Definition 14.15 Ordered pair: A pair where order matters ((a,b) ≠ (b,a)).

Definition 14.16 Cartesian product: All possible ordered pairs from two collections (A × B).

Definition 14.17 N-tuple: An ordered set containing n elements.

Definition 14.18 n-fold Cartesian product: All ordered n-tuples from n collections (A×B×...).

Theorems

Theorem 14.6 Commutativity of Union: A ∪ B=B∪A.

Proof of Theorem 14.6: We prove equality by showing both inclusions. First we need to show that A ∪ B ⊆ B ∪ A. Let a be an arbitrary element such that a ∈ A ∪ B. By the definition of a union, this means a ∈ A or a ∈ B. But this condition is the same as a ∈ B or a ∈ A. Therefore a ∈ B ∪ A. Since a was arbitrary, every element of A ∪ B is in B ∪ A. Thus A ∪ B ⊆ B ∪ A.

We now show that B ∪ A ⊆ A ∪ B. Let b be an arbitrary element such that b ∈ B ∪ A.  Again, by the definition of union, b ∈ B or b ∈ A, which is the same as b ∈ A or b ∈ B. Therefore b ∈ A ∪ B. Since b was arbitrary, B ∪ A ⊆ A ∪ B.

Since both inclusions hold, we can use the Axiom of Extensionality to state A∪B=B∪A. QED

Theorem 14.7 Commutativity of Intersection: A ∩ B=B∩A.

Theorem 14.8 Associativity of Union: (A ∪( B∪C)=(A∪B)∪C.)

Proof of Theorem 14.8: We prove equality by element-chasing to show both inclusions. We begin with showing that (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C). Let a be an arbitrary element such that
a ∈ (A ∪ B) ∪ C. By the definition of a union, this means a ∈ (A ∪ B)  or  a ∈ C.

We examine the first case where a ∈ (A ∪ B)⇒a∈A∨a∈B⇒a∈A ∪ (B ∪ C), since A is in the union, or B is inside B∪C.

For the second case, a ∈ C⇒ x ∈ A ∪ (B ∪ C)  (because C is in the union)In both cases, a ∈ A ∪ (B ∪ C). Since a was arbitrary, (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C).

Now we need to show A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C.

Let b be an arbitrary element such that b ∈ A ∪ (B ∪ C).

By the definition of union, b ∈ A  or  b ∈ (B ∪ C).

We examine the first case, b ∈ A⇒ b ∈ (A ∪ B)  (because A is in A ∪ B). This implies b ∈ (A ∪ B) ∪ C.

We now turn to the second case, b ∈ (B ∪ C)⇒ b ∈ B  or  b ∈ C⇒ b ∈ (A ∪ B)  (because B is in A ∪ B)  or  b ∈ C⇒ b ∈ (A ∪ B) ∪ C.

In both cases, b ∈ (A ∪ B) ∪ C.

Thus A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C.

Both inclusions hold, so by the Axiom of Extensionality A ∪ (B ∪ C) = (A ∪ B) ∪ C. QED

Theorem 14.9 Associativity of Intersection: (A ∩( B∩C)=(A∩B)∩C).

Theorem 14.10 Distributivity of Union over Intersection: (A ∪( B∩C)=(A∪B)∩(A∪C)).

Proof of Theorem 14.10: We shall prove equality by using element-chasing to show that both inclusions are true.

First we shall show A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).

Let a be an arbitrary element such that a ∈ A ∩ (B ∪ C).By the definition of intersection, a ∈ A and a ∈ B ∪ C.

Since a ∈ B ∪ C, we have a ∈ B or a ∈ C.

For the first case, a ∈ B. Then a ∈ A and a ∈ B ⇒ a ∈ A ∩ B ⇒ a ∈ (A ∩ B) ∪ (A ∩ C).

We turn to the second case, x ∈ C. Then a ∈ A and a ∈ C ⇒ a ∈ A ∩ C ⇒ a ∈ (A ∩ B) ∪ (A ∩ C).

In both cases, a belongs to the right-hand side.

Now, since a was arbitrary, A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).

We now show that (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).

Let b be an arbitrary element such that b ∈ (A ∩ B) ∪ (A ∩ C).

Then b ∈ A ∩ B or b ∈ A ∩ C.

We now examine the first case, b ∈ A ∩ B⇒ b ∈ A ∧ b ∈ B⇒ b ∈ A ∧ (b ∈ B ∨ b ∈ C)⇒ b ∈ A ∩ (B ∪ C).

For the second case,  b ∈ A ∩ C⇒ b ∈ A ∧ b ∈ C⇒ b ∈ A ∧ (b ∈ B ∨ b ∈ C)⇒ b ∈ A ∩ (B ∪ C).

In both cases, b ∈ A ∩ (B ∪ C).

Since b was arbitrary, (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).

So both inclusions hold, thus by the Axiom of Extensionality A ∩ (B ∪ C)=(A ∩ B)∪(A ∩ C). QED

Theorem 14.11 Distributivity of Intersection over Union: (A ∩( B∪C)=(A∩B)∪(A∩C)).

Theorem 14.12 1st Complement law: .

Proof of Theorem 14.12: We show both directions using element-chasing.

For the first direction we show .

Take any element .

By the definition of union, a∈A  or .  If a∈A, then a∈U  (because A⊆U).

If , then   (because the complement is taken inside U).

In either case, a∈U.

Therefore .
We now turn to the second direction where we need to show .

Take any element a∈U.

Either a∈A  or a∉A.

If a∈A, then .

If a∉A, then by the definition of the complement , so again .

In both cases .
Therefore .

Both inclusions hold, so by the Axiom of Extensionality: . QED

Theorem 14.13 2nd Complement law: .

Theorem 14.14 De Morgan’s first law: .

Proof of Theorem 14.14: We prove the two sets are equal by showing each is a subset of the other.

First we show .

Let a be an arbitrary element such that .

By definition of the complement, x∉A ∪ B. This means it is not the case that a∈A or x∈B, so a∉A.Therefore (by the definition of complement) and , so .

Since a was arbitrary, .

Secondly, we show .

We let a be an arbitrary element such that .

Then   and , so a∉A  and a∉B.

Therefore a is not in A and not in B, so a∉A ∪ B.

By the definition of complement, .

Since a was arbitrary, .

Both inclusions hold, so by the Axiom of Extensionality . QED

Theorem 14.15 De Morgan’s second law: .

Theorem 14.16: A ∪ Ø = A.

Proof of Theorem 14.16: We show both directions by element-chasing.

For the first direction we show that A ∪ Ø⊆A.  Let a be an arbitrary element such that a ∈ A ∪ Ø.

By  the definition of union we have, a ∈ A or a ∈ Ø.

But nothing belongs to the empty set, so a ∈ Ø is impossible.

Therefore the only possibility is a ∈ A. Since a was arbitrary, every element of A ∪ Ø belongs to A.

Thus A ∪ Ø⊆A.

Next we show A⊆A ∪ Ø.  Let a be an arbitrary element such that a ∈ A.

By the definition of union, every element that belongs to A automatically belongs to A ∪ Ø.

Therefore a ∈ A ∪ Ø.

Since a was arbitrary, every element of A belongs to A ∪ Ø.
Thus A⊆A ∪ Ø.

Both inclusions hold, so by the Axiom of Extensionality we have A ∪ Ø=A. QED

Theorem 14.17: A ∩ Ø = Ø.

Theorem 14.18: A ∪ U = U.

Proof of Theorem 14.18: Once again, we use the element-chasing method to show both inclusions.

We begin with the first inclusion, A ∪ U ⊆ U.  Let a be an arbitrary element such that a ∈ A ∪ U.

By the definition of union, this means a ∈ A or a ∈ U.

If a ∈ A, then a ∈ U (because U contains every possible element).

If a ∈ U, then we are done with this argument.

In either case, a ∈ U.

Since a was arbitrary, every element of A ∪ U belongs to U, so A ∪ U ⊆ U.

We now turn to the second inclusion, U ⊆ A ∪ U. Let a be an arbitrary element such that a ∈ U.

Because U is the universal set, a certainly belongs to U.

Therefore a ∈ A ∪ U (the second part of the disjunction holds).

Since a was arbitrary, every element of U belongs to A ∪ U, so U ⊆ A ∪ U.

Since both inclusions hold, we conclude A ∪ U = U. QED

Theorem 14.19: A ∩ U = A.

Theorem 14.20: A × Ø = Ø × A = Ø.

Proof of Theorem 14.20: We use element-chasing to prove both directions for each equality.

We begin with A × Ø = Ø⇒ A × Ø ⊆ Ø.
Take any element (a, b) ∈ A × Ø.

By definition of Cartesian product, this requires b ∈ Ø.

But nothing belongs to the empty set, so there is no such b.

Therefore no ordered pair (a, b) can belong to A × Ø.

Hence A × Ø contains no elements at all, i.e. A × Ø = Ø.

We turn to this  Ø ⊆ A × Ø.

The empty set is a subset of every set (there are no elements of Ø to violate the subset relation).

Thus Ø ⊆ A × Ø holds automatically.

Therefore A × Ø = Ø = Ø.

We now turn to this Ø × A = Ø.

Exactly the same argument, just swap the sets.

Take any supposed element (a, b) ∈ Ø × A.

Then a ∈ Ø and b ∈ A.

But a ∈ Ø is impossible so no such ordered pair exists. Therefore Ø × A = Ø.

Thus the Cartesian product with the empty set is always empty:A × Ø = Ø × A = Ø for any set A.

This is exactly analogous to how 0 is the absorbing (zero) element for multiplication, a · 0 = 0 · a = 0.

In set theory, Ø is the absorbing element for the Cartesian product. QED

Exercise 14.4: Begin with Definition 14.9 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition, principle, theorem, and proof.

Exercise 14.5:
a) Give the details for the proof of Theorem 14.7. How does your proof compare to the listed proof of theorem 13.6?
b) Give the details for a proof of Theorem 14.9. How does your proof compare to the listed proof of theorem 13.8?
c) Give the details for a proof of Theorem 14.11. How does your proof compare to the listed proof of theorem 13.10?
d) Give the details for a proof of Theorem 14.13. How does your proof compare to the listed proof of theorem 13.12?
e) Give the details for a proof of Theorem 14.15. How does your proof compare to the listed proof of theorem 13.14?
f) Give the details for a proof of Theorem 14.17. How does your proof compare to the listed proof of theorem 13.16?
g) Give the details for a proof of Theorem 14.19. How does your proof compare to the listed proof of theorem 13.18?
h) Prove (A ∪ B) × C = (A × C) ∪ (B × C)  
i) Prove (A ∩ B) × C = (A × C) ∩ (B × C)  
j) Prove A × (B ∪ C) = (A × B) ∪ (A × C)  
k) Prove A × (B ∩ C) = (A × B) ∩ (A × C)  
l) Prove that if A × B = Ø, then either A = Ø or B = Ø (or both).

Geometric Sets

With set theory now giving us the precise language of modern mathematics, we return to geometry and discover that every geometric object is nothing more than a set of points. We begin with the plane (or three-dimensional space) itself. We treat the entire collection of all points we are considering as the universal set U. Every figure we draw is then a subset of this universal set of points. We can actually use another symbol for this set of all points, for the infinite line we call it the Euclidean space in one dimension, we symbolize this with the double-struck E, and we assign the number of dimensions as an upper index, . For the infinite place, we write . For the infinite three-dimensional space (or simply three-space) we write .

A line segment joining two points A and B is the set of all points that lie between A and B, including A and B themselves. A ray starting at A consists of A together with every point extending infinitely in one direction from A. An entire straight line through A and B is the set of all points that lie on the infinite line passing through them. A circle with center O and radius r is the set of all points exactly distance r from O, while a filled disk includes every point at distance less than or equal to r. A triangle A B C is the set of all points inside and on the boundary of the three-sided figure formed by A, B, and C. A half-plane is the collection of all points lying on one side of a given line, either including the line or not, according to the definition we choose.

The familiar set operations now acquire vivid geometric meaning. The union of two regions contains every point that belongs to at least one of the regions; two overlapping disks, for example, form a union that includes both disks and their lens-shaped overlap. The intersection consists only of the points common to both regions; two intersecting lines yield one or two points, while two overlapping disks produce the lens itself. The set difference removes from one region everything that belongs to the other; subtracting a smaller disk from a larger one leaves a ring. The complement of a region, taken with respect to the whole plane or space, is simply the set of all points lying outside that region.

These operations obey the same algebraic laws we have already proved. Adding the empty set of points changes nothing, so a region united with the empty set remains itself. Intersecting any region with the empty set yields nothing. The union of a region with its complement fills the entire plane or space, while their intersection is empty. These identities are no longer abstract; they are visible facts about areas, volumes, and boundaries.

In physics, this viewpoint is extraordinarily powerful. The possible positions of a particle form a region of space representing a set of points. The trajectory of a moving particle is a curve itself another set of points. Two particles collide only if the sets representing their trajectories have a non-empty intersection. A physical state is an element of the vast set of all possible states. Forces, fields, and conservation laws all correspond to relationships among these geometric sets.

Geometry, seen through the lens of set theory, is no longer a collection of separate figures; it is a single, unified language in which every point, line, surface, and volume is a set, and every relationship among them is a set operation.

Definitions

Definition 14.19 Euclidean space (n-dimensional) : The universal set of all points in n-dimensional space subject to the rules of Euclidean geometry.

Definition 14.20 Line segment joining points A and B: The set of all points lying on the line through A and B, including A and B.

Definition 14.21 Ray starting at A (in direction toward B): The union with all points extending infinitely in one direction from A along the line.

Definition 14.22 Straight line through A and B: The infinite set of all points collinear with A and B.

Definition 14.23 Circle with center O and radius r: The set of all points exactly distance r from O.

Definition 14.24 Filled disk (ball in 2D): The set of all points at distance ≤ r from O (circle plus interior).

Definition 14.25 Triangle ABC: The set of all points inside and on the boundary of the three-sided figure formed by segments AB, BC, CA (such figures can be called a convex hull including interior and boundary).

Definition 14.26 Half-plane: The collection of all points lying on one side of a given line (may or may not include the line, depending on closed/open choice).

Exercise 14.6: Begin with Definition 14.19 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition.

Exercise 14.7:
a) Describe each of the following geometric sets using set notation and, when possible, draw a quick sketch.
    All points in the plane that are exactly 5 units from the origin.  
    All points inside the square with vertices (0,0), (2,0), (2,2), (0,2).  
    All points on the line segment joining (−1, 3) and (4, −2).  
    The set of points (x, y) such that x ≥ 0 and y ≤ 1 (a closed half-plane corner).
b) Determine whether each set excludes its boundary (the set is open), includes its boundary (is closed). Justify your choice with a brief statement.
    The disk of radius 2 centered at (0,0): .
    The disk of radius 2 centered at the origin, .
c) Let  , B = { (x,y) | |x| + |y| ≤ 1 }.
    Sketch both sets.  
    Describe A ∩ B geometrically (what shape is it?).  
    Describe A ∪ B geometrically.
d) Let I = [0, 1] and J = (2, 5).
    Sketch I × J in the plane.  
    Is I × J open, closed, or neither?  
    What is the boundary of I × J?

Families of Sets

With the basic operations of union, intersection, and complement now mastered for two or three sets, we extend the idea to any number of sets—even infinitely many. A family of sets is simply a collection whose elements are themselves sets. We usually label the individual sets with an index that runs over some index set I. When I is finite, say {1, 2, …, n}, we write the family as . When I is infinite—for example, the natural numbers, the real numbers, or the set of all angles— we write {Aᵢ}ᵢ∈I or simply {Aᵢ}.

The union of a family of sets is written

(14.30)

and contains every element that belongs to at least one of the sets in the family.

The intersection of a family is similarly written

(14.31)

and contains every element that belongs to all of the sets in the family simultaneously.

In words, the big ∪ is “or over all indices,” and the big ∩ is “and over all indices.”

Consider the family where , the set of the first n natural numbers. As n grows without bound, the union of all these sets is

(14.32)

the entire set of natural numbers, while their intersection is

(14.33)

because no single number belongs to every .

Now consider intervals centered at the origin. Let for every positive real number x. The union of all these open intervals is

(14.34)

the entire real line, because any real number is inside some interval of large enough radius. Their intersection, however, is

(14.35)

because only the origin lies inside every interval, no matter how small x becomes.

Finally, imagine a rotating a half-plane around the origin. For every angle φ, let be the half-plane below the line at angle φ. The union of all these half-planes is

(14.36)

because every point lies below some rotated line. Their intersection is

(14.37)

because no point can lie below every possible line passing through the origin.

The beautiful duality of De Morgan’s laws extends unchanged to families:

(14.38)

and

(14.39)

Distributivity also survives, intersecting a fixed set A with an arbitrary union yields the union of the individual intersections, and uniting A with an arbitrary intersection yields the intersection of the individual unions,

(14.40)

and

(14.41)

In physics, families of sets appear everywhere. The collection of all possible positions of a particle at different times is a family indexed by time. The region reachable by a robot arm is the union of all positions its joints can attain. The region forbidden by multiple constraints is the intersection of the complements of the allowed regions. Indexed unions and intersections give us the language to speak precisely about all times, all energies, all directions, or all particles at once.

A family of sets is nothing more than a set whose elements happen to be sets — and with it, the algebra of sets becomes powerful enough to describe the entire universe of physical possibilities.

Terms

Term 14.3 Family of sets: A collection whose elements are themselves sets. Usually written as where I is an index set (can be finite, countable, or uncountable).

Definitions

Definition 14.27 Index set I: Any set used to label the individual sets in the family (e.g., I = {1,2,3}, N, ℤ, R, or the set of all angles).

Definition 14.28 Union of a family: (read: “the set of everything that is in some ”).

Definition 14.29 Intersection of a family: (read: “the set of everything that is in all at once”).

Definition 14.30 Empty family: A family with no sets at all. By convention: ∪ (empty) = Ø    and    ∩ (empty) = universe (the set we are working inside).

Definition 14.31 Partition of a set X: A family of non-empty sets } such that
    (1) the are pairwise disjoint .
    (2) their union is the whole set X: .

Theorems

Theorem 14.21 De Morgan’s Laws for arbitrary families:

    
    .

Proof of Theorem 14.21: Let be an arbitrary (possibly infinite or uncountable) indexed family of sets, all contained in some universal set X. De Morgan’s laws state

(14.42)

and

(14.43)

where denotes the complement with respect to X.

Proof of (14.42): . We prove set equality by showing mutual inclusion. We begin with the subset relation. Let . By the definition of complement, . This means there is no index i∈I  such that , i.e., for every i∈I, we have . Thus   for every i∈I, so .

We n ow turn to the superset relation. Let . Then   for every i∈I, i.e., for every i∈I. Therefore x belongs to none of the , so . Hence .

Since both inclusions hold, .

Proof of (14.43): . Again, we prove the mutual inclusion. We begin with the subset relation. Let . Then .This means it is not true that x belongs to every , i.e., there exists some i∈I such that . Thus for that i, so .

We now turn to thew superset relation. Let . Then there exists some i∈I such that , i.e., . So x fails to belong to at least one , hence . Therefore .

So both inclusions hold, so .

The proofs rely only on the logical meanings of union (“there exists”) and intersection (“for all”), so they work for any index set I, finite or infinite.

These are sometimes called the generalized De Morgan’s laws; when I is finite (usually I={1,2} or {1,…,n}), they reduce to the familiar two-set or n-set versions taught in elementary set theory.

Thus, De Morgan’s laws are proven for arbitrary families of sets. QED

Theorem 14.22 Distributive laws (one set over arbitrary family)

    
    .

Proof of Theorem 14.22: Let } be an arbitrary indexed family of sets (where I can be any index set, possibly infinite), all are subsets of some universal set. Let B be any set. Our goal is to prove the two distributive laws. These hold even when I is infinite (the finite-case proofs are special cases).

Proof of Law 1: Intersection distributes over arbitrary unions. We seek to show both inclusions. We begin with the subset relation.  Let . By the definition of intersection, x∈B and . The second condition means there exists some k∈I such that . Thus x∈B and , so . Therefore .

We now turn to the superset relation.  Let . Then there exists some k∈I such that . So x∈B and , which implies . Hence .Thus, both inclusions hold, so equality holds.

I leave the proof Proof of Law 2 as an exercise.

Theorem 14.23 Monotonicity of union and intersection: If Aᵢ ⊆ Bᵢ for every i, then and .

Proof of Theorem 14.23: To prove , take an arbitrary element . By the definition of the arbitrary union, this means there exists some j∈I such that . Since (by the given condition), it follows that . Therefore, (by the definition of arbitrary union).  Since x was arbitrary, this holds for all elements of , so .

Exercise 14.8: Begin with Term 14.3 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, theorem, and proof.

Exercise 14.9:
a) Let , and in general for every positive integer n. Write the union and the intersection explicitly.  
Write and explicitly.  Is there any integer that belongs to infinitely many of the sets ?
b) Let be any family of sets (finite or infinite index set I). Prove the two infinite De Morgan laws (14.40) and (14.41) using element-chasing.
c) A family of non-empty sets is a partition of a set X if  they are pairwise disjoint: where i ≠ j, and their union is the whole set: .
Decide which of the following families are partitions of ℝ (the real line). Check to see if these are partitions of R.
     for every integer n  
     for every integer n  
     for every integer n
d) Prove Theorem 14.22 Law 2.
e) Prove Theorem 14.23 for intersection.

Proof by Mathematical Induction

Many statements concern every positive integer. For example, “the sum of the first n natural numbers is n(n+1)/2,” “a set with n elements has subsets,” “a polygon with n sides has n−2 diagonals from one vertex,” and so on.

Checking infinitely many cases one by one is impossible, so we need a single argument that covers all positive integers at once.

Say that you have arranged an infinite line of dominoes numbered 1, 2, 3, …. If  domino 1 falls into its neighbor, and  whenever domino k falls, it knocks over domino k+1, then every domino will fall, no matter how large its biggest number.

Mathematical induction is precisely this domino argument applied to the set of positive integers. We call this the Principle of Mathematical Induction. Let P(n) be a statement about the natural numbers n = 1, 2, 3, …  There are two parts of this method. The first is called the base case, where we show that P(1) is true. The second part is called the inductive step where we prove that for every k ≥ 1, if P(k) is true, then P(k+1) is also true. If we can prove both of these, then P(n) is true for all natural numbers (or the whole numbers if you begin with 0).

The set of natural numbers N = {1, 2, 3, …} has two decisive properties guaranteed by the way the numbers are built. The first is that 1 belongs to N. Whenever a number k belongs to N, the next number k+1 also belongs to N.

So, suppose P(1) holds and the inductive step holds. Assume, for contradiction, that some natural numbers fail P. Let m be the smallest natural for which P(m) is false.  By definition m cannot be 1 (this represents the base case). We can see that m cannot be larger than 1, because then m−1 is a smaller natural, P(m−1) is true (by choice of m), and the inductive step forces P(m) to be true—leading to a contradiction. Therefore no such m exists, and P(n) holds for all naturals n.

So, how do we actually write an inductive proof?

Prove the base case–Verify P(1) directly.

Prove the inductive step–Assume P(k) is true for some k ≥ 1 (this is called the induction hypothesis).

Using only that assumption, prove P(k+1).

Conclusion–By the principle of mathematical induction, P(n) is true for all naturals n.

For example, we can use this for the sum of the first n natural numbers. We begin by making the claim that

(14.44)

for every natural n. We perform step 1, establishing the base case, n = 1. This gives us

(14.45)

So, the base step is true.

We now try the inductive step. We begin this by assuming that (14.44) holds for n = k

(14.47)

Now we add k+1 to both sides:

(14.47)

If we realize that k+1=n, then this becomes (14.44), so we have proved it for all natural numbers. QED

Sometimes proving P(k+1) needs the statement to be true for all natural numbers from 1 up to k. We call this strong induction. We would write if P(1) is true and, whenever P(1), P(2), …, P(k) are all true, then P(k+1) is true and P(n) holds for every natural number n.

The domino picture still works; each new domino can be knocked over by one of the previous ones.

Undefined Terms

Term 14.4 Successor: The number following any number k, written k+1.

Definitions

Definition 14.32 Base case: The verification that the proposed theorem P is true for the value 1, often written P(1).

Definition 14.33 Inductive step (ordinary induction): Proof that for every k ≥ 1, if P(k) is true, then P(k+1) is true.

Definition 14.34 Induction hypothesis: The assumption that P(k) holds for some fixed k ≥ 1.

Definition 14.35 Strong induction: If P(1) is true and, whenever P(1), …, P(k) are all true, then P(k+1) is true, then P(n) is true for all n ∈ N.

Axioms

Axiom 14.2 Successor Axiom (Peano-style): Given 1 ∈ N, and if k ∈ N, then k+1 ∈ N.

Principles

Principle 14.10 Principle of Mathematical Induction: If P(1) holds and ∀k ≥ 1 [P(k) ⇒ P(k+1)], then P(n) holds ∀n ∈ N.

Principle 14.11 Well-Ordering Principle: Every non-empty subset of N  has a least element.

Principle 14.12 Strong Induction Principle: If P(1) holds and ∀k ≥ 1 [ (P(1) ∧ … ∧ P(k)) ⇒ P(k+1) ], then P(n) holds ∀n ∈ N.

Theorems

Theorem 14.24 Standard Induction Theorem: If the base case P(1) is true and the inductive step holds, then P(n) is true for all natural numbers n.

Proof of Theorem 14.24: We will prove this using proof by contradiction. Assume the two hypotheses hold:  P(1) is true, and ∀k≥1, P(k)   ⇒   P(k+1).

Suppose, for the sake of contradiction, that the conclusion is false. That is, suppose there exists at least one natural number m such that P(m) is false. Let S={n∈N∣P(n) is false}. By our setup, S is non-empty.  By the Well-Ordering Principle (every non-empty subset of the natural numbers has a least element), S has a smallest element. Call this smallest element m. So m is the smallest natural number for which P(m) is false.

Now consider two possibilities: Case 1: m=1. But this contradicts the base case, which states that P(1) is true. Since we are assuming that our hypothesis is false, this cannot be true. Therefore m≠1

Case 2: m≥2. Then m−1 is a natural number and m−1<m. Since m is the smallest element of S, m-1∉S. That is, P(m−1) is true. By the inductive step (with k=m−1), since P(m−1) is true, it follows that P(m) is true.

But this contradicts the fact that m∈S  (i.e., P(m) is false).

In both cases we reach a contradiction. Therefore our initial supposition must be false: there is no natural number m for which P(m) is false.

Hence P(n) is true for every natural number n.  QED

Theorem 14.25 Strong Induction: If the base case P(1) is true and the strong inductive step holds, then P(n) is true for all natural numbers n.

Proof of Theorem 14.25: We will prove this using proof by contradiction. Assume the two hypotheses hold:  P(1) is true, and ∀k≥1, [P(1)∧P(2)∧···∧P(k)]    ⇒   P(k+1).

Suppose, for the sake of contradiction, that the conclusion is false—that is, there exists at least one natural number m such that P(m) is false.

Let S={n∈N∣P(n) is false}.

By our supposition, S is non-empty. By the Well-Ordering Principle, S has a smallest element; call it m. So m is the smallest natural number for which P(m) is false.
We now examine two cases:

Case 1: m=1. But the base case states that P(1) is true. Therefore 1∉S. This contradicts the assumption that m=1 is in S. Hence m≠1.

Case 2: m≥2. Then m−1 is a natural number and m−1<m. Since m is the smallest element of S, m−1∉S. That means P(m−1) is true. Moreover, because m−1≥1, all the statements P(1),P(2),…,P(m−1) are true (again, because any smaller number cannot be in S.  

Now apply the strong inductive step with k=m−1: Since P(1)∧···∧P(m−1) holds, it follows that P(m) is true.  

But this contradicts the fact that  P(m) is false (i.e., m∈S).

In both cases we have reached a contradiction. Therefore the initial supposition is false: no such m exists. Hence P(n) is true for every natural number n.  QED

Theorem 14.26 Inductive Equivalence Theorem: The Principle of Mathematical Induction, Strong Induction, and the Well-Ordering Principle are logically equivalent.

Proof of Theorem 14.26: We prove the equivalences by showing the cycle: Standard Induction ⇒ Strong Induction ⇒ Well-Ordering ⇒ Standard Induction. (This closes the loop; the other directions follow similarly.)

Part 1: Standard Induction ⇒ Strong Induction

Assume Standard Induction holds. Let Q(n) be the auxiliary statement: “P(m) is true for all m = 1, 2, …, n.”

Base case for Q: Q(1) says P(1) is true as given by the hypothesis for P.

Inductive step for Q: Assume Q(k) is true, i.e., P(1) through P(k) all hold.

By the strong inductive hypothesis for P (with this k), P(k+1) is true.

Therefore Q(k+1) holds (P(1) through P(k+1) are all true).

By Standard Induction applied to Q, Q(n) is true for all n.

Hence P(n) is true for all n.

Thus Standard Induction implies Strong Induction.

Part 2: Strong Induction ⇒ Well-Ordering Principle

Assume Strong Induction holds.
Let S be any non-empty subset of N. We must show S has a least element.

Define the statement R(n): “Every non-empty subset of N that contains a number ≤ n has a least element.”

Base case: R(1) is true because the only non-empty subset involving 1 is {1}, which has least element 1.

Strong inductive step: Assume R(1) through R(k) are all true (i.e., every non-empty subset bounded above by k has a least element).

Now consider any non-empty subset T of N that contains a number ≤ k+1.

If T has an element ≤ k, then by the induction hypothesis R(k), T has a least element.

If not, then the smallest possible element in T must be k+1 itself (since T is non-empty and has something ≤ k+1). Thus k+1 is the least element of T.

By Strong Induction, R(n) holds for all n.

In particular, taking n large enough to exceed any element of our original non-empty S, S has a least element.

Thus Strong Induction implies the Well-Ordering Principle.

Part 3: Well-Ordering Principle ⇒ Standard Induction

Assume the Well-Ordering Principle holds.

Let P(n) be any statement satisfying the hypotheses of Standard Induction: P(1) is true, and ∀k ≥ 1, P(k) ⇒ P(k+1).

Suppose, for contradiction, that P(n) is not true for all n. Let S={n∈N∣P(n) is false}.

Then S is non-empty. By Well-Ordering, S has a least element m.

If m = 1, this contradicts the base case P(1) being true.

If m ≥ 2, then m−1 < m and m−1 ∉ S, so P(m−1) is true. By the inductive step, P(m−1) ⇒ P(m), so P(m) is true. This contradicts m ∈ S.

Both cases yield a contradiction, so S must be empty. Therefore P(n) is true for all n ∈ N.

Thus Well-Ordering implies Standard Induction.

Since we have shown Standard ⇒ Strong ⇒ Well-Ordering ⇒ Standard, all three statements are logically equivalent.QED

Exercise 14.10: Begin with Term 14.4 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, axiom,principle, theorem, and proof.

Exercise 14.11:
a) Prove that for all n ≥ 1.
b) Prove that for all positive integers n ≥ 10 (first check smaller n directly).
c) Prove that any set with n elements has exactly subsets.
d) Explain in your own words why the domino analogy captures induction perfectly.

Axioms of Set Theory

With set theory now serving as the foundation of all mathematics, we must ask: on what solid ground do we build this foundation?

At the end of the nineteenth century, naive set theory (sets defined by any property, as we have been dealing with them so far) led to paradoxes—the most famous being Russell’s paradox: “Is the set of all sets that do not contain themselves a member of itself?”

To eliminate these contradictions while preserving the power of set theory, Ernst Zermelo in 1908 proposed the first axiomatic system, later refined by Abraham Fraenkel and others. The resulting Zermelo–Fraenkel set theory with the Axiom of Choice—universally abbreviated ZFC—is today the standard foundation of mathematics.

All the set operations we have used so far can be proved from these axioms.

The ZFC Axioms are

Axiom 14.3 Axiom of Extensionality:  Two sets are equal if and only if they have exactly the same elements.

Axiom 14.4 Axiom of the Empty Set: There exists a set with no elements (the empty set Ø).

Axiom 14.5 Axiom of Pairing:  For any two objects a and b, there exists a set {a, b} that contains exactly a and b.

Axiom 14.6 Axiom of Union: For any set of sets F, there exists a set that contains exactly the elements of the sets in F ).

Axiom 14.7 Axiom of Power Set: For any set A, there exists a set whose elements are exactly all the subsets of A (the power set P(A)).

Axiom 14.8 Axiom of Infinity: There exists at least one infinite set (from which the natural numbers can be constructed).

Axiom 14.9 Axiom Schema of Separation (Comprehension): Given any set A and any definite property P(x), there exists a set containing exactly those elements of A that satisfy P(x).

Here we introduce an important definition.

Term/Definition 14.36 Function: Let A and B be sets. A function from A to B, written f: A → B, is a subset f of A × B such that for each a ∈A there exists at most one b ∈B such that (a, b)∈f. If (a, b)∈f, then we write b = f(a). We will see more about functions later in this lesson. Another word for a functions is a map.

Axiom 14.10 Axiom Schema of Replacement: If a definite function F maps elements of a set A to objects, then there exists a set containing exactly the images F(x) for x ∈ A.

Axiom 14.11 Axiom of Regularity (Foundation): Every non-empty set A has an element that is disjoint from A (this prevents sets from containing themselves).

Axiom 14.12 Axiom of Choice (AC): For any set of non-empty disjoint sets, there exists a set that contains exactly one element from each of them. This deceptively innocuous axiom has developed a great deal of controversy.

These axioms are very important. Extensionality gives us the definition of set equality we have used all along.  Empty Set, Pairing, Union, Power Set allow us to construct all the sets we need in everyday mathematics.  Infinity guarantees the existence of the natural numbers.  Separation and Replacement let us define new sets from old ones safely.  Regularity blocks the paradoxes that destroyed nave set theory.  Choice is needed for many proofs.

ZFC is the quiet, invisible foundation on which the entire edifice of modern mathematics stands.

Theorems

Theorem 14.27 Extensionality Theorem: Two sets are equal if and only if they have exactly the same elements. This follows directly from the Axiom of Extensionality.

Proof of Theorem 14.27: In precise language Theorem 14.24 can we written that for any sets A and B, A=B   ⇔   ∀x (x∈A⇔x∈B). This theorem is essentially a direct restatement of the Axiom 14.1 The Axioms of Extensionality, whose formal statement is, ∀(A∧B)   ∧(∀x) (x∈A⇔x∈B)   ⇒   A=B). We now seek to prove the “if and only if” theorem using the axiom. We prove the two directions separately. We begin with the direct implication, ⇒. If A=B, , then they have exactly the same elements. In virtually all modern set theories, the membership relation ∈ satisfies the substitution property (or “Leibniz’s law” for equality). Namely, : if two objects are equal, any property true of one is true of the other. In particular, for any object a ,if a∈A, then (by substitution) a∈B. If a∈B, then a∈A.
Thus a∈A⇔a∈B for every a, i.e., A and B have exactly the same elements. (This direction is sometimes called the “principle of substitutivity of equality” and is logically prior to, or built into, first-order logic with equality.)

We now turn to the other direction ⇐. If A and B have exactly the same elements, then A=B. We will now prove this. Assume (∀a) (a∈A⇔a∈B). This is precisely the hypothesis of the Axiom of Extensionality, whose conclusion is A=B.Therefore, by the Axiom of Extensionality, A=B.

We conclude that combining both directions, we have established the biconditional A=B   ⇔   A and B have exactly the same elements.
This is why the Axiom of Extensionality is also called the principle that sets are determined by their elements—it tells us that the only thing that matters about a set is which objects belong to it. No additional structure, labeling, or history distinguishes two sets that contain exactly the same members. QED.

Theorem 14.28 Empty Set Theorem: There exists a unique set with no elements, denoted Ø.

Proof of Theorem 14.28: This proof will have two part, existence and uniqueness. We begin with the existence part. By Axiom 14.2 The Axiom of the Empty Set, there exists a set that contains no elements. We denote this set by Ø.(Some textbooks construct Ø instead of taking it as an axiom, for example by the axiom of infinity plus separation, or by taking a singleton of something and removing it—but the standard modern treatment simply postulates its existence.) We are done with part one.

We now turn to uniqueness. Suppose A and B are both empty sets. That means that ∀x (x ∉ A) ∧ ∀x (x ∉ B).We now use Axiom 14.1 The Axiom of Extensionality, where two sets are equal if and only if they have exactly the same elements. Since every element of A is an element of B (and this is trivially true, because there are no elements of A (a vacuous truth)). Every element of B is also an element of A—also vacuously true. Therefore, by the Axiom of Extensionality, A = B. Thus any two empty sets are the same set.

In conclusion, there exists exactly one set that has no elements, and we call it the empty set Ø. QED

Theorem 14.29 Singleton Theorem: For any object a, there exists a set {a} containing a as its only element.

Proof of Theorem 14.29: Once again we will prove this in two parts, existence and uniqueness. We begin with existence. By Axiom 14.3 The Axiom of Pairing, for any objects a and b, there exists a set whose elements are exactly a and b. That is, (∃S)( ∀y) (y ∈ S  y = a ∨ y = b).To construct the singleton {x}, simply apply the axiom with a = b = x, so (∃S)( ∀y) (y ∈ S  y = x ∨ y = x). This simplifies to (∃S)( ∀y) (y ∈ S  y = x). Thus the set {x} exists. (Intuitively: every subset of A is obtained by “choosing” for each element of A whether it belongs or not. Replacement guarantees the result is a set.)More formally: consider the definable function on the set of all functions from A to {0,1} (the set of choice functions exists by other axioms). Map each such function f: A → {0,1} to the subset { a ∈ A | f(a) = 1 }. Replacement says the image of this function is a set, and that image is exactly the collection of all subsets of A. Call this set P(A). Then, by construction, X ∈ P(A) ⇔ X ⊆ A.

We now turn to uniqueness. Suppose A and B are both sets whose only element is x. That means (∀y) (y ∈ A  y = x) and (∀y) (y ∈ B  y = x). Now we apply Axiom 14.1 The Axiom of Extensionality. If something belongs to A, it must be x, and x certainly belongs to B.  So, every element of B is an element of A. Symmetrically, the only thing in B is x, which is in A. Therefore A = B by Extensionality.

In conclusion there exists exactly one set that contains x and nothing else; we call it the singleton {x}. QED.

Theorem 14.30 Unordered Pair Theorem: For any objects a and b, there exists a set {a, b} containing exactly a and b as elements.

Proof of Theorem 14.30: This will again be a proof in two parts. We begin with the existence part. We build {x, y} using only the axioms we already have. By the Singleton Theorem, the sets {x} and {y} both exist. By the Axiom of Pairing, there exists a set that contains exactly the two objects {x} and {y} as elements. Call this set P such that P = {{x}, {y}}. If x = y, then P = {{x}}, which is fine. By the Axiom of Pairing again (applied to the objects x and y themselves), there exists a set that contains exactly x and y as elements.

However, most textbooks take a slightly longer but completely explicit route to avoid any doubt. Form the singleton {x} (and show it exists). Then form the singleton {y} (and show it exists). Form the ordered pair (x, y) in 1921 the famous Polish Mathematician  Kazimierz Kuratowski’s produced a new definition of the ordered pair (x, y) ≔ {{x}, {x, y}}. The elements of this ordered pair are exactly {x} and {x, y}.  Take the union of that ordered pair {x, y}  =∪{{x}, {x, y}} = {x}∪ {x, y} = {x, y}. This union exists by the Axiom of Union. Thus {x, y} exists in all cases.

We now turn to the second part, uniqueness. Suppose A and B are both sets whose elements are exactly x and y. That means (∀z) (z ∈ A  (z = x ∨ z = y))∧(∀z) (z∈B (z=x∨z=y)). By the Axiom of Extensionality, two sets are equal if and only if they have the same elements. Every element of A is an element of B (because the only possibilities are x and y, both of which are in B).  So, every element of B is an element of A (by symmetry).
Therefore A = B.

In conclusion, for any x and y, there exists exactly one set that contains precisely x and y as its elements. We denote this unique set by {x, y}. QED

Theorem 14.31 Union Theorem: For any sets A ∧ B , the union A∪B exists as a set.

Proof of Theorem 14.31: We begin with the existence of the union. We are given a set C whose elements are themselves sets (i.e., C is a set of sets). We must construct the set that collects everything inside any member of C. Use the Axiom Schema of Replacement (or Separation, depending on the presentation). Consider the class expression {y | ∃A ∈ C (y ∈ A)}.By Replacement (applied to the definable rule that sends each A ∈ C to its elements), this class is itself a set. Call this set U. Then clearly x ∈ U ⇔ ∃A ∈ C (x ∈ A).Therefore the union exists. (Older textbooks use the Axiom of Union directly: there exists a set whose elements are all the elements of the elements of C. The modern treatment derives the same result from Replacement or Comprehension.)

We now turn to proving the uniqueness of the union. Suppose U and V are both unions of the same collection C. That is, x ∈ U ⇔ ∃A ∈ C (x ∈ A) and x ∈ V ⇔ ∃A ∈ C (x ∈ A).The right-hand sides are identical, so ∀x (x ∈ U ⇔ x ∈ V).By the Axiom of Extensionality, U = V.Therefore the union is unique. QED

Theorem 14.32 Power Set Theorem: For any set A, the power set 𝒫(A)—the set of all subsets of A—exists.

Proof of Theorem 14.32: We begin by proving existence. We need to show that the collection of all subsets of A actually forms a set. This will be a standard modern proof using the Axiom Schema of Replacement + Separation. Then, by the Axiom of Replacement (or Subsets Axiom Schema in some presentations), the class { x | x ⊆ A } is itself a set. Intuitively we realize that every subset of A is obtained by “deciding” for each element of A whether it belongs or not. Replacement guarantees the result is a set. More formally: consider the definable function on the set of all functions from A to {0,1} (the set of choice functions exists by other axioms). Map each such function f: A → {0,1} to the subset { a ∈ A | f(a) = 1 }. Replacement says the image of this function is a set, and that image is exactly the collection of all subsets of A. Call this set P(A). Then, by construction, X ∈ P(A) ⇔ X ⊆ A. Thus the power set exists.

We now turn to uniqueness. Suppose P and Q are both power sets of A. That is, X ∈ P ⇔ X ⊆ A and X ∈ Q ⇔ X ⊆ A. These are identical, so (∀X) (X ∈ P ⇔ X ∈ Q). By the Axiom of Extensionality, P = Q.Therefore the power set is unique. QED

Theorem 14.33 Subset Theorem / Separation Theorem: For any set A and any definite property φ(x), the subset { x ∈ A | φ(x) } exists as a set.

Proof of Theorem 14.33: We prove the existence and uniqueness of B using the Axiom Schema of Replacement, the Axiom of Union, and the Axiom of Extensionality.

We begin with existence. Start with the set A. Define a mapping that picks out the elements we want, for each x ∈ A,  if f(x) holds, replace x with the singleton {x} (which exists by the Singleton Theorem), if f(x) does not hold, replace x with the empty set Ø (which exists by the Empty Set Theorem). By the Axiom Schema of Replacement, the collection of all these replacements forms a set, say C = { replacement of x | x ∈ A }. (Replacement guarantees that the image under this definable rule is a set.) Now apply the Axiom of Union to C, let B = ∪ C.By the definition of union, y ∈ B ⇔ there exists some singleton or Ø in C such that y belongs to it.  The empty sets contribute nothing.  The singletons {x} contribute exactly x, and only when f(x) held. Therefore B = { x ∈ A | φ(x) }.

We now turn to uniqueness, Suppose D is another set such that D = { x ∈ A | φ(x) }.  Then ∀y (y ∈ B ⇔ φ(y) ∧ y ∈ A) ⇔ (y ∈ D). By the Axiom of Extensionality, B = D.

The Subset Theorem holds for any A and property f, the separated subset exists and is unique. QED

Theorem 14.34 Foundation / No Infinite Descent Theorem: There is no infinite descending ∈-chain … .  No set is an element of itself (x ∉ x).

Proof of Theorem 14.34: Suppose, for contradiction, there is such an infinite descending chain, , (where ∋ means “contains as an element”). Let S be the set {} (this exists by the Axiom of Infinity and Replacement, since we can enumerate the chain). S is nonempty (it has , at least). By the Axiom of Foundation, there exists some y ∈ S such that y ∩ S = Ø.
That means no element of y belongs to S. But y must be one of the in the chain. Let’s say . By the chain, , and (by the definition of S). So , which means y ∩ S ≠ Ø—this leads to a contradiction. Therefore no such infinite descending chain can exist.

We no explore the converse, no infinite descent implies the axiom of foundation. Suppose every descending membership chain is finite (no infinite descent). Assume, for contradiction, there is a nonempty set A with no “foundational” element—every x ∈ A has some common member with A (x ∩ A ≠ Ø).Start with any (thus A is nonempty). Since , pick .
Since , pick . And so on forever. This produces an infinite descending chain —this leads to a contradiction that violates the no infinite descent assumption. Therefore every nonempty set must have a foundational element.

We conclude that The Axiom of Foundation is exactly equivalent to the statement “there are no infinite descending membership chains.” With this axiom, the universe of sets is “well-founded”—every set has a clear hierarchy down to the empty set, with no bottomless pits. QED.

Theorem 14.35 Cartesian Product Theorem: For any two sets A and B, the Cartesian product A × B exists as a set.

Proof of Theorem 14.35: We prove existence and uniqueness separately. We begin with existence. We must build the set of all ordered pairs. We use the standard Kuratowski definition of ordered pair (x, y) ≔ {{x}, {x, y}}.This is a pure set built only from x and y using pairing and singleton, and it satisfies the crucial property {{x}, {x, y}} = {{u}, {u, v}} ⇔ x = u ∧ y = v. We now proceed in clean steps

For any fixed a ∈ A, the singleton {a} exists by the Singleton Theorem.

For any b ∈ B, the unordered pair {a, b} exists by the Unordered Pair Theorem.

Therefore the set {{a}, {a, b}} = (a, b) exists (again just pairing).  

For fixed a ∈ A, consider the collection of all such pairs with first component a, { (a, b) | b ∈ B } = { {{a}, {a, b}} | b ∈ B }.This collection is a set by the Axiom Schema of Replacement applied to B (replace each b with the set {{a}, {a, b}}).Call this set a × B (this can be seen as a row of pairs corresponding to a). Now collect all the rows of pairs A × B ≔ ∪ { a × B | a ∈ A }.The set { a × B | a ∈ A } exists by Replacement applied to A. Its union exists by the Union Theorem. Therefore A × B exists as a set.

We now turn to uniqueness. Suppose C and D both satisfy (z ∈ C ⇔ z is an ordered pair (x, y) with x ∈ A, y ∈ B) and the same for D. Then C and D contain exactly the same elements, so C = D
by the Axiom of Extensionality.

So, for any sets A ∧ B, there exists exactly one set A × B = { (x, y) | x ∈ A, y ∈ B }. QED.

Exercise 14.12: Begin with Definition 14.36 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition, axiom, theorem, and proof.

Exercise 14.13:
a) Prove that if two sets A and B have exactly the same elements, then A = B.
b) Using only the Axiom of Extensionality and the Axiom of Infinity (or Pairing + Separation), prove that there exists a set with no elements (i.e., ∃Ø).
c) Let A and B be arbitrary sets. Using the Pairing Axiom, prove that there exists a set whose elements are exactly A and B (i.e., {A, B} exists).
d) Let φ(x) be any formula with free variable x. Using the Axiom of Separation (Comprehension), prove that for any set A, the subset { x ∈ A | φ(x) } exists in ZFC.
e) Prove that for any set (a “family” or “set of sets”), the set exists using only the axioms already introduced (especially Union).

State Space and Dynamics

The deepest idea in physics is this, “Every physical system, at any instant, is completely described by a single element in some huge set.” That set is called the state space (usually written Ω or S). Everything the system can ever be, every possible situation it can ever find itself in, is an element of Ω. Note that we are using the word space as an arena for the mathematical establishment of rules.

Two situations that differ in any physically measurable way are two different elements. Two situations that are absolutely indistinguishable are the same element.

The laws of physics are nothing more than rules telling you how that point moves inside the state space Ω as time passes.

But what is a state? A state is the list of everything you need to know about a system to study it in relation to the problem you are considering.

So, when studying the motion of a particle in three space we need to know its position in each of the three dimension, and also it corresponding velocities.

To know everything about a single particle, you need its exact position and its exact velocity at this instant. So the state space is the set of all possible (position, velocity) pairs

(14.48)

Note that this is a six-dimensional space.

For N particles you just take six coordinates per particle,

(14.49)

this turns out to be a huge-dimensioned Euclidean space, but not infinite.

So, did you get all of that? Let’s stake a step back. Imagine an abstract system that has only one state. We could think of it as a coin glued to the table—forever showing heads.  Here the state-space consists of a single element—namely Heads (or just H)—because the system has only one state. Predicting the future of this system is extremely simple: Nothing ever happens and the outcome of any observation is always H.

The next simplest system has a state-space consisting of two points; in this case we have one abstract object and two possible states. Imagine a coin that can be either Heads or Tails (H or T).

In classical mechanics, we assume that systems evolve smoothly—without any jumps or interruptions. Such behavior is said to be continuous. Obviously you cannot move between Heads and Tails smoothly. Moving, in this case, necessarily occurs in discrete jumps. So let’s assume that time comes in discrete steps labeled by natural numbers. A world whose evolution is discrete could be called stroboscopic.

A system that changes with respect to some variable is called a dynamical system.  All dynamical systems have a variable that the system changes with respect to, we can call this the evolutionary variable. Time is usually the evolutionary variable, but it need not be. A dynamical system consists of more than a space of states. It also entails a law of evolution, or we could call it a dynamical law. The dynamical law is a rule that tells us the next state given the current state.

One very simple dynamical law is that whatever the state at some instant, the next state is the same. In the case of our example, it has two possible histories: H H H H H H . . . and T T T T T T . . . . The first law specified that the arrow from H goes to H and the arrow from T goes to T. Once again it is easy to predict the future: If you start with H, the system stays H; if you start with T, the system stays T.

Another possible dynamical law dictates that whatever the current state, the next state is the opposite. You can still predict the future. For example, if you start with H the history will be H T H T H T H T H T . . . .  If you start with T the history is T H T H T H T H . . . .

We can even write these dynamical laws in mathematical form. The number of variables describing a system are called its degrees of freedom. Our coin has one degree of freedom, which we can denote by the Greek letter sigma, σ. Sigma has only two possible values; σ=1 and σ=-1, respectively, for H and T. We also use a symbol to keep track of the time. When we are considering a continuous evolution in time, we can symbolize it with t. Here we have a discrete evolution and will use n. The state at time n is described by the symbol σ(n), which stands for σ at n.

Let’s write equations of evolution for the two laws. The first law says that no change takes place. In equation form we write,

(14.50)

In other words, whatever the value of σ at the nth step, it will have the same value at the next step.

The second equation of evolution has the form

(14.51)

implying that the state flips during each successive step.

In each case the future behavior is completely determined by the initial state, such laws are called deterministic. We can now assert, without proof, that all of the basic laws of classical physics are deterministic.

To make things more interesting, let’s generalize the system by increasing the number of states. Instead of a coin, we could use a six-sided die, where we have six possible states.

Now there are a great many possible laws, and they are not so easy to describe in words—or even in equations. One law says that given the numerical state of the die at time n, we increase the state one unit at the next instant n+1. That works fine until we get to 6, at which point the diagram tells you to go back to 1 and repeat the pattern. Such a pattern that is repeated endlessly is called a cycle. For example, if we start with 3 then the history is 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, . . . . We’ll call this pattern Dynamical Law 1.

How do we write a mathematical expression for this?

(14.52)

seems like a good attempt. But wait a minute? What happens when n=6? We need to impose some rule that brings us back to 1, when n>6. We can wrap the right-hand side of the expression in a modulo operation, denoted .

(14.53)

The modulo operation tells us that once the evolution variable exceeds 6 it return back to 1. So the evolution is exactly what we want.

Dynamical Law 2 looks a little messier than the last case, but it’s logically identical—in each case the system endlessly cycles through the six possibilities. If we relabel the states, Dynamical Law 2 becomes identical to Dynamical Law 1.

Exercise 14.14: Relabel the diagram of Dynamical Law 2 so that it looks the same as Dynamical Law 1. To make this formally true write down the rules that transform the given states into the new states to make the diagram the same, what we call isomorphic. Such rules are examples of transformations.

Not all laws are logically the same. Consider Dynamical Law 3 where there are two cycles. If you start on one of them, you can’t get to the other. Nevertheless, this law is completely deterministic. Wherever you start, the future is determined. For example, if you start at 2, the history will be 2, 6, 1, 2, 6, 1, . . .,  and you will never get to 5. If you start at 5 the history is 5, 3, 4, 5, 3, 4, . . .,  and you will never get to 6.

Dynamical Law 4 has three cycles.

It would take a long time to write out all of the possible dynamical laws for a six-state system.

Terms

Undefined Terms

Term 14.5 System: The physical object or set of objects being studied.

Term 14.6 State of a System: A state is a complete description of a system at a given instant, containing all information necessary to predict the future evolution uniquely.

Term 14.7 Time: A variable representing the ordering of events in a system.

Definitions

Definition 14.37 State Space for Finite Systems: For a system with finitely many possible distinct situations, the state space Ω is a finite set whose elements are exactly the possible states.

Definition 14.38 Dynamical Law / Evolution Rule: A dynamical law is a function f : Ω → Ω that assigns to each current state σ(t) the unique next state σ(t+1) = f(σ(t)).

Definition 14.39 Deterministic System: A system is deterministic if its dynamical law is a well-defined function (exactly one next state for each current state, see the section on functions below).

Definition 14.40 Trajectory / Orbit: Given an initial state , the trajectory is the sequence also written σ(n+1) = f(σ(n)).

Definition 14.41 Cycle: A sequence of distinct states is a cycle of length k. A fixed point σ = f(σ) is a cycle of length 1.

Definition 14.42 Degrees of Freedom: The number of independent values needed to specify a state. For a finite-state system with C(Ω) = N, the number of degrees of freedom is  N (where we are counting states).

Definition 14.43 Evolution Variable: A discrete time label n ∈ Z (or n ∈ N) that numbers the successive states.

Axioms

Axiom 14.13 Finite State Space: The system has only finitely many mutually distinguishable state variables.

Axiom 14.14 Determinism: There exists a definite rule that, given any state at step n, uniquely determines the state at step n+1.

Axiom 14.15 Time-Translation Invariance: The dynamical law does not change with time: f is the same function at every step.

Theorems

Theorem 14.36 Uniqueness of Trajectories: Let the dynamical law be a function f: S → S, where S is the state space (any set, finite or infinite, but we will only need that S is a set).  Assume the system is deterministic in the strong sense, so for each current state x ∈ S there is exactly one next state f(x). Then, for any two trajectories that start from the same initial state remain identical forever. In other words, if σ and τ are two trajectories (sequences of states) satisfying and σ(n+1) = f(σ(n)),   τ(n+1) = f(τ(n))  for all integers n ≥ 0, then σ(n) = τ(n) for every n ≥ 0.

Proof of Theorem 14.36: Here we perform a proof by mathematical induction (on the discrete time step n). We prove the statement P(n) implies σ(n) = τ(n) for all trajectories starting at the same . The base case (n = 0) is by assumption , so P(0) is true. We now turn to the inductive step where we assume P(k) is true for some fixed k ≥ 0. That is, σ(k) = τ(k). Apply the dynamical law f (this is a genuine function, so it gives the same output for the same input), σ(k+1) = f(σ(k)) = f(τ(k)) = τ(k+1). Thus P(k+1) is true. So, by mathematical induction, P(n) holds for all whole numbers n ≥ 0. Therefore σ(n) = τ(n) for every time step n. The trajectories are identical. QED.

Theorem 14.37 Eventual Periodicity: Let S be a finite set and let f: S → S be any function (deterministic dynamical law on a finite state space).Then every trajectory is eventually periodic. In other words starting from any initial state , the sequence eventually repeats with some period p ≥ 1.

Proof of Theorem 14.37: We execute a mixed proof by contradiction and induction . We fix an arbitrary starting state . Consider the sequence defined by We will prove that this sequence must repeat some state. Assume, for the sake of contradiction, that all the terms are distinct are all different from one another. Define the sets     (the first n+1 states in the sequence). Because we assumed everything is distinct, C(Sₙ) = n + 1. Now consider the statement P(n)⇒C(Sₙ) = n + 1. We prove P(n) for all n by induction. We prove the base case (n = 0), where we have , so . So the base case is true. We now turn to the inductive step, assume P(k) holds, i.e. the first k+1 states are all distinct. The next state is. By the contradiction assumption, is different from . Therefore has one more element than , so . Thus P(k+1) holds.

By mathematical induction, P(n) is true for every whole number n. That means for every n we can find n+1 distinct states inside S. But S is a fixed finite set. Let N = C(S) be the total number of elements in S. Take n = N. Then P(N) says there are N+1 distinct states in the sequence, all belonging to S, so C(S) ≥ N+1. This contradicts the fact that S has only N elements. Therefore the assumption “all terms are distinct” is false. Hence there exist integers i < j such that . The sequence from position i onward then repeats forever with period p = j − i ≥ 1. The part before i (if any) is the transient. Thus the trajectory is eventually periodic. Since the starting state was arbitrary, this holds for every trajectory. QED.

Theorem 14.38 Decomposition into Transient + Cycle: Let S be a finite set and f: S → S any function. Then, for every starting state , the trajectory decomposes uniquely as  transient (possibly empty) → cycle  That is, there exist whole numbers t ≥ 0   (representing the length of the transient, possibly 0) and p ≥ 1 (representing the length of the cycle) such that:, the states are all distinct and none of them ever reappears later  and are also all distinct. Then   . The sequence repeats the block of p states forever, for all k ≥ 0. Moreover, this decomposition is unique: t and p are completely determined by the trajectory.

Proof of Theorem 14.38: Our proof uses only the previous eventual periodicity result and finiteness. We already proved that every trajectory is eventually periodic. So there exist whole numbers m ≥ 0 and p ≥ 1 such that and the sequence repeats every p steps from position m onward. Now, lLet . From step m onward the trajectory is Because the whole trajectory is eventually periodic with period p starting at m, the cycle is exactly the set . All p states in C are distinct (otherwise the period would be smaller). Now define the transient length t as the smallest whole number such that . Such a t exists because the trajectory eventually enters the repeating part (at latest at step m). We claim that the states are all distinct and none belongs to C.  Then is the first state that lies on the cycle C.

We now prove that claim, suppose two states in the transient were equal, say with 0 ≤ i < j < t. Then the trajectory would already be periodic with period j−i before reaching the cycle—but then the eventual period would start earlier, contradicting the definition of t as the first hitting time of C. Now suppose some belonged to C. Then the trajectory would have entered C at step k < t, again contradicting the minimality of t. Therefore the transient really is a chain of distinct states leading into the cycle, and it never loops back or re-enters the cycle early. Finally, the uniqueness of t and p where t is uniquely determined as the first time the trajectory hits the eventual cycle.  So, p is uniquely determined as the minimal positive period of the tail (or equivalently the number of distinct states in the cycle).

Corollary 14.1: Let S be a finite set and f: S → S any function. Then the entire dynamics decomposes to the state space S is the disjoint union of

One or more cycles

Transient chains (possibly of length 0) that feed into those cycles.

From every state x ∈ S, after finitely many steps you reach a cycle, and once on a cycle you stay there forever.

In short every trajectory consists of a transient followed by a cycle, and there are no other possibilities.

Proof of Corollary 14.1: Take any state x ∈ S (it does not matter which one). Consider its trajectory By the Eventual Periodicity Theorem this trajectory is eventually periodic. That is, there exist t ≥ 0 and p ≥ 1 such that . Let . Then from y onward the trajectory is purely periodic with period p, So y lies on a cycle of length p. Therefore, starting from x, after exactly t steps we reach the cycle, and we stay on it forever. Since x was arbitrary, this holds for every state in S. The transient part (the first t states, if t > 0) never returns, and the cycle part repeats forever. Moreover, different cycles are disjoint (because if two cycles shared a state, the trajectories would merge and become the same cycle). Thus the whole finite set S breaks cleanly into disjoint cycles, plus transient states that flow irreversibly into one of the cycles.

There are no exceptions, no wandering states, no chaos — everything eventually settles into perfect repetition. QED.

Theorem 14.39 Existence of Fixed Points or Cycles: Let S be a finite non-empty set and f: S → S any function. Then the dynamics necessarily contains at least one cycle (and this may have length 1, i.e., a fixed point, or length p ≥ 2). In particular, there exists at least one state x ∈ S such that for some whole number p ≥ 1. In everyday language we write every finite deterministic system has at least one periodic orbit (either a state that stays forever the same, or a loop that repeats forever).

Proof of Theorem 14.39: We already proved that every trajectory is eventually periodic. Now pick any state—for example, pick an arbitrary state z ∈ S (S is non-empty, so this is possible). Follow its trajectory, By the earlier theorem, this trajectory eventually enters a cycle. That cycle is a periodic orbit contained in S. Therefore at least one cycle exists. QED.

Exercise 14.15: Begin with Term 14.5 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, axiom, theorem, and proof.

Exercise 14.16:
a) A toy robot can be either Awake (A) or Asleep (S). Every minute it follows this rule:  If it is Awake, it falls Asleep in the next minute.  If it is Asleep, it wakes up (becomes Awake) in the next minute.
    Draw the state-transition diagram (two circles, arrows).  
    Write the dynamical law in words and in mathematical form using σ(n) = A or S.  
    Starting from Awake, write the history for the first 6 steps.  
    Write the law using numbers (let A = 0, S = 1) and the modulo operation so it works for any n.
b) A traffic light for pedestrians cycles through four colors in this exact order and then repeats:Green → Yellow → Red → Blinking-Red → Green → …Label the states 1 = Green, 2 = Yellow, 3 = Red, 4 = Blinking Red
    Draw the state-transition diagram.  
    Write the dynamical law using the style of Dynamical Law 1 in your notes (σ(n+1) = σ(n) + 1 with wrap-around).  
    Starting from Red (state 3), what state is it after 23 minutes?  
    Write the same law using the modulo operator (you may use mod 4, remembering that many languages count 0–3 instead of 1–4—both are acceptable if you are consistent).
c) Relabel the diagram of Dynamical Law 2 so that it looks the same as Dynamical Law 1. To make this formally true write down the rules that transform the given states into the new states to make the diagram the same, what we call isomorphic. Such rules are examples of transformations.
d) Can you think of a general way to classify the laws that are possible for a six-state system?
e) A beetle walks on the vertices of a regular hexagon labeled 1,2,3,4,5,6 clockwise.
At every step it always moves two vertices clockwise.Examples: 1 → 3, 3 → 5, 5 → 1, 2 → 4, etc.Draw the diagram. You will discover there are actually three separate cycles. What are they?  Write the dynamical law with the simplest arithmetic expression + modulo that works for all starting positions.  Starting from position 6, write the sequence until it loops. How many steps until it returns to 6?  Is this system ergodic (can you reach any state from any other state)? Explain in one sentence.
f) Consider again six states arranged in a circle: 1-2-3-4-5-6. This time the rule is: From an odd-numbered state go to the next even (1→2, 3→4, 5→6) From an even-numbered state go to the next odd two steps ahead (2→5, 4→1, 6→3)
    Draw the complete transition diagram (you should obtain exactly two disjoint cycles of length 3).  
    Try to write a single formula of the type σ(n+1) = something with modulo that works for all six states (most people find it impossible with one formula).  
    Now write two separate formulas: one that applies when σ(n) is odd, one when it is even (this is allowed and is exactly what the book does in more complex cases).  
    Choose a starting state (e.g., 1) and list the history. After how many steps are you guaranteed to return to the starting state no matter where you began?

Power Sets

With the idea of a set now firmly established, we meet one of the most astonishing constructions in all of mathematics: the power set. As we saw in ZFC axioms the power set of a set A, written P(A) or , is the set whose elements are all possible subsets of A—including the empty set and A itself.

If A has n elements, then P(A) has exactly elements. This explosive growth—from n objects to subsets—is why the power set is often denoted where each element of A can either be “in” or “out” of a subset, giving two choices per element.

For example, If A = Ø, then P(Ø) = { Ø } has one element.  To be clear, the cardinal number of Ø is 0, but its power set has cardinal number 1. If A = {a}, then P(A) = { Ø, {a} } has two elements.  If A = {a, b}, then P(A) = { Ø, {a}, {b}, {a,b} } has four elements.  If A = {1, 2, 3}, then P(A) has elements.

The pattern is unbreakable for any finite set A.

Every property, every condition, every question we can ask about elements of A corresponds to a subset of A.  “All even numbers” → subset of integers, “All points inside the circle” → subset of the plane, “All allowed energies” → subset of possible energy values.

The power set is therefore the set of all possible properties that elements of A can satisfy.

Think of the plane as the universal set U. The power set P(U) contains every possible region you could ever draw—every point, every line segment, every triangle, every disk, every imaginable shape—because every shape is just a subset of points.

The power set shows that “all possible collections” is vastly larger than the original set. Even a tiny set of 10 elements has a power set with 1024 members; a set of 100 elements has a power set larger than the number of atoms in the observable universe.

In physics, the power set of the state space contains every conceivable physical situation—the ultimate catalogue of everything that could ever happen.

The power set is the mathematical embodiment of the idea that from simplicity explodes into a vast number of outcomes.

Definitions

Definition 14.44 Power Set of the Set A (: The set whose elements are all possible subsets of A. That is, P(A)={B∣B⊆A}.

Theorems

Theorem 14.40: Ø ∈ P(A) and A ∈ P(A) for any A.  

Proof of Theorem 14.40: We know that the empty set is always a subset of any set. Naively, A is always a subset of itself. To show that A ⊆ A, we must verify that every element of A is an element of A. This is obviously true (if x ∈ A, then x ∈ A). Therefore A ⊆ A. Again, by definition of the power set, A ∈ P(A). We conclude that for every set A (empty or not, finite or infinite), Ø ∈ P(A) and A ∈ P(A). These are the two “trivial” subsets that are present no matter what A is. QED

Theorem 14.41: If A ⊆ B, then P(A) ⊆ P(B). (Every subset of A is automatically a subset of the larger set B.)

Proof of Theorem 14.41: We will prove this by element chasing. To prove P(A)⊆P(B), take an arbitrary element X such that X∈P(A). By the definition of the power set, this means
X⊆A. We must now show that X∈P(B), i.e., that X⊆B. Let x be an arbitrary element of X. Since X⊆A, it follows that x∈A. But we are given that A⊆B, so x∈A implies x∈B. Therefore every element x of X belongs to B, which means X⊆B. Since X was an arbitrary element of P(A), every element of P(A) is also an element of P(B).  Hence P(A)⊆P(B). QED

Theorem 14.42: P(A ∪ B) ⊇ P(A) ∪ P(B) and P(A ∩ B) = P(A) ∩ P(B).

Proof of Theorem 14.42: We will prove this by element chasing for each of the two parts. We will only do this is one direction for P(A∪B)⊇P(A)∪P(B). To show this, take an arbitrary element X such that X⊆P(A)∪P(B). By the definition of a union, this means either X⊆P(A) or X⊆P(B). This gives us two cases to examine. We begin with the case, X⊆P(A). Then, by the definition of a power set we can infer that, X⊆A. Since A⊆A ∪B, it follows that X⊆A ∪B. Therefore X⊆P(A ∪B).

We now turn to the second case, X⊆P(B). Then X⊆B. Since B⊆A ∪B, it follows that X⊆A ∪B. Therefore X⊆P(A ∪B).

In both cases, X⊆P(A ∪B).  Since X was arbitrary, P(A)∪P(B)⊆P(A ∪B).

It is important to note that in general the inverse inclusion P(A∪B)⊆P(A)∪P(B)  is false in general. A simple counterexample is A={1}, B={2}. Then {1,2}⊆P(A∪B), but {1,2}∉P(A)∪P(B).)

We now turn to the second part, P(A ∩ B) = P(A) ∩ P(B), we will use element-chasing again, but in both directions. We must show two inclusions.

We begin with P(A∩B)⊆P(A)∩(B). Let X be an arbitrary element such that X⊆P(A∩B). Once again, by the definition of a power set, X⊆A∩B, this implies X⊆A. Therefore X⊆P(A) and X⊆P(B), so X∈P(A)∩P(B).

We now turn to P(A)∩P(B)⊆P(A∩B). Since X⊆P(A) and X⊆P(B), then X⊆A and X⊆B.  By the definition of an intersection, if a set is a subset of both A and B, then it is a subset of A∩B.

Thus X⊆A∩B, which means X⊆P(A∩B).

Since both inclusions hold, P(A∩B)=P(A)∩P(B).
QED

Theorem 14.43 Cantor’s Theorem: The power set operation is not reversible: there is no set B such that P(B) = A in general.

Proof of Theorem 14.43: We will prove this theorem by contradiction. Suppose, for the sake of contradiction, that there does exist some set B such that P(B)=A. This means every element of A is a subset of B. In particular, there is a way to associate to each element a∈A  a unique subset f(a)⊆B such that every possible subset of B appears exactly once as f(a) for some a∈A. (That is, the elements of A “label” all the subsets of B.)

Now construct a special subset D⊆B defined as, D={x∈B∣x∉f(x)}. This D is clearly a well-defined subset of B, so D must be a subset within P(B).

Since P(B)=A, there must exist some element b∈A such that f(b)=D.

We now ask the question, “Does b belong to D?” Suppose b∈D. By the definition of D, this means b∉f(b). But f(b)=D, so b∉D. This is a contradiction.

Now suppose b∉D. By the definition of D, this means it is not the case that b∉f(b), i.e., b∈f(b). But f(b)=D, so b∈D. This is also a contradiction.

In both cases we reach a contradiction. Therefore our initial assumption must be false. Hence, there cannot exist any set B such that P(B)=A. QED

Exercise 14.17: Begin with Definition 14.44 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition, theorem, and proof.

Exercise 14.18:
a) Let A = {1, 2, 3, 4}.
    Write out all 16 elements of P(A) explicitly.
    Identify which of these subsets have exactly 0, 1, 2, 3, and 4 elements (you should find 1 + 4 + 6 + 4 + 1 = 16).
    Highlight the two subsets mentioned in Theorem 13.21 (Ø and A itself).
b) How many subsets does the set B = {a, b, c, d, e, f, g} have? Write the answer two ways: as a power of 2 and as a decimal number. How many subsets have even cardinality (even number of elements)? How many have odd cardinality? (Hint: there is always a 50-50 split for any non-empty finite set.) How many subsets contain the element “d” at least once?
c) Prove, using the “in or out” story (each element has 2 choices), that for any finite set A with n elements, . Do this in two ways:(a) by induction on n, (b) by a direct combinatorial argument (no induction).
(d) Let A = {1, 2}, B = {1, 2, 3, 4}, C = {2, 3}.Verify Theorem 13.22: since A ⊆ B and C ⊆ B, show P(A) ⊆ P(B) and P(C) ⊆ P(B) by writing out all subsets. Compute P(A ∪ C) and P(A) ∪ P(C). Does equality hold, or only ⊇ as stated in Theorem 13.23? Compute P(A ∩ C) and P(A) ∩ P(C). Why must equality always hold here?
(e) Answer with clear justification (one or two sentences each):
    1. Everyone accepts that Ø ∈ P(Ø) is false, but P(Ø) = {Ø} has one element. Is the empty set an element of itself? Explain the difference between Ø ∈Ø (false) and Ø ∈ P(Ø) (true).
    2. Theorem 13.24 says the power set operation is not invertible in general. Give a concrete example of a set C that is NOT the power set of any set.
    3. Let B be a 3-element set, say B = {a, b, c}.  How many elements does P(B) have? How many elements does P(P(B)) have?  How many elements does P(P(P(U))) have? Write the             numbers and then comment: if the universe had only 3 objects, how many possible “collections of collections of collections” are there?
    4. In physics or computer science, the state space of a single classical bit is {0,1}. What is the size of the power set of the state space? What does each element of this power set represent         physically or information-theoretically?

Relations

We often need to describe how objects are connected to one another, one line can be parallel to another, one person can be the parent of another, one physical object can exert a force on another, or one number can be smaller than another.

Any systematic way of pairing elements of one set with elements of another (or with elements of the same set) is called a relation.

More precisely, if we have two sets A and B, a relation from A to B is simply a collection of ordered pairs (a, b) with a ∈ A and b ∈ B.

We usually denote the generic relation by a letter such as R and write a R b (pronounced “a is related to b”) whenever the pair (a, b) belongs to the relation.

The set of all possible ordered pairs, A × B, is called the Cartesian product that we saw earlier this lesson, so formally a relation R from A to B is a subset of A × B.

When the relation connects elements of the same set (A to A), we simply say it is a relation on A.

Examples are everywhere:  two lines in the plane are related if they are parallel, one person is related to another if the first is the parent of the second, one object is related to another if the first exerts a force on the second, one line segment is related to another if it is longer, and so on.

Terms

Term 14.8 Relation: The idea that there is a connection between two objects.

Definitions

Definition 14.45 Relation: A relation R from a set A to a set B is any subset of the Cartesian product A × B. If (a, b) ∈ R, we write a R b (“a is related to b”).

Definition 14.46  Relation on a Set: If A = B, we say R is a relation on A (a subset of A × A).

Definition 14.47  Domain Relation: The set of all first elements that actually appear in the pairs of R. For a relation R ⊆ A × B:  Domain of R = dom(R) = { a ∈ A | ∃b ∈ B such that a R b }.

Definition 14.48 Range (or image): The set of all second elements that appear in a relation. ran(R)={b∈B∣∃ a∈A such that a R b}.

Definition 14.49 Inverse Relation: The inverse of a relation R ⊆ A × B is . We write if and only if a R b.

Definition 14.50 Composition of Relations: If R ⊆ A × B and S ⊆ B × C, the composition S ◦ R is S ◦ R = { (a, c) | ∃b ∈ B such that (a, b) ∈ R and (b, c) ∈ S }.

Definition 14.51 Identity Relation: The identity relation on a set A is .

Theorems

Theorem 14.44 Relations Are Sets: Every relation from A to B is a set (namely, a subset of A × B, which exists by the Power Set axiom).

Proof of Theorem 14.44: We will develop a direct proof of this theorem. By definition (as you introduced in the Relations section), a relation R from A to B is any collection of ordered pairs (a, b) where a ∈ A and b ∈ B. In other words, R is intended to be a subset of the set of all possible such ordered pairs, which is the Cartesian product A×B. To show that such an R is actually a set in ZFC, we must first establish that the Cartesian product A×B itself exists as a set. Once that is done, any relation R is simply a subset of this set, and subsets exist by the Axiom Schema of Specification.

Step 1: Existence of the Cartesian Product A×B.

We construct A×B explicitly using the following axioms: Axiom of Union: The set A∪B exists. The Power Set Axiom (we will apply this twice): The power set P(A∪B) exists. Then the power set P(P(A∪B)) also exists. And The Ordered Pair Definition: The ordered pair (a, b) is defined as the set  (a,b)={{a},{a,b}}. Since a, b ∈ A ∪ B:  {a} ⊆ A ∪ B, so {a} ⊆ P(A∪B).  {a, b} ⊆ A ∪ B, so {a, b} ∈ P(A∪B).  Therefore {{a}, {a, b}} ⊆ P(A∪B), so (a, b) ∈ P(P(A∪B)).

Axiom Schema of Specification (Comprehension): We can now “carve out” exactly the desired pairs from the big set P(P(A∪B)):  A×B:={z∈P(P(A∪B))∣∃a∈A ∃b∈B (z=(a,b))}. This is a legitimate set because it is defined by restricting a known set (P(P(A∪B))) using a clear property.

Thus, A×B exists as a set, and it consists exactly of all ordered pairs (a, b) with a ∈ A and b ∈ B.

Step 2: Every Relation R from A to B Is a Subset of A×B.

By Definition 14.45 we know the a relation R from A to B is any collection of ordered pairs (a, b) with a ∈ A and b ∈ B. This is precisely the definition of a subset of A×B: R⊆A×B.

Step 3: Subsets Exist (via Specification)

By the Axiom Schema of Specification, for any set X (here, take X = A×B) and any definable property φ, the collection {z∈X∣φ(z)} is itself a set.Therefore, any relation R ⊆ A×B  (i.e., any sub-collection of the ordered pairs that satisfies whatever condition defines the relation) is a legitimate set.

Conclusion: Every relation from A to B is a set — specifically, it is a subset of the Cartesian product A×B, whose existence follows from the Power Set Axiom (applied twice), Union, Pairing (for ordered pairs), and Specification. QED

Theorem 14.45 Inverse of Inverse: .

Proof of Theorem 14.45: We will prove this by element chasing with double inclusions. We show both inclusions.

Part 1: Show .

Let (x, y) be an arbitrary ordered pair such that . By the definition of the inverse relation, .

Again by the definition of the inverse, means (x, y) ∈ R. Therefore (x,y)∈R.

Since (x, y) was arbitrary, .

Part 2: Show .

Let (x,y) be an arbitrary ordered pair such that (x,y)=R.

By the definition of the inverse relation, (x,y)∈R⇒(y,x)∈R−1.

Applying the definition of the inverse once more, .

Therefore .

Since (x, y) was arbitrary, .

Since both inclusions hold, we conclude . QED

Exercise 14.19: Begin with Term 14.8 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, theorem, and proof.

Properties of Relations

When we look at any relation—whether it’s “is taller than,” “is parallel to,” “is a parent of,” or “has the same color as”—certain patterns keep showing up. These patterns are so useful that we have given them special names.

Does every object “relate to itself”? Think of “is at least as tall as” among people; everyone is exactly as tall as himself or herself. Or “has the same birthday as” where you have the same birthday as yourself. When this is true for every element, we say the relation is reflexive. Formally, we write,

(14.54)

If a is related to b, must b automatically be related back to a? If line is parallel to , then obviously is parallel to . If person X is married to person Y, then Y is married to X. If two numbers have the same remainder when divided by 5, then each has the same remainder as the other. When reversing the arrow always works, the relation is symmetric. Formally we write,

(14.55)

Can we have arrows both ways only when the two objects are actually the same? Consider “is less than or equal to” on numbers, for example, if m ≤ n and n ≤ m, then m = n. Or “is a subset of” among sets, for example, if A ⊆ B and B ⊆ A, then A = B. A relation with this property is called antisymmetric. Formally, we write,

(14.56)

An even stronger version exists where not only is “both directions → same object,” but in fact there are never arrows both ways at all (even for the same object). That stronger property is called asymmetry (example: strict “less than” < on numbers). Formally we write,

(14.57)

Does the relation “chain” nicely? If Anna is a parent of Bob, and Bob is a parent of Clara, then Anna is a grandparent (hence an ancestor) of Clara. If 3 < 7 and 7 < 10, then 3 < 10. If event A can cause event B and event B can cause event C, then A can lead to C. Whenever a R b and b R c forces a R c, the relation is transitive. Formally we write,

(14.58)

When a relation is reflexive + symmetric + transitive, it combines the set into nice, non-overlapping clubs where everything inside a club is “equivalent” in some way. examples are “has the same color as,” “is congruent to (same shape and size).” Such a relation is called an equivalence relation.

When a relation is reflexive + antisymmetric + transitive, it lets us compare and order elements in a consistent way, like ranking or hierarchy. Examples are  ≤ on numbers, ⊆ on sets, “divides” on positive integers, “must be completed before” on project tasks. This is called a partial order (or sometimes just a partial ordering).

If every pair of elements can be compared one way or the other, we upgrade the name to total order (like ≤ on real numbers).

Sometimes the direction of a relation matters, and sometimes we want to flip it. Imagine you have a relation that says “is the parent of”: an arrow goes from a person to each of their children. If you reverse every arrow, you suddenly get the relation “is a child of”. If the original relation was “is taller than”, reversing the arrows gives “is shorter than”. If the original was “exerts a force on”, reversing it still gives “exerts a force on”, because forces always come in equal-and-opposite pairs (the relation is its own reverse).

Reversing the arrows is such a common and useful operation that it has a name. Given any binary relation R from set A to set B, the relation that contains exactly the opposite arrows is called the inverse relation and is written (read “R inverse”).

Formally: the inverse of R is the relation from B to A defined by

(14.59)

In ordered-pair language this is simply

(14.60)

Notice that the inverse swaps the roles of the two sets: if R goes from A to B, then goes from B to A.

A relation that is equal to its own inverse () is precisely the symmetric relations we met earlier—the arrow picture has arrows both ways wherever there is a connection.

When one connection is followed by another, something new appears. If Alice is a parent of Bob, and Bob is a parent of Clara, then Alice is a grandparent of Clara. If train A goes from city X to city Y, and train B goes from city Y to city Z, then you can travel from X to Z by “composing” the two journeys. If particle 1 collides with particle 2, and a moment later particle 2 collides with particle 3, then momentum has effectively been passed from 1 to 3. In each case we are chaining two relations to create a third. This chaining operation is so fundamental that it has its own name.

Given two binary relations  R from set A to set B, and S from set B to set C, the relation obtained by “doing R first, then S” is called the composition of S with R, written S ◦ R (read “S after R” or “S composed with R”).

Formally. the composition S ◦ R is the relation from A to C defined by

(14.61)

In ordered-pair notation this becomes

(14.62)

Notice the order, we write S ◦ R even though we apply R first.

Terms

Term 14.9 Property of a relation: A characteristic pattern that a relation may or may not satisfy.

Definitions

Definition 14.52 Reflexive Relation: R is reflexive on A if ∀a ∈ A, a R a.

Definition 14.53 Irreflexive Relation: R is irreflexive if ∀a ∈ A, ¬(a R a).

Definition 14.54 Symmetric Relation: R is symmetric if ∀a,b ∈ A, a R b ⇒ b R a.

Definition 14.55 Antisymmetric Relation: R is antisymmetric if ∀a,b ∈ A, (a R b ∧ b R a) ⇒ a = b.

Definition 14.56 Asymmetric Relation: R is asymmetric if ∀a,b ∈ A, a R b ⇒ ¬(b R a). Note that asymmetry is stronger than antisymmetry and implies that R is irreflexive.

Definition 14.57 Transitive Relation: R is transitive if ∀a,b,c ∈ A, (a R b ∧ b R c) ⇒ a R c.

Definition 14.58 Equivalence Relation: Any relation that is reflexive, symmetric, and transitive. We will discuss this in detail below.

Definition 14.59 Partial Order: Any relation that is reflexive, antisymmetric, and transitive. We will discuss this in detail below.

Definition 14.60 Total (Linear) Order: Any partial order R such that ∀a,b ∈ A, a R b ∨ b R a. We will discuss this in detail below.

Definition 14.61 Strict Partial Order: Any relation that is irreflexive and transitive (often also asymmetric). We will discuss this in detail below.

Definition 14.62 Inverse Relation: Any relation that is irreflexive and transitive (often also asymmetric). We will discuss this in detail below. The relation obtained by reversing every arrow:  or, in ordered-pair notation  .

Definition 14.63 Composition of Relations (S◦R): Given a relation R from set A to set B, and a relation S from set B to set C, the composition of S with R, written S◦R, is the relation from A to C defined by a (S◦R) c if and only if ∃b∈B such that (a R b and b S c). In ordered-pair notation S◦R={(a,c) ∣ ∃b∈B ((a,b)∈R and (b,c)∈S)}.

Principles

Principle 14.13 Principle of Extensionality for Relations: Two relations are equal if and only if they contain exactly the same ordered pairs.

Principle 14.14 Principle of Arrow Reversal: For any relation R, the inverse is uniquely determined by reversing the direction of every pair.

Principle 14.15 Composition Principle: Relations can be chained by composition, corresponding to “doing one relation after another.”

Theorems

Theorem 14.46: A relation is symmetric if and only if .

Exercise 14.19: Prove Theorem 14.46

Theorem 14.47: If R and S are relations, then .

Proof of Theorem 14.47: We will prove this by the double-inclusion element chasing method.

Part 1: Show
Let (x, y) be an arbitrary ordered pair such that . By the definition of the inverse relation, this means (y,x)∈S◦R. By the definition of composition, there exists some b∈B such that
y (S◦R) x ⇒y S b ∧b R x. This is exactly b R x ∧ y S b. Rewriting this in terms of the inverses . Therefore, by the definition of composition, . So . Since (x, y) was arbitrary, .

Part 2: Show

Let (x, y) be an arbitrary ordered pair such that . By the definition of composition, there exists some b∈B  such that . This means b R x ∧y S b. Therefore, y S b ∧b R x, now this is exactly the condition for y (S◦R) x. By the definition of the inverse relation, . Since (x, y) was arbitrary, .

Because both inclusions hold, we conclude . QED

Theorem 14.48 Composition of relations is associative: (T ◦ S) ◦ R = T ◦ (S ◦ R).

Proof of Theorem 14.48: We will prove this using element chasing with double inclusion.

Part 1: Show (T◦S)◦R⊆T◦(S◦R)

Let (x, y) be an arbitrary ordered pair such that (x,y)∈(T◦S)◦R. By the definition of composition, this means there exists some z∈C such that x ((T◦S)◦R) y ⇒x (T◦S) z∧z R y. Now apply the definition of composition to x (T◦S) z and there exists some w∈B such that x R w∧w (T◦S) z. We now apply the definition again to w (T◦S) z: then there exists some v∈C such that w S v∧v T z. Putting it all together, we have: x R w, w S v, and  v T z. This means x (S◦R) v (because x R w and w S v) and v T z, so x (T◦(S◦R)) z. But z=y in our original pair (the final element is ( y )), therefore (x,y)∈T◦(S◦R). Since (x, y) was arbitrary, (T◦S)◦R⊆T◦(S◦R).

Part 2: Show T◦(S◦R)⊆(T◦S)◦R

Let (x, y) be an arbitrary ordered pair such that (x,y)∈T◦(S◦R). By definition of composition, there exists some z∈C such that x (S◦R) z∧z T y. Apply the definition of S◦R so there exists some w∈B such that x R w∧w S z. Now we have x R w, w S z, and z T y. This means x ((T◦S)◦R) y, because x R w and w (T◦S) z (since w S z and z T y). Therefore (x,y)∈(T◦S)◦R. Since (x, y) was arbitrary, T◦(S◦R)⊆(T◦S)◦R.

Because both inclusions hold, we conclude (T◦S)◦R=T◦(S◦R). QED

Exercise 14.20: Begin with Term 14.9 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, principle, theorem, and proof.

Exercise 14.21:
a) For each relation below, decide which of the following properties it has: reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive. (More than one can be true.)
    “is equal to” (=) on the set of real numbers,
    “is strictly less than” (<) on real numbers,
    “is a parent of” on the set of all people,
    “is the same height as” (within 1 cm) on people,
    “divides” (a divides b means b is a multiple of a) on positive integers,
    “is married to” on people (assume no one is married to themselves),
    “is at most 5 years older than” on people,
    “has the same number of elements as” on finite sets.
b) Write T (true) or F (false) and one short sentence why.
    Every symmetric relation is also reflexive.  
    Every asymmetric relation is also antisymmetric.  
    Every antisymmetric relation is also asymmetric.  
    If a relation is both symmetric and antisymmetric, then for any a and b, a R b only when a = b.  
    A relation that is reflexive and symmetric is automatically transitive.  
    On a finite set, a transitive and irreflexive relation must be asymmetric.
c) Let A = {1, 2, 3} and consider the following relations (given as sets of ordered pairs). For each one, list all properties it has (use the same list of properties as Exercise 1).
    (1)
    (2)
    (3)
    (4)
    (5)
d) Give a concrete example (different from the ones in the notes) of a relation on the set of all current students in your school that has exactly the properties listed.
    The relation must be on a single set.Reflexive, symmetric, transitive (an equivalence relation).  
    Reflexive, antisymmetric, transitive but not symmetric (a partial order that is not just equality).
    Symmetric and transitive but not reflexive.  
    Antisymmetric and transitive but not reflexive.  
    Irreflexive and transitive (this one is surprisingly common in computer science and ordering of tasks).

Relation Representation

With relations now central to how objects in sets are connected, we need clear ways to picture and work with them. Three simple representations are enough for almost every purpose we will encounter.

The most formal and unambiguous way is to leverage the idea that the relation is a subset of the Cartesian product. We list the pairs explicitly

(14.63)

This is the definition itself, so it works for finite or infinite sets and is perfect for proofs.

Draw the elements of A and B as points. Whenever a R b, draw an arrow from a to b.

Here is an example in WL.

This picture instantly reveals symmetry (arrows go both ways), chains (a → b → c), or cycles.

In fact the diagrams in the section of State Space are examples of graphs.

When the relation is reflexive, antisymmetric, and transitive—thus forming a partial order—we can draw a cleaner picture called a Hasse diagram. Elements are placed with “greater” elements higher up. We draw a line between a and b only if a is immediately below b (a ≤ b and nothing is in between).

To do this in WL we use the ResourceFunction HasseDiagram.

Undefined Terms

Term 14.10 Representation of a relation: A way to describe or visualize a relation clearly and unambiguously.

Term 14.11 Graph: A visual structure consisting of points (vertices) and connections (edges or arrows).

Formal Definitions

Definition 14.64 Arrow diagram (also called a directed graph representation): Draw the elements of set A and set B as points (in a directed graph these are called vertices). For every pair (a,b)∈R(a, b). This is also called a relation graph.

Definition 14.65 Hasse diagram: A simplified directed graph used specifically for partial orders. Elements are drawn as points, with “greater” elements placed higher. An edge is drawn from a to b only if a<b and there is no element strictly between them (this is called a covering relation). No transitive edges are drawn—only the immediate connections.

Principles

Principle 14.16 Principle of Explicit Representation: The most formal and unambiguous way to represent a relation is to list its ordered pairs explicitly as a subset of the Cartesian product A×B. This representation works for both finite and infinite relations and is ideal for rigorous proofs.

Principle 14.17 Principle of Visual Clarity: Arrow diagrams (graphs) reveal important structural properties of a relation at a glance, such as symmetry (arrows in both directions), transitivity (chains), cycles, and reflexivity (loops).

Principle 14.18 Principle of Minimal Edges (Hasse): In a Hasse diagram of a partial order, edges are drawn only for the covering relations (immediate successors), omitting all transitive consequences to keep the diagram clean and readable.

Principle 14.19 Principle of Equivalence Between Representations: All three representations (ordered-pair list, arrow diagram, Hasse diagram) describe exactly the same relation and can be converted into one another without loss of information.

Theorems

Theorem 14.49: Every relation R⊆A×B admits a unique representation as a list of ordered pairs, an arrow diagram, and (when R is a partial order) a Hasse diagram.

Proof of Theorem 14.49: This is a direct proof.

Unique representation as a list of ordered pairs. By the definition of a relation, R is the set of all ordered pairs (a, b) that belong to it. The list representation is therefore simply
By the Principle of Extensionality (two sets are equal if and only if they have exactly the same elements), this list is the unique set that equals ( R ).
Hence the ordered-pair list is unique.

Unique representation as an arrow diagram (directed graph)

The arrow diagram of R is constructed as follows:  

Draw the elements of A and B as points (vertices).

For every pair (a,b)∈R, draw a directed arrow from a to b.

The set of arrows is therefore exactly the set of ordered pairs in R. Because R is fixed, the collection of arrows is uniquely determined. If two diagrams had different arrows, they would correspond to different sets of ordered pairs, hence different relations (by extensionality). Therefore the arrow diagram is unique to R.

Unique representation as a Hasse diagram (when R is a partial order)

Assume R is a partial order on a set A (i.e., R is reflexive, antisymmetric, and transitive).  A Hasse diagram of R is the directed graph whose vertices are the elements of A and whose edges are the covering relations:  There is an edge from a to b (with b drawn above a) if and only if a≤b in the order R and there is no element c such that a<c<b  (i.e., b covers a).

The covering relation is uniquely determined by R:  Given any partial order R, the covering pairs are exactly those pairs (a, b) where a≤b, a≠b, and no element lies strictly between them.  This set of covering pairs is fixed once R is fixed.  The placement of points (higher elements above lower ones) and the omission of transitive edges are completely determined by the covering relation and the order. By the Principle of Minimal Edges (Hasse diagrams omit all transitive consequences), there is exactly one such minimal diagram for any given partial order. If two Hasse diagrams differed in an edge or in vertical placement, they would represent different covering relations, hence different partial orders (by taking the transitive closure). Therefore the Hasse diagram is unique when R is a partial order. QED

Theorem 14.50: In an arrow diagram of a relation R, the relation is  symmetric if and only if every arrow has a reverse arrow,  transitive if there is a path from a to c whenever there is an arrow from a to b and from b to c,  reflexive if every vertex has a self-loop.

Proof of Theorem 14.50: We will prove this directly.

Symmetry

R is symmetric ⇔ every arrow has a reverse arrow. Assume R is symmetric. Let there be an arrow from a to b, i.e., a R b. By symmetry, b R a. Thus there is an arrow from b to a (the reverse arrow).

Assume every arrow has a reverse arrow. Let a R b (there is an arrow from a to b. By assumption there is a reverse arrow, so b R a.

Thus R is symmetric.

Transitivity

R is transitive ⇔ there is a path from a to c whenever there is an arrow from a to b and from b to c

Assume R is transitive. Suppose there is an arrow from a to b and from b to c, i.e., a R b and b R c. By transitivity, a R c. Thus there is a direct arrow from a to c, which is a path of length 1. (Note: longer paths follow by repeated application of transitivity.

Assume that whenever there is an arrow a→b and b→c, there is a path from a to c. In particular, for any such pair there is at least a direct arrow a→c (a path of length 1). Thus a R c. Hence R is transitive.

Reflexivity

R is reflexive ⇔ every vertex has a self-loop. Assume R is reflexive. For every a∈A, a R a. Thus there is an arrow from a to a (a self-loop) on every vertex.  Assume every vertex has a self-loop. For every a∈A, there is an arrow from a to a, i.e., a R a. Thus R is reflexive. QED

Exercise 14.22: Begin with Term 14.10 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, principle, theorem, and proof.

Exercise 14.23:
a) Let A = {1, 2, 3, 4}. The relation R is given by these arrows:1 → 1, 1 → 2, 1 → 4, 2 → 2, 3 → 1, 3 → 3, 4 → 4. Do the following in Wolfram Language:
(* Step 1: define the set of ordered pairs *)
R = {{1,1},{1,2},{1,4},{2,2},{3,1},{3,3},{4,4}};

(* Step 2: draw the arrow diagram *)
RelationGraph[MemberQ[R, {#1,#2}] &, {1,2,3,4},
  VertexLabels -> Automatic,
  GraphStyle -> “LargeGraph”,
  EdgeShapeFunction -> “CurvedArc”,
  ImageSize -> Large]
    (1) Run the code. You should see a nice directed graph with loops and curved arrows.
    (2) Change exactly one pair in the list R so that the relation becomes symmetric.
    (3) Run the code again — what changes in the picture?
b) We have this WL code:
set = Range[5];   (* {1,2,3,4,5} *)

RelationGraph[#1 <= #2 &, set,
  VertexLabels -> Automatic,
  GraphStyle -> “LargeGraph”,
  VertexShapeFunction -> “Diamond”,
  EdgeStyle -> Red,
  ImageSize -> 400]
    (1) Run it. Describe the pattern you see (triangular, loops on diagonal, etc.).
    (2) Change <= to < (strictly less than). What disappears?
    (3) Change the set to Range[8] and run again. How many arrows do you get now?

Binary Relations

We now explore a very natural way that things interact—two at a time. In the real world, almost everything that happens involves two objects affecting each other or two things being compared. For example, one planet pulls on another, one person is taller than another, one line is parallel to another, one physical state can turn into another.

Whenever we have a systematic way of pairing one object with another (possibly from different sets), we are dealing with the most common and most important kind of relation of all. We will call this a binary relation. Formally, we write,

(14.64)

When the two sets are the same (A to A), we simply say it is a binary relation on A.

Examples from everyday life and physics we have the following examples; “exerts a gravitational force on”→ between two massive bodies; the relation is symmetric because if A pulls B, then B pulls A (this is another way of writing Newton’s third law of dynamics). “Is to the left of”→ between two points or particles on a line; antisymmetric and transitive, just like ordinary <. “Repels”→ between two charged objects of the same sign; again symmetric (action-reaction). “Can physically evolve into”→ between two states of a system; usually not symmetric (time flows forward), but transitive. “Is parallel to”→ between two lines in the plane; reflexive, symmetric, and transitive — the classic equivalence relation that groups lines into parallel families. “Is taller than”, “is a friend of”, “is heavier than”, “runs faster than”, “is married to”, “is the parent of”→ all familiar binary relations we use every day.

Every single one of these is nothing more than a subset of some Cartesian product.

How do we picture them when the sets are small enough?

Draw an arrow from a to b whenever a R b → directed graph.

Make a grid with rows labelled by A, columns by B, and put a mark wherever the pair belongs → yes/no table (or 0-1 table).

Just list the pairs → ordered-pair representation (the official definition).

Master the simple idea of “which pairs are connected and which are not,” and you have the logical skeleton of nearly every physical theory, every computer algorithm, and every mathematical structure you will ever meet.

Definitions

Definition 14.66 Binary relation from set A to set B: Any subset R⊆A×B. We write a R b  (spoken as “a is related to b”) whenever the ordered pair (a,b)∈R.

Definition 14.67 Binary relation on a set A: A binary relation from A to A, i.e., a subset R⊆A×A.

Definition 14.68 Ordered-pair representation: Explicitly listing the elements of the relation:  .

Definition 14.69 Arrow diagram (also called a directed graph representation): Draw the elements of A and B as points (vertices). Draw a directed arrow from a to b whenever a R b.

Principles

Principle 14.20 Principle of Binary Pairing: Every systematic way in which two objects interact, affect each other, or are compared can be represented as a binary relation — that is, as a subset of a Cartesian product.

Principle 14.21 Principle of Multiple Representations: Every binary relation admits (at least) two useful representations: the ordered-pair list, and the arrow diagram (directed graph). These representations are equivalent and can be converted into one another without loss of information.

Principle 14.22 Principle of Extensionality for Relations: Two binary relations from A to B are equal if and only if they contain exactly the same ordered pairs.

Exercise 14.24: Begin with Definition 14.66 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition, and principle.

Exercise 14.25:
a) Let A={1,2,3}. Define a relation R on A by the ordered pairs: R={(1,2), (2,3), (1,3), (3,1)}.
    1) Draw the arrow diagram of S.
    2) List all pairs (a,b) such that a R b.
b) Consider the set of people P={Alice, Bob, Clara}. Define the binary relation “is a parent of” on P by the following facts:  Alice is a parent of Bob. Bob is a parent of Clara.
    1) Write this relation as a list of ordered pairs.
    2) Draw the arrow diagram.
    3) Is there a path from Alice to Clara? What does this suggest about the relation?
c) Let A={x,y,z}. A binary relation R on A is given by the arrow diagram with arrows: x→y, y→z, x→z, and z→x.
    1) Write R as a list of ordered pairs.
    2) Is there a path from x to z? From z to y?
    3) Does the diagram suggest the relation might be transitive? Why or why not?
d) Recall from the State Space and Dynamics section that states of a system can evolve into other states. Let be four possible states of a physical system. Suppose the binary relation     E (“can evolve into”) contains the pairs: .
    1) Draw the arrow diagram of E.
    2) List all ordered pairs in E.
    3) Is there a path from   to ? What does this mean physically?
e) Consider the set L of all straight lines in the plane. Define the binary relation P on L by “is parallel to”.
    1) Is P a binary relation on L? Explain.
    2) Draw a small portion of the arrow diagram using three lines  where is parallel to   is parallel to .
    3) Use the diagram to argue that P appears to be reflexive, symmetric, and transitive.

Forces as Binary Relations Between Objects

With binary relations now our precise language for pairing objects, we discover that every force in physics is a binary relation. Consider the set O of all physical objects (particles, planets, charges, etc.) in a given system. A force relation F is a subset of the Cartesian product O × O. We say (a, b) ∈ F and write a F b (or simply “A forces B”) whenever object a exerts a non-zero force on object b.

This simple idea captures all of classical mechanics.

Newton’s third law — “action equals reaction” — is exactly the statement that the force relation is symmetric, If (a,b) ∈ F then (b,a) ∈ F, and the forces are equal in magnitude but opposite in direction.

We write

(14.65)

Gravity between two masses, electrostatic force between two charges, tension in a rope between two ends—all are symmetric binary relations.

Here are some examples, the gravitational interaction on the set of all planets: Every ordered pair (Planet₁, Planet₂) belongs to the relation (except a planet with itself — gravity is usually taken as external or negligible self-force). Another is contact forces on the set of blocks on a table: Block a resting on block b → (a,b) ∈ exerts normal force on. By symmetry, (b,a) is also in the relation (b pushes up on a).

Some forces appear to violate symmetry, but they do not belong to the same relation. For example, friction on a box pushed across a floor where the box exerts an equal and opposite friction force on the floor—the relation is still symmetric, we just usually track only the force on the object of interest.

Another example is a rocket expelling gas where the rocket pushes the gas backward, the gas pushes the rocket forward—symmetry holds between rocket and exhaust particles.

Definitions

Definition 14.70 Force relation (F): A binary relation on the set O of all physical objects in the system, defined as the subset  F⊆O×O where (a,b)∈F  (written a F b or “a forces b”) if and only if object a exerts a non-zero force on object b.

Definition 14.71 Symmetric force relation: A force relation F is symmetric if  a F b   ⇒   b F a for all objects a,b∈O.

Principles

Principle 14.23 Principle of Forces as Binary Relations: Every force in classical mechanics can be represented precisely as a binary relation on the set of physical objects. The force relation F captures exactly which pairs of objects interact via a non-zero force.

Principle 14.24 Newton’s Third Law Principle: For every force relation F in classical mechanics, the relation is symmetric: action and reaction are equal and opposite. In relational terms a F b  if and only if b F a  (with forces equal in magnitude and opposite in direction).

Principle 14.25 Principle of Symmetry in Interactions: Gravitational forces, electrostatic forces, tension in ropes, contact (normal) forces, and friction forces are all examples of symmetric binary relations between objects.

Principle 14.26 Distinction Principle: Apparent asymmetries (e.g., a rocket pushing gas, or friction on a box) do not violate symmetry when the full pair of interacting objects is considered. The symmetry holds between the rocket and exhaust particles, or between the box and the floor.

Theorems

Theorem 14.51: In classical mechanics, the gravitational force relation between massive bodies is a symmetric binary relation on the set of objects.

Proof of Theorem 14.51: Note that this is our first proof fopr a physics theorem, we will prove it by direct methods. Let O be the set of all massive bodies (objects with mass) in the system under consideration. We then define the gravitational force relation G⊆O×O by (a,b)∈G if and only if the object a exerts a non-zero gravitational force on object b.

We must show two things:

G is a binary relation on O (i.e., G⊆O×O).

G is symmetric.

Step 1: G is a binary relation

By definition, G consists of ordered pairs (a, b) where a,b∈O. Therefore G⊆O×O, so G is a binary relation on the set O.

Step 2: G is symmetric

Let a,b∈O be arbitrary massive bodies such that a G b, i.e., object a exerts a non-zero gravitational force on object b.

In classical Newtonian mechanics, the gravitational force between two masses and separated by distance r is approximately given by

(14.66)

where G, confusingly. By Newton’s law of universal gravitation and the definition of force, the force exerted by a on b is equal in magnitude and opposite in direction to the force exerted by b on a,
. Since   (by assumption that a G b). Therefore object b exerts a non-zero gravitational force on object a, this means b G a.

Since a and b were arbitrary, we have shown a G b   ⇒   b G a for all a,b∈O.  Hence the gravitational force relation G is symmetric. QED

Exercise 14.26: Begin with Definition 14.70 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition, principle, and theorem.

Exercise 14.27:
a) Let   be the set of three planets. Suppose planet   gravitationally attracts ,   attracts , and   attracts .
    1) Write the gravitational force relation G as a list of ordered pairs.
    2) Draw the arrow diagram of G.
    3) Is G a binary relation on O? Explain briefly.
b) Consider the force relation F between two blocks A and B resting on each other (normal force). It is given that A exerts a downward force on B, and by Newton’s Third Law, B exerts an equal     upward force on A.
    1) Write F as a list of ordered pairs (include both directions).
    2) Draw the arrow diagram.
    3) Use the diagram to explain why F is symmetric but not antisymmetric.
c) A rocket R expels a gas plume G. The rocket pushes the gas backward, and the gas pushes the rocket forward with equal magnitude.  
    1) Write the force relation between R and G as ordered pairs.
    2) Draw the arrow diagram.
    3) Does this relation satisfy Newton’s Third Law? Justify using the definition of symmetry.

Equivalence Relations

We constantly collect things that are “the same in the ways that matter right now.” For example, two triangles that can be rotated or flipped to match perfectly, two microscopic states of a gas that have exactly the same energy, two points in space that look identical after you rotate the whole laboratory.

Whenever we have a systematic way of declaring certain pairs of objects “indistinguishable for our current purpose”, and this way of declaring satisfies three natural properties, we have the most important kind of relation in all of science. We call such a relation an equivalence relation.

The three properties are exactly the ones you would expect from any reasonable notion of “is the same as.”

Everything is indistinguishable from itself so the relation is reflexive. For example, every triangle is congruent to itself.

If A is indistinguishable from B, then B is indistinguishable from A so the relation is symmetric. For example, if triangle fits perfectly onto , then fits perfectly onto .

If A is indistinguishable from B and B from C, then A is indistinguishable from C, such a relation is called transitive. For example, if state has the same energy as and the same as , then has the same energy as .

Formally, an equivalence relation ~ on a set A is a binary relation, such that,

(14.67)

the relation is reflexive, also,

(14.68)

the relation is symmetric, also

(14.69)

An equivalence relation cuts the original set A into non-overlapping, exhaustive subsets called equivalence classes. Two elements end up in the same subset if and only if they are related by ~ (directly or through a chain). The collection of all these subsets is written A / ~ and is called the quotient set (or sometimes “A modulo ~”).

Examples you already know include, the congruence of triangles whose equivalence classes are all triangles of the same shape and size. “Looks the same after a rotation” whose equivalence classes are orbits under the symmetry group.

Conservation laws, such as the total energy in a closed system never changes, the conservation of energy, define equivalence classes (same conserved quantities form the various equivalence classes). Symmetries of nature define equivalence classes (states that look identical after rotation, translation, or other geometric transformations). Measurement uncertainty forces us to treat states as equivalent if we cannot tell them apart.

In the deepest sense, physics does not care about individual labeled objects—only about these equivalence classes.

Two systems that belong to the same equivalence class under every physically meaningful relation are, to all experiments and all laws, the very same physical situation.

Equivalence relations are the precise mathematical translation of the physicist’s guiding principle, “If you truly cannot tell them apart—no matter what experiment you perform—then they are the same.”

Terms

Term 14.12 Same in the ways that matter: The intuitive idea of indistinguishability for a particular purpose (e.g., same shape and size, same energy, same after rotation).

Definitions

Definition 14.72 Equivalence relation (~): On a set A,  a binary relation on A that is reflexive, symmetric, and transitive.

Definition 14.73 Equivalence class of an element a∈A: The set of all elements that are equivalent to a denoted [a]={x∈A∣x∼a}.

Definition 14.74 Quotient set (also called a partition induced by ~): Denoted A/∼A. The set of all distinct equivalence classes A/∼={[a]∣a∈A}.

Principles

Principle 14.27 Principle of Indistinguishability: An equivalence relation is the precise mathematical way to declare two objects “the same for our current purpose”—i.e., indistinguishable under all experiments or measurements that matter.

Principle 14.28 Three Properties Principle: A binary relation is an equivalence relation if and only if it is reflexive, symmetric, and transitive. These are the minimal natural properties required for a sensible notion of “sameness.”

Principle 14.29 Partition Principle: Every equivalence relation on a set A partitions A into disjoint, exhaustive, non-overlapping subsets (the equivalence classes). Conversely, every partition of A defines a unique equivalence relation (two elements are related if and only if they belong to the same subset).

Theorems

Theorem 14.52: If ~ is an equivalence relation on A, then the equivalence classes form a partition of A: they are pairwise disjoint, their union is A, and every element belongs to exactly one class.

Proof of Theorem 14.52: We will use direct proof for this. Let ∼ be an equivalence relation on A (so it is reflexive, symmetric, and transitive). For each a∈A, the equivalence class of a is [a]={x∈A∣x∼a}.

Part 1: Every element belongs to at least one equivalence class (Existence)

Let a∈A be arbitrary. By reflexivity, a∼a. Therefore a∈[a]. So every element belongs to at least its own equivalence class.

Part 2: Every element belongs to at most one equivalence class (Uniqueness / Pairwise Disjointness)

Suppose an element x∈A belongs to two equivalence classes, say x∈[a] and x∈[b] for some a,b∈A. We must now show that [a]= [b]  (i.e., the two classes are actually the same). Since x∈[a], we have x∼a.  Since x∈[b], we have x∼b. By symmetry, a∼x and b∼x. By transitivity, a∼x and x∼b imply a∼b. Now let y be any element of [a]. Then y∼a. By transitivity again: y∼a imply y∼b, so y∈[b]. Thus [a]⊆[b]. By a symmetric argument (swap a and b), [b]⊆[a]. Therefore [a]= [b]. This shows that if two equivalence classes have a common element, they are identical. Hence the equivalence classes are pairwise disjoint (any two distinct classes have empty intersection), and every element belongs to exactly one equivalence class.

Part 3: The union of all equivalence classes is exactly A

Every a∈A belongs to at least one class [a]. From Part 2, it belongs to exactly one class. Therefore the union of all equivalence classes equals A: ∪a∈A. QED

Theorem 14.53: Two elements a and b belong to the same equivalence class if and only if a∼b.

Proof of Theorem 14.53: We prove both directions separately using a direct proof.

Part 1: If a∼b, then [a]= [b]. Assume a∼b. We mist show [a]⊆[b]. Let x∈[a]. By definition of equivalence class, x∼a. Since a∼b and x∼a, transitivity gives x∼b. Therefore x∈[b]. Hence [a]⊆[b]. We now show [b]⊆[a], where these are arbitrary. Then y∼b. By symmetry, b∼a. By transitivity, y∼b and b∼a  imply y∼a. Therefore y∈[a]. Hence [b]⊆[a]. Since both inclusions hold, [a]= [b].

Part 2: If [a]= [b] then a~b. Assume [a]= [b]  is reflexive, a∼a, so a∈[a]. But [a]= [b], so a∈[b]. By the definition of the equivalence class, a∈[b] means a∼b. QED

Exercise 14.28: Begin with Term 14.12 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each term, definition, principle, and theorem.

Exercise 14.29:
a) For each relation below, say Yes or No as to whether it is an equivalence relation on the suggested set. Give one short sentence justifying your answer.
    “Has the same number of letters in the first name as” on the set of all of your friends.  
`    “Is strictly taller than” any ten people.  
    “Is at most 2 cm different in height from” any ten people.  
    “Is equal to” (=) on real numbers.  
    “Is less than or equal to” (≤) on real numbers.  
    “Shares at least one hobby with” any ten people (assume if A shares a hobby with B then B shares it with A).  
    “Has the same parity as” (both even or both odd) on integers.
b) On Z (all integers), define m ~ n if m − n is divisible by 5.  List the five equivalence classes (write them as …, −10, −5, 0, 5, 10, … etc. ).
    On the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, define a ~ b if a and b have the same remainder when divided by 3. Write the three equivalence classes.
    On the set of all current residents in your home, define X ~ Y if X and Y were born in the same month. How many equivalence classes are there? What are they called in ordinary language?
c) For each of the following proposed relations on Z, decide whether it is an equivalence relation. Prove the properties that hold and give a counterexample for any that fail.
      
    m ~ n  ⇔  m + n is even  
    m ~ n  ⇔  |m| = |n|.
d) On the set of all triangles in the plane, invent three different equivalence relations (different from congruence). For each one:describe it in words, say why it is reflexive, symmetric, and transitive, and describe what a typical equivalence class looks like (e.g., “all triangles with the same area”, “all right-angled triangles”, …).
e) (Challenging) Let S be a set with n elements.
    What is the smallest possible number of equivalence classes you can get with an equivalence relation on S? Give an example.
    What is the largest possible number of equivalence classes? Give an example.
    Suppose you have an equivalence relation on S that has exactly 3 equivalence classes.    The sizes of the classes are three positive integers that add to n.
        For n = 12, list all possible triples (up to order) of class sizes you can have.

Order Relations

Arranging the universe from “lower” to “higher”. We constantly meet situations where things are not just “the same” or “different”, but where one thing clearly comes before, is below, or is contained in another. Whenever we have a consistent way of saying “x is less than or equal to y” that obeys three very natural rules, we have the second most important kind of relation in all of science. We call such a relation an order relation (or simply an order).

The three rules are exactly what you would demand from any sensible notion of “≤.”

Everything is equal to itself, so the relation is reflexive, for example every energy is equal to itself. If x ≤ y and y ≤ x, then x and y must actually be the same thing, thus the relation is antisymmetric, for example if set A ⊆ B and B ⊆ A, then A = B. The relation chains together and it is thus transitive, for example if and , then . Another example is that if event A can influence B and B can influence C, then A can influence C.

Formally, an order relation on a set A is a binary relation ≤ that satisfies three rules,

(14.70)

the relation is reflexive, also,

(14.71)

the relation is antisymmetric, also

(14.72)

the relation is also transitive.

A set equipped with an order relation is called a poset (short for partially ordered set).

Sometimes every pair of distinct elements can be compared; for any two you can always say which one is smaller (or they are equal).

When this is true, we call the order a total order (or linear order).

Much more frequently, some elements are simply incomparable—neither is smaller than the other. For example, subsets ordered by inclusion ⊆ ( {a} and {b} are incomparable).

When incomparability exists, we call it a partial order.

Definitions

Definition 14.75 Partially ordered set (poset): A set A together with a partial order ≤ on A. We often denote it as the pair (A,≤).

Definition 14.76 Incomparable elements): Two elements a,b∈A  are incomparable if neither a≤b nor b≤a

Exercise 14.30: Begin with Definition 14.75 and copy it into your notebook. Reflect on its meaning for a few minutes. Note any thoughts that come to mind. How would you explain this to someone sitting in front of you. Write this down. Then do this for each definition.

Exercise 14.31:
a) Say Yes or No whether each relation is an order relation (i.e., reflexive + antisymmetric + transitive) on the suggested set. One short sentence justification.
    usual ≤ on real numbers ℝ  
    strict < on real numbers  
    ⊆ (subset) on the power set of {1,2,3}  
    “divides” | on positive integers (a|b means b is a multiple of a)  
    “is a parent of” on people  
    “is less than or equal to” on complex numbers (with the usual real/imaginary definition)
b) For each poset below, decide whether the order is partial or total, then draw its Hasse diagram (by hand or describe it clearly).
    (1) {1,2,3,6} with the divisibility order |
    (2) Subsets of {a,b} with ⊆
    (3) {1,2,3,4,5} with usual ≤
    (4) The set {Ø, {a}, {b}, {a,b}} with ⊆
    (5) The set of tasks {wake up, eat breakfast, go to school} with “must finish before or at the same time as”
c) On the given set, decide whether the relation is a partial order. Prove the properties that hold and give a counterexample for any that fail.
    On Z, define m !≤ n if and only if .
    On (the plane), define if and (called Pareto order).  
    On positive real numbers, define a !≤ b if .

Functions

We rarely stop at saying two things are merely connected. We want to know exactly how one thing determines another. For example, if you tell me the time, I can tell you exactly where the falling stone is. If you give me a point inside the room, I can tell you its exact temperature. If you give me a velocity and a mass, I can tell you the exact kinetic energy of the particle. If you give me a distance between two masses, I can tell you the exact strength of the gravitational force.

Whenever every element in one set is paired with exactly one element in another set (no ambiguity, no missing inputs, no double outputs for the same input), we have the single most important concept in all of applied mathematics. We call this a function (or mapping).

Formally, A function f from a set A to a set B is a binary relation between A and B such that every element a ∈ A appears in exactly one ordered pair (a, b), that unique b is written f(a) or f : a |→ b.
We write

(14.73)

where  A is called the domain–everything you are allowed to plug in, B is the codomain–the set that contains all possible answers. Now the actual set of answers that appear is called the range or image of f, formally,

(14.74)

Master functions, and you hold the precise language in which the universe declares, “Tell me this, and I will tell you that — always, exactly, forever.”

There is a “do-nothing” function id that sends everything to itself, we write

(14.75)

we call this the identity function.

Terms

Term 14.13 Determination: The idea that one thing exactly and uniquely specifies another.

Definitions

Definition 14.77 Domain of f: The set of all allowed inputs.

Definition 14.78 Codomain of f: The set that contains all possible outputs.