SEMINAR: Groups and Combinatorics Seminar: Combinatorial counting principles in axiomatic number theory


Groups and Combinatorics Seminar: Combinatorial counting principles in axiomatic number theory 
Other events...

Groups and Combinatorics Seminar
Alan Woods (UWA)
will speak on
Combinatorial counting principles in axiomatic number theory
at 1pm on Friday 11th of November in Maths Lecture Room 2
Abstract: Proofs of even simple statements in number theory are
notorious for being ``tricky''. They often seem to involve concepts
that go well beyond what is needed to state the theorem. Is there
some way of systematically characterising the assumptions
(``axioms'', if you will) required?
It has long been recognised that full Peano Arithmetic (as
sometimes briefly encountered in first or second year courses) is
actually significantly stronger than what is needed for everyday
number theoretic practice (or for that matter, the typical finite
combinatorics or finite group theory seminar). An alternative is the
axiom system similar to Peano Arithmetic, but with induction
hypotheses restricted to being arithmetic formulas having only
bounded quantifiers, i.e., ``there exists'' occurs only in the form
``there exists y < x'', and ``for every'' occurs only in the form
``for every y < x''. Such a bounded formula can only ``talk about''
numbers bounded above by the free variables appearing in it. There
is a long list of theorems of elementary number theory for which no
proof from this weaker axiom system is known, and yet which are
provable if, for a suitably chosen bounded arithmetic formula A(x),
one adds a census function c(n)={x: x < n and A(x)} counting how
many numbers x less than n have the property A(x), and allows
induction on bounded quantifier formulas containing c.
Using census functions one can also prove certain combinatorial
principles, notably versions of the pigeonhole principle and the
equipartition principle  a phenomenon which facilitates some
of the applications to number theory.
Examples surveyed briefly should include: the existence of
arbitrarily large primes (including recently published joint
work with Cornaros), the index of the subgroup of squares
in the multiplicative group (mod p) for p prime, Lagrange's
four squares theorem, and Jerabek's recent proof of the
Quadratic Reciprocity Law which is arguably the logically
simplest known proof of this theorem of Gauss.
Speaker(s) 
Alan Woods

Location 
Maths Lecture Room 2


Contact 
Michael Giudici
<[email protected]>

Start 
Fri, 11 Nov 2011 13:00

End 
Fri, 11 Nov 2011 13:45

Submitted by 
Michael Giudici <[email protected]>

Last Updated 
Wed, 09 Nov 2011 12:47

Included in the following Calendars: 

 Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
 Download this event as:
Text 
iCalendar

Mail this event:
