Prove that the union of A and (~A) is equal to the unvierse

Let ~A = not A, or all elements that are not in the set "A" and prove that the union of A and ~A is equal to the Universe.

First, assume that A and ~A is a subset of the universe. Let x be an object in the universe, then x is either an object in A or not an object in A, and therefore is always in the universe.

Prove that the intersection of A and B is a subset of A

Prove that the intersection of A and B is a subset of A


Suppose there is a x which is in the intersection of A and B. Therefore that x is also in A, and so the intersection of A and B is a subset of A. ~~~~

Let A= x: P(x) and B= x: Q(x) Prove that if for all x: P(x) = > Q(x) then A is a subset of B.

Let A= x: P(x) and B= x: Q(x)Prove that if for all x, P(x) implies Q(x) then A is a subset of B.

Let x be any object and suppose that it is a subset of A. Then P(x) must be true for all x, and since for all x, P(x) implies Q(x) then x is a subset of B. So therefore, A is a subset of B.~~~~

Prove if A is a subset of B, and B is a subset of C, then A is a subset of C.

Prove if A is a subset of B, and B is a subset of C, then A is a subset of C.

Assume A is a subset of B, and B is a subset of C.

Then there is an x in B such that, for every x in B x is in C and there exists an x in A such that, for every x in A x is in B. Thus, for every x in A, x is also in C, and therefore A is a subset of C.

Prove for any set A, A is a subset of A

Prove for any set A, A is a subset of A

Assume we have a set A, and x is an object in that set.

Then x being a subset of A, implies x is a subset of A.

Thus, for all x that is are objects in A, x is an object in A, and so, A is a subset of A. ~~~~

Prove for any set A, null is a subset of A.

Prove for any set A, null is a subset of A.

Let A be any set, and x any object.

Consider the conditional sentence: x is a subset of null implies x is a subset of A. Since the antecedent (x is a subset of null) is false, then the sentence itself is true, and therefore null is a subset of A.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of...

Euclid's algorithm is a way to find the GCD of any Euclidian domain, in this case, the natural numbers.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of positive integers q(i) and r(i) such that

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0 and

a = bq(1) + r(1)
b = r(1)q(2) + r(2)
r(1) = r(2)q(3) + r(3)
r(2) = r(3)q(2) + r(4)
.
.
.
r(k-2) = r(k-1)q(k) + r(k)
r(k-1) = r(k)q(k+1) (that is, r(k+1) = 0 )

and therefore d = r(k)

Proof

Since a < = b then there exists a q(1) and r(1) such that a = bq(1) + r(1) where 0 < = r(1) < b , and therefore, since r(1) < b there exists a q(2) and r(2) such that b=r(1)q(2) + r(2) and so one for r(2)< r(1). If we keep going down the line of positive integers we reach a point were r(k+1)=0 and so it is evident that:

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0

Now, to show that d (the GCD) is equal to r(k) we have to show that r(k) < = d and r(k) > = d.

First we show that r(k) < = d.

We first notice that r(k) divides r(k-1) (because r(k-1) = r(k)q(k+1)), we also notice that r(k) divides r(k-2) because r(k-2) = r(k-1)q(k) + r(k), and so r(k) divides both r(k) and r(k-1) by the proof we did two days ago. (When another proof is used in a proof, it is called a lemma). Now, if we keep going up the line, we see that every number has a component of the previous integer, and so r(k) is a common divisor for all the numbers including a and b. Since d is the GCD for a and b, then r(k) has to be < = d by the proof we did yesterday.

Now we show that r(k) > = d.

We note that d divides r(1) since r(1) = a - bq(1), and since d divides r(1) then by the proof we did two days ago, d also divides r(2) since r(2) = b - r(1)q(2), continuing this pattern down the line we see that d divides r(k-1) and r(k) and therefore r(k) > = d.

Now we can say that d= r(k) which is equal to 1, and 1 is the GCD of all positive integers, or the natural numbers.

Let d be the greatest common divisor of two positive integers a and b. If c is a positive integer such that c divides a ,and c divides b, then c <= d

Let d be the greatest common divisor of two positive integers a and b. Prove if c is a positive integer such that c divides a ,and c divides b, then c <= d.

This is a somewhat simple proof since it uses the definition of a greatest common divisor.

A greatest common divisor (GCD) is the largest integer which divides two other integers. Take for example the numbers 24 and 16. 8 is the GCD for 24 and 16 since 8 is the largest number that will divide both of them.

So if the GCD=d then d divides a, and d divides b.

The numbers 4 and 2 also divide 24 and 16, but are not the "Greatest". However, we do see that 4 and 2 also divide 8, which is the second part of the definition of a GCD.

For every positive integer c, if c divides a and c divides b, then c divides d.

It is this last part of the definition we will use for our proof. If c is an integer which divides a and b, then by definition c must also divide the GCD, which is d. And therefore c < d. ~~~~

