6 ms·

https://proofwiki.org/wiki/Square_Root_of_Prime_is_Irrational https://proofwiki.org/wiki/Square_Root_of_Prime_is_Irrationa... Your proof hinges on the not-dire

https://proofwiki.org/wiki/Square_Root_of_Prime_is_Irrational https://proofwiki.org/wiki/Square_Root_of_Prime_is_Irrationa... Your proof hinges on the not-directly-stated words "so, if x were 2, we would reach an impossibility" where impossibility == contradiction.

ikeboy 12y ago
But that's not the proof I used. My proof was positive. They may be equivalent, but not if we count proof by contradiction as special. In response to edit: No, it doesn't. Having proven that x contains an even number of 2s as factors, it follows that x is not two. 2 does not have an even number of 2s as factors, x does, therefore they are different. No contradiction required.
- Retra 12y ago
  I can't see the difference between your proof and the given one, except that you didn't write yours out with the same degree of formality. If you wrote your proof using only applied axioms and theorems, it would be essentially identical. The key point here is that you are partitioning the possibilities in a binary fashion: either x has even number of prime factors or it does not. You've shown that it must not have an even number of prime factors. You haven't shown that it isn't 2. You implied that if it were true, that would contradict what you have shown. How you go from "X has an even number of prime factors" to "X can't be 2" is important.
  - ikeboy 12y ago
    Take two cases. One where x has no factors of two, and one here it has at least 2. In the first case, x is not divisible by 2, while 2 is divisible by 2, therefore x is not 2. In the second case, x is divisible by 4, while 2 is not, therefore x is not 2. You're right that they are "essentially" the same proof, but excluding contradictions is weird, a bit like excluding the letter e. Rephrasing a proof to not use it may be possible in some cases.
    - Retra 12y ago
      >Take two cases. This is where you are implicitly employing proof by contradiction. Why do you take two cases and not three? Or four? What assumption allows you to restrict your conclusions like that? Probably the Law of the Excluded Middle: (P or ~P). (This is equivalent to ~~p = p.) Once you assume or derive either of those, you have validated proof by contradiction.
      - ikeboy 12y ago
        I proved that x has an even number of factors of 2. Why can't I then split that into scenarios when that even number is 0, and cases where it isn't? I don't see any restrictions here. Let's imagine I had shown that something was either one or two. You seem to be claiming I could not take positive proofs assuming each of them and turn it into a full proof.
        ebola1717 12y ago
        >Let's imagine I had shown that something was either one or two. You seem to be claiming I could not take positive proofs assuming each of them and turn it into a full proof. When you break it down to the logical axioms, you can't use cases like that. Try it yourself. You get something like this: Let A: (k > 0) B: (k = 0) k is a whole number, therefore A v B. A -> X !=2 B -> X !=2 Okay, from here, you need to deduce X != 2. Traditionally we do this by applying proof by cases, but as I showed in my other comment, this requires the law of the excluded middle. I don't see any other propositional logic axioms we can apply to achieve the same result.
        ikeboy 12y ago
        >Traditionally we do this by applying proof by cases, but as I showed in my other comment, this requires the law of the excluded middle. I think that's because you don't know A v B. But in my case you can directly prove A v B. The form is (A v B, A -> C, B -> C) -> C. https://en.wikipedia.org/wiki/Proof_by_exhaustion https://en.wikipedia.org/wiki/Proof_by_exhaustion says that this is called a direct proof.
- ebola1717 12y ago
  It's not obvious that the statement "if x and y are different prime factorizations, they are not equal" can be proven without proof by contradiction.
  - ikeboy 12y ago
    I don't need such a general statement. I only need the assumption that 2 can only be prime factorized with an odd number of 2s, which is trivial.
