Using xy for the intersection of x and y, x + y for the union
of x and y, and x' for the complement of x, Mendelsohn's axioms
for a Boolean algebra B are:
ab = ba; a(bc) = (ab)c; a = ab iff ab' = cc'; a + b = (a'b')'
From those one can prove B is a lattice with unique complementation.
Is this sufficient to show B is a Boolean algebra, ie a distributive
lattice with complementation. In other words, can one prove
distributivity
from the axioms?
The following are equivalent to distributivity:
a(b + c) = ab + ac,
a + bc = (a + b)(a + c),
ab + bc + ca = (a + b)(b + c)(c + a),
a = (a + b)(a + b'),
a = ab + ab'.
Can any of those be proved from the axioms?
Using elementary methods, I find a cyclic result of a proof for one
depending upon a proof for one of the others. It seems so unavoidable
I'm tempted to consider distributivity independent of Mendelsohn's
axioms.
Any proof, counter example, comment?
Grasping at straws, if a lattice has unique complements, is it
distributive? (The converse, complements of a distributive lattice
are unique, is simple to demonstrate.)
-- Notes
aa' = bb' iff a = aa iff aa' = aa'
Thus aa' = 0, a = aa.
abb' = aaa' = aa' = bb'
Thus a0 = 0.
a" = a"a iff a"a' = cc' iff a'a" = cc' iff a' = a'a'
Thus a" = a"a.
a = aa" iff aa"' = aa' iff aa"'a' = aa' iff a"'aa' = aa'
Thus a = aa". Uses a"' = a"'a' and a"'0 = 0.
a + b = (a'b')'; ab = (a"b")" = (a' + b')'
a = a + a; a + b = b + a; a + a' = c + c'
a + (b + c) = (a'(b + c)')' = (a'(b'c')")' = (a'(b'c'))'
= ((a'b')c')' = ((a'b')"c')' = (a'b')' + c = (a + b) + c
a = a(a + b) iff a(a + b)' = aa' iff a(a'b') = aa'
a + ab = (a'(ab)')' = (a'(a"b")')' = (a'(a' + b'))' = a" = a
a = a + b iff a = (a'b')' iff a' = a'b' iff a'b" = cc'
iff a + b' = c + c'
0 = aa'; 1 = a + a'; 1 = 0'
0a = aa'a = aa' = 0; a + 1 = a + a + a' = a + a' = 1
1a = (a + a')a = a; a + 0 = (a'0')' = (a'1)' = a" = a
ab = 0, a + b = 1 implies a = b'
Proof outline.
ab" = 0; a = ab'; a'b' = (a + b)' = 1' = 0
a' = a'b; a = (a'b)' = a + b' = ab' + b' = b'
---
On Monday, November 23, 2015 at 3:37:52 AM UTC-8, William Elliot wrote:
Using xy for the intersection of x and y, x + y for the union
of x and y, and x' for the complement of x, Mendelsohn's axioms
for a Boolean algebra B are:
ab = ba; a(bc) = (ab)c; a = ab iff ab' = cc'; a + b = (a'b')'
From those one can prove B is a lattice with unique complementation.
Is this sufficient to show B is a Boolean algebra, ie a distributive lattice with complementation. In other words, can one prove
distributivity
from the axioms?
The following are equivalent to distributivity:
a(b + c) = ab + ac,
a + bc = (a + b)(a + c),
ab + bc + ca = (a + b)(b + c)(c + a),
a = (a + b)(a + b'),
a = ab + ab'.
Can any of those be proved from the axioms?
Using elementary methods, I find a cyclic result of a proof for one depending upon a proof for one of the others. It seems so unavoidable
I'm tempted to consider distributivity independent of Mendelsohn's
axioms.
Any proof, counter example, comment?
Grasping at straws, if a lattice has unique complements, is it distributive? (The converse, complements of a distributive lattice
are unique, is simple to demonstrate.)
-- Notes
aa' = bb' iff a = aa iff aa' = aa'
Thus aa' = 0, a = aa.
abb' = aaa' = aa' = bb'
Thus a0 = 0.
a" = a"a iff a"a' = cc' iff a'a" = cc' iff a' = a'a'
Thus a" = a"a.
a = aa" iff aa"' = aa' iff aa"'a' = aa' iff a"'aa' = aa'
Thus a = aa". Uses a"' = a"'a' and a"'0 = 0.
a + b = (a'b')'; ab = (a"b")" = (a' + b')'
a = a + a; a + b = b + a; a + a' = c + c'
a + (b + c) = (a'(b + c)')' = (a'(b'c')")' = (a'(b'c'))'
= ((a'b')c')' = ((a'b')"c')' = (a'b')' + c = (a + b) + c
a = a(a + b) iff a(a + b)' = aa' iff a(a'b') = aa'
a + ab = (a'(ab)')' = (a'(a"b")')' = (a'(a' + b'))' = a" = a
a = a + b iff a = (a'b')' iff a' = a'b' iff a'b" = cc'
iff a + b' = c + c'
0 = aa'; 1 = a + a'; 1 = 0'
0a = aa'a = aa' = 0; a + 1 = a + a + a' = a + a' = 1
1a = (a + a')a = a; a + 0 = (a'0')' = (a'1)' = a" = a
ab = 0, a + b = 1 implies a = b'
Proof outline.
ab" = 0; a = ab'; a'b' = (a + b)' = 1' = 0
a' = a'b; a = (a'b)' = a + b' = ab' + b' = b'
---
Hello Elliot , yes the distributive law you seek is proved from the
same Axioms as in Mendelson in the 1950 Dover book,The Elements of Mathematical Logic by Paul Rosenbloom Pg 9-12 ,the axioms are on pg 9
and the distributive law is T21 proved on Page 12 . Regards smn
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 296 |
Nodes: | 16 (3 / 13) |
Uptime: | 56:04:56 |
Calls: | 6,652 |
Calls today: | 4 |
Files: | 12,200 |
Messages: | 5,330,863 |