Scribd
Upload
12 views5 pages

Introduction to Set Theory Basics

Uploaded by

3r32r
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views5 pages

Introduction to Set Theory Basics

Uploaded by

3r32r
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lecture 3: Sets

1 Sets
Logic is built on set of axioms that are assumed true. Euclid attempted to use
the axiomatic constructions for Geometry in his book “The Elements”. Hilbert
formalized Euclidean Geometry in 1899, with a complete set of axioms.
Set theory is starting place for all rigorous mathematics. It was developed
formally by Georg Cantor in lat 19th century. We would develop set theory infor-
mally in this lecture. We would provide a glimpse of formal set theory developed
from an axiomatic system at the end of the lecture.

1.1 Basic Definitions.


We have an undefined term set, which will informally think of as a collection of
objects. Objects contained in the set are called the elements or members of the
set. If A is a set, and a is an element of the set A, we write a ∈ A. If a is not
contained in A, then we write a ∈ / A.
Axiom: Given any set A and any object a, we assume that precisely one of
a ∈ A or a ∈/ A holds.
Representation: A set is written as {a, b, c, d}, here ordering is irrelevant.

Definition 1.1 (Important sets). 1. Set of natural numbers is denoted by


N = {1, 2, . . .}.

Z = {. . . , −2, −1, 0, 1, 2, . . .}.


2. Set of integers is denoted by

3. Set ofrational numbers, denoted by Q, is set of fractions.

4. Set of real numbers is denoted by R.

5. Set of whole numbers, denoted by N0 , also called set of non-negative


integers.

6. Set with no elements is an empty set, denoted by ∅.

1
Z
Example 1.2. Let S = {n ∈ |n is a perfect square}, then

Z
S = {n ∈ |n = k 2 for somek ∈ }, Z
Z
= {n ∈ | is a perfect square k ∈ Z such that n = k2}.
Notice that n and k are dummy variables in this set notation.
Definition 1.3 (Intervals). Let a, b be real numbers.
• An open bounded interval is defined as

(a, b) , {x ∈ R : a < x < b}.


• A closed bounded interval is defined as

[a, b] := {x ∈ R : a ≤ x ≤ b}.
• A half-open interval is defined as

