User abo - MathOverflow

Answer by abo for Should I mention my study of set theory when applying for a job outside of university?

2013-06-09T13:31:25Z

Of course you should. If you're applying for jobs that require an understanding of some type of mathematics (e.g. statistics), then it's not your knowledge of set theory which will hurt but your lack of knowledge of that type of mathematics, which will come out in the interview anyway (if you do lack it - maybe you took a course in that area, in which case you should mention it). If the job doesn't require an understanding of some specific type of mathematics, then IMHO any mathematics degree will be considered the same.

Far more important, IMHO, is the attitude which you present what you have done. You should avoid saying, It was a waste time, I should have studied something more practical. Instead you should present it as a means of improving yourself and advancing your goals. (I studied set theory because I was most passionate about it. Mathematics allowed me to become a more rigorous thinker. Writing a dissertation developed my skills at working on a long-term project. Although mathematics might seem individualist, at my university there was a lot of activity, and it shows I work well in a team. etc.)

Answer by abo for One can earn nothing on the Brownian motion, true ?

2013-06-02T19:09:26Z

Unless I'm missing something, discrete time and the lack of transaction costs mean that your question boils down to whether there is any strategy such that, after 1 time unit only, one can expect a profit. (A simple induction argument suffices to show this.) If that's true, then a symmetric distribution, where the probability of loss equals the probability of profit after 1 time unit, implies that expected profit will always be 0.

Answer by abo for Reference request: Minimal Axiomatizations of PA over (+,x,<=).

2013-05-19T10:06:21Z

This should probably be a comment, but it will be too long.

Here's an axiomatization. From the wikipedia page you cite, I replace 1 and 5 with weaker axioms. I suppress 2,3 4,7, 11, 12 and 15. I replace 8,9, and 10 with the single assumption of anti-symmetry. I strengthen 13 by replacing implication with a sort of iff. I keep the others. And then I add the well-ordering schema as you state it. That is, assume:

x + 0 = x
x + (y + 1) = (x + y) + 1
x * 0 = 0
x * (y + 1) = x * y + x
x ≤ y & y ≤ x $\implies$ x = y
x ≤ y $\implies$ $\exists$z (z + x = y)
$\exists$z (x + z = y & $\neg$ z = 0) $\implies$ x < y
$\neg$ x = 0 $\implies$ 1 ≤ x
$\neg$ 1 = 0
$\exists x\phi(x)\implies\exists x\left(\left(\phi(x)\wedge \forall y(\phi(y)\implies x\leq y)\right)\right)$

Prop. (Induction) $\left(\phi(0)\wedge\forall x\left(\phi(x)\implies\phi(x+1)\right)\right)\implies\forall x\phi(x)$
Pf: Suppose $\phi$(0) & $\forall$x($\phi$(x) $\implies$ $\phi$(x+1)). And suppose $\neg\forall$ x $\phi$(x), i.e. $\exists$x$\neg$$\phi$(x). By 10.
$\neg\phi$(c) & $\forall$y($\neg\phi$(y) $\implies$ c ≤ y)) for some c. $\neg$ c = 0, so by 8. 1 ≤ c. By 6. (z + 1) = c for some z. By 7. and 9. z < c. If $\phi$(z) then $\phi$(c) by the induction hypothesis, contradiction. Hence $\neg\phi$(z). Thus c ≤ z. By 5. z = c, contradiction. QED.

Once you have induction you can prove commutativity and associativity of addition and multiplication, and the other Wikipedia axioms should follow.

I have no idea what is known on this, however (or even whether it is worth knowing). It may well be possible to assume less.

Answer by abo for Is there any straightforward way to substitute for Gaussian/Brownian assumptions in financial mathematics?

2013-03-01T18:23:27Z

Heavy-tailed distributions are already de facto used by almost all financial companies, because they use smiles (different volatilities are assigned to different strikes). For instance in equity options lower and lower strikes are usually assigned higher and higher volatilities. If you back out the implied distribution, you get a distribution with a fat tail.

Answer by abo for Why Does Induction Prove Multiplication is Commutative?

2013-02-19T20:55:18Z

This is an answer to the edited questions Russell has added. Joel David Hamkins' reply in comments to the question is completely correct, but I'll take advantage of the greater space here.

Let (R,0,1,+,*) be a ring. Define

Sx = x + 1 and

B = {x | $\forall P(P0 \land \forall y\forall z(Py \land Sy,z \to Pz) \to Px)$}

i.e. B is the set of all x which are part of an S-chain beginning with 0.

Then S is functional and induction holds over B, i.e.

$\forall P(P0 \land \forall y\forall z(Py \land Sy,z \to Pz) \to \forall x (Bx \to Px))$.

One can define ++ and ** (both definitions being on B) from S using the normal recursive definitions, both of which can be proved commutative. By induction over B, one can show that + and ++ define the same function on B; also for * and **. Hence, if B = R, then * is commutative. So if R is a non-commutative ring, then B is properly contained in R.

"Can we prove induction fails in every non-commutative ring?" No. There are definitions of the successor function (see my other answer) so that induction will hold. OTOH, in a non-commutative ring R where the successor is defined as Sx = x + 1, induction will fail, because the set B (as defined above) cannot equal all of R. To see that induction fails, consider the predicate phi(n) to be Bn. Then clearly phi(0) and the inductive step holds, but obviously not phi(n) for all n in R.

"Is it impossible to define a successor chain that visits every ring element using addition in a non-commutative ring?" I'm not sure what you mean by this question. If successoring is defined by Sx = x + 1, then the successor chain isn't defined, it's implied (by the definition). You won't be able to prove that the successor chain is the entire ring, because again that would imply that multiplication is commutative, contrary to assumption.

Answer by abo for Why Does Induction Prove Multiplication is Commutative?

2013-02-17T15:57:45Z

This is not an answer to your question but, I hope, an answer to your confusion.

Consider 2 x 2 matrices whose elements are from the set {0,1}. Endowed with the usual addition and multiplication, the set of such matrices forms a non-commutative ring.

Now there are a finite number of elements in this set, 16 in all, so one can define a successor function arbitrarily, by choosing a first element, then a next, and so on, and touching every element in the set. For instance, one can define:

S $\begin{bmatrix} 0 &0 \cr 0& 0 \end{bmatrix}$ = $\begin{bmatrix} 0 &1 \cr 0& 0 \end{bmatrix}$

S $\begin{bmatrix} 0 &1 \cr 0& 0 \end{bmatrix}$ = $\begin{bmatrix} 0 &0 \cr 1& 0 \end{bmatrix}$

S $\begin{bmatrix} 0 &0 \cr 1& 0 \end{bmatrix}$ = $\begin{bmatrix} 0 &0 \cr 0 & 1 \end{bmatrix}$

S $\begin{bmatrix} 0 &0 \cr 0& 1 \end{bmatrix}$ = $\begin{bmatrix} 1 &0 \cr 0 & 0 \end{bmatrix}$

...

S $\begin{bmatrix} 1 &1 \cr 1&1 \end{bmatrix}$ = $\begin{bmatrix} 0 &0 \cr 0 & 0 \end{bmatrix}$

Now, if one uses this definition of succession, then the axioms of GA will hold, because (1) as we've said this successoring is a function; and (2) because every element has been included in the successoring chain, induction holds. However, the addition (call it ++) which is induced by this successoring is not normal matrix addition (call this +). For instance

$\begin{bmatrix} 0 &1 \cr 0& 0 \end{bmatrix}$ + $\begin{bmatrix} 0 &1 \cr 0&0 \end{bmatrix}$ = $\begin{bmatrix} 0 &0 \cr 0&0\end{bmatrix}$



while

$\begin{bmatrix} 0 &1 \cr 0& 0 \end{bmatrix}$ ++ $\begin{bmatrix} 0 &1 \cr 0&0 \end{bmatrix}$ = $\begin{bmatrix} 0 &0 \cr 1&0\end{bmatrix}$

Similarly the multiplication induced by this successoring is not normal matrix multiplication. You will find that the induced multiplication is in fact commutative, while (of course) matrix multiplication is not.

Is an ultrafinitist Hilbert's program doomed?

2013-01-29T20:57:47Z

Hilbert's program is popularly understood as an attempt to justify infinitary mathematics with a finitary consistency proof. Godel's Second Theorem is usually considered as showing this is not possible.

Question (to be made precise below): Can finitary mathematics be justified with a ultrafinitistic consistency proof?

Consider FPA, a multi-sorted first-order theory, with lower-case or small letters (for numbers) and upper-case or big letters for relations of n-arity (n >= 1). (Practically, I think one can limit the theory to relations where n = 1, 2, or 3.)

Full comprehension is assumed.

FPA has a constant symbol 0, a 1-ary relationship N (natural number), and a 2-ary relationship symbol S (successoring).

In this context the Peano Axioms can be written:

(PA1) N0
(PA2) $\forall$n (Nn $\Rightarrow$ $\exists$m (Nm & Sn,m))
(PA3) $\forall$n$\forall$m$\forall$m' (Nn & Nm & Nm' & Sn,m & Sn,m' $\Rightarrow$ m = m')
(PA4) $\forall$n$\forall$m$\forall$n' (Nn & Nm & Nn' & Sn,m & Sn',m $\Rightarrow$ n = n')
(PA5) $\forall$n (Nn $\Rightarrow$ $\neg$ Sn,0)
(PA6) $\forall$P (P0 & $\forall$n$\forall$m(Pn & Sn,m $\Rightarrow$ Pm) $\Rightarrow$ $\forall$n(Nn $\Rightarrow$ Pn))

FPA assumes all the Peano Axioms except (PA2), that is, everything except the totality of the successor relationship. It has as its standard models all the initial segments as well as the standard model of the natural numbers. {0} is a model. It is therefore agnostic as to whether the natural numbers go on and on. Let's call it "ultrafinitistic" even if it's not always clear to me what "ultrafinitistic" means.

Now an ultrafinitistic Hilbert's Program might be the following. Let E(n) be the wff
$\exists x_1 \exists x_2 ... \exists x_n$(N$x_1$ & S0,$x_1$ & N$x_2$ & S$x_1,x_2$ & ... & S$x_{n-1},x_n$)
i.e. the assertion that the number n exists. The ultrafinitistic hope would be that FPA can prove the consistency of FPA + E(n) for any n, or even (this would be magical) prove the assertion
$\forall$n Cons(FPA + E(n)).

Now in one sense of consistency, where like Godel one uses numbers to represent sequences, one can actually get started on this. Restricting the arities of the upper-case letters to no more than 3 (which is sufficient to develop the appropriate apparatus), it seems that FPA can prove the Godel consistency of FPA + E(1) and FPA + E(2).

However, the proof works with a certain cheat; Godel numbering uses numbers so big that the assumption that there is a proof leading to a contradiction implies the existence of a truly big number, which provides enough space for creating a model of true-in-{0,1} or true-in-{0,1,2} for propositions whose length are <= the length of the longest proposition appearing in the proof of contradiction. A more appropriate manner of representing consistency would surely be to use the upper-case letters, since then a sequence of length n only implies the existence of n, which is obviously much smaller than the Godel number. Let RCons(FPA) and the like represent this notion of consistency.

According to http://mathoverflow.net/questions/120150/can-fpa-really-prove-its-consistency whether FPA can prove RCons(FPA) is equivalent to a well-known open problem which is conjectured to be false. Obviously, this does not bode well for FPA proving stronger systems to be RCons consistent. Still, "open" brings hope, so my questions are:

(1) Can it be shown, for any n, that FPA does not prove RCons(FPA + E(n))?
(2) If so what is the smallest n?
(3) If not can it be shown that FPA cannot prove $\forall$n Cons(FPA + E(n)) ?

If something significant can be said with a different formula asserting the existence of a number other than E(n) (e.g. defined using an exponential), that would obviously be of interest. (EDITED ADDITION: The restriction of upper-case letters to arity 3 or less is welcome, especially if a "yes" answer plays on unbounded arity.)

Since this is my third question about this theory, I would also like here to refer to this question/answer, where the models (and other details) of FPA are described: http://mathoverflow.net/questions/119919/provability-in-second-order-arithmetic-without-the-successor-axiom so with one search I can later find everything.

Thanks for your time.

Can FPA really prove its consistency?

2013-01-28T22:03:48Z

I will ask the question first and then explain.

QUESTION: FPA can prove its own consistency in the Godelian sense. But can it really prove its consistency?

FPA is a multi-sorted first-order theory, with lower-case or small letters (for numbers) and upper-case or big letters for relations of n-arity (n >= 1). (Practically, I think one can limit the theory to relations where n = 1, 2, or 3.)

Full comprehension is assumed.

FPA has a constant symbol 0, a 1-ary relationship N (natural number), and a 2-ary relationship symbol S (successoring).

In this context the Peano Axioms can be written:

In FPA it is possible to define formula for addition, multiplication, less than, exponentiation, and, except obviously for totality and any related property, prove the usual properties. Intuitively, the existence of a natural number n implies that every number less than n exists.

Predicates for numbers can be defined:
one(n) if and only if S0,n & Nn,
two(n) if and only if $\exists$x (one(x) & Sx,n) & Nn
Obviously one cannot prove there exists any n such that one(n). But if such an n exists, then one can show it has all the usual properties of 1. Similarly for two, three, etc.

FPA proves the Fundamental Theorem of Arithmetic.

Recursion is available and it is possible to define formula expressing syntax in the Godel fashion. For instance, Term1(n) ("n is a lower-case term") might be defined as: seven(n) $\vee$ $\exists$y$\exists$z (+(y,y,n) & eleven(z) & z >= n). (Seven(n) expresses n is 0, and the lower-case variables are the even numbers >= eleven.)

One can continue and define a formula GProof(n,x) which says that n is the Godel number of a proof in FPA of a wff whose Godel number is x. Letting $\mathcal{F}$ be "$\neg$ 0 = 0", then GCons(FPA) is the formula:
$\neg$ $\exists$p (GProof(p,$\mathcal{F}$))

But FPA proves GCons(FPA). Intuitively the reasoning goes like this. Suppose $\neg$ GCons(FPA). Then there is a number p such that GProof(p,$\mathcal{F}$). But, because of the nature of Godelization, and its use of a single number to represent sequences of numbers via exponentiation, this is a very big number, easily bigger than what is required to define "true in {0}" for all propositions of length smaller than the propositions in the purported proof. FPA can show the axioms are true in {0}, that the deduction rules preserve truth in {0} for all steps in the proof, but of course $\mathcal{F}$ is not true in {0}. Contradiction, so FPA proves GCons(FPA).

Well this does seem like a bit of a cheat, because it uses the fact that Godelization, by using numbers to represent sequences, needs very big numbers. Instead of lower-case numbers to code a sequence, one can use upper-case letters: R is a sequence if and only if dom(R) is {x : x <= n} for some natural number n. One can then redefine a formula RProof(R,S) which says that R is a sequence representing a proof of the proposition represented by the sequence S. And define a new formula RCons(FPA).

The question is: does FPA prove RCons(FPA)?

The proof for the Godelization formula doesn't go through because now only a small number (the length of the proof) is implied, and this is not enough, at least prime facie, to construct a model of true-in-{0} for the propositions in the proof. To show that FPA proves RCons(FPA), it would suffice to show that any proof of an inconsistency would have to be very, very long. To show that FPA doesn't prove RCons(FPA), maybe Godel's original proof would go through, but this makes me nervous, because of the problem with GCons(FPA).

Sorry for the long question, but any help appreciated!

Provability in Second-Order Arithmetic without the Successor Axiom

2013-01-26T06:53:24Z

Consider second-order Peano Arithmetic Z2, i.e. the two-sorted first-order theory with induction and comprehension. Remove the assumption about the totality of the successor relationship (the Successor Axiom), i.e. the assumption that every number is successored by a number. Call this theory FPA. FPA has as models the standard model (if it exists) and all the initial segments. FPA is "downward": if a natural number exists, it can prove all numbers less than that number exists, but none that are greater. So it cannot prove the infinity of the primes, but then this assertion isn't even true in all its models, e.g. {0,1,2,3} has two primes, and 2 is a member of the set, so the set of primes is finite in this model. FPA can, however, prove Bertrand's Postulate.

Are there any simple mathematical examples of assertions true in all models of FPA, provable in Z2, but not provable in FPA?

EDIT: On François' advice, I am adding here some clarifications which appear in comments.

Full comprehension is used.

Successoring is considered to be a 2-ary relationship, addition and multiplication to be 3-ary relationships. The usual axioms can be easily restated in these terms.

