Corollary

Let a and b be integers. If a | b and b | a, then a = ± b.

Can we use Bounds by Divisibility (BBD) if we did not say a \(\ne\) 0 and b \(\ne\) 0

The answer to that is we must consider a,b = 0 as a special case, and use BBD for other cases.

Proof:

Case 1: Since 0 | 0 and 0 \(\nmid\) n for any non-zero integer n,
then when a = 0, b must be zero and vice versa

Case 2:
When a \(\ne\) 0, and b \(\ne\) 0
From a | b and b \(\ne\) 0, we can use BBD to get |a| \(\le\) |b|
From b | a and a \(\ne\) 0, we can use BBD to get |b| \(\le\) |a|
Hence |a| = |b|
Therefore a = ± b

Negating an Implication

A \(\Rightarrow\) B and \(\lnot\)A v B are the same

A B A \(\Rightarrow\) B \(\lnot\)A not A v B
T T T F T
T F F F F
F T T T T
F F T T T

\(\lnot\)(A \(\Rightarrow\) B) \(\equiv\) \(\lnot\)((\(\lnot\)A) v B)
\(\equiv\) ((\(\lnot\)(\(\lnot\)A)) \(\land\) (\(\lnot\) B))
\(\equiv\) A \(\land\) (\(\lnot\) B)

In A then B Implication
A and not B Negated Implication

If a | b and b|c then a|c.
Negated Implication:
a | b and b | c and a \(\nmid\) c

If a | bc then a|b or a|c.
Negated Implication:
a | bc and a \(\nmid\) b and a \(\nmid\) c

If a | b and b \(\ne\) 0, then|a|≤|b|.
Negated Implication:
a | b and b \(\ne\) 0 and |a| > |b|

Divisibility of Integer Combinations.

“If m is an integer and 14 | m,
prove that 7 | 135m + 693”.
Note that 7 \(\nmid\) 135, so this is not a straight-forward result.

Recall previously: Proposition (Divisibility of Integer Combinations (DIC))
Let a, b and c be integers.
If a | b and a | c, then for any integers x and y, a | (bx + cy).

Proof: Assume 14 | m
Since 7 | 14, by Transivity of Divisibility 7 | m
m = 7k, for some integer k

Now 135m + 693 = 135(7k) + 7(99) = 7(135k + 99)
As 135k + 99 is an integer, 7 | (135m + 693)

Converse

Given an implication:

If A then B.

the converse of “If A then B” (A \(\Rightarrow\) B) is “If B then A” (B \(\Rightarrow\) A)

An implication and its converse are not logically related.

##Sets

Sets are collection of objects, called elements or members

∅ = { }. The empty-set has nothing in it.
{∅} has one element, namely the empty set, so
{∅} ≠ ∅.

\(\mathbb{R}\) is the set of real numbers. This is essentially the set that contains every possible number we have seen (unless you have seen complex numbers).

\(\mathbb{Q}\) is the set of rational numbers. These are numbers of the type 2, 1, 5 , 2, etc. The members are fractions, with numerator and denominator both being integers, and denominator cannot be zero.

\(\mathbb{Z}\) = {…,−3,−2,−1,0,1,2,3,…}, the set of integers (whole numbers)

\(\mathbb{N}\) = {1,2,3,…}, the set of natural numbers (positive integers). Note that in MATH 135, N starts at 1 and 0 ∉ N. This may be different that what you learn in CS.

Negation, Start of Sets | Home