1
vote
2answers
98 views

An impressive fact expressible in presburger arithmetic?

Is there something expressible in presburger arithmetic that would seem impressive to students at an undergraduate level?
1
vote
1answer
25 views

how to find percentage loss

I am passing through a question in which problem is like `I sold a book for $250$ dollars, which resulted in a loss of 50 dollars. So how much loss in percentage. The formula I understand to fit on it ...
1
vote
2answers
41 views

Are there real extensions of the operations of addition, multiplication, exponentiation, etc in the other direction?

We have $\underbrace{a+a+a...+a}_{n\:times}$ which equals $a \times n$, and also $\underbrace{b \times b \times b.... \times b}_{p\: times}$ is $b^p$, so I was wondering if the generalization would ...
1
vote
1answer
50 views

Is this assertion true or false? $(\exists x)(\exists y)(\forall z)(y \ne x+z \Rightarrow y\lt x)$ Cohn - Classic Algebra P7

$x,y,z\in\mathbb{N}$ with $0$ $(\forall x)(\forall y)(\exists z)(y \geq x \Rightarrow y=x+z)$ Can you help me with trivial thing above? I imagine it is because I am tired, but I can't see if this is ...
1
vote
0answers
74 views

Types realized in ultrapowers consisting of definable functions

Let $\mathcal{M}$ be a nonstandard model of arithmetic and let $M$ be its universe. Let $U$ be a nonprincipal ultrafilter over $M$ and let $\mathcal{N}$ be the ultrapower $\mathcal{M}^M / U$. Let $F$ ...
0
votes
0answers
33 views

Extensions by recursive definitions

In the Wikipedia entry on Extension by definitions I learn that an explicit definition in the language of a theory $T$ yields a conservative extension $T'$ of $T$. I wonder if this eventually does ...
2
votes
2answers
43 views

Definition and decidability of bounded quantifiers

Consider quantifier-free formulas $P(x,y) = Q(x,y)$ of Peano arithmetic. Consider $P(x,y),Q(x,y)$ to be terms composed of variables $x,y, \operatorname{succ}, +, \times$. Note that these are ...
1
vote
1answer
81 views

How to define multiplication in addition terms in monadic second order logic?

How to define multiplication in addition terms in monadic second order logic? meaning, having natural numbers variables, N sub-groups variables, successor function, negations, "for every", "there ...
0
votes
1answer
24 views

An implication between two statements concerning integers

Does "Every non-empty bounded below set of integers has a smallest element" $\implies$ "If $m,n$ are integers with $m>n$ , then $m-n\ge1$" ? If not then what additional assumption is needed ...
0
votes
2answers
71 views

Logic and mathematical variables as objects

I am currently working on describing a predicate logic for which the objects are mathematical variables. Thus I can say stuff like: $\forall x: R(x) \implies \text{operator}(x)=1$ Here $x$ is a ...
4
votes
2answers
127 views

Why is the language of arithmetic usually $(+, \cdot, 0, s)$, not $(+, \cdot, 0, 1)$?

The formalized theory of arithmetic has usually $(+, \cdot, 0, s)$ as its language. However, from what we usually do in ring theory, it seems natural to use $(+, \cdot, 0, 1)$ as the language of ...
1
vote
1answer
58 views

$pq\mid (a - pq) \implies pq\mid a$?

This may be a dumb question. I'm not a math major, but, since I'm studying logic, I decided to learn a bit of number theory. I've just begun my studies (I'm reading Davenport's The Higher Arithmetic) ...
0
votes
2answers
57 views

Proving that Order for N is Anti-symmetric

I'm having trouble deriving the following fact from the basic properties of $+_{\mathbb{N}}$ and the definition: Definition. $\forall n, m \in \mathbb{N}: (n \geq m) \leftrightarrow (\exists a \in ...
1
vote
1answer
141 views

Addition within lambda calculus

I've been reading "The Emperor's New Mind" by Roger Penrose. He briefly introduces lambda calculus (pp. 86-92) and gives this formula for addition: $A = \lambda fgxy.[((fx)(gx))y]$ This was my ...
1
vote
0answers
32 views

On the Legitimacy of Grossone [duplicate]

A paper describing grossone used to measure such things as the sierpinski carpet here:http://arxiv.org/abs/1203.3150 I'd like to discuss the legitimacy of grossone. What is the general consensus ...
2
votes
2answers
83 views

Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately ...
0
votes
2answers
67 views

what area of math for studying mathematical laws as a logical system?

As a relative beginner trying to understand math more deeply, I'm trying to learn more about the mathematical laws (the laws of the operations $+, -, \times, \div$) For example, I know the basic laws ...
1
vote
1answer
47 views

Making an inequality true

$n > 10$ implies $n + 3 \leq \Box\times n$ Possible answers: $1$ $2$ $3$ $4$ I answered "$2$" and got it wrong. Why? When $n=2$, $(11) + 3 \le 2(11)$. $n > 1$ ...
1
vote
0answers
101 views

Is this first order version of the Collatz conjecture decidable in peano arithmetic?

Let $\phi(x)$ be a first order formula in the language of arithmetic with one free variable $x$. Consider the sentence $\psi_\phi$, defined as: $$\phi(0)\wedge \phi(1) \wedge (\forall x \phi(x) \to ...
0
votes
0answers
91 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
72 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
0
votes
1answer
152 views

Are there statements in set theory about arithmetic beyond the reach of the analytical hierarchy?

Even if the answer were negative for arithmetics(I have no idea), in the more general case: Can any mathematical statement be expressed as a $\Delta_m^n$ (with n, m belongs to N) statement in a chosen ...
16
votes
1answer
494 views

Are the real numbers ever needed to prove a property of the natural numbers?

Suppose no one had invented/discovered the real numbers yet (so e.g., no calculus), would this constrain the possible theorems or knowledge we could have about the natural numbers?
-1
votes
3answers
233 views

Two easy proofs by contradiction

Check the validity of the statements below using contradiction method (i) p: The sum of an irrational number and a rational number is irrational (ii) q: If $n$ is a real number with $n ...
7
votes
4answers
459 views

Is the set of PA theorems the same as the set of solvable halting problems?

I am not sure if this is a trivial question. By Post's theorem we know that every PA (first order logic) theorem is equivalent to stating that a given input C in a given Turing machine halts or ...
2
votes
2answers
75 views

Proof by induction on $\{1,\ldots,m\}$ instead of $\mathbb{N}$

I often see proofs, that claim to be by induction, but where the variable we induct on doesn't take value is $\mathbb{N}$ but only in some set $\{1,\ldots,m\}$. Imagine for example that we have to ...
4
votes
1answer
166 views

Is every φ above the second level of the arithmetical hierarchy independent of PA?

If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
1
vote
3answers
196 views

What is it wrong in this argument about the interpretability hierarchy?

This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one. Background: (from ...
1
vote
1answer
77 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n? This is a follow up from a previous question: Given a φ independent of PA which is true ...
9
votes
1answer
205 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
2
votes
2answers
142 views

Similarity between integer and logical operations through parity

Lets observe the parity property of integers while adding them or multiplying. It's simple to notice that when we add two numbers, the parity of the result depends on parity of summands: ...
3
votes
1answer
199 views

Is the arithmetic most mathematicans use a modelled within first or a second order logic?

I often read that arithmetic in first order logic has problems and you really want to do it in second order logic. However, aren't the Zermelo–Fraenkel axioms written down in the language of first ...
5
votes
1answer
165 views

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?

There is a recursive definition of the set of squares which uses only addition: $CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$ $IS(x)⇔ x=0 ...
5
votes
2answers
203 views

$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?

Update : Should have left the Arithmetic out of this question, the new modified question is posted here : $\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable? ...
2
votes
2answers
120 views

logic and with additions

the table of logic and ($ \wedge $) is 0 0 0 0 1 0 1 0 0 1 1 1 I can build a "logic and" operation with additions and subtractions?
4
votes
2answers
181 views

What does a nonstandard proof of Con(PA) look like?

As in Godel's incompleteness theorem natural numbers encode proofs of theorems. Due to Godel's completeness theorem there is a natural number (in some nonstandard model) that proves $Con(PA)$. What ...
1
vote
3answers
309 views

How is Kleene's T predicate defined?

What I don't understand is how to extract information from the number that encode the computation history. I know it's defined in Kleene's Introduction to Metamathematics. But what page? References ...
14
votes
3answers
795 views

Can multiplication be defined in terms of divisibility?

Peano Arithmetic has two axioms which use the multiplication symbol: ∀x:x*0=0 and ∀x:∀y:x*Sy=x+x*y. The 2-term relation "x divides y" can be expressed as D(x,y) := ∃z:z*x=y. Multiplication is a ...
4
votes
1answer
276 views

Non Higher-Order Formulation of Gödels Incompletness Theorem

I was just having a look at Gödels incompletness theorem as found in: http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf I noticed that Gödel used a higher order logic. At least ...