Mathematical Induction. Well-ordering property. Basic and inductive steps. Why mathematical induction is valid. Second principle of mathematical induction.

Show that any interval of the set of reals and the set of reals have the same cardinality. Show that any two circles on the real plane have the same cardinality. Show that a family of disjoint intervals on a line is countable as well as a family of disjoint circles on a real plane.

1) |A|=|B| if there is a bijection from A to B

Lemma 1. Any two intervals have the same cardinality.

Proof. Let a<b, c<d.

Through (a,c) and (b,d) a unique line y=f(x) passes. It is a bijection from (a,b) to (c,d)

Picture 1

Since f is line and is not constant, it is 1-1 ax+b=ax2+b=> x1=x2 f is onto as a continuous function, which have all intermediate value between c and d.

Lemma 2. |(-p/2;p/2)| =|R|

Proof.Tan: (-p/2;p/2)->R is a bijection.

Th.|(a,b)|=|R|

Proof. |(a,b)|= |(-p/2;p/2)| =||R|=>|(a,b)|=|R|

2)pictures 2 Point on a circle is defined by its angles j, jϵ[0,2p), so any two circles have the same cardinalities with [0,2p) then they have the same ordinarily.

3) A family of disjoint intervals on a line is countable

Proof: Let {(ai,bi):iϵI} be a set of disjoint interval. Any interval contains a rational number. Q- is countable. Since intervals are disjoint any rational number cannot belong to 2 intervals. So, the number of intervals ≤ the number of rationales.

A family of disjoint circles on the real plane is countable.

Proof. Let {Ri:iϵI} be a set of disjoint circles. Any circle contains point (q1.,q2) with rational coordinates. Since circles are disjoint any point cannot belong to two circles. So, the number of circles ≤ |QxQ| picture 3/ (q1,q2)ϵ circle |QxQ| is countable because the Cartesian product of countable sets is countable.

28. Show that the image of the union of two sets under a function is equal to the union of the images of these sets.

Let f : X → Y. If A ⊆ X, B ⊆ X , then unions are preserved. That is f ( A ∪ B ) = f ( A ) ∪ f ( B )

Proof:We begin by showing f ( X ∪ Y ) ⊆ f ( X ) ∪ f (Y )

If y ∈ f ( A ∪ B ) this means there exists an x₀ ∈ A ∪ B such that y = f ( x₀ ) . Hence, x₀ ∈ A or x₀ ∈ B and so f ( x₀ ) ∈ f ( A) or f ( x₀ ) ∈ f ( B ) , and so we have f ( x₀ ) ∈ f ( A ) ∪ f ( B ) which verifies f ( A ∪ B ) ⊆ f ( A ) ∪ f ( B ) . We leave the verification that f ( A ) ∪ f ( B ) ⊆ f ( A ∪ B ) to the reader. Although the intersection of sets is not preserved for functions, it is preserved for the inverse of a function

Show that the image of the intersection of two sets under a function is a subset of the intersection of the images of these sets.

If f : X → Y and A ⊆ X , B ⊆ X , then the images of intersections satisfy

f ( A ∩ B ) ⊆ f ( A ) ∩ f ( B )

Proof:Lety∈f(A∩B). Hence, there exists anx∈A∩Bsuch thatf ( x ) = y . Hence x ∈ A and x ∈ B . But

x ∈ A ⇒ y = f ( x ) ∈ f ( A) x ∈ B ⇒ y = f ( x ) ∈ f (B)

Hence y = f ( x ) ∈ f ( A) ∩ f (B) .

Let us now try to show the converse; that is f ( A ) ∩ f ( B ) ⊆ f ( A ∩ B )

Letting y ∈ f ( A ) ∩ f ( B ) we have y ∈ f ( A ) and y ∈ f ( B ) Hence

x₁ ∈ A ⇒ f ( x₁ ) = y

x2 ∈ A ⇒ f (x2)= y

from which we conclude f ( x₁ ) = f ( x₂ ) which is only true if the function f is one-to-one. In general, intersections of sets are not preserved under the image of a function. However, the following theorem shows intersections are preserved.

Show that the image of the intersection of two sets under an injective function is equal to the intersection of the images of these sets.

Let f : X → Y be a one-to-one function. If A ⊆ X , B ⊆ X , then intersection is preserved under mappings: f ( A ∩ B ) = f ( A) ∩ f ( B )\

Proof:It suffices to showf(A)∩f(B)⊆f ( A ∩ B ) . Letting y ∈ f ( A ) ∩ f ( B ) ,

we have y ∈ f (A ) and y ∈ f ( B ) . Hence

∃x₁ ∈ A such that f ( x₁ ) = y => f ( x₁ ) = f ( x₂ )

∃x₂ ∈ B such that f ( x₂ ) = y

But f is assumed 1-1 so we conclude x₁ = x₂ and so x₁ ∈ A and x₁ ∈ B and thus x₁ ∈ A ∩ B

Hence y = f ( x₁ ) ∈ f ( A ∩ B ) which proves theorem

Show that the pre-image of the union of two sets is equal to the union of pre-images of these two sets. Show that the pre-image of the intersection of two sets is equal to the intersection of pre-images of these two sets. Show that the complement of the pre-image of a set is equal to the pre-image of the complement of this set.

For a subset A of the range of a function ƒ, the set of points x in the domain of ƒ for which ƒ(x) is a member of A. Also known as inverse image.

f:A->B, f(a)=b. b is the image of a under f. a is a preimage of b.

1) Th. Letf:X→YandC⊆Y,D⊆Y, then the inverse image of intersections and unions satisfies f ⁻¹ (C ∪ D ) = f ^{− 1} (C ) ∪ f ⁻¹ ( D )

Proof y ∈ f ⁻¹ (C UD ) ⇔ f ( y ) ∈ CUD

⇔ f ( y ) ∈ C and f ( y ) ∈ D

⇔ y ∈ f ⁻¹ ( C ) and y = f ⁻¹ ( D )

⇔ y ∈ f ⁻¹ ( C ) U f ⁻¹ ( D )

2) f ⁻¹ (C ∩ D ) = f ^{− 1} (C ) ∩ f ⁻¹ ( D )

y ∈ f ⁻¹ (C ∩ D ) ⇔ f ( y ) ∈ C ∩ D

⇔ f ( y ) ∈ C and f ( y ) ∈ D

⇔ y ∈ f ⁻¹ ( C ) and y = f ⁻¹ ( D )

⇔ y ∈ f ⁻¹ ( C ) ∩ f ⁻¹ ( D )

3) a ϵ f^-1(черточка А)ó f(a) ϵ черточка А ó f(a) not ϵ A ó a not ϵ f^-1 (A) ó a ϵf^-1(A)

32. Rules of inference. The six basic rules of inference. Vacuous, trivial, indirect proof and proof by contradiction. Prove that the square root of 2 is irrational.