The Open Logic Text — accessible offline edition

Relations — Explore equations

Relations

Reading preferences

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

Equation guide

Every distinct expression in Relations appears once below with navigable MathML, its conventional reading, its meaning in this chapter, and links to every exact occurrence.

260 expressions

Expression 1

Rxy

Conventional reading: R relates x to y

Meaning here: The ordered pair with first coordinate x and second coordinate y belongs to relation R.

17 occurrences
  1. Occurrence 1: relations-as-sets.tex, line 58, column 17
  2. Occurrence 2: reflections.tex, line 58, column 26
  3. Occurrence 3: special-properties.tex, line 29, column 65
  4. Occurrence 4: special-properties.tex, line 35, column 1
  5. Occurrence 5: special-properties.tex, line 40, column 1
  6. Occurrence 6: special-properties.tex, line 45, column 26
  7. Occurrence 7: special-properties.tex, line 46, column 65
  8. Occurrence 8: special-properties.tex, line 48, column 21
  9. Occurrence 9: special-properties.tex, line 59, column 32
  10. Occurrence 10: special-properties.tex, line 76, column 17
  11. Occurrence 11: equivalence-relations.tex, line 20, column 56
  12. Occurrence 12: equivalence-relations.tex, line 43, column 55
  13. Occurrence 13: equivalence-relations.tex, line 48, column 42
  14. Occurrence 14: equivalence-relations.tex, line 50, column 53
  15. Occurrence 15: equivalence-relations.tex, line 60, column 46
  16. Occurrence 16: orders.tex, line 121, column 1
  17. Occurrence 17: orders.tex, line 133, column 31

Expression 9

T=⟨A,≤⟩

Conventional reading: T equals the ordered pair consisting of A and the less-than-or-equal relation

Meaning here: The tree T consists of underlying set A together with the displayed partial-order relation.

1 occurrence
  1. Occurrence 1: trees.tex, line 122, column 4

Expression 11

L={⟨0,1⟩,⟨0,2⟩,…,⟨1,2⟩,⟨1,3⟩,…,⟨2,3⟩,⟨2,4⟩,…},

Conventional reading: L equals the ordered pairs zero one, zero two, and so on; one two, one three, and so on; two three, two four, and so on

Meaning here: The relation L contains exactly the ordered pairs whose second coordinate is greater than the first.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 87, column 1

Expression 15

{y1,y2}⊆{z:z<x}

Conventional reading: the set containing y sub 1 and y sub 2 is a subset of the set of z such that z is less than x

Meaning here: Both y sub 1 and y sub 2 belong to the strict lower segment below x.

1 occurrence
  1. Occurrence 1: trees.tex, line 72, column 60

Expression 17

01≠10

Conventional reading: zero one is not equal to one zero

Meaning here: The two binary strings have different symbol order and are distinct.

1 occurrence
  1. Occurrence 1: orders.tex, line 50, column 48

Expression 28

n

Conventional reading: n

Meaning here: The integer or natural-number variable n in the surrounding statement.

14 occurrences
  1. Occurrence 1: relations-as-sets.tex, line 40, column 37
  2. Occurrence 2: relations-as-sets.tex, line 51, column 43
  3. Occurrence 3: relations-as-sets.tex, line 103, column 33
  4. Occurrence 4: equivalence-relations.tex, line 66, column 17
  5. Occurrence 5: equivalence-relations.tex, line 66, column 65
  6. Occurrence 6: equivalence-relations.tex, line 69, column 5
  7. Occurrence 7: equivalence-relations.tex, line 69, column 32
  8. Occurrence 8: equivalence-relations.tex, line 71, column 1
  9. Occurrence 9: equivalence-relations.tex, line 71, column 62
  10. Occurrence 10: equivalence-relations.tex, line 73, column 14
  11. Occurrence 11: equivalence-relations.tex, line 74, column 45
  12. Occurrence 12: equivalence-relations.tex, line 80, column 62
  13. Occurrence 13: orders.tex, line 63, column 56
  14. Occurrence 14: orders.tex, line 64, column 26

Expression 30

A⊆N∗

Conventional reading: A is a subset of the set of finite natural-number sequences

Meaning here: Every member of A is a finite sequence of natural numbers.

1 occurrence
  1. Occurrence 1: trees.tex, line 114, column 68

Expression 31

⟨A,≤⟩

Conventional reading: the ordered pair consisting of A and the less-than-or-equal relation

