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 $\mathbb {R}$: The Real Numbers $\mathbb {C}$: The Complex Numbers

The Natural Numbers are the set of non-negative and non-zero integers $\{1,2,3,4,\ldots \}.$ The Integers are all the natural numbers, their negative counterparts and zero $\{\ldots ,-2,-1,0,1,2,\ldots \}$. 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{\mbox{ 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{\mbox{ 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\land s\in B\}$.

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

If $S\subset A$, the set $A-S=\{s:s\in A\land 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\Delta B)\Delta C=A\Delta (B\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,\qquad 1-(2-3)=2$

Commutativity

A composition Δ is said to be commutative if:

$A\Delta B=B\Delta A$

For instance, multiplication is commutative because:

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

Notice that division is not commutative:

$2\div 3={\frac {2}{3}},\qquad 3\div 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\Delta x=x\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\Delta f=e$

$f\Delta e=f$

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

Ordered Pairs

Most readers should recognize the ordered coordinate pairs from the cartesian coordinate graphing system as an ordered pair of values, (x,y).

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}{\mbox{ 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,\qquad (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},\ldots a_{n})$

Answer

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