# 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

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$^{−1}$ 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 |