ACIT4330-Page/content/Lectures/Lecture 1 - 1.1 Sets and Numbers.md

lecture, date

lecture	date
1	2025-01-06

Prime Numbers

\mathbb{N} = \{1,2,3,\dots\} (natural numbers)

Prime Number - p \in \mathbb{N} \setminus \{1\} only divisible by 1 and p.

They are building blocks for multiplication; for instance 90 = 9 \times 10 = 3 \times 3 \times 2 \times 5 = 2 \times 3^2 \times 5 = 5 \times 3^2 \times 2

p \times q = p' \times q'

\implies (need proof #Theorem 1.1.1)

p = p' \; \cap \; q=q'

p = q' \; \cap \; q = p'

Theorem 1.1.1

Any natural number other than one is a product of unique primes

Proof Existence

Divide as long as possible Uniqueness (Gauss): Need Euclid's lemma, saying that If n|ab with gcd(a,b) = 1, then n|a or n|b.

This lemma follows from the axiom: Each non-empty subset of \mathbb{N} has a least element/number.

QED

COR 1.1.2

There are infinitely many primes.

Proof

Say we had finitely many primes p_{1}, \ldots, p_{n}. Applying #Theorem 1.1.1 to p_{1} \times p_{2} \times \ldots \times p_{n} + 1 gives the absurdity that 1 can be divided by some prime number

This is impossible as for example p_{1} \times p_{2} \times \ldots \times p_{n} + 1 and p_{1} \times p_{7} \times p_{n}, you can divide both sides by something like p_{1}, however on the LHS with + 1 would result in + 1 \frac{1}{p_{1}}

QED

Statements

These are mostly similar to logic in computer science with And, Or, Not, and Implies.

Sets

A set X is characterised by its elements or members x \in X.

They can be listed like \{1,5,4\}, or described by some property, like the set of all primes, or like X = \{x | P(x)\}; here x is from the outset supposed to belong to some (universal) set. Otherwise X = \{ x | \notin X \} (Russel's paradox) - which is not allowed. X = \{ x \in | x > 7\} - which is OK!

Y \subset means x \in Y \implies x \in X

Get \emptyset \subset X

Union

The union \cup_{i \in I} X_{i} consists of x \in X_{i} for at least one i \in I

Disjoint union when X_{i} \cap X_{j} = \emptyset for all possible i and j.

Intersection

The intersection \cap_{i \in I} X_{i} consists of x \in X_{i}, \; \forall i \in I

Complement

The complement X \setminus Y of Y in X consists of x \in X \cap x \notin Y Write Y^\complement (a complement of Y) when X is understood.

Product

The product X \times Y consists of the ordered pairs

(x, y) \neq (y, x) \equiv \{ \{ y \}, \{ y, x \} \}

(x \in X and y \in Y)

(x,y) = (x', y') \iff x = x' \cap y = y'

A more compact way of writing this: X \times Y = \{ (x, y) | x \in X \cap y \in Y \}

Relation

A relation on a set X is R \subset X \times X with xRy \equiv ((x,y) \in R). (R here meaning is related to)

Example

R= \{ (x, x) | x \in X \} \subset X \times X, xRy \iff (x, y) \in R \implies x = y. These two elements x and y can only relate if they are the same.

Equivalence Relation

An equivalence relation 0 \sim X is a relation on \sim on X such that:

1. x \sim x
2. x \sim y \implies y \sim x
3. (x \sim y) \cap (y \sim z) \implies x \sim z For all x,y,z \in X.

It partitions X into a disjoint union \frac{X}{\sim} of equivalence classes [x] \equiv \{ y \in X | y \sim x \}, with x called a representative of [x] (equivalence class).