Relations — Read

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

How to use Read

Read follows the source chapter in ordinary reading order. Mathematics remains native MathML so a compatible screen reader or braille system can navigate its internal structure. Each small source link returns to the exact source line.

Relations as Sets

Explanation

In the Some Important Sets section, we mentioned some important sets: $N$ source 14, $Z$ source 14, $Q$ source 14, $R$ source 14. You will no doubt remember some interesting relations between the elements of some of these sets. For instance, each of these sets has a completely standard order relation on it. There is also the relation is identical with that every object bears to itself and to no other thing. There are many more interesting relations that we'll encounter, and even more possible relations. Before we review them, though, we will start by pointing out that we can look at relations as a special sort of set.

For this, recall two things from the Pairs, Tuples, Cartesian Products section. First, recall the notion of an ordered pair: given $a$ source 24 and $b$ source 24, we can form $⟨ a, b ⟩$ source 25. Importantly, the order of elements does matter here. So if $a \neq b$ source 26 then $⟨ a, b ⟩ \neq ⟨ b, a ⟩$ source 26. (Contrast this with unordered pairs, i.e., $2$ source 27-element sets, where ${a, b} = {b, a}$ source 28.) Second, recall the notion of a Cartesian product: if $A$ source 29 and $B$ source 29 are sets, then we can form $A \times B$ source 29, the set of all pairs $⟨ x, y ⟩$ source 30 with $x \in A$ source 30 and $y \in B$ source 30. In particular, $A^{2} = A \times A$ source 31 is the set of all ordered pairs from $A$ source 32.

Now we will consider a particular relation on a set: the $<$ source 34-relation on the set $N$ source 35 of natural numbers. Consider the set of all pairs of numbers $⟨ n, m ⟩$ source 36 where $n < m$ source 36, i.e., $R = {⟨ n, m ⟩ : n, m \in N and n < m} .$ source 37 There is a close connection between $n$ source 40 being less than $m$ source 40, and the pair $⟨ n, m ⟩$ source 41 being a member of $R$ source 41, namely: $n < m iff ⟨ n, m ⟩ \in R .$ source 42 Indeed, without any loss of information, we can consider the set $R$ source 45 to be the $<$ source 46-relation on $N$ source 46.

In the same way we can construct a subset of $N^{2}$ source 48 for any relation between numbers. Conversely, given any set of pairs of numbers $S \subseteq N^{2}$ source 50, there is a corresponding relation between numbers, namely, the relationship $n$ source 51 bears to $m$ source 51 if and only if $⟨ n, m ⟩ \in S$ source 52. This justifies the following definition:

Definition: Binary relation

A binary relation on a set $A$ source 56 is a subset of $A^{2}$ source 56. If $R \subseteq A^{2}$ source 56 is a binary relation on $A$ source 57 and $x, y \in A$ source 57, we sometimes write $R x y$ source 58 (or $x R y$ source 58) for $⟨ x, y ⟩ \in R$ source 58.

source 55

Example: Relations on the natural numbers

