Set Theory Essentials

By Emil Milewski

REA’s Essentials provide quick and easy access to critical information in a variety of different fields, ranging from the most basic to the most advanced. As its name implies, these concise, comprehensive study guides summarize the essentials of the field covered. Essentials are helpful when preparing for exams, doing homework and will remain a lasting reference source for students, teachers, and professionals. Set Theory includes elementary logic, sets, relations, functions, denumerable and non-denumerable sets, cardinal numbers, Cantor's theorem, axiom of choice, and order relations.

• Language: English
• Publisher: Research & Education Association
• Release date: Jan 1, 2013
• ISBN: 9780738672069

Book preview

NUMBERS

CHAPTER 1

ELEMENTARY LOGIC

1.1 STATEMENTS AND THEIR DISJUNCTION AND CONJUNCTION

By a statement we mean a declarative sentence that has one of two logical values, 0 and 1 (denoted also by F and T). The value 0 is assigned to a false statement and the value 1 to a true statement. All the statements in mathematics are of this kind, i.e. they take values of either 0 or 1.

Let p, q, r, ... be statements

Definition of Disjunction

The disjunction of the statements p and q (also called the sum), denoted by p ∨ q (read "p or q") is the compound statement which is true if at least one of the components is true.

Definition of Conjunction

The conjunction of the statements p, q (also called the product), denoted by p ∧ q (read "p and q") is the compound statement which is true if both statements are true.

The truth table for p ∨ q and p ∧ q

Definition of Equivalence

Let p and q be two statements. p and q are equivalent, denoted by

p = q or p ⇔ q,

if and only if p and q have the same logical value.

Theorem 1

If p, q and r are statements,

then

(1)

(2)

(3)

(4)

(5)

The last equivalence (5) is called the distributive law.

1.2 NEGATION AND IMPLICATION

The negation of a true statement is a false statement and the negation of a false statement is a true statement.

The negation of a statement p is denoted by ∼p or by ¬p.

The truth table for negation

Note: ∼(∼p) ≡ p

Theorem 2 (Aristotelian Logic)

In classical logic Theorem 2 is formulated as follows:

From two contradictory statements only one is true; no statement can be true simultaneously with its negation.

Theorem 3 (De Morgan Laws)

Observe that the sum can be defined with the aid of product and negation. In fact, from Theorem 3 p ∨ q ≡ ∼((∼p) ∧ (∼q))

Similarly the product can be defined with the aid of sum and negation : p ∧ q ≡ ∼((∼p) ∨ (∼q))

Definition of Turplication

Turplication p ⇒ q is defined by

p ⇒ q is read: p implies q, or:

if p, then q.

The truth table for implication:

We have

if p ⇒ q and q ⇒ p then p ≡ q

Turplication has properties analogous to deduction. However, the meaning of the expression implication is different from the expression deduction.

Theorem 4: The Syllogism Law

The Law of Contraposition

The proof by reductio ad absurdum (or the indirect method of proof) depends on the law of contraposition.

Some properties of implication:

Definition of Tautology

A statement that is true in each of all logical possibilities is said to be a tautology.

Examples of tautologies

p ∨ ∼p

p ⇒ p

p ∧ q ⇒ q

The truth tables can be applied to prove any law of logic. The other method is deductive reasoning.

Example:

Prove that (p ⇒ r) ∨ (q ⇒ s) ≡ (p ∧ q) ⇒ (r ∨ s)

We have (p ⇒ r) ∨ (q ⇒ s)

≡((∼p) ∨ r) ∨ ((∼q) ∨ s)

≡((∼p) ∨ (∼q)) ∨ (r ∨ s)

≡(∼(p ∧ q)) ∨ (r ∨ s)

≡ (p ∧ q) ⇒ (r ∨ s)

In this case deductive reasoning is the faster way to solve the problem because the truth table requires 2⁴ =