Solving Set Theory Questions Using Natural Numbers and the Latin Alphabet

[inbuninbu]

I've been trying to wrap my brain around sets lately. Please bear with me, as I've been trying to teach myself.

So, from what I've read, you can construct most everything in modern mathematics from sets. You can form the natural numbers from the successor function, you can construct the integers from the natural numbers, and the rationals from integers. Functions(well, relations) as a set of ordered pairs pairing elements from the input set and the output set. I think I understand this part pretty well.

So here is where my question comes in. You can create a set of the latin alphabet as a set of naturals 0-25.
Suppose I want to construct a set consisting of integers(Z) and letters(A). The intuitive thing to do would be the union of Z and A. But of course, this isn't meaningful. Since the alphabet is defined as natural numbers, how do I tell 0 from 'A'? Is there some operator similar to a union but preserves the different 'types'?

Thanks for any suggestions!

 

[matt grime]

I think you're taking things too literally. The natural numbers are not really the thing you just described. That (the peano stuff) is just a way of demonstrating that if we really want to we can formally construct something from sets that behaves just like the natural numbers, with a set theoretic operation for addition: most of us are happy to accept that the natural numbers are the set {0,1,2,...}.

You claim to have constructed the letters as a set, but have you? Or have you just created a set with 26 elements that you've labelled A,B,..,Z? In what way does that make an alphabet?

 

[inbuninbu]

I think you're taking things too literally. The natural numbers are not really the thing you just described. That (the peano stuff) is just a way of demonstrating that if we really want to we can formally construct something from sets that behaves just like the natural numbers, with a set theoretic operation for addition: most of us are happy to accept that the natural numbers are the set {0,1,2,...}.

You claim to have constructed the letters as a set, but have you? Or have you just created a set with 26 elements that you've labelled A,B,..,Z? In what way does that make an alphabet?

The natural example was just an example to illustrate where I'm coming from. More specifically, I'm approaching this from a computer science standpoint. Ultimately the alphabet has to be encoded as a number from this point of view. I'm just hoping there is a set-theoretic concept which can conveniently encapsulate this.

 

[matt grime]

If this is all you want to do, then you assign some max bit size of numbers you're going to deal with. Let's say 6 bits. Then you decide to encode everything in, say, 8 bits, and the first two bits are used to identify what the string means, eg anything starting 00 is a number, and 01 encodes a letter.

 

[inbuninbu]

Thanks,

A simple way to do it with a structure, in, say, C, with arbitrary complexity would be to use a 'union'.

But while I'm approaching sets from the mindset of a programmer, my question has more to do with the set-theoretic side of things than the implementation side. For example, I know how to deal with strings in a number of languages; it is a built-in feature of most of them. A while ago was wondering how you might formalize strings in set theory, and I came across kleene closures. I'm after the same sort of answer, but to a different question.

On paper, I can represent the alphabet with letters, but I can't do it that from the point of view of a program. I have to distinguish the set of letters from the set of integers somehow. You can do that by using the concept 'types'. I guess what I'm asking is how you might express the notion of a type in set theory, like I was wondering for strings before.
I've read a little about something called 'type theory', but I don't understand it enough to know if that is the right direction or not.

 

[matt grime]

Uh, in *set theory*, the set of integers, and the set {a,b,c,..,z} are disjoint, so there is nothing to worry about. This is entirely an implementation problem - if you can't specify the members of your sets uniquely, then you're stuck.

You almost certainly don't want to use 'types' from set theory since if I recall correctly that is a way to deal with Russell's paradox and classes that are too large to be sets.

 

[inbuninbu]

Thanks for your help!

 

[gel]

But while I'm approaching sets from the mindset of a programmer, my question has more to do with the set-theoretic side of things than the implementation side. For example, I know how to deal with strings in a number of languages; it is a built-in feature of most of them. A while ago was wondering how you might formalize strings in set theory, and I came across kleene closures. I'm after the same sort of answer, but to a different question.

On paper, I can represent the alphabet with letters, but I can't do it that from the point of view of a program. I have to distinguish the set of letters from the set of integers somehow. You can do that by using the concept 'types'. I guess what I'm asking is how you might express the notion of a type in set theory, like I was wondering for strings before.
I've read a little about something called 'type theory', but I don't understand it enough to know if that is the right direction or not.

I think type theory might be what you're looking for. What matt grime was referring to is Russell's type theory, and I agree that you probably don't want to use that, but there are other type theories used to describe computer programs.
I don't know what your background is, but computer scientists learn about category theory in order to describe types and functions used in computer languages. In particular, I've heard http://en.wikipedia.org/wiki/Cartesian_closed_categories" discussed in this context.

What you were asking about sounds like the disjoint union of two sets - or the http://en.wikipedia.org/wiki/Coproduct" of objects in a category.

 

[matt grime]

That's a good point, gel. I'd thought more in terms of the problem being with reusing labels for elements, loosely.

Coproduct might be the kind of thing you're after. Although it all seems to boil down to the same issues in using labels to describe elements. But you'd implement coproduct via attaching an extra few bits to elements, perhaps...

Is the main issue one of theory or of implementation? I'm still a little hazy.

 

[CRGreathouse]

Here's one easy way to tell them apart. However your system defines 0, 1, 2, ... as distinct sets this will work:

Encode 0 not as 0 but as {0}, 1 as {1}, and so on, with n encoded as {n} for any number n.

For letters, code A as {0, {}}, B as {1, {}}, and so on up to Z as {25, {}}.

 

[Take_it_Easy]

Is there some operator similar to a union but preserves the different 'types'?

Thanks for any suggestions!

Yes there is! It is called the DISJOINT UNION!

First of all you have to understand what is an ordered pair.
If A is a set, and x,y belongs to A then you can define the ordered pair (x,y) to be the following set.

(x,y) := { x , {x,y} }

The most important property of the ordered pair is that for every set A and every x,y,z,t in A we have:

(x,y) = (z,t) if and only if x=z & y=t

You can prove this statement bt your own (the <= is obvious and the => is boring but simple.. you have just to apply the definitions).

Now you must know some set with at least 2 distincts elements.
There are plenty of these sets!
You know that S = {1,2} is such a set couse you know the naturals numbers and you know that 1 is NOT = 2.
Now you have two sets A, B and you can make the DISJOINT UNION of these sets!

How do you do?

Simple!

Call C = {(a,1) | a in A}, and D = {(b,2) | b in B}

the DISJOINT UNION of A and B is defined to be the UNION of C and D.