unique factorization sentence
Tegiri Nenashi
quantifiers and subscripts? Im looking into a first order sentence
with all the variables implicitly universally quantified which is
simple implication like this
x * y = u * t & ... -> x = u
scattered
Unless you are more precise about what you are looking for it is hard
to be sure but I think that the answer is "no", at least if you stick
to the language of ring theory. If such a sentence (or set of
sentences) existed it seems that they, together with axioms for
commutative rings with unity, would show that unique factorization
domains (UFDs) form a quasivariety - a class of algebraic structures
defined by identities and quasi-identities (implications whose
conclusions are equations and whose premises are conjunctions of
equations, e.g., the sort of thing you indicated above). A standard
fact from universal algebra is that a class of algebras is a
quasivariety if and only if it is closed under isomorphisms,
subalgbras and products. But UFDs are *not* closed under the formation
of subalgberas in the sense that a subring of a UFD need not be a UFD.
For example, the complex numbers form a UFD (albeit in a trivial
sense) but the subring consisting of all numbers of the form a+(b*sqrt
(5))i, where a,b are integers is not a UFD. Thus UFDs can't be defined
by quasi-identities. More generally, it is not even clear that UFDs
are first-order definable at all since conditions for rings being UFDs
tend to be second order, involving conditions on prime ideals.
hth
-scattered
Tegiri Nenashi
I must confess I don't actually have a ring, nor even a semiring. What
is the most general structure where a unique decomposition
x = a * b * ...
is defined? For example, what about unique representation of an
element as a meet of atoms in a lattice
z = a ^ b ^ ...
?
(The reason why I'm looking into a simple expression for the unique
decompositio is that I have my algebra sitting in Prover9, so I'm
simply unable to express complex assertions, like UFD).
scattered
>
> - Show quoted text -
The problem is that unique factorization is not in general preserved
by substructures, so it can't in general be defined by universal
sentences (which, being universal, hold everywhere - hence in
substructures). For a simple example - call an element, a, of a
commutative semigroup (S,*,1) with unity prime if a is a nonidentity
element with the property that a = bc implies a = b or a = c (this
coincides with the usual definition of prime in the special case of
the natural numbers under multiplication). Unique factorization is
defined in the usual way. Let S be the power set of a 3-element set
{a,b,c} with * the operation of union. Denote elements of S by 1 (for
the empty set - the identity element), a,b,c, ab,ac,bc,abc so that
ab*bc = abc.
Then the prime elements are exactly the singletons a,b,c and it is
easy to see that unique factorization holds. But the sub-semigroup {1,
ab,ac,bc,abc} does *not* have the unique factorization property since
in the subalgebra ab,ac,bc are now the primes and abc = ab*bc = ac*bc
so abc has 2 fundamentally different factorizations into primes. This
example illustrates the general problem - unique factorizations into
irreducibles (however defined) is not unique factorizations period (at
least in most algebraic structures) but irreducibility is not a local
property. Some elements might be irreducible in a subalgebra but not
irreducible in the original algebra. But the some "harmless" non-
unique factorizations in the whole algebra (harmless in the sense that
not all of the factors involved are irreducible) might become a
factorization into irreducibles in a subalgebra. I'm not claiming that
this is always the case - some types of algebras might have the
property that you can define unique factorization for them in a
natural way and that for those algebras it is preserved by
substructures (but even then, you would need closure under products to
get a quasivariety). But - I suspect that such examples are fairly
rare and (if they exist) uninteresting.
As far as using Prover9 (which google tells me is an automated theorem
prover), there surely must be a fair amount in the literature about
how to handle existential quatifiers. Using something called
Skolemization it is even possible to in some sense eliminate them (I
forget the details). But in the case of unique factorization you seem
to be in trouble since it really isn't a first order property at all
since "There exists x1,x2,...,xn" is not a standard quatifier. You are
implicitly quantifying over *sets*, which is second order.
hth
-scattered
Tegiri Nenashi
> For a simple example - call an element, a, of a
> commutative semigroup (S,*,1) with unity prime if a is a nonidentity
> element with the property that a = bc implies a = b or a = c (this
> coincides with the usual definition of prime in the special case of
> the natural numbers under multiplication). Unique factorization is
> defined in the usual way. Let S be the power set of a 3-element set
> {a,b,c} with * the operation of union. Denote elements of S by 1 (for
> the empty set - the identity element), a,b,c, ab,ac,bc,abc so that
> ab*bc = abc.
I'm not sure I'm capable to digest your message fully, yet. Perhaps,
one more question might help. UFD implies a well defined lattice
structure, where the join is LCM and meet is GCD. I assume this is not
the case for algebraic structures where UFD is not true. Then, has UFD
property anything to do with lattice atomicity? (As I'm comfortable
with lattices more than with groups/fields any explanation from the
lattice perspective would help).
scattered
Well, *finite* distributive lattices admit a form of unique
factorization into join-irreducible elements: each element has a
unique representation as a join of a *join-irredundant* (meaning: you
get a strictly smaller join if any element in the join is deleted) set
of join-irreducible elements. See Birkhoff's "Lattice Theory" for a
proof. Since all finite distributive lattices have this property, you
don't need to woory about how to express it, at least in the case of
finite strucutres. Generalizations to inifinite lattices (not really
my area) would probably require some sort of completeness assumptions
and would involve infinite joins, so you would no longer be in first-
order lattice theory. The property of having each element be the join
of atoms is not preserved by substructures (it is easy to find an
example in the power set of a 3 element set) so couldn't be expressed
by a universal sentence. There is a fair amount of literature about
the representation of types as lattices as collections of sets or
partitions (cf. Priestly Duality for distributive lattices) that might
be relevant for your concerns.
I probably won't post for the rest of the year since I plan to take a
break from work - so Merry Christmas and Happy Ney Year if you
celebrate either or both of those holidays.
hth
-scattered