Prove if c divides a and c divides b, then c divides any combination an+bm, where n and m are integers

Prove if c divides a and c divides b, then c divides any combination an+bm, where n and m are integers.

Since c divides both a and b then there must exist integers j and t such that a=cj and b=ct.

So by substitution into an+bm we get

an+bm = (cj)n+(ct)m = c (jn + tm). So c divides (an + bm) ~~~~

Thus, if c divides a and b, then c also divides any multiple of a and b.

Prove that X = Y where X is a solution to x^2 - 1 = 0 and y = 1,-1

Prove that X = Y where X is a solution to x^2 - 1 = 0 and y = 1,-1

This is a set theory proof. The idea is that if X is a subset of Y, and Y is a subset of X, then X = Y.

So, first we show that Y is a subset of X. And we can do this by simply substituting the values for y in x^2 - 1 = 0. We see that both 1 and -1 work when substituted for X, and so Y is a subset of X.

Now we have to prove that X is a subset of Y. If we factor x^2 - 1 we get (x-1)(x+1) = 0. It is evident that this product is 0 exactly when x=1 or x=-1; so X is a subset of Y.

Now since Y is a subset of X, and X is a subset of Y, then X=Y

Prove if k and m are rational numbers with k < m, there exists a rational number between k and m

Prove if k and m are rational numbers with k < m, there exists a rational number between k and m

k < m = k+k < k+m = 2k < k+m = k < k+m/2 so k < (m+k)/2

and

k < m = k+m < m+m = k+m < m+m = k+m < 2m so (k+m)/2 < m

if we let t=(k+m)/2 then t is a rational number between k and m. ~~~~

Prove if x+y is irrational then x or y are irrational.

For real numbers x and y prove if x+y is irrational then x or y are irrational.

This is a proof by contraposition, so we assume x and y are rational.

then x=m/k and y=n/t where m,k,n,t are integers.

so x+y = m/k + n/t = (mt + nk)/(kt) which is rational since m t n k are integers.

So x+y is rational. Therefore, by contraposition (~q=>~p therefore p=>q), if x+y is irrational then x or y are irrational.

Prove for every odd integer n, 4n^2 + 3n + 2 is odd

Prove for every odd integer n, 4n^2 + 3n + 2 is odd

Let n be an odd integer, so n = 2h + 1 for some integer h.

So 4n^2 + 3n + 2 = 4(2h+1)^2 + 3(2h+1) + 2 =

16h^2 + 16h + 4 + 6h + 3 + 2 =

16h^2 + 22h + 9 =

2(8h^2 + 11h + 4) + 1, which is odd, and therefore

4n^2 + 3n + 2 is odd for every odd integer n.

Prove that there do not exist integers k and j such that 2j + 6k = 9

Prove that there do not exist integers k and j such that 2j + 6k = 9

Assume that j and k are integers. Then 2j + 6k = 2(j+3k) which is even, but 9 is odd, so it is evident that no integers j and k can be used to equal an odd number.

Prove if m is irrational, then 5m is irrational. (Contraposition)

Prove if m is irrational, then 5m is irrational.

Remember that contraposition is where we have to prove P => Q so we use the following logic:

~Q => ~P so therefore P => Q

Thus we start off assuming the opposite of the consequent (~Q) which is that 5m is rational.

If that is true then 5m can be equal to two integers j and k(non-zero) such that 5m = j/k , since a rational number is one that can be expressed as the ratio of two integers, and an irrational number is one which can't, like 3.333333 or Pi.

So 5m = j/k and m = j/(5*k) , and thus m is rational, so now we have ~P for the contraposition part of the proof, and so we can say ~Q => ~P so therefore P => Q and so if m is irrational then 5m is irrational

Prove if ab is odd, then both a and b are odd. (Contradiction)

Assume a and b are positive integers, prove if a*b is odd then a and b are odd.

Proof by contradiction: where we want to prove Q => P we take ~P=> Q Λ ~ Q which is a contradiction, so therefore we conclude P.

This is a proof by contradiction which means that we have to assume the opposite consequent, which is the say that a and b are not both odd. So either a is even or b is even.

If a is even, then a=2k for some integer k, and b*2k will always be even.

If b is even, then b=2m for some integer m, and a*2m will always be even.

So either case leads to a contradiction that a*b is odd, and therefore if a*b is odd, then both a and b are odd.

Prove if x is even, then x+1 is odd.

Let x be an integer and prove if x is even, then x+1 is odd.

We will use contraposition for this proof, so we start by assuming that x + 1 is not odd.

Then we can say there exists an integer k such that x + 1 = 2k

so x = 2k - 1 = 2(k-1) + 1

Thus x = 2(k-1) + 1 which is odd. So we can no say if x + 1 is not odd, then x is not even. Thus, by contraposition, if x is even, x+1 is odd.

If x^2 (x squared) is odd then x is odd. (Contraposition)

Assume x is an integer. If x^2 (x squared) is odd then x is odd.