Meaning here: A set together with the displayed order relation.

1 occurrence
  1. Occurrence 1: trees.tex, line 67, column 4

Expression 36

x∈A

Conventional reading: x is an element of A

Meaning here: The object x belongs to set A.

10 occurrences
  1. Occurrence 1: relations-as-sets.tex, line 30, column 38
  2. Occurrence 2: special-properties.tex, line 24, column 65
  3. Occurrence 3: special-properties.tex, line 70, column 71
  4. Occurrence 4: equivalence-relations.tex, line 32, column 60
  5. Occurrence 5: orders.tex, line 116, column 14
  6. Occurrence 6: trees.tex, line 45, column 26
  7. Occurrence 7: trees.tex, line 52, column 54
  8. Occurrence 8: trees.tex, line 62, column 19
  9. Occurrence 9: trees.tex, line 67, column 42
  10. Occurrence 10: trees.tex, line 86, column 1

Expression 41

R−=R∖IdA

Conventional reading: R minus equals R set minus the identity relation on A

Meaning here: R minus is formed by deleting all diagonal pairs on A from R.

1 occurrence
  1. Occurrence 1: orders.tex, line 139, column 40

Expression 46

y2<y1<x

Conventional reading: y sub 2 is less than y sub 1, which is less than x

Meaning here: The strict order places y sub 2 below y sub 1 and y sub 1 below x.

1 occurrence
  1. Occurrence 1: trees.tex, line 79, column 11

Expression 47

x

Conventional reading: x

Meaning here: The object or element denoted by x.

9 occurrences
  1. Occurrence 1: equivalence-relations.tex, line 19, column 68
  2. Occurrence 2: equivalence-relations.tex, line 33, column 33
  3. Occurrence 3: trees.tex, line 39, column 8
  4. Occurrence 4: trees.tex, line 39, column 63
  5. Occurrence 5: trees.tex, line 40, column 28
  6. Occurrence 6: trees.tex, line 59, column 60
  7. Occurrence 7: trees.tex, line 63, column 23
  8. Occurrence 8: trees.tex, line 63, column 41
  9. Occurrence 9: trees.tex, line 80, column 19

Expression 49

IdA={⟨x,x⟩:x∈A}

Conventional reading: the identity relation on A equals the set of ordered pairs x, x such that x is in A

Meaning here: This defines the identity relation as the diagonal of A cross A.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 84, column 35

Expression 50

⟨y,z⟩∈IdA

Conventional reading: the ordered pair y, z is in the identity relation on A

Meaning here: y and z are elements of A and are equal.

1 occurrence
  1. Occurrence 1: orders.tex, line 127, column 28

Expression 52

{⟨x,y⟩∈Z2:x−1=y}

Conventional reading: the set of ordered pairs x, y in the integers squared such that x minus 1 equals y

Meaning here: The predecessor relation on the integers.

1 occurrence
  1. Occurrence 1: operations.tex, line 40, column 1

Expression 63

E={⟨n,m⟩:n>5 or m×n≥34}

Conventional reading: E equals the set of ordered pairs n, m such that n is greater than 5 or m times n is at least 34

Meaning here: The relation E holds when either its first coordinate exceeds 5 or the product of its coordinates is at least 34.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 116, column 1

Expression 68

(∀x∈A)(x<a↔x<b)

Conventional reading: for every x in A, x is less than a if and only if x is less than b

Meaning here: a and b have exactly the same strict predecessors in A.

1 occurrence
  1. Occurrence 1: orders.tex, line 163, column 9

Expression 69

A/R={[x]R:x∈A}

Conventional reading: A modulo R equals the set of R equivalence classes of x for x in A

Meaning here: The quotient of A by R is the set of all R-equivalence classes represented in A.

1 occurrence
  1. Occurrence 1: equivalence-relations.tex, line 35, column 1

Expression 72

{⟨x,y⟩∈Z2:x+2=y}

Conventional reading: the set of integer pairs x, y such that x plus 2 equals y

Meaning here: The relation that connects each integer to the integer two greater than it.

1 occurrence
  1. Occurrence 1: operations.tex, line 43, column 1

Expression 75

⊊

Conventional reading: is a proper subset of

Meaning here: Strict set inclusion: the left set is contained in but not equal to the right set.

1 occurrence
  1. Occurrence 1: orders.tex, line 95, column 14

Expression 76

℘({a,b})={∅,{a},{b},{a,b}}

