mathematics this usually requires finding the maxi-
mum or minimum value of a function, perhaps sub-
ject to some constraints. The techniques of
CALCULUS
are immensely successful in achieving such goals. (See
MAXIMUM
/
MINIMUM
.)
Some optimization problems can be solved geomet-
rically. Consider, for instance, the challenge of finding
the shortest path from a point Ato a point Bthat “vis-
its” 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 Ato Bvia the wall is
matched by a path of the same length from Ato the same
point of contact on the wall, and then to the mirror
image B′of Bon the other side of the wall. As the
straight path connecting Ato B′(making equal angles on
either side of the wall) is the shortest route from Ato B′,
it follows that the shortest route from Ato Bvia the wall
is the one that bounces off the wall at equal angles. Alter-
natively, one can solve this problem by drawing
ELLIPSE
s
about the points Aand Bwith Aand Bas foci. The first
ellipse that touches the wall gives the location on the wall
that yields the shortest path from Ato Bvia 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 Aof an ellipse to a
point on the curve of the ellipse and back to the second
focus Bis 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 Aof an ellipse follows a path that
reflects off the side of the ellipse so as to arrive at the
second focus B.
S
NELL
’
SLAW
of refraction can also be viewed as the
solution to an optimization problem.
See also
ISOSCELES TRIANGLE
;
LINEAR PROGRAM
-
MING
;
OPERATIONS RESEARCH
;
PEDAL TRIANGLE
; S
TEINER
POINT
.
orbit See
DYNAMICAL SYSTEM
.
ordered set A set Sis 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 ≤afor all a∈S.
2. Antisymmetry: If a≤band b≤a, then a= b.
3. Weak Transitivity: If a≤band 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 sub-
sets 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 exam-
ples 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 ∈Seither a≤bor b≤aholds.
(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 num-
bers, 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≥ato mean a≤b
and a< bto mean a≤band 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 aand bof a set Swith partial
order relation ≤, we say that an element uof Sis an
upper bound for aand bif a≤uand b≤u. We call ua
least upper bound if uis smaller than any other upper
bound for aand b; that is, if a≤vand b≤vfor some
other element v, then u≤v. For example, in the exam-
ple of subsets, the least upper bound of {A,B} and {B,C}
exists and equals their union {A,B,C}. Similarly, an ele-
ment lis a lower bound for aand bif l≤aand l≤b,
ordered set 365