0

A set $N$ is defined with some axioms, where $P$ and $Q$ are two of the axioms.

I am trying to prove a statement $P\rightarrow Q$ to show that $Q$ is redundant. I'm doing this by using the contrapositive. So, I assumed $\neg Q$. I defined a function $f:N \rightarrow N$ which is definitely well-defined. It can be showed that the definition of $f$ implies $\neg P$. So, $\neg Q \rightarrow \neg P$ or at least that is what I think it is.

I'm worried about making a function that contradicts an axiom of the set it's defined on. Am I doing this correctly?

Caleb Stanford
  • 45,895
Foon
  • 137
  • 3
    This is very vague. It sounds like you have not done anything wrong but I would strongly recommend that you explain more precisely what you are doing if you want a more definitive answer. – Eric Wofsey Aug 22 '18 at 16:43
  • 1
    Why are you proving a statement $P \to Q$ if you already know $P$? Why not just prove $Q$? That is why your proof seems weird. But it's a perfectly valid proof of $Q$. – Caleb Stanford Aug 22 '18 at 16:43
  • I have edited the question . Actually $Q$ is also an axiom, the purpose is to show that $Q$ is redundant. I hope that makes my intentions clear. – Foon Aug 22 '18 at 16:49
  • If you can confirm that what I'm doing is valid then please post it as an answer and I'll accept it as best answer. – Foon Aug 22 '18 at 16:51
  • @Foon Thanks for clarifying -- I understand now, and I wrote an answer. – Caleb Stanford Aug 22 '18 at 16:52
  • 1
    It looks rather fishy with "I defined a function $f$ which is definitely well-defined" -- how can a definition of a function imply anything about your axioms? The description makes me suspect that you might be confusing satisfiability for truth somewhere. I would recommend that you ask about what you're doing in a less hush-hush way for a sanity check. – hmakholm left over Monica Aug 22 '18 at 16:58
  • @HenningMakholm I rechecked what I was doing and just as you suspected, I'm 99% sure that $f$ requires $Q$ to be defined. And so, my proof is wrong. Thanks for the critique! If I do feel like I found a valid $f$, then I'll post again with the details in a new post. The answer selected below did remove my confusion for which I asked the question. – Foon Aug 22 '18 at 17:37

1 Answers1

1

EDIT: If $Q$ is also used to construct $N$, then the proof is likely invalid. The below assumes only $P$ is used to construct $N$.

A set $N$ is defined with some axioms, where $P$ is one of the axioms.

I assume that you mean that you assumed axiom $P$ in the construction of the set $N$; that is, that without axiom $P$, you wouldn't be able to prove that $N$ existed in the first place.

I am trying to prove a statement $P\rightarrow Q$ by using the contrapositive. So, I assumed $\neg Q$. I defined a function $f:N \rightarrow N$ which is definitely well-defined. It can be showed that the definition of $f$ implies $\neg P$. So, $\neg Q \rightarrow \neg P$ or at least that is what I think it is.

I see that as you clarified in the comments, you are no longer assuming $P$ is an axiom (otherwise you would just prove the statement $Q$, instead of trying to prove $P \to Q$).

Your proof is correct, but you are right that it's a bit fishy. Specifically, it is not a proof by contrapositive -- it's a proof by contradiction!

Let's discuss why this is. You assumed $\lnot Q$, but you also defined the function $f: N \to N$. In order to define it, you needed to assume $P$. So you are not really just assuming $\lnot Q$. You are assuming $\boldsymbol{P}$ and $\boldsymbol{\lnot Q}$. That's the form of a proof by contradiction.

Then, when you arrive at the conclusion that the definition of $f$ implies $\lnot P$, this contradicts your earlier assumption $P$ (you assumed $P$ and not $Q$). That is, it is impossible for $P$ to hold and not $Q$, which is the same as saying that $P$ implies $Q$ ($P \to Q$).

I'm worried about making a function that contradicts an axiom of the set it's defined on. Am I doing this correctly?

Essentially your worry is correct -- but your proof ends up being right anyway, as long as you phrase it as a proof by contradiction instead of a proof by contrapositive.

Caleb Stanford
  • 45,895
  • Ugh, how did I even miss that! xD Thank you so much for clarifying! This clears out everything! – Foon Aug 22 '18 at 16:57
  • I am not at all confident that your initial assumption is what OP meant. As I read it, $P$ and $Q$ are axioms that are used to characterize $N$ (e.g., the Peano axioms for the natural numbers), rather than to prove its existence. – Eric Wofsey Aug 22 '18 at 16:57
  • @EricWofsey Well, I didn't notice that $Q$ was added to the list of axioms, so that is a problem. But whether they are used to characterize or to construct, I don't see a huge difference. – Caleb Stanford Aug 22 '18 at 17:01
  • @Foon I didn't see that you added $Q$ to the axioms. If construction or characterization of $N$ depends on axiom $Q$, the proof would not be valid any longer. – Caleb Stanford Aug 22 '18 at 17:02
  • @6005 Yes. That makes sense. However, $Q$ does not bring any element into existence, it only talks about a property that holds for all elements in $N$. Does that count as a characterization? – Foon Aug 22 '18 at 17:04
  • Nevermind. I found that, very subtly, $f$ depends on $Q$. So the proof is invalid. – Foon Aug 22 '18 at 17:39
  • @Foon Oh, I see. Right, if the axiom $Q$ is used in any way in constructing $N$ or $f$ or reasoning about $N$ or $f$, then the proof would be invalid. The proof of contradiction from assuming $P$ and $\lnot Q$ must not assume $Q$. – Caleb Stanford Aug 22 '18 at 18:02