- gamegoblin 12y ago
  If you are rigorous in your expansion of "it follows that x is not two", you will find your contradiction. Here is a more rigorous form of what you've said there: Let X be an integer with a prime factorization in the form 2^(2k) * p_1 * p_2 ... * p_n where k is a positive integer and p_i for any i is a prime not equal to 2. Proposition: X is not 2 Proof: Assume X is 2. The prime factorization of X is: X = 2 By the definition of X, we have: 2 = 2^(2k) * p_1 * p_2 ... * p_n Since we defined k to be a positive integer, we have min(2^(2k)) = 2^(2(min(k)) = 2^(2*1) = 4 So we have: 2^(2k) >= 4 So we have: 2^(2k) > 2 Since p_i for all i are all positive integers, we have: 2 < 2^(2k) * p_1 * p_2 ... * p_n So we have: 2 != 2^(2k) * p_1 * p_2 ... * p_n Thus: 2 != X And we have arrived at a contradiction.
  - ikeboy 12y ago
    First 3 lines are same as yours. Consider k. Either it is 0, or greater. Consider 0. In that case, X is not divisible by 2, hence cannot be 2. Now consider k positive. (My original proof didn't show k wa positive, so I needed to deal seperately.) Use your proof to show that 2^(2k) > 2, and then 2!=X. As far as I can tell you never actually used the assumption that 2=x, so that can be deleted from the proof and it remains valid.
    - ebola1717 12y ago
      I think "Proof by cases" uses proof by contradiction. You're proving that given A -> C and !A -> C, then C, which requires the axiom A v !A, i.e. proof by contradiction. In your proof, you've proven k=0 -> X != 2, and k > 0 -> X !=2, but it doesn't follow that X != 2 without contradiction.
      - ikeboy 12y ago
        I proved k was a whole number previously. I don't need that axiom, because I can prove it in the case of k.

ikeboy 12y ago

But that's not the proof I used. My proof was positive. They may be equivalent, but not if we count proof by contradiction as special. In response to edit: No, it doesn't. Having proven that x contains an even number of 2s as factors, it follows that x is not two. 2 does not have an even number of 2s as factors, x does, therefore they are different. No contradiction required.

Retra 12y ago
I can't see the difference between your proof and the given one, except that you didn't write yours out with the same degree of formality. If you wrote your proof using only applied axioms and theorems, it would be essentially identical. The key point here is that you are partitioning the possibilities in a binary fashion: either x has even number of prime factors or it does not. You've shown that it must not have an even number of prime factors. You haven't shown that it isn't 2. You implied that if it were true, that would contradict what you have shown. How you go from "X has an even number of prime factors" to "X can't be 2" is important.
- ikeboy 12y ago
  Take two cases. One where x has no factors of two, and one here it has at least 2. In the first case, x is not divisible by 2, while 2 is divisible by 2, therefore x is not 2. In the second case, x is divisible by 4, while 2 is not, therefore x is not 2. You're right that they are "essentially" the same proof, but excluding contradictions is weird, a bit like excluding the letter e. Rephrasing a proof to not use it may be possible in some cases.
  - Retra 12y ago
    >Take two cases. This is where you are implicitly employing proof by contradiction. Why do you take two cases and not three? Or four? What assumption allows you to restrict your conclusions like that? Probably the Law of the Excluded Middle: (P or ~P). (This is equivalent to ~~p = p.) Once you assume or derive either of those, you have validated proof by contradiction.
    - ikeboy 12y ago
      I proved that x has an even number of factors of 2. Why can't I then split that into scenarios when that even number is 0, and cases where it isn't? I don't see any restrictions here. Let's imagine I had shown that something was either one or two. You seem to be claiming I could not take positive proofs assuming each of them and turn it into a full proof.
      - ebola1717 12y ago
        >Let's imagine I had shown that something was either one or two. You seem to be claiming I could not take positive proofs assuming each of them and turn it into a full proof. When you break it down to the logical axioms, you can't use cases like that. Try it yourself. You get something like this: Let A: (k > 0) B: (k = 0) k is a whole number, therefore A v B. A -> X !=2 B -> X !=2 Okay, from here, you need to deduce X != 2. Traditionally we do this by applying proof by cases, but as I showed in my other comment, this requires the law of the excluded middle. I don't see any other propositional logic axioms we can apply to achieve the same result.
        ikeboy 12y ago
        >Traditionally we do this by applying proof by cases, but as I showed in my other comment, this requires the law of the excluded middle. I think that's because you don't know A v B. But in my case you can directly prove A v B. The form is (A v B, A -> C, B -> C) -> C. https://en.wikipedia.org/wiki/Proof_by_exhaustion https://en.wikipedia.org/wiki/Proof_by_exhaustion says that this is called a direct proof.
ebola1717 12y ago
It's not obvious that the statement "if x and y are different prime factorizations, they are not equal" can be proven without proof by contradiction.
- ikeboy 12y ago
  I don't need such a general statement. I only need the assumption that 2 can only be prime factorized with an odd number of 2s, which is trivial.
gamegoblin 12y ago
If you are rigorous in your expansion of "it follows that x is not two", you will find your contradiction. Here is a more rigorous form of what you've said there: Let X be an integer with a prime factorization in the form 2^(2k) * p_1 * p_2 ... * p_n where k is a positive integer and p_i for any i is a prime not equal to 2. Proposition: X is not 2 Proof: Assume X is 2. The prime factorization of X is: X = 2 By the definition of X, we have: 2 = 2^(2k) * p_1 * p_2 ... * p_n Since we defined k to be a positive integer, we have min(2^(2k)) = 2^(2(min(k)) = 2^(2*1) = 4 So we have: 2^(2k) >= 4 So we have: 2^(2k) > 2 Since p_i for all i are all positive integers, we have: 2 < 2^(2k) * p_1 * p_2 ... * p_n So we have: 2 != 2^(2k) * p_1 * p_2 ... * p_n Thus: 2 != X And we have arrived at a contradiction.
- ikeboy 12y ago
  First 3 lines are same as yours. Consider k. Either it is 0, or greater. Consider 0. In that case, X is not divisible by 2, hence cannot be 2. Now consider k positive. (My original proof didn't show k wa positive, so I needed to deal seperately.) Use your proof to show that 2^(2k) > 2, and then 2!=X. As far as I can tell you never actually used the assumption that 2=x, so that can be deleted from the proof and it remains valid.
  - ebola1717 12y ago
    I think "Proof by cases" uses proof by contradiction. You're proving that given A -> C and !A -> C, then C, which requires the axiom A v !A, i.e. proof by contradiction. In your proof, you've proven k=0 -> X != 2, and k > 0 -> X !=2, but it doesn't follow that X != 2 without contradiction.
    - ikeboy 12y ago
      I proved k was a whole number previously. I don't need that axiom, because I can prove it in the case of k.