Conventional reading: the power set of a, b equals the set containing the empty set, the singleton a, the singleton b, and the set a, b

Meaning here: A complete enumeration of all four subsets of the two-element set containing a and b.

1 occurrence
  1. Occurrence 1: orders.tex, line 56, column 13

Expression 78

G={⟨1,0⟩,⟨2,0⟩,⟨2,1⟩,⟨3,0⟩,⟨3,1⟩,⟨3,2⟩,…},

Conventional reading: G equals the ordered pairs one zero, two zero, two one, three zero, three one, three two, and so on

Meaning here: Relation G contains the pairs n, m for which n is greater than m.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 93, column 1

Expression 83

R[A]={y:(∃x∈A)Rxy}

Conventional reading: the image of A under R equals the set of y such that there exists x in A with R relating x to y

Meaning here: This defines relational application: all R-successors of elements of A.

1 occurrence
  1. Occurrence 1: operations.tex, line 31, column 41

Expression 84

A

Conventional reading: A

Meaning here: The set denoted by A.

27 occurrences
  1. Occurrence 1: relations-as-sets.tex, line 29, column 14
  2. Occurrence 2: relations-as-sets.tex, line 32, column 6
  3. Occurrence 3: relations-as-sets.tex, line 56, column 35
  4. Occurrence 4: relations-as-sets.tex, line 57, column 42
  5. Occurrence 5: relations-as-sets.tex, line 85, column 17
  6. Occurrence 6: relations-as-sets.tex, line 111, column 36
  7. Occurrence 7: relations-as-sets.tex, line 114, column 33
  8. Occurrence 8: special-properties.tex, line 79, column 66
  9. Occurrence 9: special-properties.tex, line 80, column 47
  10. Occurrence 10: equivalence-relations.tex, line 20, column 12
  11. Occurrence 11: equivalence-relations.tex, line 33, column 40
  12. Occurrence 12: equivalence-relations.tex, line 34, column 50
  13. Occurrence 13: equivalence-relations.tex, line 40, column 67
  14. Occurrence 14: orders.tex, line 40, column 4
  15. Occurrence 15: orders.tex, line 41, column 1
  16. Occurrence 16: orders.tex, line 98, column 25
  17. Occurrence 17: orders.tex, line 105, column 29
  18. Occurrence 18: orders.tex, line 139, column 30
  19. Occurrence 19: orders.tex, line 156, column 36
  20. Occurrence 20: trees.tex, line 44, column 43
  21. Occurrence 21: trees.tex, line 50, column 56
  22. Occurrence 22: trees.tex, line 51, column 33
  23. Occurrence 23: trees.tex, line 84, column 62
  24. Occurrence 24: trees.tex, line 116, column 39
  25. Occurrence 25: operations.tex, line 20, column 32
  26. Occurrence 26: operations.tex, line 28, column 34
  27. Occurrence 27: operations.tex, line 31, column 34

Expression 85

10≼01

Conventional reading: one zero is no longer than zero one

Meaning here: The two binary strings have equal length, so the no-longer-than preorder relates 10 to 01.

1 occurrence
  1. Occurrence 1: orders.tex, line 50, column 22

Expression 88

01≼10

Conventional reading: zero one is no longer than one zero

Meaning here: The two binary strings have equal length, so the no-longer-than preorder relates 01 to 10.

1 occurrence
  1. Occurrence 1: orders.tex, line 49, column 62

Expression 89

⟨0,0⟩⟨0,1⟩⟨0,2⟩⟨0,3⟩…⟨1,0⟩⟨1,1⟩⟨1,2⟩⟨1,3⟩…⟨2,0⟩⟨2,1⟩⟨2,2⟩⟨2,3⟩…⟨3,0⟩⟨3,1⟩⟨3,2⟩⟨3,3⟩…⋮⋮⋮⋮⋱

Conventional reading: the displayed matrix of ordered pairs has five rows and five columns, with ellipses indicating continuation. Row one: ordered pair zero, zero; ordered pair zero, one; ordered pair zero, two; ordered pair zero, three; then a horizontal ellipsis. Row two: ordered pair one, zero; ordered pair one, one; ordered pair one, two; ordered pair one, three; then a horizontal ellipsis. Row three: ordered pair two, zero; ordered pair two, one; ordered pair two, two; ordered pair two, three; then a horizontal ellipsis. Row four: ordered pair three, zero; ordered pair three, one; ordered pair three, two; ordered pair three, three; then a horizontal ellipsis. Row five has a vertical ellipsis in each of the first four columns, followed by a diagonal ellipsis. The diagonal entries, ordered pair zero, zero; ordered pair one, one; ordered pair two, two; ordered pair three, three; and the diagonal ellipsis, are printed in bold.