[a, b) := {x ∈ R : a < x ≤ b.
• An open unbounded interval is defined as

(a, ∞) := {x ∈ R : a < x}.


• A closed unbounded interval is defined as

[a, ∞) := {x ∈ R : a ≤ x}.
Remark 1. +∞ and −∞ are not real numbers.
Remark 2. Dummy variables cannot be used outside the definition without re-
defining them. For example, let y ∈ [a, b], then y ≥ a and y ≤ b.

1.2 Relation between Sets


We are interested in finding relations between sets.
Definition 1.4 (Subset). Let A and B be sets. We say that A is a subset of B
if x ∈ A implies x ∈ B, and is denoted by A ⊆ B. If A is not a subset of B, we
write A * B.
This is shown in the Figure 1 In other words, we can say that A ⊆ B if
∀x([x ∈ A] → [x ∈ B]). While, we say that A * B if (∃x)([x ∈ A] ∧ [x 6∈ B]).

2
B

A
C D

A⊆B
C 6⊆ D
Figure 1: In first example, A ⊆ B. In second example, C * D.

Lemma 1.5. Let A, B, and C be sets, then the following are true.

1. A ⊆ A.

2. ∅ ⊆ A.

3. If A ⊆ B and B ⊆ C then A ⊆ C.

Proof. Let A, B, and C be sets.

1. Let x be an arbitrary element of set A. Since any element in A is in A itself,


therefore A ⊆ A.

2. We need to show that for any x ∈ ∅, we have x ∈ A. However, since empty


set ∅ has no elements, conclusion necessarily follows.

3. Let’s assume A ⊆ B and B ⊆ C. Let x be an arbitrary element of set A,


then by assumption A ⊆ B, we have x ∈ B. Further, since B ⊆ C, we have
x ∈ C. Since choice of x was arbitrary in A, we conclude? A ⊆ C.

Definition 1.6 (Equality of Sets). Let A and B sets. We say that A equals B,
denoted A = B, if A ⊆ B and B ⊆ A.

To show A = B, we would show A ⊆ B and B ⊆ A. To show A ⊆ B, we


would choose arbitrary a ∈ A, and logically deduce that a ∈ B. Similarly, to show
B ⊆ A, we would choose arbitrary b ∈ B and logically deduce that b ∈ A.

Definition 1.7 (Proper Subset). We say that A is a proper subset of B if


A ⊂ B, and A 6= B, denoted as A B(A ⊂ B).

3
Lemma 1.8. Let A, B, and C be sets, then following is true
1. A = A.
2. If A = B then B = A.
3. If A = B and B = C then A = C.
Definition 1.9 (Power Set). Let A be a set. The power set of A denoted by
P(A) is the set whose elements are subsets of A.
Example 1.10. Power set of S = {1, 2}, is P = {{1}, {2}, {1, 2}, ∅}.
Example 1.11 (Russell’s Paradox). Let set S be defined as
S , { set of all sets},
T , {A ∈ S|A 6∈ A}.
Then is T ∈ T ? If T ∈ T , then T 6∈ T by definition. If T 6∈ T , then T ∈ T by
definition.
To resolve such paradoxes. Set theory is built from some basic axioms. One
such axiomatic system is discussed below.

2 Axiomatic System for Set Theory


We will study one of the widely accepted axiomatic system for set theory due
to Zermelo and Fraenkel. We would refer to them as ZF axioms. Informally we
tend to distinguish between sets and elements. In the ZF axioms we make no such
distinction. Everything in the ZF axioms is a set. Once we assume that everything
in the ZF axioms is a set, then the relation of membership, denoted by the symbol
∈, is a relation between sets.

2.1 Zermelo-Fraenkel axioms


1. Axiom of Extensionality. Two sets are equal if they have the same ele-
ments. That is,
∀x∀y[∀z(z ∈ x ⇔ z ∈ y) ⇒ x = y].

2. Axiom of Empty Set. There is a set z such that x ∈


/ z for all sets x.
3. Axiom of Pairing. If x and y are sets, then there exists a set which contains
x and y as elements. That is,
∀x∀y∃z(x ∈ z ∧ y ∈ z).

4
4. Axiom of Union. The union over the elements of a set exists. Let x be a
set. There is a set z such that w ∈ z if and only if there is some y ∈ x such
that w ∈ y. That is,

∀x∃z∀w[(w ∈ y ∧ y ∈ x) ⇒ w ∈ z].

5. Axiom of Power Set. Let x be a set. There is a set z such that w ∈ z if


and only if w ⊆ x. That is,

∀x∃y∀z[(z ⊆ x) ⇒ z ∈ y].

6. Axiom of Regularity. Every non-empty set x contains a member y such


that x and y are disjoint sets. That is,

∀x[∃a(a ∈ x) ⇒ ∃y(y ∈ x ∧ ¬∃z(z ∈ y ∧ z ∈ x))].

7. Axiom Schema of Specification/Separation/Restricted Comprehen-


sion. Let P (y) be a logical property of sets with one free variable y that can
be formulated in the context of the ZF axioms. Let x be a set. Then there
is a set z such that y ∈ z if and only if y ∈ x and P (y) is true.

8. Axiom Schema of Replacement. Image of any set x under any definable


function f : x → y will also fall inside a set z. Let f (s, t) be a functional
property of sets with two free variables s and t that can be formulated in the
context of the ZF axioms. Let x be a set. Then there is a set z such that
y ∈ z if and only if there is some w ∈ x such that f (w, y) is true.

9. Axiom of Infinity. There exists a set having infinity many elements. Let’s
define s(w) = w ∪ {w} for any set w. Then, there is a set x such that ∅ ∈ x,
and if y ∈ x then s(y) ∈ x. Formally,

∃x[∅ ∈ x ∧ ∀y(y ∈ x ⇒ s(y) ∈ x)].

10. Axiom of Choice. Let x be a set. Suppose that if y, w ∈ x, then y 6= ∅


and y ∩ w = ∅. Then there is a set z such that if y ∈ x, then y ∩ z contains
a single element.

Common questions

Powered by AI

Russell's Paradox arises when considering the set of all sets that do not contain themselves. If we define a power set as the set of all subsets of a set, Russell's Paradox challenges the notion of a 'set of all sets' by questioning whether such a universal set could contain itself as a subset. The paradox implies that naively defining sets without constraints leads to contradictions, thus motivating the development of axiomatic systems like the Zermelo-Fraenkel axioms to avoid such issues .

Georg Cantor's development of set theory had a profound impact on modern mathematics by providing a new way to understand and manipulate infinite sets and cardinalities. His work laid the groundwork for significant areas in mathematics, such as real analysis, and enabled the rigorous development of mathematical concepts that involve infinity. His introduction of concepts like bijective functions and different sizes of infinity challenged previous mathematical understandings and paved the way for further advancements in logic, topology, and measure theory .

The Axiom Schema of Specification is significant in avoiding set-theoretical paradoxes by allowing the formation of subsets based on well-defined properties, ensuring that sets are constructed without self-referencing definitions that could lead to contradictions. Its role in formulating restricted sets means that given a set, a new set can be formed that only contains elements satisfying a particular condition, providing a way to carefully define sets without invoking paradoxes like Russell's Paradox .

Axioms in set theory, such as those in the Zermelo-Fraenkel system, help resolve logical paradoxes by providing a strict and finite set of rules that govern the formation and manipulation of sets. They prevent contradictions by excluding definitions and premises that lead to paradoxes, such as defining a set of all sets. These axioms create a systematic method ensuring consistency by rigorously defining set membership and operations, thereby preventing paradoxical sets from forming .

The Axiom of Regularity stipulates that every non-empty set x contains a member y such that x and y are disjoint. This axiom helps prevent paradoxes like Russell’s Paradox by ensuring that no set is a member of itself, directly or indirectly, thus avoiding circularity in set membership. This helps maintain the consistency of the set theory framework by disallowing sets that could lead to contradictions .

In the Zermelo-Fraenkel axioms, everything is considered a set, including elements, unlike the informal definition in set theory where elements and sets are distinguished. This lack of distinction allows for a more rigorous framework, permitting operations and relationships between sets to be handled within a single consistent theory. The importance of this distinction lies in its ability to avoid logical paradoxes and inconsistencies, ensuring a consistent foundation for mathematics .

The Axiom of Infinity is pivotal because it guarantees the existence of infinite sets, specifically the set of natural numbers. By asserting that there is a set containing the empty set and a successor for every element, it integrates into the axiomatic framework by providing a foundational basis for constructing numbers and sequences. This axiom is integral in exploring concepts such as cardinality and order types in infinite sets, influencing theories related to natural numbers and beyond .

The Axiom of Choice is crucial in the Zermelo-Fraenkel axioms as it asserts that for any set of non-empty sets, there exists a function that chooses an element from each of these sets. This axiom is controversial because it can lead to non-intuitive results, such as Banach-Tarski Paradox, which states that a ball can be split into a finite number of disjoint subsets that can be rearranged to form two balls identical to the original. Despite its unintuitive implications, it is widely used in proofs and has foundational importance in areas like topology and functional analysis .

The distinction between open and closed intervals is significant because it defines whether the endpoints are included in the interval. In real analysis, this distinction affects properties such as continuity, limits, and convergence. Closed intervals include endpoints, leading to compactness, which is crucial for the Bolzano-Weierstrass Theorem and Heine-Borel Theorem. Understanding how sets behave at their boundaries influences many results and proofs in analysis .

Hilbert formalized Euclidean Geometry in 1899 by providing a complete set of axioms. This work was significant as it laid the foundation for modern mathematical logic, by establishing a rigorous axiomatic system where all propositions about geometry could be deduced from these axioms. This approach influenced the development of other fields in mathematics, such as set theory, by showing the importance of having a solid axiomatic foundation .

You might also like