The set $N^{2}$ source 63 of pairs of natural numbers can be listed in a 2-dimensional matrix like this: $\begin{array}{ccccc} ⟨ 0, 0 ⟩ & ⟨ 0, 1 ⟩ & ⟨ 0, 2 ⟩ & ⟨ 0, 3 ⟩ & \dots \\ ⟨ 1, 0 ⟩ & ⟨ 1, 1 ⟩ & ⟨ 1, 2 ⟩ & ⟨ 1, 3 ⟩ & \dots \\ ⟨ 2, 0 ⟩ & ⟨ 2, 1 ⟩ & ⟨ 2, 2 ⟩ & ⟨ 2, 3 ⟩ & \dots \\ ⟨ 3, 0 ⟩ & ⟨ 3, 1 ⟩ & ⟨ 3, 2 ⟩ & ⟨ 3, 3 ⟩ & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{array}$ source 65 We have put the diagonal, here, in bold, since the subset of $N^{2}$ source 78 consisting of the pairs lying on the diagonal, i.e., ${⟨ 0, 0 ⟩, ⟨ 1, 1 ⟩, ⟨ 2, 2 ⟩, \dots},$ source 80 is the identity relation on $N$ source 83. (Since the identity relation is popular, let's define ${Id}_{A} = {⟨ x, x ⟩ : x \in A}$ source 84 for any set $A$ source 85.) The subset of all pairs lying above the diagonal, i.e., $L = {⟨ 0, 1 ⟩, ⟨ 0, 2 ⟩, \dots, ⟨ 1, 2 ⟩, ⟨ 1, 3 ⟩, \dots, ⟨ 2, 3 ⟩, ⟨ 2, 4 ⟩, \dots},$ source 87 is the less than relation, i.e., $L n m$ source 91 iff $n < m$ source 91. The subset of pairs below the diagonal, i.e., $G = {⟨ 1, 0 ⟩, ⟨ 2, 0 ⟩, ⟨ 2, 1 ⟩, ⟨ 3, 0 ⟩, ⟨ 3, 1 ⟩, ⟨ 3, 2 ⟩, \dots},$ source 93 is the greater than relation, i.e., $G n m$ source 97 iff $n > m$ source 97. The union of $L$ source 98 with $I$ source 98, which we might call $K = L \cup I$ source 98, is the less than or equal to relation: $K n m$ source 99 iff $n \leq m$ source 99. Similarly, $H = G \cup I$ source 99 is the greater than or equal to relation. These relations $L$ source 101, $G$ source 101, $K$ source 101, and $H$ source 101 are special kinds of relations called orders. $L$ source 102 and $G$ source 102 have the property that no number bears $L$ source 102 or $G$ source 103 to itself (i.e., for all $n$ source 103, neither $L n n$ source 103 nor $G n n$ source 103). Relations with this property are called irreflexive, and, if they also happen to be orders, they are called strict orders.

source 61

Exercise: List the subset relation on a power set

List the elements of the relation $\subseteq$ source 121 on the set $℘ ({a, b, c})$ source 122.

source 120

Philosophical Reflections

In the Relations as Sets section, we defined relations as certain sets. We should pause and ask a quick philosophical question: what is such a definition doing? It is extremely doubtful that we should want to say that we have discovered some metaphysical identity facts; that, for example, the order relation on $N$ source 16 turned out to be the set $R = {⟨ n, m ⟩ : n, m \in N and n < m}$ source 17 that we defined in the Relations as Sets section. Here are three reasons why.

First: in the ordered-pair definition, we defined $⟨ a, b ⟩ = {{a}, {a, b}}$ source 21. Consider instead the definition $‖ a, b ‖ = {{b}, {a, b}} = ⟨ b, a ⟩$ source 22. When $a \neq b$ source 23, we have that $⟨ a, b ⟩ \neq ‖ a, b ‖$ source 24. But we could equally have regarded $‖ a, b ‖$ source 25 as our definition of an ordered pair, rather than $⟨ a, b ⟩$ source 26. Both definitions would have worked equally well. So now we have two equally good candidates to “be” the order relation on the natural numbers, namely: $\begin{matrix} R & = {⟨ n, m ⟩ : n, m \in N and n < m} \\ S & = {‖ n, m ‖ : n, m \in N and n < m} . \end{matrix}$ source 29 Since $R \neq S$ source 33, by extensionality, it is clear that they cannot both be identical to the order relation on $N$ source 34. But it would just be arbitrary, and hence a bit embarrassing, to claim that $R$ source 35 rather than $S$ source 36 (or vice versa) is the ordering relation, as a matter of fact. (This is a very simple instance of an argument against set-theoretic reductionism which Benacerraf made famous in 1965. We will revisit it several times.)

Second: if we think that every relation should be identified with a set, then the relation of set-membership itself, $\in$ source 42, should be a particular set. Indeed, it would have to be the set ${⟨ x, y ⟩ : x \in y}$ source 44. But does this set exist? Given Russell's Paradox, it is a non-trivial claim that such a set exists. In fact, it is possible to develop set theory in a rigorous way as an axiomatic theory, and that theory will indeed deny the existence of this set. So, even if some relations can be treated as sets, the relation of set-membership will have to be a special case.

Third: when we “identify” relations with sets, we said that we would allow ourselves to write $R x y$ source 58 for $⟨ x, y ⟩ \in R$ source 58. This is fine, provided that the membership relation, “ $\in$ source 59”, is treated as a predicate. But if we think that “ $\in$ source 60” stands for a certain kind of set, then the expression “ $⟨ x, y ⟩ \in R$ source 61” just consists of three singular terms which stand for sets: “ $⟨ x, y ⟩$ source 62”, “ $\in$ source 63”, and “ $R$ source 63”. And such a list of names is no more capable of expressing a proposition than the nonsense string: “the cup penholder the table”. Again, even if some relations can be treated as sets, the relation of set-membership must be a special case. (This rolls together a simple version of Frege's concept horse paradox, and a famous objection that Wittgenstein once raised against Russell.)

So where does this leave us? Well, there is nothing wrong with our saying that the relations on the numbers are sets. We just have to understand the spirit in which that remark is made. We are not stating a metaphysical identity fact. We are simply noting that, in certain contexts, we can (and will) treat (certain) relations as certain sets.

Special Properties of Relations

Definition: Reflexivity

A relation $R \subseteq A^{2}$ source 24 is reflexive iff, for every $x \in A$ source 24, $R x x$ source 25.

source 23

Definition: Transitivity

A relation $R \subseteq A^{2}$ source 29 is transitive iff, whenever $R x y$ source 29 and $R y z$ source 30, then also $R x z$ source 30.

source 28

Definition: Symmetry

A relation $R \subseteq A^{2}$ source 34 is symmetric iff, whenever $R x y$ source 35, then also $R y x$ source 35.

source 33

Definition: Anti-symmetry

A relation $R \subseteq A^{2}$ source 39 is anti-symmetric iff, whenever both $R x y$ source 40 and $R y x$ source 40, then $x = y$ source 40 (or, in other words: if $x \neq y$ source 40 then either $\neg R x y$ source 41 or $\neg R y x$ source 41).

source 38

Definition: Connectivity

A relation $R \subseteq A^{2}$ source 58 is connected if for all $x, y \in A$ source 58, if $x \neq y$ source 59, then either $R x y$ source 59 or $R y x$ source 59.

source 57

Exercise: Compare special properties of relations

Give examples of relations that are (a) reflexive and symmetric but not transitive, (b) reflexive and anti-symmetric, (c) anti-symmetric, transitive, but not reflexive, and (d) reflexive, symmetric, and transitive. Do not use relations on numbers or sets.

source 62

Definition: Irreflexivity

A relation $R \subseteq A^{2}$ source 70 is called irreflexive if, for all $x \in A$ source 70, not $R x x$ source 71.

source 69

Definition: Asymmetry

A relation $R \subseteq A^{2}$ source 75 is called asymmetric if for no pair $x, y \in A$ source 75 we have both $R x y$ source 76 and $R y x$ source 76.

source 74

Note that if $A \neq \emptyset$ source 79, then no irreflexive relation on $A$ source 79 is reflexive and every asymmetric relation on $A$ source 80 is also anti-symmetric. However, there are $R \subseteq A^{2}$ source 81 that are not reflexive and also not irreflexive, and there are anti-symmetric relations that are not asymmetric.

Equivalence Relations

The identity relation on a set is reflexive, symmetric, and transitive. Relations $R$ source 14 that have all three of these properties are very common.

Definition: Equivalence relation

A relation $R \subseteq A^{2}$ source 18 that is reflexive, symmetric, and transitive is called an equivalence relation. elements $x$ source 19 and $y$ source 20 of $A$ source 20 are said to be $R$ source 20-equivalent if $R x y$ source 20.

source 17

Equivalence relations give rise to the notion of an equivalence class. An equivalence relation “chunks up” the domain into different partitions. Within each partition, all the objects are related to one another; and no objects from different partitions relate to one another. Sometimes, it's helpful just to talk about these partitions directly. To that end, we introduce a definition:

Definition: Equivalence classes and quotient

Let $R \subseteq A^{2}$ source 32 be an equivalence relation. For each $x \in A$ source 32, the equivalence class of $x$ source 33 in $A$ source 33 is the set ${[x]}_{R} = {y \in A : R x y}$ source 33. The quotient of $A$ source 34 under $R$ source 34 is $A /_{R} = {{[x]}_{R} : x \in A}$ source 35, i.e., the set of these equivalence classes.

source 31

The next result vindicates the definition of an equivalence class, in proving that the equivalence classes are indeed the partitions of $A$ source 40:

Proposition: Equality of equivalence classes

If $R \subseteq A^{2}$ source 43 is an equivalence relation, then $R x y$ source 43 iff ${[x]}_{R} = {[y]}_{R}$ source 44.

source 42

Proof

For the left-to-right direction, suppose $R x y$ source 48, and let $z \in {[x]}_{R}$ source 48. By definition, then, $R x z$ source 49. Since $R$ source 49 is an equivalence relation, $R y z$ source 50. (Spelling this out: as $R x y$ source 50 and $R$ source 50 is symmetric we have $R y x$ source 51, and as $R x z$ source 51 and $R$ source 51 is transitive we have $R y z$ source 52.) So $z \in {[y]}_{R}$ source 52. Generalising, ${[x]}_{R} \subseteq {[y]}_{R}$ source 53. But exactly similarly, ${[y]}_{R} \subseteq {[x]}_{R}$ source 54. So ${[x]}_{R} = {[y]}_{R}$ source 54, by extensionality.

For the right-to-left direction, suppose ${[x]}_{R} = {[y]}_{R}$ source 57. Since $R$ source 58 is reflexive, $R y y$ source 58, so $y \in {[y]}_{R}$ source 58. Thus also $y \in {[x]}_{R}$ source 59 by the assumption that ${[x]}_{R} = {[y]}_{R}$ source 60. So $R x y$ source 60.

End of proof.

Example: Congruence modulo n

A nice example of equivalence relations comes from modular arithmetic. For any $a$ source 65, $b$ source 65, and $n \in Z^{+}$ source 65, say that $a \equiv_{n} b$ source 65 iff dividing $a$ source 66 by $n$ source 66 gives the same remainder as dividing $b$ source 66 by $n$ source 66. (Somewhat more symbolically: $a \equiv_{n} b$ source 67 iff, for some $k \in Z$ source 67, $a - b = k n$ source 68.) Now, $\equiv_{n}$ source 68 is an equivalence relation, for any $n$ source 69. And there are exactly $n$ source 69 distinct equivalence classes generated by $\equiv_{n}$ source 70; that is, $N /_{\equiv_{n}}$ source 70 has $n$ source 71 elements. These are: the set of numbers divisible by $n$ source 71 without remainder, i.e., ${[0]}_{\equiv_{n}}$ source 72; the set of numbers divisible by $n$ source 73 with remainder $1$ source 73, i.e., ${[1]}_{\equiv_{n}}$ source 73; …; and the set of numbers divisible by $n$ source 74 with remainder $n - 1$ source 74, i.e., ${[n - 1]}_{\equiv_{n}}$ source 75.

source 63

Exercise: Congruence modulo n

Show that $\equiv_{n}$ source 79 is an equivalence relation, for any $n \in Z^{+}$ source 79, and that $N /_{\equiv_{n}}$ source 80 has exactly $n$ source 80 members.

source 78

Orders

Definition: Preorder

A relation which is both reflexive and transitive is called a preorder.

source 22

Definition: Partial order

A preorder which is also anti-symmetric is called a partial order.

source 27

Definition: Linear order

A partial order which is also connected is called a total order or linear order.

source 32

Example: Hierarchy of order types

Every linear order is also a partial order, and every partial order is also a preorder, but the converses don't hold. The universal relation on $A$ source 40 is a preorder, since it is reflexive and transitive. But, if $A$ source 41 has more than one element, the universal relation is not anti-symmetric, and so not a partial order.

source 37

Example: No-longer-than preorder

Consider the no longer than relation $≼$ source 46 on $B^{*}$ source 47: $x ≼ y$ source 47 iff $len (x) \leq len (y)$ source 47. This is a preorder (reflexive and transitive), and even connected, but not a partial order, since it is not anti-symmetric. For instance, $01 ≼ 10$ source 49 and $10 ≼ 01$ source 50, but $01 \neq 10$ source 50.

source 45

Example: Subset partial order

An important partial order is the relation $\subseteq$ source 54 on a set of sets. This is not in general a linear order, since if $a \neq b$ source 55 and we consider $℘ ({a, b}) = {\emptyset, {a}, {b}, {a, b}}$ source 56, we see that ${a} ⊈ {b}$ source 57 and ${a} \neq {b}$ source 57 and ${b} ⊈ {a}$ source 57.

source 53

Example: Divisibility as an order

The relation of divisibility without remainder gives us a partial order which isn't a linear order. For integers $n$ source 63 and $m$ source 63, we write $n ∣ m$ source 64 to mean $n$ source 64 (evenly) divides $m$ source 64, i.e., iff there is some integer $k$ source 65 so that $m = k n$ source 65. On $N$ source 65, this is a partial order, but not a linear order: for instance, $2 ∤ 3$ source 66 and also $3 ∤ 2$ source 66. Considered as a relation on $Z$ source 67, divisibility is only a preorder since it is not anti-symmetric: $1 ∣ - 1$ source 68 and $- 1 ∣ 1$ source 68 but $1 \neq - 1$ source 69.

source 61

Example: Extension order on finite sequences

The extension relation on a set of sequences $A^{*}$ source 73 is the following: $s ⊑ s'$ source 74 iff $s = Λ$ source 74 (the empty sequence), $s = s'$ source 75, or $s = ⟨ s_{1}, \dots, s_{n} ⟩$ source 75 and $s' = ⟨ s_{1}, \dots, s_{n}, s_{n + 1}, \dots, s_{m} ⟩$ source 75. If $s ⊑ s'$ source 76 we also say that $s$ source 77 is an initial segment of $s'$ source 77. The extension relation on $A^{*}$ source 78 is a partial order but not a linear order, e.g., if $a \neq b$ source 79, then $a b ⋢ b a$ source 79 and $b a ⋢ a b$ source 79.

source 72

Definition: Strict order

A strict order is a relation which is irreflexive, asymmetric, and transitive.

source 82

Definition: Strict linear order

A strict order which is also connected is called a strict total order or strict linear order.

source 87

Example: Strict and non-strict orders

$\leq$ source 93 is the linear order corresponding to the strict linear order $<$ source 94. $\subseteq$ source 94 is the partial order corresponding to the strict order $⊊$ source 95.

source 92

Any strict order $R$ source 98 on $A$ source 98 can be turned into a partial order by adding the diagonal ${Id}_{A}$ source 99, i.e., adding all the pairs $⟨ x, x ⟩$ source 99. (This is called the reflexive closure of $R$ source 100.) Conversely, starting from a partial order, one can get a strict order by removing ${Id}_{A}$ source 102. These next two results make this precise.

Proposition: Add identity to a strict order

If $R$ source 105 is a strict order on $A$ source 105, then $R^{+} = R \cup {Id}_{A}$ source 105 is a partial order. Moreover, if $R$ source 106 is a strict linear order, then $R^{+}$ source 106 is a linear order.

source 104

Proof

Suppose $R$ source 111 is a strict order, i.e., $R \subseteq A^{2}$ source 111 and $R$ source 111 is irreflexive, asymmetric, and transitive. Let $R^{+} = R \cup {Id}_{A}$ source 112. We have to show that $R^{+}$ source 113 is reflexive, anti-symmetric, and transitive.

$R^{+}$ source 115 is clearly reflexive, since $⟨ x, x ⟩ \in {Id}_{A} \subseteq R^{+}$ source 115 for all $x \in A$ source 116.

To show $R^{+}$ source 118 is anti-symmetric, suppose for reductio that $R^{+} x y$ source 118 and $R^{+} y x$ source 119 but $x \neq y$ source 119. Since $⟨ x, y ⟩ \in R \cup {Id}_{A}$ source 119, but $⟨ x, y ⟩ \notin {Id}_{A}$ source 120, we must have $⟨ x, y ⟩ \in R$ source 120, i.e., $R x y$ source 121. Similarly, $R y x$ source 121. But this contradicts the assumption that $R$ source 122 is asymmetric.

To establish transitivity, suppose that $R^{+} x y$ source 124 and $R^{+} y z$ source 124. If both $⟨ x, y ⟩ \in R$ source 125 and $⟨ y, z ⟩ \in R$ source 125, then $⟨ x, z ⟩ \in R$ source 125 since $R$ source 126 is transitive. Otherwise, either $⟨ x, y ⟩ \in {Id}_{A}$ source 126, i.e., $x = y$ source 127, or $⟨ y, z ⟩ \in {Id}_{A}$ source 127, i.e., $y = z$ source 127. In the first case, we have that $R^{+} y z$ source 128 by assumption, $x = y$ source 128, hence $R^{+} x z$ source 129. Similarly in the second case. In either case, $R^{+} x z$ source 129, thus, $R^{+}$ source 130 is also transitive.

Concerning the “moreover” clause, suppose that $R$ source 132 is also connected. So for all $x \neq y$ source 133, either $R x y$ source 133 or $R y x$ source 133, i.e., either $⟨ x, y ⟩ \in R$ source 134 or $⟨ y, x ⟩ \in R$ source 134. Since $R \subseteq R^{+}$ source 134, this remains true of $R^{+}$ source 135, so $R^{+}$ source 135 is connected as well.

End of proof.

Proposition: Remove identity from a partial order

If $R$ source 139 is a partial order on $A$ source 139, then $R^{-} = R ∖ {Id}_{A}$ source 139 is a strict order. Moreover, if $R$ source 140 is a linear order, then $R^{-}$ source 140 is a strict linear order.

source 138

Proof

This is left as an exercise.

End of proof.

Exercise: Removing identity from a partial order

Give a proof of the proposition turning a partial order into a strict order.

source 148

The following simple result establishes that strict linear orders satisfy an extensionality-like property:

Proposition: Strict orders determined by predecessors

If $<$ source 156 is a strict linear order on $A$ source 156, then: $(\forall a, b \in A) ((\forall x \in A) (x < a \leftrightarrow x < b) \to a = b) .$ source 157

source 155

Proof

Suppose $(\forall x \in A) (x < a \leftrightarrow x < b)$ source 163. If $a < b$ source 163, then $a < a$ source 163, contradicting the fact that $<$ source 164 is irreflexive; so $a ≮ b$ source 164. Exactly similarly, $b ≮ a$ source 165. So $a = b$ source 165, as $<$ source 165 is connected.

End of proof.

Graphs

A graph is a diagram in which points—called “nodes” or “vertices” (plural of “vertex”)—are connected by edges. Graphs are a ubiquitous tool in discrete mathematics and in computer science. They are incredibly useful for representing, and visualizing, relationships and structures, from concrete things like networks of various kinds to abstract structures such as the possible outcomes of decisions. There are many different kinds of graphs in the literature which differ, e.g., according to whether the edges are directed or not, have labels or not, whether there can be edges from a node to the same node, multiple edges between the same nodes, etc. Directed graphs have a special connection to relations.

Definition: Directed graph

A directed graph $G = ⟨ V, E ⟩$ source 25 is a set of vertices $V$ source 26 and a set of edges $E \subseteq V^{2}$ source 26.

source 24

Example: Directed graphs differing by an isolated vertex

The graph $⟨ V, E ⟩$ source 44 with $V = {1, 2, 3, 4}$ source 44 and $E = {⟨ 1, 1 ⟩, ⟨ 1, 2 ⟩, ⟨ 1, 3 ⟩, ⟨ 2, 3 ⟩}$ source 44 looks like this:

two directed graphs. The first has vertices one, two, three, and four, with edges from one to one, from one to two, from one to three, and from two to three; vertex four is isolated. This is a different graph from the ordered pair capital V prime, capital E, where capital V prime equals the set containing one, two, and three. The second graph has vertices one, two, and three, with the same four directed edges.

source 47

Directed graph on vertices 1, 2, 3, and 4

A directed graph with edges from 1 to itself, from 1 to 2, from 1 to 3, and from 2 to 3. Vertex 4 is isolated.

Vertices: 1, 2, 3, 4
Directed edges: 1 to 1; 1 to 2; 1 to 3; 2 to 3
Isolated vertex: 4

source 48

Directed graph on vertices 1, 2, and 3

A directed graph with edges from 1 to itself, from 1 to 2, from 1 to 3, and from 2 to 3.

Vertices: 1, 2, 3
Directed edges: 1 to 1; 1 to 2; 1 to 3; 2 to 3
Isolated vertices: None.

source 60

source 43

Exercise: Draw the less-than-or-equal graph

Consider the less-than-or-equal-to relation $\leq$ source 73 on the set ${1, 2, 3, 4}$ source 73 as a graph and draw the corresponding diagram.

source 72

Trees

A particular kind of partial order which plays an important role in all parts of logic is a tree. Finite trees occur in elementary parts of logic: for example, formulas can be understood in terms of their decomposition into a syntax tree, while derivations in many derivation systems also take the form of finite trees.

Infinite trees appear already in the proof of the completeness theorems for propositional and first-order logic, and are used throughout mathematical logic.

The set-theoretic concept of a tree is closely related to the notion of a tree in graph theory. Here is a picture of a (finite) tree:

Finite rooted tree with root r

The lowermost root r has children a and b. Node a has children c, d, and e. Nodes b, c, d, and e are leaves.

Edges: r to a; r to b; a to c; a to d; a to e.

$r$ source 27 — root.
$a$ source 28 — child of r; parent of c, d, and e.
$c$ source 29 — leaf; child of a.
$d$ source 30 — leaf; child of a.
$e$ source 31 — leaf; child of a.
$b$ source 33 — leaf; child of r.

source 26

The lowermost node $r$ source 37 is the root. Every node other than $r$ source 37 has exactly one parent node immediately below it. We can think of the relation a node $x$ source 39 stands in to a node $y$ source 39 if $y$ source 39 can be reached from $x$ source 39 by following edges upwards as $x$ source 40 being an ancestor of $y$ source 40.

The ancestor relation in a tree is a strict partial order. This motivates the set-theoretic definition. To state it we need two concepts. A least element in a set $A$ source 44 partially ordered by $\leq$ source 45 is an element $x \in A$ source 45 such that for all $y \in A$ source 45 we have that $x \leq y$ source 46. A set is well-ordered by $\leq$ source 46 if every one of its non-empty subsets has a least element.

Definition: Tree

A tree is a pair $T = ⟨ A, \leq ⟩$ source 50 such that $A$ source 50 is a set and $\leq$ source 51 is a partial order on $A$ source 51 with a unique least element $r \in A$ source 52 (called the root) such that for all $x \in A$ source 52, the set ${y : y \leq x}$ source 53 is well-ordered by $\leq$ source 53.

source 49

Definition: Successors

Suppose $T = ⟨ A, \leq ⟩$ source 57 is a tree. If $x, y \in A$ source 58, $x < y$ source 58, and there is no $z \in A$ source 58 such that $x < z < y$ source 59, then we say that $y$ source 59 is a successor of $x$ source 59.

source 56

The successors of $x \in A$ source 62 are also called its children. If $y$ source 63 is a successor of $x$ source 63, then we call $x$ source 63 the predecessor or parent of $y$ source 64.

Proposition: A tree node has at most one predecessor

If $⟨ A, \leq ⟩$ source 67 is a tree, then every $x \in A$ source 67 other than the root has at most one predecessor.

source 66

Proof

Suppose $y_{1} < x$ source 72 and $y_{2} < x$ source 72 and $y_{1} \neq y_{2}$ source 72. Then ${y_{1}, y_{2}} \subseteq {z : z < x}$ source 72. Since ${z : z < x}$ source 73 is well-ordered by $\leq$ source 74, its subset ${y_{1}, y_{2}}$ source 74 has a least element, which obviously must be either $y_{1}$ source 75 or $y_{2}$ source 75. So either $y_{1} \leq y_{2}$ source 76 or $y_{2} \leq y_{1}$ source 76. We assumed that $y_{1} \neq y_{2}$ source 76, so actually either $y_{1} < y_{2}$ source 77 or $y_{2} < y_{1}$ source 77. Since we assumed that $y_{1} < x$ source 78 and $y_{2} < x$ source 78, we furthermore have that either $y_{1} < y_{2} < x$ source 78 or $y_{2} < y_{1} < x$ source 79. So $y_{1}$ source 79 and $y_{2}$ source 79 cannot both be predecessors of $x$ source 80.

End of proof.

Definition: Finite and finitely branching trees

A tree $T = ⟨ A, \leq ⟩$ source 84 is said to be infinite if $A$ source 84 is an infinite set, and finite otherwise. If $T$ source 85 is such that every $x \in A$ source 86 has only finitely many successors, then we say that $T$ source 86 is finitely branching.

source 83

Definition: Branches

Given a tree $T = ⟨ A, \leq ⟩$ source 91, a branch of $T$ source 91 is a maximal chain in $T$ source 92, i.e., a set $B \subseteq A$ source 92 such that for any $x, y \in B$ source 93 either $x \leq y$ source 93 or $y \leq x$ source 93, and for any $z \in X ∖ B$ source 94 there exists $u \in B$ source 94 such that neither $z \leq u$ source 95 nor $u \leq z$ source 95.

We use $[T]$ source 97 to denote the set of all branches of $T$ source 97.

source 90

Example: Infinite binary tree

A classic example of a finitely branching tree is the infinite binary tree of finite sequences of $0$ source 102s and $1$ source 102s, sometimes denoted ${0, 1}^{*}$ source 103 or $B^{*}$ source 103, ordered by the extension relation $⊑$ source 104 (e.g., $101 ⊑ 101101$ source 104). Since any binary string can always be extended by adding a $0$ source 106 or a $1$ source 106 on the end, this tree contains infinitely many elements: every element $s$ source 107 has exactly two successors, $s 0$ source 107 and $s 1$ source 107. Its root is the empty sequence $Λ$ source 107.

source 100

Example: Tree of finite natural-number sequences

Slightly more generally, the set of finite sequences of natural numbers $N^{*}$ source 112 with the extension relation $⊑$ source 112 is also a tree. It is obviously not finitely branching: every $s \in N^{*}$ source 113 has infinitely many successors $s n$ source 114, one for every $n \in N$ source 114. Every $A \subseteq N^{*}$ source 114 which is closed under $⊑$ source 115 is a subtree of $N^{*}$ source 116. (That is, $A$ source 116 is such that if $s \in A$ source 116 and $s' ⊑ s$ source 117, then also $s' \in A$ source 117.) All finite trees can be represented as finite subtrees of $N^{*}$ source 118.

source 110

Proposition: König's lemma

If $T = ⟨ A, \leq ⟩$ source 122 is a finitely branching infinite tree, then $T$ source 123 has an infinite branch.

source 121

A special case of König's lemma widely used in computability theory, known as weak König's lemma, is the following: any infinite subtree of ${0, 1}^{*}$ source 128 has an infinite branch.

Operations on Relations

It is often useful to modify or combine relations. In the proposition turning a strict order into a partial order, we considered the union of relations, which is just the union of two relations considered as sets of pairs. Similarly, in the proposition turning a partial order into a strict order, we considered the relative difference of relations. Here are some other operations we can perform on relations.

Definition: Inverse, product, restriction, and application

Let $R$ source 20, $S$ source 20 be relations, and $A$ source 20 be any set.

The inverse of $R$ source 22 is $R^{- 1} = {⟨ y, x ⟩ : ⟨ x, y ⟩ \in R}$ source 22.

The relative product of $R$ source 25 and $S$ source 25 is $(R ∣ S) = {⟨ x, z ⟩ : \exists y (R x y \land S y z)}$ source 25.

The restriction of $R$ source 28 to $A$ source 28 is $R ↾_{A} = R \cap A^{2}$ source 28.

The application of $R$ source 31 to $A$ source 31 is $R [A] = {y : (\exists x \in A) R x y}$ source 31

source 19

Example: Operations on the integer successor relation

Let $S \subseteq Z^{2}$ source 36 be the successor relation on $Z$ source 36, i.e., $S = {⟨ x, y ⟩ \in Z^{2} : x + 1 = y}$ source 37, so that $S x y$ source 37 iff $x + 1 = y$ source 37.

$S^{- 1}$ source 39 is the predecessor relation on $Z$ source 39, i.e., ${⟨ x, y ⟩ \in Z^{2} : x - 1 = y}$ source 40.

$S ∣ S$ source 42 is ${⟨ x, y ⟩ \in Z^{2} : x + 2 = y}$ source 43

$S ↾_{N}$ source 45 is the successor relation on $N$ source 45.

$S [{1, 2, 3}]$ source 47 is ${2, 3, 4}$ source 47.

source 35

Definition: Transitive closure

Let $R \subseteq A^{2}$ source 50 be a binary relation.

The transitive closure of $R$ source 52 is $R^{+} = ⋃_{0 < n \in N} R^{n}$ source 52, where we recursively define $R^{1} = R$ source 53 and $R^{n + 1} = R^{n} ∣ R$ source 53.

The reflexive transitive closure of $R$ source 56 is $R^{*} = R^{+} \cup {Id}_{A}$ source 56.

source 50

Example: Closure of the integer successor relation

Take the successor relation $S \subseteq Z^{2}$ source 61. $S^{2} x y$ source 61 iff $x + 2 = y$ source 61, $S^{3} x y$ source 62 iff $x + 3 = y$ source 62, etc. So $S^{+} x y$ source 62 iff $x + n = y$ source 62 for some $n \geq 1$ source 63. In other words, $S^{+} x y$ source 63 iff $x < y$ source 63, and $S^{*} x y$ source 63 iff $x \leq y$ source 63.

source 60

Exercise: Transitivity of the transitive closure

Show that the transitive closure of $R$ source 68 is in fact transitive.

source 67