0

I want to prove the following theorem:

Theorem 1: Let $a,b,c\in\mathbb{N}$, then $a+b\neq a$

using the following axiom

Axiom: There exists a set $\mathbb{N}$ with an element $1 \in\mathbb{N}$ and a function $s: \mathbb{N}\rightarrow\mathbb{N}$ that satisfy the following three properties.

  1. There is no n $\in\mathbb{N}$ such that $s(n)=1$.

  2. The function $s$ is injective.

  3. Let $G\subseteq\mathbb{N}$ be a set. Suppose $1 \in G$, and that if g $\in G$ then $s(g)\in G$. Then $G=\mathbb{N}$.

and theorem

Theorem 1: There is a unique binary operation +: $\mathbb{N}\rightarrow\mathbb{N}$ that satisfies the following two properties for all n,m $\in\mathbb{N}$

1) $n+1=s(n)$

2) $n+s(m)=s(n+m)$

I have two proof ideas, and I do not know if they satisfy the "$g\in G\rightarrow s(g)\in G$" line of part 3 of the axiom.

My first idea was to consider a set $G=\{a\in\mathbb{N}:\forall b\in\mathbb{N}(a+b\neq a)\}$ and show that the contrapositve of $g\in G\rightarrow s(g)\in G$ is true, that is, $\neg(s(g)\in G)\rightarrow\neg(g\in G)$, but I do not know if changing the axiom like that is allowed.

My second idea was to show that $((g\in G)\land\neg(s(g)\in G))\rightarrow false$ which is shown here to be logically eqivalent to $g\in G\rightarrow s(g)\in G$. Again, I do not know if its okay to change the logical structure of an axiom.

Community
  • 1
Lindstorm
  • 201
  • 1
    You're missing a definition of $+$ (or at least axioms that assert some properties of it). – hmakholm left over Monica Aug 10 '16 at 20:46
  • Anyway, if you manage to prove $\forall g: s(g)\notin G\to g\notin G$ then you don't need to "change the axiom". Simply derive $\forall g:g\in G\to s(g)\in G$ from $\forall g:s(g)\notin G\to g\notin G$ by contraposition, and you're all set to use the official form of the axiom. – hmakholm left over Monica Aug 10 '16 at 20:50
  • @HenningMakholm I did not think that would matter because I am only concerned with the logical structure of the proof (can I use the contrapositive instead of the premise given) and not so much with the details of the actual proof. I will add the definition of $+$. – Lindstorm Aug 10 '16 at 20:52
  • @HenningMakholm Am I allowed to derive the official form of the axiom from the contrapositive? Because I would not be using any theorems or definitions to do that, I would just be using a truth table? – Lindstorm Aug 10 '16 at 20:56
  • 1
    You don't need to "derive the official form of the axiom" -- it's an axiom; you already have it. But you're certainly always allowed to derive $P\to Q$ from $\neg Q\to \neg P$, or to derive $\neg Q\to\neg P$ from $P\to Q$ -- that's what the two statements being equivalent means. – hmakholm left over Monica Aug 10 '16 at 20:58
  • @HenningMakholm The reason I am ask this is becuase I was told some mathematicians do not like using the idea of a contrapositve, so I thought maybe it was not allowed. And to clairfy, all I have to do to is say the general statement is equivalent to the contrapositive by contraposition, then its okay? – Lindstorm Aug 10 '16 at 23:07
  • 1
    The contrapositive of an implication is equivalent in classical logic. In intuitionistic logic they are not, but you should focus on learning one logic at a time, starting with classical (first-order) logic. Later once you've a good enough grasp of classical logic it is easy to learn about other logics. Almost all modern mathematics is done in classical logic, so feel free to use the equivalence. – user21820 Aug 21 '16 at 17:09

0 Answers0