- #1

honestrosewater

Gold Member

- 2,142

- 6

I want to prove some various but closely-related things about a language, so if I need help later on, I'll just add it here. Definitions are in indigo.

The primitive symbols of formal language L fall into two disjoint sets: a countably infinite set of propositional symbols and a non-empty finite set of connective symbols. The set S of primitive symbols is then countably infinite.

A string of length n is a map from {1, 2, 3, ..., n} to S. The empty string has length 0. Conjecture: The set G of strings is countably infinite.

I got this idea from seeing Cantor's diagonal process. Let G

p

p

p

...

Then the members of G

(p

I can't think of a way to visualize the process for higher G

Do the same for each remaining G

Does that work? Make sense?

The primitive symbols of formal language L fall into two disjoint sets: a countably infinite set of propositional symbols and a non-empty finite set of connective symbols. The set S of primitive symbols is then countably infinite.

A string of length n is a map from {1, 2, 3, ..., n} to S. The empty string has length 0. Conjecture: The set G of strings is countably infinite.

I got this idea from seeing Cantor's diagonal process. Let G

_{n}denote the set of strings of length n. Then G is countable if each G_{n}is at most countable. G_{0}has one member. G_{1}= S, so is countable. For G_{2}, consider the infinite array, where p_{n}is a primitive symbol:p

_{1}p_{1}, p_{1}p_{2}, p_{1}p_{3}, ...p

_{2}p_{1}, p_{2}p_{2}, p_{2}p_{3}, ...p

_{3}p_{1}, p_{3}p_{2}, p_{3}p_{3}, ......

Then the members of G

_{2}can be arranged in the sequence:(p

_{1}p_{1}; p_{2}p_{1}, p_{1}p_{2}; p_{3}p_{1}, p_{2}p_{2}, p_{1}p_{3}; ...). So G_{2}is countable.I can't think of a way to visualize the process for higher G

_{n}s, but here's the idea, with G_{3}as an example. Arrange the members of G_{3}into a sequence by groups. Let group 1 contain all arrangements of p_{1}: p_{1}p_{1}p_{1}. Let group 2 contain all arrangements of p_{1}and p_{2}not in group 1 (I'll just write the subscripts): 112, 121, 122, 211, 212, 221, 222. Let group M contain all arrangements of p_{1}, p_{2}, ..., p_{M}not in previous groups. Put the members of each group into the sequence. Then the sequence contains all members of G_{3}and is countable.Do the same for each remaining G

_{n}. Then every G_{n}is at most countable.Does that work? Make sense?

Last edited: