FOM: expr. power of syntax (fwd)

[Ben Abraham]

slight clarification (omission) see below.

On Thu, 18 Jul 2002, Ben Abraham wrote:

>
>
> 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.

should read "the range of the map when restricted to the wffs"

> 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!
> >
>
>
>