s5cs04 formal number systems

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!

We know what's coming, don't we?

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'.

Let it snow, let it snow!

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 (but not beyond).

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 setI have no idea what this means. It is possible to define a finite setI have no idea what this means 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 cardinalityI have no idea what this means (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| (sometimes magnitude). These are also referred to as countable setsI have no idea what this means. 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 setsI have no idea what this means 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 an actual 'thing'.

Quiet = {ε}

#Quiet = 1 ...or... |Quiet| = 1

Task 2.4 Emptiness

OUTCOME : Nothing

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 :)

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).

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 in your notebook.

If Σ = {0,1}, what is Σ3?

If Σ = {x, y, z}, what is Σ2?

If Σ = {A, B, C, D}, what is Σ0?

Describe the set defined by { 1n | n ∈ {4, 5, 6} }

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, x

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, ∈ and non-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} so 6 ∈ A and 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, ∆ or ⊖

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 | 𝑥 ∈ ℤ }

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 subsetI have no idea what this means, 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 (⊄).

For example, if we define...

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

Then we can state...

B ⊆A, B ⊂ A
C ⊆ A, C ⊄ A
D ⊄ 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

Start by 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 immutableUnable to be mutated or changed. - 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.

Print out your work for checking

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

Start by open up the Python programming environment, IDLE.

Create a simple set

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.

Import the itertools library and get those permutations!

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?

Print out your work for checking

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?

Research

Choose one research area and write / draw / dance about it ...

Find out about the irrational numbers called 'Pi', 'e', ‘Euler’s number’ and ‘the Golden Ratio’.

Apart from those of 2, 3 and 99, identify some other square roots that are irrational numbers.

Find out which number types are supported as data types in Python.

Why do programming languages often have several different data types for an integer?

The Ancient Greeks did not recognise the number zero. How did their number systems work without it?

Haiku

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.

Hey man - what other number sets are there?

Two sets of numbers we haven't mentioned are the Algebraic NumbersI have no idea what this means (𝔸) and the Transcendental NumbersI have no idea what this means. What are they? Give some real world examples.

Double struck

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. Then take a gander at this full(ish) list of set symbols.

Automaticity

Great website which produces automatic set stuff.

It's a mystery

Can you work out what these Python functions do? It would be great if you could because I've completely forgotten! The second one looks like recursion to me...

def permutate(values, size):
  return map(lambda p: [values[i] for i in p], permutate_positions(len(values), size))

def permutate_positions(n, size):
  if (n==1):
    return [[n]]
  unique = []
  for p in map(lambda perm: perm[:size], [ p[:i-1] + [n-1] + p[i-1:] for p in permutate_positions(n-1, size) for i in range(1, n+1) ]):
    if p not in unique:
      unique.append(p)
  return unique

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.

Last modified: April 9th, 2024

Login

s5cs04 formal number systems

Extension Activities