Tag: “Math Improve”
Logic on Math StackExchange
- Example of a statement in PA which cannot be proved in PA and cannot be proved in ZFC? December 2, 2024I'm aware of a number of statements (for example, Con(PA), and those given by Goodstein's theorem and the ParisāHarrington theorem) which are stateable in Peano Arithmetic (PA), but not provable within PA. Each of these is provable in ZFC. Is there an example of a statement in PA which is not provable both in PA […]Ollie Taylor
- How can I ensure that $x \iff p \land q$ here? December 2, 2024Say I am writing a Boolean formula in which only $\land$ is between clauses, and only $\oplus$ is between literals in the clauses. How can I make it such that an assignment of variables satisfies the formula only if, for variables $x,p,q$, $ \ \ x \iff p \land q$? My problem is that I'm […]Princess Mia
- formalize "there exists a function f such that f(a)=b" into first-order formula [closed] December 1, 2024I want to know how to formalize the sentence "there exists a function f such that f(a)=b" into a first-order formula. It should not be $\exists f f(a)=b$ because first-order logic does not allow quantifying over functions. Update: Maybe we need to restrict the first-order language to that for ZFC which has no other relation […]peter
- Problem characterizing Lindenbaum algebras December 1, 2024Given a first order type $\tau$, we use $S^\tau$ to denote the set of $\tau$-sentences, i.e. formulas with no free variables. Let $T = (\Sigma, \tau)$ a theory, with $\Sigma$ the set of axioms in the theory. Then we can define \begin{equation*} \varphi \dashv \vdash_T \psi \iff T \vdash \left( \varphi \leftrightarrow \psi \right) \end{equation*} […]lafinur
- Completeness for existential second-order logic November 30, 2024I find in this link that existential second-order logic is compact. On the other hand, I find in this link that existential second-order logic is not complete. Here is a quote: A "naturally occurring logic" that also serves to show that (2) (compactness) does not imply (1) (completeness) is the existential fragment of second order […]user1868607
- Does Peano Arithmetic implicitly describe a set? November 30, 2024Apologies if my language is incorrect. My question is that in the axiomatizations of PA I have seen, they implicitly posit a 'set' of natural numbers and then describe which elements belong to it. To my understanding PA is a set of axioms added to first order logic, and sets and membership are not described […]Orion Jordan
- References and Explanations for Hugh Woodin "On the Mathematical Necessity of the Infinite", Finite Peano Arithmetic (FPA) November 30, 2024In this lecture (I will only ask about the first 20 minutes), Woodin makes several interesting statements, that I would like more explanation on. @6:08, Woodin outlines the axioms of FPA (the axioms of Finite Peano Arithmetic), and discusses the Induction Axiom vs. the Pigeonhole Principle, and how the former is weaker than the latter […]D.R.
- Truth tree terminology [closed] November 29, 2024I was busy with a long complicated proof using a proof tree ( see Proof of grz theorem ) And in that proof i came across paths with formulas like: $$(n) P$$ $$(n+i) Q \lor P $$ (Where $Q$ was a quite complicated formula) But if $Q$ is true or false doesn't really matter, we […]Whogius
- Derive formula in formal arithmetic from axioms November 29, 2024I have formal arithmetic with these non-logical axioms: $ \begin{align*} A_{x0} &: \quad \forall x \, (x \times 0 = 0) \\ A_{x_s} &: \quad \forall x \, \forall y \, (x \times s(y) = x \times y + x) \\ A_{+0} &: \quad \forall x \, (x + 0 = x) \\ A_{+s} &: […]leeeeeeeeess
- How to prove partial correctness of a program with Hoare Logic? November 29, 2024I am working on a problem where I need to prove the partial correctness of the following program using Hoare logic: z = x; while (z > 1) { z = z - 2; } Problem Description This program determines whether the input x is even or odd. Use Hoare logic and prove partial correctness […]asfasfasf
Recent Comments