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 | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Various stuff, mostly about sets

**Physics Forums | Science Articles, Homework Help, Discussion**