mathematics this usually requires finding the maximum or minimum value of a function, perhaps subject to some constraints. The techniques of CALCULUS
are immensely successful in achieving such goals. (See
MAXIMUM/MINIMUM.)
Some optimization problems can be solved geometrically. Consider, for instance, the challenge of finding
the shortest path from a point A to a point B that “visits” a straight wall. Noticing that it suffices to consider
only paths composed of two straight-line segments, we
ask which such pair of segments yields the shortest
journey.
Notice that each path from A to B via the wall is
matched by a path of the same length from A to the same
point of contact on the wall, and then to the mirror
image B′ of B on the other side of the wall. As the
straight path connecting A to B′ (making equal angles on
either side of the wall) is the shortest route from A to B′,
it follows that the shortest route from A to B via the wall
is the one that bounces off the wall at equal angles. Alternatively, one can solve this problem by drawing ELLIPSEs
about the points A and B with A and B as foci. The first
ellipse that touches the wall gives the location on the wall
that yields the shortest path from A to B via the wall.
That these two solutions solve the same problem
establishes the well-known reflection property of an
ellipse: as any path from one focus A of an ellipse to a
point on the curve of the ellipse and back to the second
focus B is a solution to the path-walking problem (with
the straight wall being the tangent line to the ellipse), it
follows that this path bounces off the side of the ellipse
at equal angles. Consequently, a beam of light emitted
from one focus A of an ellipse follows a path that
reflects off the side of the ellipse so as to arrive at the
second focus B.
SNELL’S LAW of refraction can also be viewed as the
solution to an optimization problem.
See also ISOSCELES TRIANGLE; LINEAR PROGRAMMING; OPERATIONS RESEARCH; PEDAL TRIANGLE; STEINER
POINT.
orbit See DYNAMICAL SYSTEM.
ordered set A set S is said to be partially ordered if it
comes equipped with a relation, usually denoted ≤, that
allows one to compare the size or the relative positions
of elements in the set. The relation ≤ must satisfy the
following three conditions:
1. Reflexivity: a ≤ a for all a ∈ S.
2. Antisymmetry: If a ≤ b and b ≤ a, then a = b.
3. Weak Transitivity: If a ≤ b and b ≤ c, then a ≤ c.
For example, interpreting ≤ as “less than or equal to”
provides a partial order on the set of all real numbers.
For instance, 4.6 ≤ √
–
30 and –1 ≤ 0. The set of all subsets of the set {A,B,C,D,E}, for example, is partially
ordered if one interprets ≤ to mean “is a subset of.” In
this case, for instance, {B,D} ≤ {A,B,D,} and Ø ≤ {C},
but {A,B,C} ≤ / {B,C,D,E}. The set of natural numbers
may also be partially ordered by interpreting ≤ as “is a
factor of.” For example, in this setting we have 3 ≤ 6
and 4 ≤ 12, but 5 ≤ / 12. Notice in these last two examples that not all elements in the set can be compared.
A set is called totally ordered if a fourth condition
holds:
4. Trichotomy: For all a,b ∈ S either a ≤ b or b ≤ a holds.
(If both hold, then a = b.)
The set of all real numbers, or the set of all natural
numbers, for example, are both totally ordered under
the “less than or equal to” relation. The natural numbers, however, are not totally ordered under the “is a
factor of” relation. Neither is the set of all subsets of a
given set.
Sometimes a totally ordered set is called a chain or
a sequence, since all elements can be arranged on a
line, with each element on the line in relation ≤ to each
element to its right.
Often it is convenient to write b ≥ a to mean a ≤ b
and a < b to mean a ≤ b and a ≠ b. The statement b > a
is interpreted similarly. For instance, in the example of
subsets, we have {A} < {A,B} and {C,D} ≥ {D,C}. (In
fact, {C,D} = {D,C}.)
Given two elements a and b of a set S with partial
order relation ≤, we say that an element u of S is an
upper bound for a and b if a ≤ u and b ≤ u. We call u a
least upper bound if u is smaller than any other upper
bound for a and b; that is, if a ≤ v and b ≤ v for some
other element v, then u ≤ v. For example, in the example of subsets, the least upper bound of {A,B} and {B,C}
exists and equals their union {A,B,C}. Similarly, an element l is a lower bound for a and b if l ≤ a and l ≤ b,
ordered set 365
are immensely successful in achieving such goals. (See
MAXIMUM/MINIMUM.)
Some optimization problems can be solved geometrically. Consider, for instance, the challenge of finding
the shortest path from a point A to a point B that “visits” a straight wall. Noticing that it suffices to consider
only paths composed of two straight-line segments, we
ask which such pair of segments yields the shortest
journey.
Notice that each path from A to B via the wall is
matched by a path of the same length from A to the same
point of contact on the wall, and then to the mirror
image B′ of B on the other side of the wall. As the
straight path connecting A to B′ (making equal angles on
either side of the wall) is the shortest route from A to B′,
it follows that the shortest route from A to B via the wall
is the one that bounces off the wall at equal angles. Alternatively, one can solve this problem by drawing ELLIPSEs
about the points A and B with A and B as foci. The first
ellipse that touches the wall gives the location on the wall
that yields the shortest path from A to B via the wall.
That these two solutions solve the same problem
establishes the well-known reflection property of an
ellipse: as any path from one focus A of an ellipse to a
point on the curve of the ellipse and back to the second
focus B is a solution to the path-walking problem (with
the straight wall being the tangent line to the ellipse), it
follows that this path bounces off the side of the ellipse
at equal angles. Consequently, a beam of light emitted
from one focus A of an ellipse follows a path that
reflects off the side of the ellipse so as to arrive at the
second focus B.
SNELL’S LAW of refraction can also be viewed as the
solution to an optimization problem.
See also ISOSCELES TRIANGLE; LINEAR PROGRAMMING; OPERATIONS RESEARCH; PEDAL TRIANGLE; STEINER
POINT.
orbit See DYNAMICAL SYSTEM.
ordered set A set S is said to be partially ordered if it
comes equipped with a relation, usually denoted ≤, that
allows one to compare the size or the relative positions
of elements in the set. The relation ≤ must satisfy the
following three conditions:
1. Reflexivity: a ≤ a for all a ∈ S.
2. Antisymmetry: If a ≤ b and b ≤ a, then a = b.
3. Weak Transitivity: If a ≤ b and b ≤ c, then a ≤ c.
For example, interpreting ≤ as “less than or equal to”
provides a partial order on the set of all real numbers.
For instance, 4.6 ≤ √
–
30 and –1 ≤ 0. The set of all subsets of the set {A,B,C,D,E}, for example, is partially
ordered if one interprets ≤ to mean “is a subset of.” In
this case, for instance, {B,D} ≤ {A,B,D,} and Ø ≤ {C},
but {A,B,C} ≤ / {B,C,D,E}. The set of natural numbers
may also be partially ordered by interpreting ≤ as “is a
factor of.” For example, in this setting we have 3 ≤ 6
and 4 ≤ 12, but 5 ≤ / 12. Notice in these last two examples that not all elements in the set can be compared.
A set is called totally ordered if a fourth condition
holds:
4. Trichotomy: For all a,b ∈ S either a ≤ b or b ≤ a holds.
(If both hold, then a = b.)
The set of all real numbers, or the set of all natural
numbers, for example, are both totally ordered under
the “less than or equal to” relation. The natural numbers, however, are not totally ordered under the “is a
factor of” relation. Neither is the set of all subsets of a
given set.
Sometimes a totally ordered set is called a chain or
a sequence, since all elements can be arranged on a
line, with each element on the line in relation ≤ to each
element to its right.
Often it is convenient to write b ≥ a to mean a ≤ b
and a < b to mean a ≤ b and a ≠ b. The statement b > a
is interpreted similarly. For instance, in the example of
subsets, we have {A} < {A,B} and {C,D} ≥ {D,C}. (In
fact, {C,D} = {D,C}.)
Given two elements a and b of a set S with partial
order relation ≤, we say that an element u of S is an
upper bound for a and b if a ≤ u and b ≤ u. We call u a
least upper bound if u is smaller than any other upper
bound for a and b; that is, if a ≤ v and b ≤ v for some
other element v, then u ≤ v. For example, in the example of subsets, the least upper bound of {A,B} and {B,C}
exists and equals their union {A,B,C}. Similarly, an element l is a lower bound for a and b if l ≤ a and l ≤ b,
ordered set 365