You are Here: Home >< Maths

# Help on Group Theory watch

1. I've started an Automata module in my CS degree, and have begun learning about sets and group theory.

I believe I understand the concept of a set and its operators, but I've now been introduced to:
Tuples
Pairs
Words/Strings
and I'm really struggling to get my head around them.

From what I understand, all of these are 'sequences', which area list of elements in a specific order. A pair is two elements and any more is a tuple of k length.
But I'm unsure where sets come into this. Do the elements of a set have anything to do with the elements of a sequence/tuple?

By far the most confusing part of this to me, however, is what a word is in group theory.
The complete definition of what a word is, given by the lecturer, is:

"A word, or string, is a sequence of elements of arbitrary length (even zero)"

I really don't understand what makes words/strings unique to tuples. What's the difference between a tuple and a word? The fact that it's of arbitrary length?
Where do the elements of a word come from?
He then went on to use words in the kleene star operation which just made matters worse. I have little to no idea what makes a word relevant to any other kind of sequence, and he's begun using it in an operation.

None of the books he has provided mention a word or string in this context and I don't know where else to turn. It's so frustrating and confusing and I don't want to fall behind because of something as obnoxious as this.

2. (Original post by Forumpy)
I've started an Automata module in my CS degree, and have begun learning about sets and group theory.

I believe I understand the concept of a set and its operators, but I've now been introduced to:
Tuples
Pairs
Words/Strings
and I'm really struggling to get my head around them.

From what I understand, all of these are 'sequences', which area list of elements in a specific order. A pair is two elements and any more is a tuple of k length.
But I'm unsure where sets come into this. Do the elements of a set have anything to do with the elements of a sequence/tuple?

By far the most confusing part of this to me, however, is what a word is in group theory.
The complete definition of what a word is, given by the lecturer, is:

"A word, or string, is a sequence of elements of arbitrary length (even zero)"

I really don't understand what makes words/strings unique to tuples. What's the difference between a tuple and a word? The fact that it's of arbitrary length?
Where do the elements of a word come from?
He then went on to use words in the kleene star operation which just made matters worse. I have little to no idea what makes a word relevant to any other kind of sequence, and he's begun using it in an operation.

None of the books he has provided mention a word or string in this context and I don't know where else to turn. It's so frustrating and confusing and I don't want to fall behind because of something as obnoxious as this.

The basic underlying structure here is the set. A set is an unordered collection of elements that contains no repeats. So {a,b,c,d} is the same set as {b,a,c,d} and something like {a,b,b,c} is not a set.

You then start building different structures out of the elements that are contained in sets. So ordered pairs are things of the form (x,y) where x and y are drawn from a set such as {a,b,c,d,e,f}. Notice that (a,a) is allowed and that (a,b) is distinct from (b,a).

Then you move on to ordered k-tuples. Let's take 3-tuples as an example to be concrete: (x,y,z) where x, y and z are drawn from some set. Really no more difficult a concept that ordered pairs, just longer.

A word or string (the terms are often taken as synonyms), is a finite sequence of symbols drawn from some alphabet. Here an alphabet is just a set of symbols. The main difference between a word and a k-tuple is that a word can be of any length whereas a k-tuple is exactly k symbols long. You can, if you want, represent any string of length k as a k-tuple - but since you're often interested in concatenating strings in computer science, (thus not keeping to fixed length k-tuples), it makes sense to use the terminology of words/strings.

As concatenation of words/strings is so important, it makes sense to construct a structure where concatenations of strings can "live" - and this is the Kleen Star construction. Informally speaking , it's the set of all possible concatenations of words constructed out of some alphabet. The Wikipedia article is decent description of how this works.
3. (Original post by Gregorius)
The basic underlying structure here is the set. A set is an unordered collection of elements that contains no repeats. So {a,b,c,d} is the same set as {b,a,c,d} and something like {a,b,b,c} is not a set.
At the risk of derailing this, I feel the need to say that this looks weird to me: to my mind, is a set, but is the same as , since and , and that's really the only test we can make on a set i.e. we can ask a set, via , if it does or doesn't contain an element, but we can't ask if how many times it contains it.

Is there some school of thought where textually repeating an element of a set makes it undefined? Confused.
4. (Original post by Gregorius)
The basic underlying structure here is the set. A set is an unordered collection of elements that contains no repeats. So {a,b,c,d} is the same set as {b,a,c,d} and something like {a,b,b,c} is not a set.

You then start building different structures out of the elements that are contained in sets. So ordered pairs are things of the form (x,y) where x and y are drawn from a set such as {a,b,c,d,e,f}. Notice that (a,a) is allowed and that (a,b) is distinct from (b,a).

Then you move on to ordered k-tuples. Let's take 3-tuples as an example to be concrete: (x,y,z) where x, y and z are drawn from some set. Really no more difficult a concept that ordered pairs, just longer.

A word or string (the terms are often taken as synonyms), is a finite sequence of symbols drawn from some alphabet. Here an alphabet is just a set of symbols. The main difference between a word and a k-tuple is that a word can be of any length whereas a k-tuple is exactly k symbols long. You can, if you want, represent any string of length k as a k-tuple - but since you're often interested in concatenating strings in computer science, (thus not keeping to fixed length k-tuples), it makes sense to use the terminology of words/strings.

