Set Theory definitions

22 cards·by my brain 12

A function f: A --> B [impt for proof]

is a rule which assigns to each element of a given set A called the domain, one element of a secondset B called the codomain. If the funct

A function f: A --> B is 1-1 [impt for proof]

if whenever f(r) = f(s) then r = s

A function f: A --> B is onto [impt for proof]

if for every element w e B, there exists some element t e A with f(t) = w

We say that A subset of B, and write A C B [impt for proof]

if whenever x e A then x e B

A state of a well-formed formula (wff) [impt for proof]

is an assignment of T or F to each of the identifiers in the wff

In the implication P --> Q [impt for proof/use for induction proof on test]

P is the antecedent and Q is the consequent

The implication P --> Q

is false only when the antecedent P is true and the consequent Q is false

The converse [opposite] of the implication P --> Q

is the implication Q --> P

The contrapositive [negative] of the implication P --> Q

is the implication -Q -->-P

Modus Ponens

is the logical rule that states that in a proof if P is true and P --> Q is true, then we conclude that Q is true

A 1-1 correspondence

between two sets S and T is a function f: S --> T that is both 1-1 and onto

The well-ordering principle is an axiom about

N, the set of natural numbers, which states that if S is any non-empty subset of N, then S has a least element

The axiom of weak induction [proof on test]

is an axiom about N which states that if S is any subset of N that satisfies : Base Case (1) 1 e S and Inductive step (2) Hypothesis If k e

The axiom of strong induction [proof on test]

is an axiom about N which states that if S is any subset of N that satisfies : Base Case (1) 1 e SandInductive step (2) Hypothesis If t e

If S is a set of numbers, then the statement that statement that S is bounded above means

there exists a number M such that if x e S then x less than or equal to M. Such a number M is called an upper bound for the set S.

If S is a set of numbers, then the statement that statement that S is bounded below means

there exists a number L such that if x e S then L less than or equal to x. Such a number L is called an lower bound for the set S.

The statement that the set S is bounded

means that S is bounded above and bounded below

Suppose that S is a set of numbers.The statement that W is a least upper bound [LUB] of the set S

means that 1. W is an upper bound of S 2. If M is an upper bound of S, then W less than or equal to M

LUB Axiom

If the set of real numbers S is bounded above, then S has a least upper bound.

We say that the integer a divides b

and write aIb if a is not = zero and there exists an integer q with b=aq

We say that the integer a is less than b, and write a < b,

if there is some natural number n such that a +n = b

Trichotomy is an axiom

about the integers which states that if a is any integer, then exactly one of the following is true: a < 0 [a is negative] a = 0 a > 0 [a