Question

Prove , <= , is a partial order on a Boolean algebra, where we define x <= y iff x + y = y.

Answer 1

A partial ordering on a set X is a binary relation on X which is reflexive, transitive, and
antisymmetric;

Answer 2

not sure what you mean by that?

Answer 3

so we can prove the following:

1. x<= x for all x,
2. if x<= y , and y<= z then x <= z
3. if x <= y then y is not <= x if x,y are distinct
(equivalently you can prove if x<= y and y<= x , then x = y )

Answer 4

a partial ordering distills the features of what an ordering is, in terms of a binary relation.

Answer 5

for example the relation "less than or equal" or "<= " is a partial ordering on the integers.
2 <= 2 (reflexivity)
if 2 =< 3 and 3 =< 5 then 2 =< 5 (transitivity)
if 2 <= 3 then 3 is not <= 2 (antisymmetric)

But keep in mind, partial order is more general than 'less than' , they don't have to deal with numbers. You can make a partial ordering on subsets of a set.

Answer 6

but its easier to use the equivalent definition of antisymmetric relation,
if x <= y and y<= x , then x = y .

Answer 7

Antisymmetric relation. if R(a,b) and R(b,a), then a = b,
or, equivalently, if R(a,b) with a \(\neq \) b, then R(b,a) must not hold.

Answer 8

Now we want to prove that for any boolean algebra , the relation <= defined by
x <= y iff x + y = y , is a partial ordering.

Answer 9

the first thing we have to prove is that x<=x (which we defined x<=y means x+x = x )
is it true in a boolean algebra that x + x = x ?