Date: Wed, 08 Jan 1997 20:45:22 GMT Server: NCSA/1.4.2 Content-type: text/html
We can prove this by induction on i:
Basis: The statement is true for i = 0 because for
any x and so
Inductive hypothesis: Assume that the statement is true for i=k:
Inductive step: From this we need to show it is true for i=k+1:
By induction, the statement is true for all .
where A and B are fixed sets and X is a set variable. Assume that B is not empty.
To do this, we verify that below:
Let X be a solution to the equation.
One way of proving that
is by showing that
for
any
. Intuitively, we can see this by substituting
for X into the equation a few times:
First we notice that = X, so it must be true that
. Similarly, after the first substitution we can say that
, so
. Thus, for any i we can apply i substitutions to
get
. The union of these is also a subset of X, so
The answer above is all I really wanted,
although to be truly formal we should prove
that for all
by induction:
Basis: We know that from above.
Inductive hypothesis: Assume
for some
.
Inductive step: From the inductive hypothesis, we know that
. This means there must be some Y where
. Substituting this into the equation we get
.
From this we can see that that
.
Therefore, for all
.