CS04 : Different ways of counting


Numbers aren't simply numbers. They can be categorised and this always helps computer scientists and mathematicians to make sense of them.

We are learning ...
  • About number systems
So that we can ...
  • Explain the features of different number systems ...
    - Natural numbers
    - Integer numbers
    - Rational numbers
    - Irrational numbers
    - Ordinal numbers
  • Describe simple set theory
    - Set notation
    - Finite / Infinite sets
    - Set comprehension (in Python)
    - Compact set representation
    - Set operations (cartesian product, membership, union, intersection, difference)
    - Subsets, proper subsets, countable sets
    - Permutations

Activity 1 Different sets of number (60)

There are 7 recognised set of numbers, some of which are given their own, special symbols ...
  • Natural numbers ()
  • Integer numbers ()
  • Real numbers ()
  • Rational numbers ()
  • Irrational numbers (no accepted symbol, but often  \  or )
  • Imaginary numbers (𝕀)
  • Complex numbers ()
You may wish to go to the Maths is Fun website to find out more!

We can also describe numbers in a set in terms of their ...
  • Ordinality (ordering)
  • Cardinality (counting)
  • Nominality (naming)
You may wish to go to the Maths is Fun website to find out more!



Task 1.1 Poster

You will be assigned one set of numbers each and you have to make an informative poster about it including ...
  • Definition
  • Background
  • Examples
Each of you must also include examples or ordinality, cardinality and nominality on your poster as well.

OUTCOME : Beautiful poster about one particular number system


Activity 2 Set Theory (280) A Level Only

A set is a mathematical term used to represent a group of related 'things'.


Task 2.1 Research into sets

Research simple set theory using the Maths is fun website. Make some simple notes to help you with your revision and try the activities at the end.

OUTCOME : Set of notes about sets


Set comprehension

So, a set is a collection of ordered values where each value appears only once in the set. The values in the set are sometimes referred to as elements, objects or members. Defining a set is called set comprehension or set building.

For example ...

A = { 𝑥 | 𝑥 ∈ ℕ ∧ 𝑥 ≥ 5 }

where ...
  • A is the name of the set
  • the curly braces { } represent the contents of the set
  • 𝑥 represents the actual values of the set
  • the pipe | means 'such that', meaning that the equation after the 𝑥 denotes the values of 𝑥
  • ∈ means 'is a member of'
  • ℕ is a set of all of the natural numbers, e.g. {0, 1, 2, 3, ...} (see below)
  • ∧ means 'logical and'
  • ≥ 5 means greater than or equal to 5.
So we could 'write' this set comprehension as 'The set A is defined in terms of 𝑥 such that 𝑥 is a member of the set of natural numbers, ℕ and 𝑥 is greater than or equal to 5'.

