Naive Theory of Sets
1
Department of Computer Science,
Faculty of Electrical Engineering and Computer Science,
VSB - Technical University of Ostrava
Naive Theory of Sets
2
•
What is it a set
?
•
A set is a collection of elements,
and it is determined just by its elements;
a set consisting of elements
a, b, c
is denoted
: {a, b, c
}
•
An element of a set can be again
a set
,
a set may consist of
n
o elements,
it may be
empty
(
denoted by
)
!
•
Examples
:
,
{a, b
}, {b, a
}, {a, b, a
}, {{a, b
}}, {a,
{b, a
}},
{
, {
}, {{
}}}
•
Sets are identical if and only if (iff) they have exactly the same
elements
(
the
princip
le of
extensionality)
•
Notation
: x
M
– „
x
is an element of
M
“
•
a
{a, b
}
,
a
{{a, b
}}, {a, b
}
{{a, b
}},
{
, {
}, {{
}}},
{
, {
}}, but:
x
for any
(
i.e
.
,
all
)
x.
•
{a, b
}
=
{b, a
}
=
{a, b, a
}, but: {a, b
}
{{a, b
}}
{a,
{b, a
}}
Naive theory of sets:
∀
∃
α
β
λ
|
-
3
•
Union
: A
B = {x
|
x
A
o
r
x
B}
read
: „
The set of all
x
such that
x
is an element of
A
o
r
x
is
an element of
B.“
•
{a, b, c
}
{a, d
} = {a, b, c, d
}
•
{odd numbers
}
{even numbers
} = {natural numbers
}
–
denoted
Nat
•
U
i
I
A
i
=
{x
| x
A
i
for
some
i
I
}
•
Let
A
i
=
{x
| x
= 2.
i
fo
r
some
i
Nat
}
•
U
i
Nat
A
i
=
the set of all even numbers
Set-theoretical operations
(create new sets from sets)
∀
∃
α
β
λ
|
-
4
•
Intersection
: A
B = {x
|
x
A
a
nd
x
B}
read
: „
The set of all
x
such that
x
is an element of
A
a
nd
x
is an element of
B
as well
.“
•
{a, b, c
}
{a, d
} = {a
}
•
{even numbers
}
{odd numbers
} =
•
i
I
A
i
=
{x
| x
A
i
for
a
ll
i
I
}
•
Let
A
i
=
{x
| x
Nat
,
x
i
}
•
Then
i
Nat
A
i
=
Set-theoretical operations
(create new sets from sets)
∀
∃
α
β
λ
|
-
5
•
A set
A
is a
subset
o
f a set
B,
denoted
A
B,
iff each
element of
A
is also an element of
B.
•
A set
A
is a
p
roper subset
o
f a set
B,
denoted
A
B,
iff each element of
A
is also an element of
B
but
n
ot vice versa
.
{a
}
{a}
{a, b
}
{{a, b
}}
!!!
•
It holds
: A
B,
iff
A
B a
nd
A
B
•
It holds
: A
B,
iff
A
B = B,
iff
A
B = A
Relations between sets
∀
∃
α
β
λ
|
-
6
•
Difference
: A \ B = {x
|
x
A a
nd
x
B}
•
{a, b, c
} \ {a, b
} = {c
}
•
Complement
:
Let
A
M.
The complement of
A
with
respect to
M
is the set
A’ = M \ A
•
Cartesian product
: A
B = {
a,b
|
a
A, b
B}
•
where
a,b
je
an
o
rdered couple
(
the ordering is important:
a is the first, b is the second
)
•
It holds
:
a,b
=
c
,d
iff
a = c, b = d
•
But
:
a,b
b,a
,
though
{a,b
} = {b,a
} !!!
•
generalization
: A
…
A
the set of
n
-
tuples
,
denoted also by
A
n
Some others set-theoretical operations
∀
∃
α
β
λ
|
-
7
•
Poten
tial set
:
2
A
= {B | B
A},
denoted also by
P(A)
2
{a,b
}
= {
, {a
}, {b
}, {a,b
}}
2
{a,b,c
}
= {
, {a
}, {b
}, {c
}, {a,b
}, {a,c
}, {b,c
}, {a,b,c
}}
How many elements are there in
2
A
?
If
|A|
is the number of elements (cardinality) of a set
A,
then
2
A
has
2
|A|
elements
(
hence the notation:
2
A
)
2
{a,b
}
{a
}
= {
, {
a,a
}
,
{
b,a
}
,
{
a,a
,
b,a
}}
Some others set-theoretical operations
∀
∃
α
β
λ
|
-
8
A: S
\(P
M
)
=
(
S\P)
(S\M)
S(
x
)
(
P(
x
)
M(
x
)
)
S(
x
)
P(
x
)
M(
x
)
B:
P
\(S
M
)
=
(
P\S)
(P\M)
P
(
x
)
(
S
(
x
)
M(
x
)
)
P
(
x
)
S
(
x
)
M(
x
)
C:
(S
P
) \
M
S(
x
)
P(
x
)
M(
x
)
D:
S
P
M
S(
x
)
P(
x
)
M(
x
)
E:
(S
M) \ P
S(
x
)
M(
x
)
P(
x
)
F:
(P
M) \ S
P
(
x
)
M(
x
)
S
(
x
)
G:
M
\(P
S
)
=
(
M\P)
(M\S)
M
(
x
)
(
P(
x
)
S
(
x
)
)
M
(
x
)
P(
x
)
S
(
x
)
H:
U \
(S
P
M
)
= (U \
S
U \ P
U \
S
)
(
S(
x
)
P(
x
)
M(
x
)
)
S(
x
)
P(
x
)
M(
x
)
S
P
M
A
B
C
D
E
F
G
H
Grafical picturing (in a universe U):
∀
∃
α
β
λ
|
-
9
•
Is it true that
any
collection of elements (i.e., a collection
defined in an arbitrary way) can be considered to be a set?
•
It is normal that a set and its elements are entities of different
types. Hence a “normal set”
is not an element of itself
.
•
Let
N
is a set of
all
normal sets:
N
= {M | M
M}.
•
Question: Is
N
N
?
In other words, is
N
itself normal?
•
Yes
?
But then according to the definition of
N
it holds that
N
is normal, i.e.,
N
N
.
•
No?
But then
N
N
, hence
N
is normal, and therefore it belongs to
N
, i.e.,
N
N.
•
Both the answers lead to a contradiction.
N
is not well defined. The
definition does not determine a collection of elements that could be
considered to be a set.
Russell's paradox
∀
∃
α
β
λ
|
-
A set is a collection of elements uniquely determined by its contents. Explore the basic principles of sets, set notation, set operations, and relations between sets. Learn about subsets, proper subsets, set differences, complements, and more in the naive theory of sets.
Uploaded on Mar 05, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB - Technical University of Ostrava Naive Theory of Sets 1
Naive theory of sets: What is it a set? A set is a collection of elements, and it is determined just by its elements; a set consisting of elements a, b, c is denoted: {a, b, c} An element of a set can be again a set, a set may consist of no elements, it may be empty (denoted by ) ! Examples: , {a, b}, {b, a}, {a, b, a}, {{a, b}}, {a, {b, a}}, { , { }, {{ }}} Sets are identical if and only if (iff) they have exactly the same elements (the principle of extensionality) Notation: x M x is an element of M a {a, b}, a {{a, b}}, {a, b} {{a, b}}, { , { }, {{ }}}, { , { }}, but: x for any (i.e., all) x. {a, b} = {b, a} = {a, b, a}, but: {a, b} {{a, b}} {a, {b, a}} 2
Set-theoretical operations (create new sets from sets) Union: A B = {x | x A or x B} read: The set of all x such that x is an element of A orx is an element of B. {a, b, c} {a, d} = {a, b, c, d} {odd numbers} {even numbers} = {natural numbers} denoted Nat Ui I Ai = {x| x Ai for somei I} Let Ai = {x| x = 2.i for some i Nat} Ui Nat Ai = the set of all even numbers 3
Set-theoretical operations (create new sets from sets) Intersection: A B = {x | x A and x B} read: The set of all x such that x is an element of A and x is an element of B as well. {a, b, c} {a, d} = {a} {even numbers} {odd numbers} = i I Ai = {x| x Ai for alli I} Let Ai = {x| x Nat, x i} Then i Nat Ai = 4
Relations between sets A set A is a subset of a set B, denoted A B, iff each element of A is also an element of B. A set A is a proper subset of a set B, denoted A B, iff each element of A is also an element of B but not vice versa. {a} {a} {a, b} {{a, b}} !!! It holds: A B, iff A B and A B It holds: A B, iff A B = B, iff A B = A 5
Some others set-theoretical operations Difference: A \ B = {x | x A and x B} {a, b, c} \ {a, b} = {c} Complement: Let A M. The complement of A with respect to M is the set A = M \ A Cartesian product: A B = { a,b |a A, b B} where a,b je an ordered couple (the ordering is important: a is the first, b is the second) It holds: a,b = c,d iff a = c, b = d But: a,b b,a , though{a,b} = {b,a} !!! generalization: A Athe set of n-tuples, denoted also by An 6
Some others set-theoretical operations Potential set: 2A = {B | B A}, denoted also by P(A) 2{a,b} = { , {a}, {b}, {a,b}} 2{a,b,c} = { , {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} How many elements are there in 2A ? If |A| is the number of elements (cardinality) of a set A, then 2A has 2|A| elements (hence the notation: 2A) 2{a,b} {a} = { , { a,a }, { b,a }, { a,a , b,a }} 7
Grafical picturing (in a universe U): A: S\(P M) = (S\P) (S\M) S(x) (P(x) M(x)) B: P\(S M) = (P\S) (P\M) P(x) (S(x) M(x)) C: (S P) \ M S(x) P(x) M(x) D: S P M S(x) P(x) M(x) E: (S M) \ P S(x) M(x) P(x) F: (P M) \ S P(x) M(x) S(x) G: M\(P S) = (M\P) (M\S) M(x) (P(x) S(x)) H: U \ (S P M) = (U \ S U \ P U \ S) (S(x) P(x) M(x)) S(x) P(x) M(x) S P(x) S(x) M(x) A E C D G B F P M M(x) P(x) S(x) H S(x) P(x) M(x) 8
Russell's paradox Is it true that any collection of elements (i.e., a collection defined in an arbitrary way) can be considered to be a set? It is normal that a set and its elements are entities of different types. Hence a normal set is not an element of itself. Let N is a set of all normal sets: N = {M | M M}. Question: Is N N ? In other words, is N itself normal? Yes? But then according to the definition of N it holds that N is normal, i.e., N N. No? But then N N, hence N is normal, and therefore it belongs to N, i.e., N N. Both the answers lead to a contradiction. N is not well defined. The definition does not determine a collection of elements that could be considered to be a set. 9
