Binary Relations

Download Report

Transcript Binary Relations

Binary Relations
Binary Relations
on
Real Numbers
Arithmetic Axioms

Operations and Relations

What’s the difference ?


10/7/2013
Binary relation ~ “relates” one number
with another: x ~ y defines an ordered
pair in a set of ordered pairs relating x
to y in some way
Binary operator ¤ acts on two elements
to produce a third …
… so that x ¤ y = z
Binary Relations
2
Arithmetic Axioms

Operations and Relations

Examples
 Binary relation: a set of ordered pairs
 1. x ~ y if and only if x is a prime that
divides y evenly
 2. x < y if and only if x is less than y

10/7/2013
Binary operation: a set of ordered triples
 1. x + y = z
y
 2. x = z
Binary Relations
3
Equivalence and Order

Equivalence Relations: ≡ , = , ≠

Identity Relation: ≡
 Used to identify or define operations
 Examples: x – y ≡ x + (-y)
x / y ≡ x • y–1

Used to identify equivalence classes
 Example: 10 ≡ 2
mod 8
≡ 18mod 8
≡ 26mod 8
≡ 2 + 8k for some integer k
10/7/2013
Binary Relations
4
Equivalence and Order

Equivalence Relations: ≡ , = , ≠

Non-Equality Relation: ≠


10/7/2013
Declaration of non-interchangeability
Examples: (3 + 4) ≠ 5
(3 + 4) ≠ (9 + 2)
1≠0
Binary Relations
5
Equivalence and Order

Equivalence Relations: ≡ , = , ≠

Equality Relation: =


Declaration of interchangeability …
if x = y then x and y are interchangeable
Examples: (3 + 4) = 7
(3 + 4) = (9 – 2)
(x2 – 1) = (x – 1)(x + 1)
(x2 – 1) = 24
10/7/2013
Binary Relations
6
Equivalence and Order

Properties of = Relation

10/7/2013
Three primary properties:

Reflexivity: x = x

Symmetry: x = y if and only if y = x

Transitivity: if x = y and y = z then x = z
Binary Relations
7
Equivalence and Order

Order Relations

Four relations: < , ≤ , > , ≥



10/7/2013
Less Than: <
x less than y in numerical value, i.e. to
the left of y on the real number line, is
written x < y
Less Than or Equal: ≤
Binary Relations
8
Equivalence and Order

Order Relations

Four relations: < , ≤ , > , ≥

Less Than or Equal: ≤
 If x ≤ y then either x < y or x = y
… but not both!
Why ?
symmetric
transitive???
Question: Is ≤ reflexive

10/7/2013
Greater Than: >
Binary Relations
9
Equivalence and Order

Order Relations

Four relations: < , ≤ , > , ≥

Greater Than: >
 If x is greater than y in numerical value,
i.e. to the right of y on the real number
line, then x > y
symmetric
transitive???
Question: Is > reflexive

10/7/2013
Greater Than or Equal: ≥
Binary Relations
10
Equivalence and Order

Order Relations

Four relations: < , ≤ , > , ≥

Greater Than or Equal: ≥
 If x ≥ y then either x > y or x = y
… but not both!
Why ?
symmetric
transitive???
Question: Is ≥ reflexive
10/7/2013
Binary Relations
11
The Trichotomy Law

Trichotomy of the Real Numbers

If x and y are any real numbers, then
exactly one of the following holds:
 x = y
 x < y
 x > y
Question: Why are ≤ and ≥ not included ?
10/7/2013
Binary Relations
12
Think about it !
10/7/2013
Binary Relations
13