Meaning here: The array displays the whole Cartesian square of the natural numbers and highlights its diagonal, the identity relation.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 65, column 1

Expression 90

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.

Conventional reading: 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.

Meaning here: The first directed graph has an isolated fourth vertex; the second omits that vertex while retaining the four displayed directed edges.

1 occurrence
  1. Occurrence 1: graphs.tex, line 47, column 1

Expression 96

⟨x,y⟩∈R∪IdA

Conventional reading: the ordered pair x, y is in R union the identity relation on A

Meaning here: The pair x, y belongs either to R or to the diagonal of A.

1 occurrence
  1. Occurrence 1: orders.tex, line 119, column 31

Expression 99

{a}⊈{b}

Conventional reading: the singleton a is not a subset of the singleton b

Meaning here: Because a and b are distinct, a is not an element of the singleton containing b.

1 occurrence
  1. Occurrence 1: orders.tex, line 57, column 13

Expression 106

⟨a,b⟩={{a},{a,b}}

Conventional reading: the ordered pair a, b equals the set containing the singleton a and the set a, b

Meaning here: The Wiener-Kuratowski representation of the ordered pair a, b.

1 occurrence
  1. Occurrence 1: reflections.tex, line 21, column 58

Expression 109

(R∣S)={⟨x,z⟩:∃y(Rxy∧Syz)}

Conventional reading: R relative product S equals the set of ordered pairs x, z such that there exists y with R relating x to y and S relating y to z

Meaning here: The relative product composes R followed by S through an intermediate object y.

1 occurrence
  1. Occurrence 1: operations.tex, line 25, column 47

Expression 111

(∀a,b∈A)((∀x∈A)(x<a↔x<b)→a=b).

Conventional reading: for all a and b in A, if every x in A is less than a if and only if it is less than b, then a equals b

Meaning here: In a strict linear order, two elements with exactly the same predecessors are identical.

1 occurrence
  1. Occurrence 1: orders.tex, line 157, column 1

Expression 114

R∗=R+∪IdA

Conventional reading: R star equals R plus union the identity relation on A

Meaning here: The reflexive transitive closure is obtained by adding the identity relation to the transitive closure.

1 occurrence
  1. Occurrence 1: operations.tex, line 56, column 51

Expression 116

‖a,b‖

Conventional reading: the alternate ordered pair a, b

Meaning here: The alternative set-theoretic coding of the ordered pair with first coordinate a and second coordinate b.

1 occurrence
  1. Occurrence 1: reflections.tex, line 25, column 10

Expression 123

{a}≠{b}

Conventional reading: the singleton a is not equal to the singleton b

Meaning here: The singleton sets differ because a and b are distinct.

1 occurrence
  1. Occurrence 1: orders.tex, line 57, column 42

Expression 125

N

Conventional reading: the natural numbers

Meaning here: The set of natural numbers.

9 occurrences
  1. Occurrence 1: relations-as-sets.tex, line 14, column 1
  2. Occurrence 2: relations-as-sets.tex, line 35, column 12
  3. Occurrence 3: relations-as-sets.tex, line 46, column 34
  4. Occurrence 4: relations-as-sets.tex, line 83, column 36
  5. Occurrence 5: reflections.tex, line 16, column 49
  6. Occurrence 6: reflections.tex, line 34, column 51
  7. Occurrence 7: special-properties.tex, line 15, column 32
  8. Occurrence 8: orders.tex, line 65, column 39
  9. Occurrence 9: operations.tex, line 45, column 59

Expression 126

[x]R={y∈A:Rxy}

Conventional reading: the R equivalence class of x equals the set of y in A such that R relates x to y

Meaning here: The equivalence class of x consists exactly of the elements of A that are R-equivalent to x.

1 occurrence
  1. Occurrence 1: equivalence-relations.tex, line 33, column 55

Expression 127

s=⟨s1,…,sn⟩

Conventional reading: s equals the sequence s sub 1 through s sub n

Meaning here: The finite sequence s has entries s sub 1 through s sub n.

1 occurrence
  1. Occurrence 1: orders.tex, line 75, column 25