As concatenation of words/strings is so important, it makes sense to construct a structure where concatenations of strings can "live" - and this is the Kleen Star construction. Informally speaking , it's the set of all possible concatenations of words constructed out of some alphabet. The Wikipedia article is decent description of how this works.
This is fantastic. Thank you so much.
I have some further questions however.

Do sequences/tuples/pairs etc need to come from some set originally?

When you say "A word is a finite sequence of symbols", does that essentially mean that its length is not known or not relevant?
So for instance, "abracadabra" could be seen as a 11-tuple, but for the purposes of concatenation, its exact length is not important?

And finally, regarding the Kleene Star operation, is this the set of all possible concatenations? It doesn't have an order?
How long is a product of a Kleene Star operation? Is it infinite? I've seen examples where they show (0,1)* as {0,1,00,11,0101,0011...}. Is it finite or does its length not matter?
And also, why is this useful?

Thank you so much for your help. You've worded it in an understandable way.
5. (Original post by atsruser)
At the risk of derailing this, I feel the need to say that this looks weird to me: to my mind, is a set, but is the same as , since and , and that's really the only test we can make on a set i.e. we can ask a set, via , if it does or doesn't contain an element, but we can't ask if how many times it contains it.

Is there some school of thought where textually repeating an element of a set makes it undefined? Confused.
Perhaps take a look here.
6. (Original post by Forumpy)
This is fantastic. Thank you so much.
I have some further questions however.

Do sequences/tuples/pairs etc need to come from some set originally?
Depends on what you mean by "need to" ! The usual formalism that is used starts off from the idea of a set of elements. Indeed, in a slightly more formal treatment, pairs and tuples are defined in terms of the Cartesian product of sets. Going this way makes things nice and clean. I expect (not having thought about this) that if you start off with some primitive notion of "pairs", you could recover the idea of a set from projection on either factor.

When you say "A word is a finite sequence of symbols", does that essentially mean that its length is not known or not relevant?
So for instance, "abracadabra" could be seen as a 11-tuple, but for the purposes of concatenation, its exact length is not important?
Yes. This idea of word or string removes the constraint of fixed length and allows you to freely use the concatenation operator and stay within the structure you started off with.

And finally, regarding the Kleene Star operation, is this the set of all possible concatenations? It doesn't have an order?
It is a set, but it is a set of objects that themselves have an order. Think about a simple example like {ab, ba}. This set has two elements which are words of length two; ab is not the same as ba as order matters for them. But as far as the containing set is concerned, {ab, ba} = {ba, ab}. Does that help?

How long is a product of a Kleene Star operation? Is it infinite? I've seen examples where they show (0,1)* as {0,1,00,11,0101,0011...}. Is it finite or does its length not matter? And also, why is this useful?
Yes, it is an infinite set. The point of it is that removes any restriction on the length of strings that you can use, when you're interested in using the concatenation operator.. If you were to restrict your set to strings of length 235 or less, then concatenating two strings of length 200 would give you something not contained in your set. Removing the length restriction gives you the generally desirable property of "closure" under the operation (concatenation) that you are interested in.
7. (Original post by Gregorius)
Perhaps take a look here.
I'm familiar with multisets - in fact, many years ago, I wrote a software implementation of a multiset (in C, mind, the manly way - none of this C++ standard lib nonsense). However, my question didn't have much to do with multisets. I was querying your assertion that "something like {a,b,b,c} is not a set".

The only way that makes sense to me is to interpret it as saying "if you insist that the object {a,b,b,c} is a meaningful object, containing 2 distinct b-s, then it can't be a set". In which case, I agree, but I also think the expression {a,b,b,c} is a perfectly good set - it just happens to be the same set as {a,b,c}.
8. (Original post by atsruser)
(in C, mind, the manly way - none of this C++ standard lib nonsense).
Bravo!

However, my question didn't have much to do with multisets. I was querying your assertion that "something like {a,b,b,c} is not a set".

The only way that makes sense to me is to interpret it as saying "if you insist that the object {a,b,b,c} is a meaningful object, containing 2 distinct b-s, then it can't be a set". In which case, I agree, but I also think the expression {a,b,b,c} is a perfectly good set - it just happens to be the same set as {a,b,c}.
Understood. Key here is what those curly braces mean and what you are allowed to put in them. I follow the convention I was taught that the curly braces denote that you are going to list the elements of a set (or multiset). As as set has to have distinct elements, a listing of elements thence distinguishes between a set and a multiset.
9. (Original post by Gregorius)
Understood. Key here is what those curly braces mean and what you are allowed to put in them. I follow the convention I was taught that the curly braces denote that you are going to list the elements of a set (or multiset). As as set has to have distinct elements, a listing of elements thence distinguishes between a set and a multiset.
OK, I understand what you mean now - I guess if you use multisets then it's useful to overload the meaning of the braces like this (though why not just invent a standard notation?) - I've never used multisets in any real mathematical way though, so it strikes me as slightly odd.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 18, 2017
Today on TSR

### Makeup, beauty and skincare

Best of Black Friday 2018

### University open days

Wed, 21 Nov '18
• Buckinghamshire New University
Wed, 21 Nov '18
• Heriot-Watt University
Wed, 21 Nov '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams