abo
|
Unregistered User
|
|
|
Jun 9 |
answered | Should I mention my study of set theory when applying for a job outside of university? |
|
Jun 2 |
comment |
One can earn nothing on the Brownian motion, true ? Well, that was meant to be a comment. Can't see how to change it, though. |
|
Jun 2 |
answered | One can earn nothing on the Brownian motion, true ? |
|
May 30 |
comment |
Deduction theorem @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. |
|
May 29 |
comment |
Deduction theorem 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. |
|
May 19 |
answered | Reference request: Minimal Axiomatizations of PA over (+,x,<=). |
|
May 18 |
comment |
Reference request: Minimal Axiomatizations of PA over (+,x,<=). 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... |
|
Mar 1 |
answered | Is there any straightforward way to substitute for Gaussian/Brownian assumptions in financial mathematics? |
|
Feb 20 |
revised |
Why Does Induction Prove Multiplication is Commutative? deleted 49 characters in body; added 16 characters in body |
|
Feb 20 |
comment |
Why Does Induction Prove Multiplication is Commutative? 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. |
|
Feb 20 |
accepted | Why Does Induction Prove Multiplication is Commutative? |
|
Feb 19 |
answered | Why Does Induction Prove Multiplication is Commutative? |
|
Feb 18 |
comment |
Why Does Induction Prove Multiplication is Commutative? 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. |
|
Feb 18 |
comment |
Why Does Induction Prove Multiplication is Commutative? 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. |
|
Feb 17 |
answered | Why Does Induction Prove Multiplication is Commutative? |
|
Feb 17 |
comment |
Why Does Induction Prove Multiplication is Commutative? 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. |
|
Jan 30 |
revised |
Is an ultrafinitist Hilbert’s program doomed? deleted 38 characters in body |
|
Jan 30 |
comment |
Is an ultrafinitist Hilbert’s program doomed? 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. |
|
Jan 30 |
comment |
Is an ultrafinitist Hilbert’s program doomed? 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. |
|
Jan 30 |
revised |
Is an ultrafinitist Hilbert’s program doomed? deleted 48 characters in body |
|
Jan 30 |
revised |
Is an ultrafinitist Hilbert’s program doomed? Small qualification to question added |
|
Jan 29 |
awarded | ● Nice Question |
|
Jan 29 |
comment |
Can FPA really prove its consistency? And your reward is even more questions! |
|
Jan 29 |
asked | Is an ultrafinitist Hilbert’s program doomed? |
|
Jan 29 |
comment |
Can FPA really prove its consistency? Thank you very much, Emil. |
|
Jan 29 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom Thanks very much for that information. |
|
Jan 28 |
asked | Can FPA really prove its consistency? |
|
Jan 28 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom By the way, I can't upvote you because I'm not registered. Sorry. |
|
Jan 28 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom 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)? |
|
Jan 28 |
awarded | ● Scholar |
|
Jan 28 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom @Carl. I am a little nervous about the example of G(FPA). FPA can consider the same one-element model and prove that it itself is consistent (using the Godel formula for consistency). This does not contradict the Second Incompleteness Theorem, because FPA is not "sufficiently strong". Why then is Z2 able to prove G(FPA) but not FPA? I guess you're asserting that Z2 can prove Cons(FPA) => G(FPA) while FPA cannot, but where exactly does the proof go wrong? |
|
Jan 27 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom (x) = "for all x", [x] = "there exists x", "!" = "not" (0) Full comprehension schema (as you write) (1) N0 (2) (n)(Nn => [m](Nm & Sn,m)) (3) (n)(m)(m')(Nn & Nm & Nm' & Sn,m & Sn,m' => m = m') (4) (n)(m)(n')(Nn & Nm & Nn' & Sn,m & Sn',m => n = n') (5) (n)(Nn => ! Sn,0) (6) Induction (as you write) Consider this as Z2, and FPA as having the same axioms, only without (2). FPA (and Z2) can then define addition, multiplication, and <, and prove these have the usual properties (except totality). (If I get 2 upvotes on this comment, I'll re-edit my question. Ow I'll leave it here.) |
|
Jan 27 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom Yes, to your question, except I'll make it into two. Are there any? Is there a simple, mathematical one (i.e. no fair talking about consistencies of theories and so on)? The axiom set itself that you are talking about is getting too complicated. There's a simpler way of writing the axioms which I'll state here. |
|
Jan 27 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom I mean proved in a theory with small and big letters, with full comprehension and induction as stated now in the question. Deductively, this can be considered a first-order theory with many sorts. But semantically, it can be considered a second-order theory. (I hope that makes sense!) |
|
Jan 26 |
revised |
Provability in Second-Order Arithmetic without the Successor Axiom Clarification added.; added 37 characters in body |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom P has size n: sorry about this, perhaps I should have said multi-sorted rather than two-sorted? (I'll edit if you confirm.) That is, the logic is supposed to allow one to talk about 2-ary (or 3-ary, etc....) relationships, so you are able to write down the usual (there exists R)(R is 1-1 & R is a function & ...). |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom Induction. Again choices. Here's one way (since I said FPA uses full comprehension), with N a 1-ary predicate symbol for natural number and S a 2-ary for successoring: (P)(P0 & (n)(m)(Pn & Nn & Sn,m => Pm) => (n)(Nn => Pn)). |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom @François. There are choices. It's possible to define a formula M(P,n) which says that "P has size n". First, say a < b iff (there exists non-zero n s.t. +(a,n,b)). Then define "P has size n" iff there exists 1-1 function from {x | x < n} onto P. The infinitude of primes is then stated as "not there exists natural number n such that M(P,n))", where P = {p | p is prime}. Another possibility is simply to claim unboundedness: (n)(there exists p)(p is prime & p > n). Both cases are unprovable in FPA. |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom @Carl. Right, instead of successor as a function, consider successor as a relationship. Addition and multiplication are 3-ary relationships. All axioms can be easily restated. |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom Yes I'm talking about the full (standard) model. |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom Yes, full comprehension. I'm not trying to be confusing, but I don't see why it is. Simpson uses this terminology all the time: "the language of second-order arithemtic is a two-sorted language," "the axioms of second-order arithmetic," "by second oder arithmetic we mean the formal system...," |
|
Jan 26 |
comment |
Provability in Second-Order Arithmetic without the Successor Axiom No, it's not, but I guess that's my fault. I'm talking about the models of the two-sorted theory considered as a second-order theory. |
|
Jan 26 |
asked | Provability in Second-Order Arithmetic without the Successor Axiom |
|
Jan 25 |
comment |
Even XOR Odd Infinities? second-order entities to represent numbers (and proving the standard facts about them). Hence the 4-square theorem is true for +\, and thus it is true for + (in GA). As you can see, I work at a sophistication far below your own, but it does still get the job done (I hope!). |
|
Jan 25 |
comment |
Even XOR Odd Infinities? ... except for the last link (between the greatest element and its successor); and if there is no such element, then define S\ to be S. It can be shown that S\ satisfies all of the Peano axioms except for the totality of successorship. Call this system FPA. S\ defines an addition +\, and since S\ is contained in S, +\ is contained in +, the addition defined from S. But FPA proves the 4-square theorem, stating "Every number n is the sum of 4 squares". If I'm not mistaken the largest number needed in the standard proof is n^2, so the standard proof goes through in FPA using the ... |
|
Jan 25 |
comment |
Even XOR Odd Infinities? @Emil: the proof I have sounds like yours. I prove it in a weaker version than MA, which subtracts from MA the assumption of the totality of the successor relationship as well as its one-to-oneness, i.e. it assumes only induction and the functionality of the successor relationship. I'm using of course, as you observed, comprehension. Call this system GA or GA2, as you prefer. The ancestral of the successor relationship S provides an ordering < (the normal ordering), and basically if there is a greatest element wrt < having a successor, then consider the relationship S\ which is like S ... |
|
Jan 25 |
comment |
First-order vs second-order provability Yes, "second-order arithmetic" is a two-sorted first order theory. Conversely, a particular two-sorted first-order theory is called "second-order arithmetic". That's a fact; it's standard usage by now. You can then ask questions about provability in this two-sorted first-order theory aka "second-order arithmetic." |
|
Jan 24 |
awarded | ● Yearling |
|
Jan 24 |
awarded | ● Student |
|
Jan 24 |
asked | First-order vs second-order provability |