Expression 128

≤

Conventional reading: less than or equal to

Meaning here: The non-strict order relation under discussion.

10 occurrences
  1. Occurrence 1: special-properties.tex, line 14, column 37
  2. Occurrence 2: special-properties.tex, line 15, column 54
  3. Occurrence 3: orders.tex, line 18, column 7
  4. Occurrence 4: orders.tex, line 93, column 1
  5. Occurrence 5: graphs.tex, line 73, column 47
  6. Occurrence 6: trees.tex, line 45, column 4
  7. Occurrence 7: trees.tex, line 46, column 49
  8. Occurrence 8: trees.tex, line 51, column 5
  9. Occurrence 9: trees.tex, line 53, column 50
  10. Occurrence 10: trees.tex, line 74, column 19

Expression 132

⟨x,y⟩∉IdA

Conventional reading: the ordered pair x, y is not in the identity relation on A

Meaning here: x and y are not the same element of A.

1 occurrence
  1. Occurrence 1: orders.tex, line 120, column 1

Expression 136

101⊑101101

Conventional reading: one zero one is an initial segment of one zero one one zero one

Meaning here: The string 101 is a prefix of the string 101101.

1 occurrence
  1. Occurrence 1: trees.tex, line 104, column 31

Expression 139

V={1,2,3,4}

Conventional reading: V equals the set containing 1, 2, 3, and 4

Meaning here: The graph's vertex set has exactly the four displayed elements.

1 occurrence
  1. Occurrence 1: graphs.tex, line 44, column 31

Expression 147

a<a

Conventional reading: a is less than itself

Meaning here: The strict order relates a to itself; this is used as an irreflexivity contradiction.

1 occurrence
  1. Occurrence 1: orders.tex, line 163, column 66

Expression 153

{⟨x,y⟩:x∈y}

Conventional reading: the set of ordered pairs x, y such that x is an element of y

Meaning here: The proposed membership relation represented as a set of ordered pairs.

1 occurrence
  1. Occurrence 1: reflections.tex, line 44, column 1

Expression 155

R

Conventional reading: R

Meaning here: The relation denoted by R.

31 occurrences
  1. Occurrence 1: relations-as-sets.tex, line 41, column 39
  2. Occurrence 2: relations-as-sets.tex, line 45, column 66
  3. Occurrence 3: reflections.tex, line 35, column 64
  4. Occurrence 4: reflections.tex, line 63, column 18
  5. Occurrence 5: equivalence-relations.tex, line 14, column 23
  6. Occurrence 6: equivalence-relations.tex, line 20, column 37
  7. Occurrence 7: equivalence-relations.tex, line 34, column 60
  8. Occurrence 8: equivalence-relations.tex, line 49, column 53
  9. Occurrence 9: equivalence-relations.tex, line 50, column 63
  10. Occurrence 10: equivalence-relations.tex, line 51, column 43
  11. Occurrence 11: equivalence-relations.tex, line 58, column 25
  12. Occurrence 12: orders.tex, line 98, column 18
  13. Occurrence 13: orders.tex, line 100, column 55
  14. Occurrence 14: orders.tex, line 105, column 4
  15. Occurrence 15: orders.tex, line 106, column 29
  16. Occurrence 16: orders.tex, line 111, column 9
  17. Occurrence 17: orders.tex, line 111, column 60
  18. Occurrence 18: orders.tex, line 122, column 6
  19. Occurrence 19: orders.tex, line 126, column 10
  20. Occurrence 20: orders.tex, line 132, column 50
  21. Occurrence 21: orders.tex, line 139, column 4
  22. Occurrence 22: orders.tex, line 140, column 28
  23. Occurrence 23: graphs.tex, line 37, column 33
  24. Occurrence 24: operations.tex, line 20, column 5
  25. Occurrence 25: operations.tex, line 22, column 23
  26. Occurrence 26: operations.tex, line 25, column 32
  27. Occurrence 27: operations.tex, line 28, column 27
  28. Occurrence 28: operations.tex, line 31, column 27
  29. Occurrence 29: operations.tex, line 52, column 34
  30. Occurrence 30: operations.tex, line 56, column 44
  31. Occurrence 31: operations.tex, line 68, column 37

Expression 161

y1<y2<x

Conventional reading: y sub 1 is less than y sub 2, which is less than x

Meaning here: The strict order places y sub 1 below y sub 2 and y sub 2 below x.

