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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

# Various stuff, mostly about sets

Have something to add?

- Similar discussions for: Various stuff, mostly about sets

Loading...

**Physics Forums - The Fusion of Science and Community**