Chapter 2 Flashcards Preview

MAT 1362 > Chapter 2 > Flashcards

Flashcards in Chapter 2 Deck (15)
Loading flashcards...
1

4 characteristics of natural numbers [axiom]

  1. If a, b ∈ N,  then a + b ∈ N . 
    (The subset N is closed under addition.)
     
  2. If a, b ∈ N, then ab ∈ N .
    (The subset N is closed under multiplication.)
     
  3. 0 ∉ N . 
     
  4. For every a ∈ Z, we have
    a ∈ N
    or a = 0
    or -a ∈ N. 

2

order on the intergers [definition]

For a, b ∈ Z, we write
a < b (and say a is less than b)
or b > a  (and say b is greater than a,
if and only if (b - a) ∈ N

We write a ≤ b (and say a is less than or equal to b)
or b ≥ a (and say b is greater than a)
if and only if a < b or a = b

3

transitivity of <

Suppose a, b, c ∈ Z. 
If a < b and b < c ,
then a < c
(ie the relation < is transitive).

4

N has no largest element [proposition]

For each a ∈ N, there exists b ∈ N such that b > a . 

5

notation for "A is a subset of B" [notation]

"A is a subset of B" 
can be written 
A ⊆ B . 

6

notation for "A = B" (ie the two sets A and B are equal) [notation]

A = B
can be expressed as
A ⊆ B and B ⊆ A 
or
x ∈ A ⇔ x ∈ B . 

 

7

notation for " P ⇒ Q and Q ⇒ P" [notation]

P ⇒ Q and Q ⇒ P
can be expressed as
P ⇔ Q .

8

difference between ⊈ and ⊊ [notation]

A ⊈ B
means that A is not a subset of B, ie at least one element of A is not an element of B

A ⊊ B
means that A is a subset of B, but at least one element of B is not in A; can also be expressed as
A ⊆ B and A ≠ B

9

notation for all intergers satisfying a given property [notation]

{n ∈ Z : some property of n}

ex: {n ∈ Z : n > 69} denotes the set of all intergers greater than 69.

10

induction [axiom]

(i) 1 ∈ A

(ii) n ∈ A ⇒ n + 1 ∈ A . 

Then N ⊆ A . 

 

11

principle of mathematical induction - first form [theorem]

Suppose that, for each kN, we have a statement P(k) , and that ...

(i) P(1) is true, and

(ii) for all nN, P(n) ⇒ P(n + 1) .

Then P(k) is true for all k ∈ N.

12

priciple of mathematical induction - first form revisited [theorem]

Suppose that m is a fixed integer,
and that for each k ∈ Z with k ≥ m , we have a statement P(k) ,
and that...

(i) P(m) is true, and

(ii) for all n, P(n) ⇒ P(n + 1) .

Then P(k) is true for all k ≥ m .

13

smallest and greatest elements [definition]

Suppose AZ is nonempty.

If there exists mA such that ma for all aA,
then we say m is a smallest element of A
and write m = min(A).

If there exists MA such that M ≥ a for all aA,
then we say M is a greatest element of A
and write M = max(A).

14

well-ordering principle [theorem]

Every nonempty subset of N has a smallest element.

15

gcd [definition]

Suppose a, bZ. If a and b are not both zero,

we define

gcd(a, b) = min ({k ∈ N : k = ax + by for some x , y ∈ Z} )