1 occurrence
  1. Occurrence 1: trees.tex, line 78, column 60

Expression 163

⟨v1,v2⟩∈E

Conventional reading: the ordered pair v sub 1, v sub 2 is in E

Meaning here: The directed graph has an edge from v sub 1 to v sub 2.

1 occurrence
  1. Occurrence 1: graphs.tex, line 34, column 1

Expression 166

{z:z<x}

Conventional reading: the set of z such that z is less than x

Meaning here: The strict lower segment consisting of all predecessors of x.

1 occurrence
  1. Occurrence 1: trees.tex, line 73, column 43

Expression 169

s∈N∗

Conventional reading: s is a finite sequence of natural numbers

Meaning here: s belongs to the set of finite sequences over the natural numbers.

1 occurrence
  1. Occurrence 1: trees.tex, line 113, column 53

Expression 171

E={⟨1,1⟩,⟨1,2⟩,⟨1,3⟩,⟨2,3⟩}

Conventional reading: E equals the set of ordered pairs 1,1; 1,2; 1,3; and 2,3

Meaning here: The edge relation E contains exactly the four displayed directed edges.

1 occurrence
  1. Occurrence 1: graphs.tex, line 44, column 56

Expression 175

n<m iff ⟨n,m⟩∈R.

Conventional reading: n is less than m if and only if the ordered pair n, m is in R

Meaning here: The usual less-than relation is represented by membership of the ordered pair n, m in R.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 42, column 1

Expression 177

s′=⟨s1,…,sn,sn+1,…,sm⟩

Conventional reading: s prime equals the sequence s sub 1 through s sub n, followed by s sub n plus 1 through s sub m

Meaning here: s prime extends s by appending the entries indexed n plus 1 through m.

1 occurrence
  1. Occurrence 1: orders.tex, line 75, column 59

Expression 185

‖a,b‖={{b},{a,b}}=⟨b,a⟩

Conventional reading: the alternate ordered pair a, b equals the set containing the singleton b and the set a, b, which equals the ordered pair b, a

Meaning here: The alternate coding of the ordered pair with coordinates a, b is the usual ordered pair with coordinates b, a. It still distinguishes coordinate order and determines a and b uniquely.

1 occurrence
  1. Occurrence 1: reflections.tex, line 22, column 55

Expression 188

R={⟨n,m⟩:n,m∈N and n<m}S={‖n,m‖:n,m∈N and n<m}.

Conventional reading: R is the set of ordered pairs n, m of natural numbers with n less than m; S is the set of alternate ordered pairs n, m of natural numbers with n less than m

Meaning here: The display compares two different, equally valid set-theoretic codings of the less-than relation: R uses the usual ordered pairs, while S uses the alternate ordered pairs.

1 occurrence
  1. Occurrence 1: reflections.tex, line 29, column 1

Expression 190

S={⟨x,y⟩∈Z2:x+1=y}

Conventional reading: S equals the set of integer pairs x, y such that x plus 1 equals y

Meaning here: S is the successor relation on the integers.

1 occurrence
  1. Occurrence 1: operations.tex, line 37, column 1

Expression 196

len(x)≤len(y)

Conventional reading: the length of x is less than or equal to the length of y

Meaning here: Sequence x is no longer than sequence y.

1 occurrence
  1. Occurrence 1: orders.tex, line 47, column 37

Expression 199

{b}⊈{a}

Conventional reading: the singleton b is not a subset of the singleton a

Meaning here: Because a and b are distinct, b is not an element of the singleton containing a.

1 occurrence
  1. Occurrence 1: orders.tex, line 57, column 65

Expression 202

⟨x,x⟩∈IdA⊆R+

Conventional reading: the ordered pair x, x is in the identity relation on A, which is a subset of R plus

Meaning here: Every diagonal pair on A belongs to R plus.

1 occurrence
  1. Occurrence 1: orders.tex, line 115, column 35

Expression 206

R−1={⟨y,x⟩:⟨x,y⟩∈R}

Conventional reading: R inverse equals the set of ordered pairs y, x such that the ordered pair x, y is in R

Meaning here: The inverse relation reverses every ordered pair in R.

1 occurrence
  1. Occurrence 1: operations.tex, line 22, column 30

Expression 208

R={⟨n,m⟩:n,m∈N and n<m}

Conventional reading: R equals the set of ordered pairs n, m of natural numbers with n less than m

Meaning here: R is the usual strict less-than relation on the natural numbers.

