Search the web
Sign In
New User? Sign Up
univalg · List for use by the Universal Algebra co
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Show off your group to the world. Share a photo of your group with us.

Best of Y! Groups

   Check them out and nominate your group.
Having problems with message search? Fill out this form to ensure your group is one of the first to be migrated to the new message search system.

Messages

  Messages Help
Advanced
When does variety-generated-by preserve subalgebra gaps?   Message List  
Reply | Forward Message #501 of 654 |
Call A < B a subalgebra gap when A is a maximal proper subalgebra of B.
The respective varieties generated by A and B need not form a variety
gap V(A) < V(B), witness the signature 1-1 algebra B = ({0,1,2,3},f,g)
for which f(3) = 1, g(3) = (2), and f(x) = g(x) = 0 otherwise. (Writing
the arguments as 2-bit binary numerals 00, 01, 10, and 11, f clears the
leftmost 1 if any and g the rightmost.) This has one maximal proper
subalgebra, namely A = {0,1,2}. Both f(x) = g(x) and f(f(x)) = f(x)
hold in A but not B, yet adding the first equation to the theory of B
does not entail the second.

Sometimes however the generated varieties do preserve gaps, witness the
three smallest Heyting algebras 1 < 2 < 3, all chains. As for any
signature, V(1) is axiomatized by x = y (the inconsistent theory). V(2)
is Boolean algebras, and in Boolean algebra every nontautology famously
entails x = y, that is, V(1) < V(2) is a gap. The less well known gap
V(2) < V(3) can be shown using any refutation of excluded middle x v x'
= 1 in any non-Boolean Heyting algebra H. Let that refutation have
left-hand-side a v a' = b; then {0,b,1} is a subalgebra of H isomorphic
to 3, whence every proper extension of V(2) extends V(3). The one
delicate bit here is to show b' (= b --> 0) is in {0,b,1}, which follows
from 0 = b&b' = (a v a')&b' = a&b' v a'&b', whence a&b' = 0. But a' is
the greatest x such that a&x = 0 whence b' <= a'. So b' <= b whence b'
= 0.

1. What other subalgebra gaps between Heyting algebras are preserved by
their respective varieties? In particular what about the gaps 3 < 4 < 5
< ...?

2. With an eye towards a one-line abstract-nonsense proof of gaphood of
V(2) < V(3), what natural conditions are sufficient for the preservation
of subalgebra gaps under generation of their respective varieties?

This line of thought was prompted by a recent talk at Stanford by
Vladimir Lifshitz on stable models for logic programming, at which one
member of the audience expressed confidence that adding any equation to
the theory of the Heyting algebra 3 would axiomatize Boolean algebra.
("How could there be anything in between?") His intuition turned out to
be correct, though the argument he had in mind would seem to depend on a
suitable answer to question 2.

Analogous questions arise for quotient gaps.

Vaughan Pratt



Mon May 12, 2008 12:30 am

pratt@...
Send Email Send Email

Forward
Message #501 of 654 |
Expand Messages Author Sort by Date

Call A < B a subalgebra gap when A is a maximal proper subalgebra of B. The respective varieties generated by A and B need not form a variety gap V(A) < V(B),...
Vaughan Pratt
pratt@...
Send Email
May 12, 2008
12:31 am

Jonsson¹s lemma is an obvious tool to use here. The varieties generated by the finite Heyting chains are distinct since, by Jobsson, the SIs in Var(n) are...
Brian Davey
B.Davey@...
Send Email
May 12, 2008
12:37 am

Thanks, Brian. Meanwhile I see from Exercise 4.48(18) of MMT that every HA with a gap at the top (1 covering a penultimate b) is SI. So presumably the other...
Vaughan Pratt
pratt@...
Send Email
May 12, 2008
7:18 am

Hi All, This is the answer to the second question by Vaughan: The three-element semigroup S consisting of a two-element left-zero semigroup with additional...
Petar Markovic
jjdragon1974
Online Now Send Email
May 12, 2008
8:51 am

... This is false for the case when A and B are semigroups. Here is an interesting pair. Let B2 = <c,d:cc=dd=0,cdc=c,dcd=d> be the Brandt semigroup of order...
whelee2000
Offline Send Email
May 12, 2008
10:03 am
Advanced

Copyright © 2009 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines - Help