Abstract Algebra/Sets and Compositions

A set is a grouping of values, and are generally denoted with upper-case letters. For instance, let's say that A is the set of all first names that start with the letter 'A'. From this definition, we can see that "Andrew" is a member of set A, but "Michael" is not.

Sets

Common Sets

Here are some of the common sets:

$\mathbb{N}$: The Natural Numbers $\mathbb{Z}$: The Integers $\mathbb{Q}$: The Rational Numbers $ℝ$: The Real Numbers $ℂ$: The Complex Numbers

The Natural Numbers are the set of non-negative and non-zero integers $\{1,2,3,4,\dots \}.$ The Integers are all the natural numbers, their negative counterparts and zero $\{\dots ,-2,-1,0,1,2,\dots \}$. The Rational numbers are all the numbers that can be formed as a fraction of two integers with a non-zero denominator. The Real numbers include the rational numbers, and also includes all the numbers that cannot be formed as a ratio of two integers. The Complex numbers are all the numbers that involve the imaginary number, i. Notice that C can contain numbers that are imaginary (no real part), real (no imaginary part) and complex (real and imaginary parts).

Set Notation

Frequently, it is required that we define a set by a specific mathematical relationship. For instance, we can say that we want to define the set of all the even integers. Since $\mathbb{Z}$ is the set notation for integers, we can say:

$\{x\in \mathbb{Z}:x\text{ mod }2=0\}$

In English, this statement says "All x in set $\mathbb{Z}$ such that x modulo 2 equals zero". Or, if we are not familiar with the modulo operation, it is perfectly acceptable to use plain English when defining our set:

$\{x\in \mathbb{Z}:x\text{ is even}\}$

The colon (:) here is read as "such that". This notation will come up a lot in the rest of this book, so it is important for the reader to familiarize themselves with this.

$a\in A$ denotes that $a$ is an element of A.

Set Operations

A subset S of a set A is a set such that $s\in S\to s\in A$. This is denoted as $S\subset A$.

The intersection of two sets A and B is the set $A\cap B=\{s:s\in A\wedge s\in B\}$.

The union of two sets A and B is the set $A\cup B=\{s:s\in A\vee s\in B\}$.

If $S\subset A$, the set $A-S=\{s:s\in A\wedge s\notin S\}$.

Cartesian Product

A cartesian product between two sets shows the domains of two or more variables. For instance, if we have the variables x and y, and the sets A and B, we can use the cartesian product to show the domains of x and y in terms of A and B:

$A\times B=\{(x,y):x\in A,y\in B\}$

Compositions

Compositions are operations on a set that act on numbers of the set, and return a value that is in that same set, that is if $A$ is a set, a composition is a function $*:A\times A\to A$

For instance, addition between two integers produces an integer result. Therefore addition is a composition in the integers. Whereas division of integers is an example of an operation that is not a composition, since $1/2$ is not an integer.

If we have a set $A$, we say that a composition acts on $A\times A$ and produces a result in $A$. This is also known as closure.

Associativity

A composition Δ is said to be associative if:

$(A\mathrm{\Delta }B)\mathrm{\Delta }C=A\mathrm{\Delta }(B\mathrm{\Delta }C)$

For instance, the addition operation is an associative operation over the integers, Z:

$(1+2)+3=6=1+(2+3)$

Notice however, that subtraction is not associative:

$(1-2)-3=-4,1-(2-3)=2$

Commutativity

A composition Δ is said to be commutative if:

$A\mathrm{\Delta }B=B\mathrm{\Delta }A$

For instance, multiplication is commutative because:

$2\times 3=6=3\times 2$

Notice that division is not commutative:

$2÷3=\frac{2}{3},3÷2=\frac{3}{2}$

Neutral Element

A Neutral Element (or Identity) is an item in E such that a composition in E $\times$ E into E returns the other operand. For instance, say that we have a composition Δ, a neutral element $e\in E$, and a non-neutral element $x\in E$. If Δ is commutative, we have the following relation:

$e\mathrm{\Delta }x=x\mathrm{\Delta }e=x$

For instance, in addition, the neutral element is 0, because 1 + 0 = 1. Also notice that in multiplication, 1 is the neutral element, because 1 × 2 = 2.

Each composition may have only one neutral element, if it has any at all. To prove this fact, let's assume a composition Δ with two neutral elements, e and f:

$e\mathrm{\Delta }f=e$

$f\mathrm{\Delta }e=f$

But since e and f are commutative under Δ by definition, we know that e = f.

Ordered Pairs

Ordered pairs are artificial constructions where we set two values into a specific order. More formally, we can define an ordered pair as the set
$(a,b)=\{\{a\},\{a,b\}\}$

Let's say that we have two ordered pairs, A and B, comprised of values $a_1,a_2,b_1$ and $b_2$ respectively:

$A=(a_1,a_2)$

$B=(b_1,b_2)$

We can see that $A=B$ if and only if

$a_1=b_1\text{ and }{a}_2=b_2$

Functions

A function is essentially a mapping that connects two values, x and y. We use the following notation to show that our function f is a relationship between x and y:

$(x,y)\in f$

Notice that x and y form an ordered pair: If we reverse the order of x and y, the relationship will be different (or non-existent). We say that the set of possible values for x is the domain, D, of the function, and the set of possible y values is the Range, R.

In other words, using some of the terms we have discussed already, we say that our function f maps from "D × R into R".

Inverses

If f is a function in D × R, to R, then f⁻¹ is the inverse of f if it is in R × D to D, and the following relationship holds:

$(x,y)\in f,(y,x)\in f^{-1}$

Exercise

• Of the four arithmetic operations, addition, subtraction, multiplication, and division, which are associative? commutative?
• Using the definition of the ordered pair as a model, give a formal definition for an ordered n-tuple: $(a_1,a_2,\dots a_n)$

Answer

operation	associative	commutative
Addition	yes	yes
Multiplication	yes	yes
Subtraction	No	No
Division	No	No