Basic algebraic structures

HEGL Illustrating Mathematics Seminar
Winter Semester 2024-2025

Jonas Schäfer and Hannah Rothe
Heidelberg University

Why constructive algebra?

• Law of excluded middle.

• Axiom of choice.

• Being mindful of them.

Recall from last talk

• Sets and logic.

• Denial inequality and decidability.

Structure of the talk

• Monoids and groups.

• Rings and fields.

• Heyting fields.

• Introduction to Euclidean algorithm.

Definition of a monoid

Be a set and :

• "Multiplication", meaning that, .
• Associative law, meaning that, .
• Identity, meaning that, so that: .

In a "multiplicative monoid", is often denoted by . In an "additive monoid", by .

Abelian monoid

, .

Unit

:

• b is an inverse of a, meaning that: .

• We also write .

• Then a is a unit, meaning that it is invertible.

Definition of a group

• "Next step" after monoids.

• Every element is a unit.

• | is invertible .

Possible project

Show that the set of units of a monoid is a group.

• | is invertible is a group.

Definition of a ring

A ring is an additive abelian group R which is also a multiplicative monoid.

• is a group and is a monoid.

• "Distributive laws", meaning that:

• .

• .

• Trivial if .

Commutativity

is an abelian monoid.

• .

Division ring

• iff is a unit.

• Denial inequality .

• Traditionally: every element is a unit except 0.

Definition of a field

• Commutative division ring.

• Example: .

Decidable fields

• A decidable field is a decidable commutative ring such that and .
• For instance, the set carries a structure of decidable field.
• Note that if is a decidable field and is a unit, then .

Problem with decidability

• Not every set is decidable regarding the denial inequality.

• In general, the denial inequality "" is neither co-transitive nor tight.

• Example after explanation of "co-transitive and tight".

Apartness

• Irreflexivity, meaning that, .

• Symmetry, meaning that, .

• Co-transitivity, meaning that, .

• Tightness, meaning that, .

Definition of a Heyting field

• A Heyting field is a commutative ring equipped with a tight apartness relation such that and .
• Every decidable field can be turned into a Heyting field because on a decidable set, the denial inequality is a tight apartness relation (Project?).
• Not every Heyting field is a decidable field: the set of real numbers does not have decidable equality but carries a structure of Heyting field.

Constructive point of view

• Of course, if we assume LEM, then every field is decidable.

• Replace denial inequality with a tight apartness.

• The ring is a Heyting field.

Rational numbers

• is decidable field.

• are decidable in .

• Define commutative ring C: Cauchy sequences in .

• Define I: Zero sequences in ,
  I is ideal in C.

Real numbers

• Define is ring.

• = not decidable in , so denial inequality no tight appartness.

• Want to define distinctness using .

Distinctness on

• iff
  .

• Define .

• We can show: is Heyting field with .

Intro to Euclidean algorithm

• We state the Euclidean algorithm for discrete (=decidable) commutative rings with recognizable units, rather than just for discrete fields.

Recognizable units

• A ring is said to have recognizable units if its units form a detachable subset.

• In other words: The units are recognizable if the membership of the elements are decidable.

Example

• is a discrete commutative ring (Project?).

Polynomial ring

• Define Polynomials in one indeterminate over a ring as .

• For define n-1 degf iff
  f = .

• For define degf n iff
  f = and for some i n.

Degree of a polynomial

• For define degf = n iff
  degf n and n degf.

• Define degf = -1 iff degf -1.

• For define degf degg iff
  it holds that degg n implies degf n-1.

Existence of degree

• Possible project: If R discrete + commutative Ring, every polynomial has a degree.

• If R not discrete, statement does not hold.

Proof (1): Existence of degree for discrete ring R

For , let (*n) be the statement:
.

• n=0: It follows degf degf=k-1 for k=0

Proof (2): Existence of degree for discrete ring R

• Assume (*n) for .
• Let .
• Set : deg = k-1.
• R discrete 1) or 2) .

1. .

2. degf, and
   degf n by definition
   degf=n.

Proof (3): Existence of degree for discrete ring R

• By Induction it follows: (*n) holds .

• Let R: f = (with (*n)): .

Proposition: division algorithm

• Let R commutative ring, such
  that degf m and degg .
• Let a be the coeficcient of in g
  R[X]: .

Proof: division algorithm

Induction on m:

• m=n-1: Set .
• : Assume proposition for := m-1.
  • Write .
  • Set = af-.
  • .
  • .
  • Proposition holds with .

Proposition: division algorithm in discrete ring

• Let R be discrete commutative ring, f,g R[X], leading coeficient of g be 1.

• .

• Corollary: In discrete field, g can have any leading coefficient.

Proof of existence: division algorithm in discrete ring

• .
• Set m=max{n-1,k-1} .
• Existence from first proposition.

Proof of uniqueness: division algorithm in discrete ring

• Let R[X] such that they fulfil proposition.
  (*)
  R discrete such that .

• Natural numbers discrete Case analysis:

  1. False (because of (*)) .

  2. k=0 and .

Summary

• Basic algebra until we hit a wall with fields.

• Forced to be more precise with definition.

• Define a more general notion of field namely the Heyting field, is Heyting field that is not decidable.

• New definition equivalent to traditional one if we assume LEM.