1 occurrence
  1. Occurrence 1: reflections.tex, line 17, column 20

Expression 212

Rn+1=Rn∣R

Conventional reading: R to the power open parenthesis n plus 1 close parenthesis equals R to the power n relative product R

Meaning here: Relational powers are defined recursively by composing the nth power with R.

1 occurrence
  1. Occurrence 1: operations.tex, line 53, column 55

Expression 215

R⊆A2

Conventional reading: R is a subset of A squared

Meaning here: R is a binary relation on A.

13 occurrences
  1. Occurrence 1: special-properties.tex, line 24, column 12
  2. Occurrence 2: special-properties.tex, line 29, column 12
  3. Occurrence 3: special-properties.tex, line 34, column 12
  4. Occurrence 4: special-properties.tex, line 39, column 12
  5. Occurrence 5: special-properties.tex, line 58, column 12
  6. Occurrence 6: special-properties.tex, line 70, column 12
  7. Occurrence 7: special-properties.tex, line 75, column 12
  8. Occurrence 8: special-properties.tex, line 81, column 36
  9. Occurrence 9: equivalence-relations.tex, line 18, column 12
  10. Occurrence 10: equivalence-relations.tex, line 32, column 5
  11. Occurrence 11: equivalence-relations.tex, line 43, column 4
  12. Occurrence 12: orders.tex, line 111, column 38
  13. Occurrence 13: operations.tex, line 50, column 37

Expression 224

Ryx

Conventional reading: R relates y to x

Meaning here: The ordered pair y, x belongs to R.

10 occurrences
  1. Occurrence 1: special-properties.tex, line 35, column 18
  2. Occurrence 2: special-properties.tex, line 40, column 11
  3. Occurrence 3: special-properties.tex, line 45, column 36
  4. Occurrence 4: special-properties.tex, line 47, column 5
  5. Occurrence 5: special-properties.tex, line 48, column 31
  6. Occurrence 6: special-properties.tex, line 59, column 41
  7. Occurrence 7: special-properties.tex, line 76, column 27
  8. Occurrence 8: equivalence-relations.tex, line 51, column 19
  9. Occurrence 9: orders.tex, line 121, column 19
  10. Occurrence 10: orders.tex, line 133, column 40

Expression 233

R={⟨n,m⟩:n,m∈N and n<m}.

Conventional reading: R equals the set of ordered pairs n, m of natural numbers with n less than m

Meaning here: R is the strict less-than relation on the natural numbers.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 37, column 1

Expression 236

R+=⋃0<n∈NRn

Conventional reading: R plus equals the union over positive natural numbers n of R to the n power

Meaning here: The transitive closure of R contains every pair connected by a positive finite number of R steps.

1 occurrence
  1. Occurrence 1: operations.tex, line 52, column 41

Expression 240

{⟨0,0⟩,⟨1,1⟩,⟨2,2⟩,…},

Conventional reading: the set containing the ordered pairs zero zero, one one, two two, and so on

Meaning here: The diagonal relation on the natural numbers.

1 occurrence
  1. Occurrence 1: relations-as-sets.tex, line 80, column 1

Expression 245

R↾A=R∩A2

Conventional reading: the restriction of R to A equals R intersect A squared

Meaning here: Restricting R to A keeps exactly the pairs of R whose two coordinates lie in A.

1 occurrence
  1. Occurrence 1: operations.tex, line 28, column 41

Expression 249

⟨a,b⟩≠‖a,b‖

Conventional reading: the ordered pair a, b is not equal to the alternate ordered pair a, b

Meaning here: The usual and alternate pair codings do not in general produce the same set.

1 occurrence
  1. Occurrence 1: reflections.tex, line 24, column 6

Expression 251

{y1,y2}

Conventional reading: the set containing y sub 1 and y sub 2

Meaning here: A two-element set consisting of the indexed objects y sub 1 and y sub 2.

1 occurrence
  1. Occurrence 1: trees.tex, line 74, column 37

Expression 255

R+yx

Conventional reading: R plus relates y to x

Meaning here: The ordered pair y, x belongs to the reflexive closure formed by adding the identity relation on A to R.

1 occurrence
  1. Occurrence 1: orders.tex, line 119, column 1

Expression 259

{y:y≤x}

Conventional reading: the set of y such that y is less than or equal to x

Meaning here: The initial segment at x: all elements preceding or equal to x.