The actual members of A (called the alphabet and given the symbol capital Greek sigma, Σare {5, 6, 7, 8, ...}. Notice the ellipsis (...) which indicates that the sequence continues, to infinity.

Task 2.2 Set comprehension

'Write' the following set comprehensions out as a sentence which describes the members of the set. If you can, write down the members of the set as well.
  • A = { 𝑥 | 𝑥 ∈ ℕ ∧ 10 ≥ 𝑥 ≥ 2 }
  • A = { 𝑥 | 𝑥 ∈ ℕ ∧ 𝑥 > 10}
  • A = { 2𝑥 | 𝑥 ∈ ℕ } 
  • A = { 𝑥2 | 𝑥 ∈ ℕ }
  • A = { 𝑥 ∈ ℝ | 𝑥 = 𝑥2 }
  • A = { 2𝑥 + 1 | 𝑥 ∈ ℤ }

OUTCOME : Written descriptions of set comprehensions


Finite and infinite sets

The ellipsis seen in the previous section indicates that the sequence of members continues for ever. This is called an infinite set. It is possible to define a finite set with a limited number of members. The first example in the previous exercise is a finite set since it only has 8 members.

All finite sets have cardinality (see above) which means their elements can be counted using natural numbers (ℕ). The cardinality of a set can also refer to the size of the set and is given the symbol # or denoted using pipe symbols around the set name, for instance |A| (magnitude). These are also referred to as countable sets. Infinite sets do not have cardinality since we do not know the total size of the set. However, for some infinite sets, it's still possible to count the elements, even though you would never reach the end. These are described as countably infinite sets as their elements can be counted off against the natural (countable) numbers.

Interesting note : The set of real numbers () is not countable.

Task 2.3 Definitions

Using the passage above, plus your textbook and possibly a web browser, write definitions for the following terms in your notebooks.
  • Finite set
  • Infinite set
  • Cardinality
  • Countable set
  • Countably infinite set
OUTCOME : Definitions for key terms.


Empty sets and empty strings

There is a special set known as the empty set which is represented by either { } or the symbol ∅. The empty set has no elements.
  • An empty set has a cardinality of zero. It does not contain zero. Consider ...

    Records = { }
    # Records = 0   ... or ...   |Records| = 0

  • An empty set is not the same as an empty string which is denoted using the lowercase epsilon, ε. A set can contain an empty string - it is a 'thing'.

    Quiet = {
    ε}
    # Quiet = 1   ... or ...   |Quiet| = 1

Task 2.4 Emptiness


OUTCOME : Nothing

Not really

Compact set notation

When defining potentially non-numeric sets, such as words in a language, things can get a little trickier. In this instance, This is a little theoretical, but read the examples s ... l ... o ... w ... l ... y and you'll be OK :)
  1. Using alphabets

    If L is a formal language (a possibly infinite set of finite length strings), the alphabet of L, given by the Greek letter sigma (Σ), is the set containing all symbols which can occur in any string in L. For any language, the set of all strings over the alphabet of length n is given by Σn.

    - For the binary 'language', 
    Σ = {0,1}
    - All two symbol length words are given by Σ2 = {00,01,10,11}
    - All three symbols length words are given by Σ3 = {000,001,010,011,100,101,110,111} ... and so on

    Sets defined in this way are usually finite (although it is possible to define infinite sets using a special notation called a Kleene Star).

  2. Using formal grammar

    We've seen examples of this with sets containing numbers (usually denoted by 𝑥). However, what if the set comprehension operated on a symbol instead? Consider the following examples ...

    - The set { an | n ∈  } represents the infinite set { a, aa, aaa, aaaa, aaaaa, ...}
    - The set { an | n ≥ 0 } represents the infinite set { ε, a, aa, aaa, aaaa, aaaaa, ...}
    - The set { 0n1n | n ≥ 1 } represents the infinite set { 01, 0011, 000111, 00001111, ...}

Task 2.5 Compact set notation

Answer the following questions
  1. If Σ = {0,1}, what is Σ3?
  2. If Σ = {x, y, z}, what is Σ2?
  3. If Σ = {A, B, C, D}, what is Σ0?
  4. Describe the set defined by { 1n | n ∈ {4, 5, 6}}
  5. Describe the set defined by { anbm | n ∈ {1, 2} ∧ m = n2 }

OUTCOME : A list of sets defined by set notation


Set operations

It is possible to perform operations on sets.
  • Cartesian product

    The cartesian product of two sets is the set of all possible ordered pairs whose first component is a member of the first set and whose second component is a member of the second set. For instance ...

    A = {1, 2, 3}
    B = {A, B}

    A x B = {{1, A}, {1, B}, {2, A}, {2, B}, {3, A}, {3, B}}
    A x B = { 𝑥, 𝑦 | 𝑥 ∈ A ∧ 𝑦 ∈ B }

    The cardinality of the resulting set is the product of the cardinalities of the two individual sets.

  • Membership

    The symbol ∈ represents set membership. For instance 𝑥 ∈ A literally means '𝑥 is a member of set A'. Conversely, the symbol ∉ means 'not a member of'.

    A = {5, 6, 7}, 6 ∈ A, 4 ∉ A

  • Union


    This operation joins two sets together so that the new set is a combination of both original sets, i.e. which belong to one set or the other. The union operation is given the symbol ∪.

    Be careful, however, because 'each value in a set can only appear once', therefore, if there are common elements in the two sets, the union of those sets will only contain the item once.

    A = {0, 1, 3, 5, 7, 9}
    B = {0, 2, 4, 6, 8}

    A ∪ B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    Notice that the element 0 appears only once in the union of A and B.

  • Intersection


    This operation joins two sets together so that the resulting set contains elements common to both, i.e. those which belong to one set and the other. Again, be aware that the resulting elements can appear only once in the new set. The intersection operation is given the symbol ∩.

    A = {1, 3, 4, 6, 7, 8}
    B = {0, 3, 5, 6, 7, 9}

    A ∩ B = {3, 6, 7}

  • Difference


    Bet you can guess this one! The difference operation joins two sets together so that the resulting set contains elements which are in either set but not in the intersection. Difference is given the symbol ∆ or ⊖.

    A = {1, 3, 4, 6, 7, 8}
    B = {0, 3, 5, 6, 7, 9}

    A ⊖ B = {0, 1, 4, 5, 8, 9}

Task 2.6 Set operations

Calculate the cartesian product of the following pairs of sets
  • A = {1, 2}, B = {1, 2, 3}
  • A = {1, 2, 3}, B = {6, 8, 7}
  • A = {a, b}, B = {1, 2}
For each element, state whether it is a member of the set P = { 2𝑥+1 | 𝑥 ∈ ℤ }
  • 3
  • 5
  • 8
State the union of the sets stated
  • {1, 0} ∪ {2, 3, 4, 5, 6}
  • {1, 10} ∪ {0, 2, 9, 10}
  • {7, 8, 1} ∪ {2, 3}
State the intersection of the sets stated
  • {3, 9} ∩ {5, 7, 3}
  • {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ∩ {4, 5, 6}
  • {20, 21, 30, 31} ∩ {1, 2, 3}
State the difference of the sets stated
  • {3, 9} ⊖ {5, 7, 2}
  • {77, 88, 99, 100} ⊖ {77, 88, 100}
  • {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ⊖ {0, 4, 5, 6}
OUTCOME : Practice examples for set operations, written up nice like.


Subsets

When all elements of one set are contained in another, it is said to be a subset, given the symbol ⊆ (notice the line at the bottom). If the subset has fewer elements than the other set, it can be further defined as a proper subset, given the symbol ⊂ (notice the absence of the line at the bottom). We can also declare sets as not being subsets (⊈) or not being proper subsets (⊄).

A = {1, 2, 3, 4, 5, 6}
B = {3, 4, 5}
C = {1, 2, 3, 4, 5, 6}
D = {5, 6, 7}

⊆A, B ⊂ A
 A, C ⊄ A
⊄ A, D ⊈ A

Take a moment to work through these statements to make sure you understand them. Note that if one set is a proper subset of another, it is also a subset. If one set is a subset of another but is not the same set then it must be a proper subset.
(A ⊆ B) ∧ (A ≠ B) → A ⊂ B

Task 2.7 Subsets

For each pair of sets, determine whether A is a subset of B. If it also a proper subset, say so.
  • A = {0, 1}, B = {0, 1, 3, 5}
  • A = {0, 9, 8}, B = {9, 8}
  • A = {1, 2, 3, 4}, B = {2, 3}
  • A = {0, 1, 2}, B = {0, 1, 2}
  • A = {0, 8, 1}, B = {6, 0, 1, 8}

OUTCOME : Identification of subsets and proper subsets.


Set comprehensions in Python

OK - how about getting Python to do some of the work for us? Python has some pretty powerful set comprehension operations which will perform many of the tasks we have looked at already. One odd thing about Python sets is that they are not ordered. The set data type is optimised for set operations not iterability. Use a list or a dictionary for that.

Before you start these exercises, create a blank word processed document with a suitable header and footer. Record what you have done and what you have learnt using a combination of screenshots and written explanations.

Task 2.8 Set comprehensions in Python


  • Open up the Python programming environment, IDLE.

  • At the prompt : First, let's create a set by typing each element individually. Type each line followed by the  Enter  key. Notice that the set is surrounded by curly braces (like a dictionary, without keys).

    >>> A = {1, 2, 3}
    >>> print(A)

    Write about what you have done in your word processed document.

  • At the prompt : Next, let's use set comprehension to create some sets without typing the individual elements. Type each line followed by the  Enter  key.

    >>> B = {x for x in range(2,10)}
    >>> print(B)
    >>> C = {x**2 for x in [2,3,4]}
    >>> print(C)

    Notice that in the last instance, the elements of C are not in order. Don't worry about this - Python sets are not lists. Note also that the elements in these sets are immutable - they cannot be changed. Write about what you have done in your word processed document.

  • Cartesian product

    At the prompt : There is no built in way of calculating a cartesian product. You have to use the itertools library. Type each line followed by the  Enter  key, twice at the end.

    >>> import itertools
    >>> D = itertools.product(A,C)
    >>> for item in D:
            print(item)

    The loop produces a list of tuples (shown in normal brackets). Tuples are immutable like sets and are the only data structure that you can store in a set - you can't store lists in a set. Write about what you have learnt.

  • Membership

    At the prompt : You can check the membership of an element in a set using the in keyword. Type the following commands, pressing the  Enter  key after each one.

    >>> 15 in C
    >>> 16 in C

    Write about what you have learnt in your word processed document.

  • Set operations

    At the prompt : Set operations work like you'd expect. Type each of the following commands, pressing the  Enter  key after each one.

    >>> E = A.union(B)
    >>> print(E)
    >>> F = E.intersection(C)
    >>> print(F)
    >>> G = C.difference(F)
    >>> print(G)

    Write about what you have learnt in your word processed document

  • Subsets

    At the prompt : The x.issubset(y) function returns True or False depending on whether x is a subset of y or not. Type the following commands, pressing the  Enter  key after each one.

    >>> F.issubset(A)
    >>> F.issubset(C)

    Write about what you have learnt in your word processed document.

Now print out your word processed document and stick it in your notebooks.

OUTCOME : Nice set of word processed notes about set comprehension in Python.


Set permutations

A permutation is another word for modification, shift or transformation. Python can perform set permutation operation on lists. For instance, the complete set of permutations of 1, 2 and 3 are ...

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

This is easier to do in Python that it might first seem, by using our old friend the itertools module! 

Before you start these exercises, create a blank word processed document with a suitable header and footer. Record what you have done and what you have learnt using a combination of screenshots and written explanations.

Task 2.9 Set permutations in Python


  • Open up the Python programming environment, IDLE.

  • First, let's create a simple set. Type the following line followed by the  Enter  key. 

    >>> A = {1, 2, 3}


    We are keeping this example close to set notation for the purposes of this section but you could do this with a list or a tuple as well. Write about what you have done in your word processed document.

  • There is no built in permutations function in the standard Python Library - we need the itertools library to help us with this task. Type the following commands at the prompt, followed by the  Enter  key, twice at the end.

    >>> import itertools
    >>> for permutation in itertools.permutations(A):
            print(permutation)

    That's it! Notice that you always get a set of tuples back from this operation. How about trying different sets and seeing what output you get?

Now print out your word processed document and stick it in your notebooks.

OUTCOME : Nice set of word processed notes about set permutations in Python.



Extension Activities 

How about these?
  • Choose one research area and write / draw / dance about it ...

    a) Find out about the irrational numbers called 'Pi', 'e', ‘Euler’s number’ and ‘the Golden Ratio’.
    b) Apart from those of 2, 3 and 99, identify some other square roots that are irrational numbers.
    c) Find out which number types are supported as data types in Python.
    d) Why do programming languages often have several different data types for an integer?
    e) The Ancient Greeks did not recognise the number zero. How did their number systems work without it?

  • Write a Haiku about number systems or sets. Remember, a Haiku has three lines; 5 syllables, 7 syllables and 5 syllables. Often, the first two lines are upbeat and connected and the last line gives a little twist in the tale. The best ones will go on display.

  • Two sets of numbers we haven't mentioned are the Algebraic Numbers (𝔸) and the Transcendental Numbers. What are they? Give some real world examples.

  • The characters used to represent the sets are called "double struck characters" or "blackboard font". Read the Wikipedia article about this, for a bit of fun.

  • Full(ish) list of set symbols.

  • Great website which produces automatic set stuff.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT