Intereting Posts

Prove that the multiplicative groups $\mathbb{R} – \{0\}$ and $\mathbb{C} – \{0\}$ are not isomorphic.
Orthogonal projection matrix
Showing that the product and metric topology on $\mathbb{R}^n$ are equivalent
Maximum principle for subharmonic functions
Non-integer powers of negative numbers
What are the real-world applications of real analysis?
How to find number of strings generated by permuting the given string satisfying the below conditions?
Factoring $x^n + y^n$ over the integers
For what $n$ does a hyperbolic regular $n$-gon exist around a circle?
Quantum translation operator
Linear Programming 3 decision variables (past exam paper question)
If $T:X \to Y$ is a linear homeomorphism, is its adjoint $T^*$ a linear homeomorphism?
Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015
A finite set always has a maximum and a minimum.
In how many ways can a number be expressed as a sum of consecutive numbers?

It is a simple exercise to prove using mathematical induction that if a natural number n > 1 is not divisible by 2, then n can be written as m + m + 1 for some natural number m. (Depending on your definition of odd number, this can either be stated as “every number is even or odd”, or as “every odd number is one greater than an even number”. My question is, can this be proven without induction? In other words, can this be proven in Robinson arithmetic? If not, what is example of a nonstandard model of Robinson arithmetic that doesn’t have this property?

The reason I’m asking this is that the proof of the irrationality of the square root of 2 is usually presented with only one use of induction (or an equivalent technique). But the proof depends on the fact if k^2 is even, then k is even, and that fact in turn depends on the fact that the square of a number not divisible by 2 is a number not divisible by 2. And that fact is, as far as I can tell, is a result of the proposition above. (I’m open to correction on that point.) So if that proposition depended on induction, then the proof that sqrt(2) is irrational would depend on two applications of induction. (The reason that the ancient Greeks wouldn’t have been aware of this is that Euclid implicitly assumes the proposition above, when he defines an odd number as “that which is not divisible into two equal parts, or that which differs by a unit from an even number”.)

Any help would greatly appreciated.

- Definition of an $n$-tuple agreeing with the Kuratowski's definition of an ordered pair
- Is formal truth in mathematical logic a generalization of everyday, intuitive truth?
- Is mathematics one big tautology?
- What concepts does math take for granted?
- Can we found mathematics without evaluation or membership?
- How to prove $2+2=4$ using axioms of real number system?

Thank You in Advance.

- Is there a consistent arithmetically definable extension of PA that proves its own consistency?
- Unpacking the Diagonal Lemma
- Is the negation of the Gödel sentence always unprovable too?
- Is the empty set a subset of itself?
- Foundation for analysis without axiom of choice?
- Theorems that we can prove only by contradiction
- How do we know that we'll never prove a contradiction in Math
- Difference between $\implies$ and $\;\therefore\;\;$?
- How to prove that $b^{x+y} = b^x b^y$ using this approach?
- When does the set enter set theory?

Take $M = \{P = a_nx^n + \ldots + a_0 \in \Bbb Z[x] / a_n > 0 \}$, with the usual addition and multiplication on polynomials. Interprete $S(P)$ as $P(X)+1$.

Then $M$ is a model of Robinson arithmetic, but there are long strings of “not-even” numbers, such as $X,X+1,X+2,\ldots$. So in this model, it is false that if $n$ is not even then $n+1$ is even.

If you define “$n$ is odd” as “$\exists k / n= k+k+1$”, then it is false that every number is even or odd.

However, it is still true in $M$ that addition is associative and commutative, and so if $n$ is odd then $n+1$ is even, and if $n$ is even, then $n+1$ is odd. (you will need a stranger model for this to fail)

If you want a model in which $a^2-2b^2 = 0$ has a solution, you can pick $M = \{ P \in \Bbb Z[X,Y]/(X^2-2Y^2) / \lim_{y \to \infty} P(\sqrt 2 y,y) = + \infty$ or $P \in \Bbb N \}$

I asked a similar question: Even XOR Odd Infinities?. I am not sure you can prove what you are trying to prove even with induction.

My question was about a theory I call Modular Arithmetic (MA). Like Edward Nelson, I came up with MA as a tool for proving PA is inconsistent. MA has the same axioms as PA except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. Assuming we can define the modulo function in PA, my question can be translated into PA. The natural number $n$ is odd if it satisfies both of the following expressions:

$O1: \forall x((x = 0 \lor x+x \neq 0) \mod n)$

$O2: \exists x((x+x = 1) \mod n)$

$n$ is even if both of these statements are false. I am not sure how I would define “odd and even numbers alternate”. My question was “is every natural number exclusively even or exclusively odd?”:

$\forall n(\exists x((x \neq 0 \land x+x = 0) \mod n) \overline{\vee} \exists x((x+x = 1) \mod n))$

The answer to my question was no. It was proven $O2 \rightarrow O1$. However, $O1 \rightarrow O2$ is false. $O1$ is true and $O2$ false in the 2-adics integers, $Z_2$. There is no 2-adic integer, $m \neq 0$, such that $2m=0 \overline{\vee} 2m=1$. The statement above is also false for $n = -1 = …111 \in Z_2$.

All infinite models of MA are non-standard and are an initial segment of some model of PA. $Z_2$ is a ring, but it can be “extended” into an uncountable, non-standard model of PA. We create a copy of $Z_2$ that starts with $0’$. Let $S(-1)=0’$. We continue adding copies of $Z_2”$ and let $S(-1′) = 0”$ to get a model of PA. We can prove there are non-standard numbers in this model that are not exclusively even or exclusively odd.

I have read there are inductive proofs of $\forall x \exists y(x=y+y \lor x=S(y+y))$ in PA. I would be interested in any proof of $\forall x \exists y(x=y+y \overline{\vee} x=S(y+y))$ in PA.

This is just a partial answer. Let $\mathcal L =\{S,<\}$ be the language with an unary function $S$ and a binary relation $<$. Consider the structure $(\mathbb N, S,<)$ ($S$ is the successor function), then $E=\{2n:n\in\mathbb N\}$ is not definable in $(\mathbb N, S,<)$. To see this consider the elementary extension $\mathfrak C=(\mathbb N\sqcup \mathbb Z, S,<)$, and define an automorphism $\Phi:\mathfrak C\to \mathfrak C$ as follows $\Phi(n)=n$ if $n\in\mathbb N$ and $\Phi(n)=S(n)$ otherwise. It is easy to see, using $\Phi$, that there is no formula defining $E$.

I appear to have found an answer to my own question, from page 49 of Edward Nelson’s book The Elements (which was a failed attempt to prove that Peano arithmetic is inconsistent):

“Here is a semantic indication that induction is necessary to prove this. Take a nonstandard model of $P$ and let $\alpha$ be a nonstandard number. Take the external set $U$ of all standard numbers together with all numbers obtained by repeatedly applying the functions symbols of $Q_{90}$ to $\alpha$. Then U is the universe of a model of $Q_{90}$, but there is no individual $\beta$ in $U$ such that either $2 \beta = \alpha $

or $2 \beta + 1= \alpha $.”

Here $P$ denotes Peano arithmetic and $Q_{90}$ denotes Robinson arithmetic with basic properties of addition, multiplication, and order added.

Can anyone explain what Nelson’s reasoning? Why can’t there be a $\beta$ in $U$ such that either $2 \beta = \alpha $

or $2 \beta + 1= \alpha $?

- Help with these isomorphisms
- prove the identity using combinatorics
- Curves triangular numbers.
- Find pairs of side integers for a given hypothenuse number so it is Pythagorean Triple
- Motivation for the importance of topology
- Analytic method for determining if a function is one-to-one
- “Proof” that $\mathbb{R}^J$ is not normal when $J$ is uncountable
- Limit of algebraic function avoiding l'Hôpital's rule
- A question on convergence of derivative of power series
- Prove an inequality
- Is the following matrix invertible?
- Does factor-wise continuity imply continuity?
- Do we have negative prime numbers?
- Conjecture: Only one Fibonacci number is the sum of two cubes
- Visualization of surface area of a sphere