This is the same proof as we did yesterday, except this time we will prove the statement using another form of logic called contraposition.


To do this, we must first state the contrapositive of what we set out to prove.

so

If x^2 (x squared) is odd then x is odd

now becomes

If x^2 (x squared) is even then x is even

which is the contrapositive, the idea is that if we can prove that x^2 is even for all x that is even, it stands to reason that x^2 can only be odd for all x that is odd.

The way to write this symbolically is ~Q => ~P so therefore P => Q.

So now we prove if x^2 (x squared) is even then x is even

x is even so x=2y for some integer y.

then x^2 = 2y(2y) = (4y^2) = 2(2y^2) which is even.

Therefore if x^2 is even x is even, so by contraposition, if x^2 is odd, x is odd.

Prove that if x^2 is odd then x is odd. (Direct proof)

Assume x is an integer. If x^2 (x squared) is odd then x is odd.

First lets look at some examples

3^2 is 9
5^2 is 25
7^2 is 49
9^2 is 81

So it does appear that for any odd integer, its square is also an integer, how can we prove this for all cases?

First we assume x is odd, then x=2y+1 for some integer y.

So now x^2 = (2y+1)(2y+1) = 4y^2 + 4y + 1= 2(2y^2 + 2) + 1 which is odd.

Prove if x*y = 1 then x = y = 1

Assume that x and y are positive integers, prove that if x * y = 1 then x = y = 1

If x * y = 1 then x = (1/y) and y = (1/x)

Yesterday we proved that if an integer x divides an integer y then x<=y.

So since y divides 1 or (1/y) then y<=1

and since x divides 1 or (1/x) then x<=1

Since both x and y are integers then y=1 and x=1, so x = y = 1

Prove that if x divides y, then x<=y

Assume that x and y are positive integers, prove that if x divides y then x<=y.

If x divides y then there exists another integer j such that y=xj.


Now we can say x =< xj and canceling out the x we get 1<=j or that is to say, j is greater than or equal to 1.

This is true because both x and y are positive so j must be positive for our initial antecedent y=xj to be true. Also since we assumed j is an integer then j>=1. So now we know that x<=xj and by substitution of y=xj we get x<=y.

Prove that |x+y| <= |x| + |y|

Assume x and y are real numbers prove that the absolute(positive) value of x+y is less than or equal to the absolute value of x plus the absolute value of y.

Or:

Prove that |x+y| <= |x| + |y|

This proof has 4 parts:

PART 1
Assume x < 0 and y < 0 then x + y< 0, so that |x+y| = (x+y) or -(x+y) in the first case (x+y)=|x|+|y| and in the second case -(x+y)<|x|+|y| thus |x+y|<=|x|+|y|

Part 2
Assume x < 0 and y >= 0 then since x<0 then |x+y| < y < |x| + |y|

thus |x+y| < |x|+|y|

Part 3
Assume y < 0 and x >= 0 then since y<0 |x+y| < x < |x| + |y|

thus |x+y| < |x|+|y|

Part4
Assume x > 0 and y > 0 then |x+y| = x + y = |x| + |y|

thus |x+y|=|x|+|y|

Prove that if x is even and y is odd, then x+y is odd

Let x and y be integers. Prove that if x is even and y is odd, then x+y is odd.

x is even, therefore x=2k for some integer k.
y is odd, therefore y=2j+1 for some integer j.

by substitution into x+y=odd we get

2k + 2j + 1 = odd

2k + 2j + 1 = 2(k+j) + 1, which is odd.

Prove that there exist integers m and n such that 2m+7n=1

Prove that there exist integers m and n such that 2m + 7n=1

Let m=4 and n=-1. Then 2m + 7n = 1

On Mathematics and Mathematical Proofs

Mathematics is a language like any other language. It uses symbols to represent ideas, and those ideas attempt to represent reality. Like any language however, the symbols, letters, or words used are an abstraction, they are meaningless by themselves.

The beauty of mathematics is that new meanings fall from the symbols which cannot always be explained. One could say the same thing for words, a certain arrangement of words, in a novel or poem might enlighten us to new meanings we had not before perceived, and in mathematics there exist certain inherent patterns and meanings within the system, waiting to be explained or discovered.

The symbols matter. The better the symbols, the more efficient the phrases, and the more profound the thoughts. Let's consider for a moment all the different ways to write division:

1. In English: Six divided by four.
2. On way in math: 6 ÷ 4
3. Another math way: 6/4

Which method of representing the idea of six divided by four best leads you to realize that six divided by four is that same idea as three divided by two?

Or that is to say:

6/4 = 3/2

Thus in mathematics, or all languages, we are presented with the interesting problem that the symbols we contrive to use have a direct impact on the conclusions we make and how clearly we can express them.

For the purposes of mathematical proofs we will use the following generally accepted standard symbols:

Λ as "and"
V as "or"
~ as "the opposite"