## Logic and Sets.

Expand Messages
• Hello Chris, Thank you for your considerate comment. Your comment about the set not being the first or last word in mathematics is interesting. The set is
Message 1 of 5 , Oct 31, 2001
• 0 Attachment
Hello Chris,
not being the first or last word in mathematics is interesting. The
set is fruitful of course because it has the same algebra as a
subset of logic, Boolean algebra. As maths is supposed to analyse
the laws of human thought then a set will be a good starting point.
However to reward the industry of the list in dwelling on the
mysteries of the universe (only briefly I hope) I shall throw said
cat amongst pigeons once more by sharing with you a secret and one of
the best links on the web if you haven't seen it already.
Did you know that De Morgan's laws cannot be proved using
Boolean algebra? Incredible but true. De Morgan's laws have their
origin in human thought. J. To prove this, use the wonderful
automatic deduction software `Son of Birdbrain' at this link.

http://www-unix.mcs.anl.gov/AR/sobb/

Set up a Boolean algebra as axioms and then click on the De Morgan's
laws hypothesis. The computer cannot prove them with the Boolean
algebra axioms, even though De Morgan's laws are usually described
by Boolean algebra notation!

Regards,
Paul Mills
England.
• ... Sorry, I disagree. Let: C[ ] be the complement of a set u the union n the intersection E belongs to Lets proof the first one: C[X u Y] C[ X] n
Message 2 of 5 , Oct 31, 2001
• 0 Attachment
Paul wrote:

>Did you know that De Morgan's laws cannot be proved using
>Boolean algebra? Incredible but true.

Sorry, I disagree.

Let:
C[ ] be the complement of a set
u the union
n the intersection
E belongs to

Lets proof the first one: C[X u Y] <---> C[ X] n C[Y] (the second law 's proof is similar)

1. Supose that x E C[ X u Y] , then x [not E] (X u Y)
2. Then x [not E] X and x [not E] Y
3. Then x E C[X] and x E C[Y]
4. Then x E (C[X] n C[Y]) (left to right part of the proof)
5. Now supose that y E (C[X] n C[Y]) , then ( y E C[ X]) and (y E C[ Y])
6. Then ( y [not E] X) and ( y [not E] Y)
7. Then y [not E] ( X u Y)
8. Then y E C[ X u Y] (right to left part od the proof) Q.E.D.

Regards,

Peter

[Non-text portions of this message have been removed]
• ... Propositional calculus is complete. Every tautology has a proof. DeMorgan s laws are true by truth-table, therefore they re provable. ... You mean come up
Message 3 of 5 , Oct 31, 2001
• 0 Attachment
On Wed, 31 October 2001, paulmillscv@... wrote:
> Did you know that De Morgan's laws cannot be proved using
> Boolean algebra? Incredible but true. De Morgan's laws have

Propositional calculus is complete. Every tautology has a proof. DeMorgan's laws are true by truth-table, therefore they're provable.

> their
> origin in� human thought. J. To prove this, use the wonderful
> automatic deduction software `Son of Birdbrain' at this link.
>
> http://www-unix.mcs.anl.gov/AR/sobb/
>
> Set up a Boolean algebra as axioms and then click on the De
You mean come up with our own definition of the + and * operators? Well in that case of course Morgan's laws aren't necessarily going to hold.

> Morgan's
> laws hypothesis. The computer cannot prove them with the Boolean
> algebra axioms, even though De Morgan's laws are usually described
> by Boolean algebra notation!

You didn't try hard enough. I can prove both of DeMorgan's laws with only 6 hypotheses. Hypotheses which are pretty fundamental to how one would define the operations of 'and' and 'or' from first principles. Unsurprisingly - if you set up the two operators to have just what's needed to look like 'and' and 'or', then you do end up with DeMorgan's laws holding for them. I'm actually surprised that they can be proved with as few as 6 simply hypotheses, it looked like 8 would be required until I tried to just through out ones and see what happened.

Phil

Mathematics should not have to involve martyrdom;
Support Eric Weisstein, see http://mathworld.wolfram.com
Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
• Hello Juan, Phil, Yes you are right. De Morgan s laws can be proved from the 8 axioms of Boolean Algebra (as in `Son of Birdbrain or Bell). As Phil notes,
Message 4 of 5 , Oct 31, 2001
• 0 Attachment
Hello Juan, Phil,
Yes you are right. De Morgan's laws can be proved from the 8
axioms of Boolean Algebra (as in `Son of Birdbrain' or Bell). As
Phil notes, they can even be proved without commutativity (the first
two radio buttons on the web page) and so only require 6 axioms.
However in my defence all I can say is that when I tried the software
about 6 months ago, it really did not prove it. Of course it is
likely I did not press the right buttons. So one lives and learns!
Thanks for that (major) learning experience.

But your comments Juan are interesting. Note that you use a new
operation `belongs to' which does not belong to the Boolean axioms,
this means that your proof is really a `transformation.' But it may
well be the case that `belongs to' can be expressed in terms of the 8
(or 6) axioms. You see, I can be a strict algebraist when I try!

tautology (i.e. every proposition with all Ts in the truth table) is
provable. I am inclined to agree with you. So therefore as the
truth table is isomorphic to Boolean algebra then every tautology
should have a corresponding proof using the Boolean axioms.
Therefore it is only necessary to look at its truth table in order to
prove a proposition with Boolean logic. Super stuff.

Regards,
Paul Mills
• Hello Paul, Thanks, you are right with the comment about the Boolean operator (E) belongs to , but it is not hard to obtain it from the primitive Boolean
Message 5 of 5 , Nov 1, 2001
• 0 Attachment
Hello Paul,

Thanks, you are right with the comment about the Boolean operator (E)
'belongs to', but it is not hard to obtain it from the primitive Boolean
operators:

Let a, b, c, 0, 1 be objects 'belonging to' the K Boolean Set. All the
properties for 'belongs to' are:

(a E a)
if (a E b) and (b E a) then a=b
if (a E b) and (b E c) then (a E c)
(a E 1) and (0 E a)
(a E (a+b)) and ((a.b) E a)
if (a E b) then ((not b) E (not a))

but Boolean Algebra don't need that operator, and of course Morgan's Law's
are easy to derive from the original Huntington set (1904).