FOM: expr. power of syntax (fwd)

[Ben Abraham]

This needs further clarification.

alluding to your previous post, we can create a bijective map (recursive)
from the wff's of sentential logic to a regular language. and then create
a recursive map from the all possible strings over the symbols of
sentential logic such that the range of the map is a regular language.
of course the trick is in the map, but recursion affords us alot of power,
because the sets are countable.

enumerate the wff's of sentential logic in any fixed order, associate them
with the regular language a*, basically unary, the number of a's in the
range is the order in the enumeration of the wff.

associate the non-wff's with anything for examples b; ab, aabb, aaabbb,
... (whatever);

we've created a map from all possible strings of symbols each member of
the set a* represents a wff. sorry if the above seems trivial, but i think
i need further clarification. i do have a guess at what you are saying but
i'll let you clarify first.


On Thu, 18 Jul 2002, Thomas Forster wrote:

> Yes, that's the easy bit.  The harrd bit is to find a formal way
> of saying something like: no language with the expressive power of
> propositional logic can be regular.  It's pretty clear that something
> like that must be true, but i'm not sure how to state it!
>