The logic is supposed to include variable n-ary relationships, for n = 1 but also for n > 1, which can be quantified over and whose existence can be proved using comprehension. So for instance, FPA is able to define size equivalence in the straightfoward fashion: A ~ B if and only if (there exists R)(R is a 1-1 function from A onto B). (In fact, given this apparatus, addition and multiplication can be defined from successoring, so one doesn't even need axioms about addition and multiplication, although this is a detail which should not affect the question asked.)

Induction can be considered to be: (P)(P0 & (n)(m)(Pn & Nn & Sn,m => Pm) => (n)(Nn => Pn)), where "N" is "is natural number" and "S" is successoring.

There are many ways to assert the infinity of primes. One way would be to define "a < b" as

(there exists x)(x > 0 & +(a,x,b)) and

"MP,n" (P has size n) as

P ~ {x : x < n}. Then

(not there exists n)(Nn & M{p : p is prime},n)

asserts the infinity of primes. Or one can state in via unboundedness: (n)(Nn => (there exists p)(p > n and p is prime)).

First-order vs second-order provability

2013-01-24T06:29:54Z

Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except ∀x(Sx≠0) is replaced with ∃x(Sx=0). Let MA2 be the second-order variation, with second-order induction.

Answering to a question by Russell Easterly, Emil Jerabek has shown that

http://mathoverflow.net/questions/119375/even-xor-odd-infinities

∃x(x≠0∧x+x=0) ∨ ∃x(x+x=S0)

is unprovable in MA. There is, however, a proof in MA2.

There are mathematical examples which distinguish first-order and second-order PA, but they are more esoteric (Paris-Harrington Theorem) or less mathematical (the consistency of first-order PA). So the result of Jerabek seems IMHO to be of interest, by providing a simple mathematical proposition and system where the second-order system can prove the proposition but not the first-order.

Are there other simple examples of a first-order theory T and an assertion S where T cannot prove S but second-order T, with second-order induction, can prove S? (Obviously, the interest of Emil's result increases if there are none which aren't "reasonably" equivalent.)

Answer by abo for Even XOR Odd Infinities?

2013-01-20T21:37:20Z

NOTE: The first proof is wrong because it uses second-order induction. The second-proof is wrong as well per Wofsey's comment.

Ashutosh in the comments has shown that exclusion holds.

Here is a proof of existence.

Let A be the elements of the model. Let p be the predecessor of 0 in A. Let T = S \ {(p,0)}. Then T induces the normal ordering < on A, with p the maximal element. It can be shown that (1) x < Sy implies x <= y.

Clearly p + p <= p. Let x be the least element such that x + x <= x. We claim x + x = 0 or x + x = 1. Suppose not. Then there exists y such that Sy = x and v such that SSv = x + x and y < x and v < x + x. (y < x because otherwise x = 0, so x + x = 0, a contradiction.) But v = y + y, and v < x + x <= x. So v < Sy. By (1) v <= y, contradicting the leastness of x.

ABOVE assumed second-order induction. BELOW works using first-order induction (and is easier to boot...).

I claim: (x)(∃y(y+y=x v S(y+y)=x))

For this is true when x = 0 (take y = 0). Suppose true for k. If y+y=k, then S(y+y)=Sk. And if S(y+y)=k, then Sy+Sy =Sk. So if true for k, then true for Sk. By induction (first-order!!), the claim is true.

Let p be the predecessor of 0. Then by the claim y+y=p or S(y+y) = p for some y. In the first case Sy+Sy = 1, in the second Sy+Sy = 0.

Answer by abo for What axioms are used to prove Godel's Incompleteness Theorems?

2013-01-06T12:39:35Z

Here's a different way of looking at things. Use FPA to denote second-order Peano Arithmetic minus the Successor Axiom (the axiom which says that every natural number has a successor). FPA is neither weaker nor stronger than IΔ0+Ω1, since the latter assumes the Successor Axiom but assumes a weaker form of induction.

FPA can prove the First Incompleteness Theorem. Undoubtedly, fragments of FPA can as well.

More interesting is when one clarifies the nature of the logical system under metalogical study. Usually, the syntax of first-order logic is defined so that one can always concatenate two strings to form a larger one. E.g. one uses this principle in the Deduction Theorem, which is one of the first metalogical theorems one tends to prove. But this assumption, essentially equivalent to the Successor Axiom, is not necessary, and one can refrain from making it.

In this environment (where the syntax is not assumed to be unboundedly long), one can say this: FPA can prove the First Incompleteness Theorem. But Godel's proof seems only to work in the case of FPA + Successor Axiom. In the case FPA + not Successor Axiom, one basically formalizes the idea that a proof is generally longer than any axiom. It does not appear that Godel's proof of the Second Completeness Theorem goes through, and I do not know whether this can be repaired.

Answer by abo for Physics and Church–Turing Thesis

2012-12-16T12:24:06Z

I would answer that the question is uninteresting, because even if single physical devices were restricted to calculating computable functions, interacting or communicating physical devices are not.

This can be seen by considering two devices which are able to communicate. Both devices are Turing-like and have tapes. One device is programmed to space to the right until it reaches the end of its input. It then communicates with the second device and outputs what it has communicated. The second device alternates between two states: ready to communicate 0 or ready to communicate 1. The behaviour of the two devices together is time-dependent. If, for instance, one assumes that time is like the real numbers, and the ratio of operating speeds is precise and can be any irrational number, then the two devices together can compute a non-computable function (input being the input of the first device and output being the output of the first device). OTOH, it's probably more realistic to say that the behaviour of these two devices together is simply not functional (and thus, a fortiori, not computable-functional) since the operating ratio is unlikely to be precise.

Answer by abo for Is there any formal foundation to ultrafinitism?

2012-11-29T06:45:49Z

I would suggest the following axiomatization to my ultrafinitist friends. Let Nx mean "x is a natural number", Sxy mean "y succeeds x", and 0 to be "zero". The Peano Axioms are:

1/ N0

2/ S is into N

3/ S is total on N (every number has a successor)

4/ S is a function

5/ S is one-to-one

6/ 0 is not in the image of S

7/ Induction

Remove Axiom 3. Then the models of these axioms are: the standard model (if it exists) and the initial segments. {0} for instance is a model.

One can work either in second-order logic and define sequences as second-order entities (http://www.andrewboucher.com/papers/arith-succ.pdf) or work in first-order logic and add sequences directly as first-order entities, with some additional axioms (http://www.andrewboucher.com/papers/fpa.pdf).

With sequences one can make the usual recursive definitions of addition, multiplication, and exponentiation, and then towers of powers. It will not, of course, be able to prove any of them total.

So the ultrafinitist who has any particular idea which numbers are permissible and which are not can simply add in the axioms he wants, such as

E/ "the product of 100 and 100 exist" and

F/ "a tower of 10 powers of 2 does not exist".

IMHO, these assumptions are not of any mathematical interest, since the system without Axiom 3 is capable of proving many mathematical theorems (Quadratic Reciprocity...), and adding any axioms such as E or F only adds trivial capabilities to prove additional theorems. So it is better, mathematically at least (and IMHO philosophically), to be agnostic about the successor axiom, rather than an atheist or a theist.

Answer by abo for Finite versions of Godel' s incompleteness

2012-06-29T05:24:17Z

The answer to the second question is negative. Consider a (first-order) theory of PA without the successor axiom like fpa. Then T is consistent and proves its own consistency. Let k be the complexity of this proof of consistency. Then trivially T is k-consistent and k-proves its k-consistency.

[the following is added in an edit] As my comment indicated, the previous remarks are not completely correct. Instead: Let T be a (first-order) theory of PA without the successor axiom like fpa. Then T is consistent and proves its own consistency. In fact, T proves:

(x)(there does not exist an x-proof of a contradiction in T). (*)

Let this proof have complexity z. Then T can prove - call this sentence S(y) -

"there does not exist a y-proof of a contradiction in T" for any y,

but its proof may have greater complexity than z; indeed, if the proof uses (*), then it will have greater complexity, by say f(y). That is, T proves S(y) with a proof of complexity no greater than z + f(y). Suppose there exists a k such that k <= z + f(k). Then T k-proves S(k), i.e. T k-proves the k-consistency of T. Since T is k-consistent, the answer to the question would therefore be negative.

Is there likely to exist k <= z + f(k)? The important step is to find k which can be referred to with complexity much less than k. If complexity is defined to be say the length of the proof, then this should be possible by defining an exponential operator and defining k to be a power of two reasonably large numbers.

Answer by abo for Essential reads in the philosophy of mathematics and set theory

2012-04-18T05:40:40Z

For the philosophy of Mathematics side, rather than the set theory side, I'd suggest:

Philosophy of Mathematics: Selected Readings; by Benacerraf & Putnam

From Frege to Godel: A Source Book in Mathematical Logic; edited by Jean van Heijenoort

Logic, Logic, and Logic; by George Boolos

Fixing Frege; by John Burgess

Foundations without Foundationalism; by Stewart Shapiro

New Waves in the Philosophy of Mathematics; edited by Linnebo and Bueno

For their historical interest:

Foundations of Arithmetic; by Gottlob Frege

An Introduction to Mathematical Philosophy; by Bertrand Russell

One book on the set theory side that I can recommend:

Set Theory and its Philosophy; by Michael Potter

Answer by abo for Intuitive and/or philosophical explanation for set theory paradoxes

2012-04-15T11:09:58Z

I'm still partisan of my own explanation:

www.andrewboucher.com/papers/paradoxes.htm

Answer by abo for How do you restrict the induction axiom in second (or higher) order logic?

2012-03-27T05:56:27Z

ACA0 does not merely restrict the induction axiom. It also restricts the comprehension axiom, which asserts the existence of the second-order entities, to formulae which contain no quantification over big (second-order) letters, that is comprehension in ACA0 is:

(there exists X)(for all n)(n in X iff phi(n)),

where phi(n) contains no quantifiers with big (second-order) letters.

To define the natural numbers N in second-order logic, you would use phi(n) as

(F)(F0 & (x)(y)(Fx & Sx,y implies Fy) implies Fn).

But this obviously has a big-letter quantified, so this definition cannot be made in ACA0. This is why, as Andreas points out, you assume the existence of N - because it cannot be defined.

Answer by abo for Can ZFC prove "false theorems", and still be consistent? (was "Junk Theorems" follow up)

2012-03-13T06:54:29Z

The phenomenon of junk theorems - and the example you cite - are present in a small fragment of ZFC (without the Axiom of Infinity, replacement, choice, ...) which can be modeled by PA, which I presume you accept is consistent. This does not, of course, imply that adding in these deleted axioms might not then cause an inconsistency, just that I don't think you could say it's because of the junk theorems.

Answer by abo for Set theories without "junk" theorems?

2012-03-11T15:10:58Z

The question being, "Would it be correct to say that structural set theory is an attempt to get rid of such junk theorems?", the answer I think is "only partly or only if extremely limited."

Clicking on the link, I find a theory called ETCS as an example of structural set theory. ETCS has 0, N (the natural numbers), and S (the successor function) as primitives in its language, and it assumes effectively as axioms the normal assumptions about them (e.g. it assumes the existence and uniqueness of recursion).

Obviously, if you assume 0, N, and S as primitives and make the normal assumptions about them, rather than constructing them and proving the normal assumptions (Russell's honest toil rather than theft), then one can avoid junk theorems about the natural numbers. The same effect could be achieved, by modifying ZFC by introducing the same primitives and assuming, on top of the normal ZFC axioms, the Peano Axioms.

ETCS does not, however, get rid of all junk theorems unless it is only supposed to be about arithmetic and the natural numbers. If it, for instance, is also supposed to allow the construction of the real numbers and the development of analysis, then it will still get junk theorems about the real numbers.

Answer by abo for Subsystems of Peano arithmetic and incompleteness theorem

2012-02-12T12:59:04Z

First, it's not clear whether you are talking about first-order PA or second-order PA. It seems, because you are mentioning induction as an axiom rather than a schema, that you are talking about second-order PA, but I will answer for a special form of first-order Peano Arithmetic, denoted PA1. The answer for PA2 is similar.

Secondly, it is incorrect to ask what is "the" largest. The answer to your question is: there exists sub-systems of PA which prove their own consistency but there is no largest such sub-system.

Let PA have the language with a constant 0, a one-place predicate N, and a 2-place predicate Sx,y. Usually the axioms of PA1 include axioms for addition and multiplication. I will present a system which has axioms for sequences rather than addition and multiplication; addition and multiplication can then be defined using the notion of sequences. The axioms of PA1 are:

(1) N0

(2) (n)(m)(Nn & Sn,m => Nm)

(3) (n)(Nn => (there exists m) Sn,m)

(4) (n)(m)(m')(Nn & Sn,m & Sn,m' => m = m')

(5) (n)(m)(n')(Nn & Nn' & Sn,m & Sn',m => n = n')

(6) (n)(Nn => not Sn,0)

(7) Induction schema, phi[0\n] & (n)(m)(Nn & Sn,m & phi => phi[m\n]) => (n)(Nn => phi)

(8) For every natural number x, there exists a sequence <(0,x)>

(9) For every sequence f, if Nn & Sn,m & <(m,x)> belongs to f, then <(n,y)> belongs to f for some y

(10) For every sequence f, if Nn & Nm & Ny & Sn,m & <(n,x)> belongs to f, there there exists a sequence g exactly like f except that it may differ at the mth place where <(m,y)> belongs to g

Apologies for the imprecision of (8), (9), and (10), but it's the quickest way for me to write them down here.

Call fpa the system made up of axioms (4) through (10). Then fpa proves its own consistency. It also proves the consistency of fpa + (1) (call this X). So a fortiori X proves its own consistency. fpa also proves the consistency of fpa + (N0 => (2) & (3)), so this latter (call it Y) also proves its own consistency. But any system stronger than both X and Y contains PA1, which can't prove its own consistency. Hence there is no strongest sub-system of PA1 which proves its own consistency.

Please see http://www.andrewboucher.com/papers/fpa.pdf for details.

Answer by abo for History of Logic Development

2012-01-18T19:09:31Z

I would suggest to start with "The Search for Mathematical Roots, 1870-1940" by I. Grattan-Guiness, which has some chapters on Cantor, which you can skip if it really doesn't interest you, so that you begin with chapter 4, which is on Peirce and Frege. It has less on Tarski than you might want, in which case you can read the Feferman biography called "Alfred Tarski: Life and Logic". It may also have less on Wittgenstein than you want, but there are myriad supplemental materials there.

Comment by abo

2013-06-02T19:11:32Z

Well, that was meant to be a comment. Can't see how to change it, though.

Comment by abo

2013-05-30T05:31:40Z

@Francois. I wasn't aware I was loosening the rules. Looking at Mendelson, he defines a formal axiomatic theory for the propositional calculus with three axioms. Keep only the first of the three, which is A => (B => A). Then A => A isn't provable, but at least according to Mendelson's definition, it is a formal axiomatic theory (just not an interesting one). Point taken that there are some systems where not even A follows from A.

Comment by abo

2013-05-29T21:31:47Z

Perhaps one should include "interesting" in front of "axiomatic system"? Even in an empty axiomatic system, A always follows from A, but in an empty axiomatic system, one cannot prove anything, much less A => A. By considering any set of axioms which do not allow the proof of A => A, the deduction theorem would still evidently not hold.

Comment by abo

2013-05-18T14:24:05Z

Are you looking for something like: 1/ Induction: From phi(0) & (n)(phi(n) => phi(n+1)) infer (n)phi(n) 2/ x ≤ y iff (there exists z)(z + x = y) 3/ x + 0 = 0 4/ x + (y + 1) = (x + y) + 1 5/ x * 0 = 0 6/ x * (y + 1) = (x * y) + x 7/ There is no ≤ maximal element I think that works...

Comment by abo

2013-02-20T06:22:46Z

It's actually not quite a theorem of GA2 because you don't know that the successor of x exists. But it can be proven, if the successor of x exists, then it equals x + S0. Yes, finite non-commutative rings would be models of that theory.

Comment by abo

2013-02-18T18:56:12Z

Yes it does satisfy the successor axiom. But the problem is that with this definition of successor all the GA2 axioms do not hold, because induction does not hold. Why doesn't it? Define e.g. the predicate phi to be (n = 0 v n = S0). Then phi(0), and if phi(n), then phi(Sn), by a very simple argument on cases. But it's not true that every element in the ring is 0 or S0. So induction doesn't hold. Because induction doesn't hold for 2x2 matrices over {0,1} with this definition of successor, you can't use the results about GA2 to infer that matrix multiplication is commutative.

Comment by abo

2013-02-18T06:28:48Z

OK, let the zero matrix be 0 and the identity matrix I (1's on the diagonal and 0's elsewhere) be the successor of 0. And define Sx to be x + I. Then S0 = I and SS0 = 0. So the successoring chain starting from 0 only includes two elements, {0,I}, and not the whole ring. You therefore cannot conclude that multiplication is commutative on the whole ring.

Comment by abo

2013-02-17T09:02:44Z

I don't understand the "why" of your question. Consider 2 x 2 matrices. What do you propose to define as the successor relationship (from which you then define addition and multiplication)? What is the successor of 0? I imagine a first-order version cannot prove multiplication is commutative.

Comment by abo

2013-01-30T19:07:32Z

I guess the question in my subject was badly chosen. I wasn't actually asking whether there are possible ways to redo a Hilbert program, but whether one specific way was possible. In any case, thank you for the information, I'll take a look.

Comment by abo

2013-01-30T19:04:34Z

Thank you for your answers, Emil. Sorry to have taken you from your work. The "consistency of RCons(FPA + E(n)" was not, as you devined, intentional. I'll re-edit. Bye.

Comment by abo

2013-01-29T20:59:11Z

And your reward is even more questions!

Comment by abo

2013-01-29T19:15:59Z

Thank you very much, Emil.

Comment by abo

2013-01-29T19:12:54Z

Thanks very much for that information.

Comment by abo

2013-01-28T19:31:39Z

By the way, I can't upvote you because I'm not registered. Sorry.

Comment by abo

2013-01-28T19:30:54Z

Very nice, Emil. Thanks very much. I once went through a paper that proved the Prime Number Theorem in I\Delta_0+exp and it seemed to me the proof went through in FPA. Would this be in error? Also, I would like to ask another question about provability in FPA. If I were to describe the system as x + y, where y is just the list of the Peano axioms which FPA uses, what is the shortest x which is clear? Following Goldstern: a many-sorted first order theory with one "lowercase" sort (for numbers) and infinitely many "upper-case sorts" (the nth sort being n-ary relations)?