Mathematics/Discrete Math/Proofs - Revision history

Brodriguez: Brodriguez moved page Discrete Math/Proofs to Mathematics/Discrete Math/Proofs

2020-10-25T17:23:32Z

Brodriguez moved page Discrete Math/Proofs to Mathematics/Discrete Math/Proofs

← Older revision

Revision as of 17:23, 25 October 2020

Brodriguez: Brodriguez moved page Discrete Math - Proofs to Discrete Math/Proofs: Clean url with subpages

2020-05-15T08:55:10Z

Brodriguez moved page Discrete Math - Proofs to Discrete Math/Proofs: Clean url with subpages

← Older revision

Revision as of 08:55, 15 May 2020

Brodriguez: Update direct proof logic

2019-12-20T00:50:18Z

Update direct proof logic

← Older revision		Revision as of 00:50, 20 December 2019
Line 19:		Line 19:
	</pre>		</pre>

	By definition of an odd number, we have proven that our n^2 is also odd.		If you think about it, we can simplify this down to:<br>
			<code>2m + 1</code>, for <code>m = (2k^2 + 2k)</code>.

			This <code>2m + 1</code> is comparable to our orginal <code>2k + 1</code> definition of an odd number.

			So by definition of an odd number, we have proven that our n^2 is also odd.

	== Proof by Contraposition ==		== Proof by Contraposition ==

Brodriguez: Add induction proofs

2019-09-10T06:55:09Z

Add induction proofs

@@ Line 71: / Line 71: @@
 === Proof by Contradiction Example ===
-Let's try to prove that √2 is irrational.
+Let's try to prove that '''√2 is irrational'''.
 Using proof by contradiction, we first assume the opposite, aka that √2 must be rational.
@@ Line 95: / Line 95: @@
 Logically, this means our assumption is false, and the original statement (√2 is irrational) must be true.

Brodriguez: Create page

2019-09-09T13:49:09Z

Create page

New page

Proofs are a formal means to mathematically show that something is true or false. It can be done in three main ways.

== Direct Proof ==
This is a proof in which we directly declare that <code>p → q</code>. We assume that p is true and go on to show that means q is automatically true. Often times, this is a fairly straightforward means of creating proofs.

=== Direct Proof Example ===
Let's prove the theorem "'''If n is an odd integer, then n^2 is odd.'''"

First, we can define an odd number as "any value <code>2k + 1</code> where k is an integer".

Thus, we have the first part of our proof, <code>n = 2k + 1</code> to define any odd integer.

Next, we want to prove that any n^2 is odd, so we have:

<pre>
n^2 = (2k+1)^2 is odd.
= 4k^2 + 4k + 1
= 2(2k^2 + 2k) + 1
</pre>

By definition of an odd number, we have proven that our n^2 is also odd.

== Proof by Contraposition ==
Sometimes, a direct proof isn't easy to create. An alternative means is to prove the opposite is true, that is by proving <code>¬p → ¬q</code>.

=== Proof by Contraposition Example ===
Let's prove that "'''If n is an integer and 3n + 2 is odd, then n is odd.'''"

We start by attempting a direct proof first. So by once again defining an odd number as "any value <code>2k + 1</code> where k is an integer", we have:
<pre>
3n + 2 = 2k + 1
3n + 1 = 2k
</pre>

At this point, we have two variables and not much we can do with them. So we move on to attempt a proof by contraposition. That is, we start by assuming the original statement is false, which gives us the alternative: "'''If n is an integer and 3n + 2 is odd, then n is even.'''"

We can define an even number as <code>n=2k</code> for any integer k. So we can substitute to get:

<pre>
3n + 2
3(2k) + 2
6k + 2
2(3k + 1)
</pre>

As we can see, no matter what value we enter for k, the end result will be a multiple of 2. This means that, if we assume n is even, then <code>3n + 2</code> is actually also even, thus proving our contraposition false.

By extension, this means that the opposite of our assumption must have been true after all, which means we have indirectly proven that "'''If n is an integer and 3n + 2 is odd, then n is odd.'''"

==== Note About Example ====
Note that there may be multiple ways to solve a given proof. In our example, we could have solved it directly if we used substitution instead. We would have:

"'''If n is an integer and 3n + 2 is odd, then n is odd.'''"<br>
We define an odd number as "any value <code>2k + 1</code> where k is an integer."

<pre>
3n + 2
3(2k + 1) + 2
6k + 3 + 2
6k + 4 + 1
2(3k + 2) + 1
</pre>

No matter what value we enter for k, we will result in a multiple of 2, plus 1. This leads us back to our original definition of an odd number, thus proving our original assumption.

== Proof by Contradiction ==
A proof by Contradiction is similar to a proof by contraposition, in that it is an indirect proof that may start off similarly. However, proof by contradiction attempts to prove a given p in three steps:
* First, assuming ¬p. Aka, assume that p is false.
* Next, prove that ¬p implies both q and ¬q. That is, <code>¬p → (q ∧ ¬q)</code>.
* Since q and ¬q cannot both be true, then ¬p must be false, meaning that p is true.

=== Proof by Contradiction Example ===
Let's try to prove that √2 is irrational.

Using proof by contradiction, we first assume the opposite, aka that √2 must be rational.

Thus, by definition of a rational number, then there must be two numbers a, b, such that <code>√2 = a/b</code>. Note that b ≠ 0, and a and b have no factors.

We can then go on to solve:

<pre>
√2 = a/b
2 = a^2/b^2
2b^2 = a^2
</pre>

At this point, we can use the definition of an even integer to declare that a^2 must be even. If a is even, then a=2c for some arbitrary integer c. Which gives us:

<pre>
2b^2 = 4c^2
b^2 = 2c^2
</pre>

We can now declare that b^2 is even. But wait. We already determined that a/b must be in lowest terms, resulting in a and b having no factors. By definition, if they're both even, then they can be factored, therefore they cannot both be even at once.

Logically, this means our assumption is false, and the original statement (√2 is irrational) must be true.