1 occurrence
  1. Occurrence 1: trees.tex, line 53, column 9

Three diagrams

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

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. 1 2 34

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 vertices
4

Read continuously as: Vertices: 1, 2, 3, 4. Directed edges: 1 to 1; 1 to 2; 1 to 3; 2 to 3. Vertex 4 has no incident edge.

Source line 48

Directed graph on vertices 1, 2, and 3

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. 1 2 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

Read continuously as: Vertices: 1, 2, 3. Directed edges: 1 to 1; 1 to 2; 1 to 3; 2 to 3.

Source line 60

Finite rooted tree with root r

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. rabcde

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.

Root
r
Children of r
a and b
Children of a
c, d, and e
Leaves
b, c, d, and e

Read continuously as: Root: r. Children of r: a and b. Children of a: c, d, and e. Leaves: b, c, d, e.

Source line 26

52 formal objects

  1. Definition: Binary relation — source line 55.
  2. Example: Relations on the natural numbers — source line 61.
  3. Exercise: List the subset relation on a power set — source line 120.
  4. Displayed mathematics — source line 29.
  5. Definition: Reflexivity — source line 23.
  6. Definition: Transitivity — source line 28.
  7. Definition: Symmetry — source line 33.
  8. Definition: Anti-symmetry — source line 38.
  9. Definition: Connectivity — source line 57.
  10. Exercise: Compare special properties of relations — source line 62.
  11. Definition: Irreflexivity — source line 69.
  12. Definition: Asymmetry — source line 74.
  13. Definition: Equivalence relation — source line 17.
  14. Definition: Equivalence classes and quotient — source line 31.
  15. Proposition: Equality of equivalence classes — source line 42.
  16. Example: Congruence modulo n — source line 63.
  17. Exercise: Congruence modulo n — source line 78.
  18. Definition: Preorder — source line 22.
  19. Definition: Partial order — source line 27.
  20. Definition: Linear order — source line 32.
  21. Example: Hierarchy of order types — source line 37.
  22. Example: No-longer-than preorder — source line 45.
  23. Example: Subset partial order — source line 53.
  24. Example: Divisibility as an order — source line 61.
  25. Example: Extension order on finite sequences — source line 72.
  26. Definition: Strict order — source line 82.
  27. Definition: Strict linear order — source line 87.
  28. Example: Strict and non-strict orders — source line 92.
  29. Proposition: Add identity to a strict order — source line 104.
  30. Proposition: Remove identity from a partial order — source line 138.
  31. Exercise: Removing identity from a partial order — source line 148.
  32. Proposition: Strict orders determined by predecessors — source line 155.
  33. Definition: Directed graph — source line 24.
  34. Example: Directed graphs differing by an isolated vertex — source line 43.
  35. Displayed mathematics — source line 47.
  36. Directed graph on vertices 1, 2, 3, and 4 — source line 48.
  37. Directed graph on vertices 1, 2, and 3 — source line 60.
  38. Exercise: Draw the less-than-or-equal graph — source line 72.
  39. Finite rooted tree with root r — source line 26.
  40. Definition: Tree — source line 49.
  41. Definition: Successors — source line 56.
  42. Proposition: A tree node has at most one predecessor — source line 66.
  43. Definition: Finite and finitely branching trees — source line 83.
  44. Definition: Branches — source line 90.
  45. Example: Infinite binary tree — source line 100.
  46. Example: Tree of finite natural-number sequences — source line 110.
  47. Proposition: König's lemma — source line 121.
  48. Definition: Inverse, product, restriction, and application — source line 19.
  49. Example: Operations on the integer successor relation — source line 35.
  50. Definition: Transitive closure — source line 50.
  51. Example: Closure of the integer successor relation — source line 60.
  52. Exercise: Transitivity of the transitive closure — source line 67.

Nine references

  1. the Some Important Sets section — relations-as-sets.tex, line 13.
  2. the Pairs, Tuples, Cartesian Products section — relations-as-sets.tex, line 23.
  3. the Relations as Sets section — reflections.tex, line 12.
  4. the Relations as Sets section — reflections.tex, line 18.
  5. the ordered-pair definition — reflections.tex, line 21.
  6. 1965 — reflections.tex, line 39.
  7. the proposition turning a partial order into a strict order — orders.tex, line 149.
  8. the proposition turning a strict order into a partial order — operations.tex, line 13.
  9. the proposition turning a partial order into a strict order — operations.tex, line 15.