Sets

Sets in Terence Tao's Analysis I

Definition (informal for now)

We define a set A to be any unordered collection of objects, e.g., {3, 8, 5, 2} is a set. If x is an object, we say that x is an
element of A or x ∈ A if x lies in the collection; otherwise we say that x ∉ A. For instance, 3 ∈ {1, 2, 3, 4, 5} but
7 ∉ {1, 2, 3, 4, 5}.

We must also note that a set is also considered an object and that.

We also define the notion of subsets.

Let A, B be sets. We say that A is a subset of B, denoted A ⊆ B, if and only if every element of A is also an element of B,
i.e. For any object x, x ∈ A ⟹ x ∈ B. We say that A is a proper subset of B, denoted A ⊂ B, if A ⊆ B and A ≠ B.

We can see that that the notion of subset obeys the axiom of substitution, which in this case translates to:
′ ′
A ⊆ B ∧ A = A ⟹ A ⊆ B

This doesn't need to be proven as in fact the notion of subsets is defined in terms of the element operation, which we
already prove that it obeys the axiom.

We also note that the empty set is always a subset of a set (including itself) since all it's element are in any set, because it
doesn't have any.

Set equality

We proceed to define equality as such: Two sets A and B are equal, A = B, if and only if every element of A is an element
of B and vice versa. To put it another way, A = B if and only if every element x of A belongs also to B, and every element y
of B belongs also to A. In signs:

(∀a ∈ A : a ∈ B) ∧ (∀b ∈ B : b ∈ A) ⟺ A = B

We must also note that this equality obey the transitive, reflexive, symmetric and substitution axioms, which makes it an
equality equivalent to the "=".

Concerning the set equality: We can check and prove that set equality is transitive, reflexive and symmetric. But we define
equality axiomatically, so how come we can prove this. The answer is that this set equality is defined as an axiom here. We
can also assert that this implies the truth of the other properties of equality.

This approach is either not mandatory, we could also accept the following axioms:

Symmetric axiom, given any object x we have:

x = x

Reflexive axiom, gives any 2 objects x and y of the same class:

x = y ⟺ y = x

Transitive axiom, given any 3 objects x , y and z of the same class:

x = y ∧ y = z ⟹ x = z

Substitution axiom with regards to sets , given any 2 sets x and y and a function or operation f
For all sets x and y, if x = y, then for all objects z, z ∈ x if and only if z ∈ y.
For all objects x and y, if x = y, then for all sets z, x ∈ z if and only if y ∈ z.

Then we only need to add the axiom of extensionality:

For all sets x and y, if for all objects z, z ∈ x if and only if z ∈ y, then x = y.
Otherwise we can, like Terence Tao, define the following axiom and proof all the properties of equality:

For all sets x and y, x = y if and only if, for all objects z, z ∈ x if and only if z ∈ y.

The main difference being that Terence Tao theory is based on first order logic without equality.
More info for further clarification here: More info

Mini proof for the equality properties in Analysis I

Substitution

x ∈ A ∧ A = B ⟹ x ∈ B , which means that the property ∈ preserved equality. Which means that as long as we define

properties in terms of ∈ we will have a property that preserves equality and abides the axiom of substitution.

Symmetry

We need to show that A = A , we refer to the definition of set equality.

(∀a ∈ A : a ∈ A) ∧ (∀a ∈ A : a ∈ A) ⟹ A = A

This is obviously true.

Q.E.D.

Reflexivity

We need to show that A = B ⟺ B = A

Both statements are true:

(∀a ∈ A : a ∈ B) ∧ (∀b ∈ B : b ∈ A) ⟹ A = B

(∀b ∈ B : b ∈ A) ∧ (∀a ∈ A : a ∈ B) ⟹ B = A

This implies that A = B ⟺ B = A

Q.E.D.

Transitivity

We need to show that (A = B) ∧ (B = C) ⟹ A = C

∀a ∈ A : a ∈ B by definition, but we know that B = C so a ∈ B : a ∈ C
The same can be said the other way starting from c ∈ C . Thus A = C by definition.

Q.E.D.

Axioms

1. Sets are objects. If A is a set, then A is also an object. In particular, given two sets A and B, it is meaningful to ask
whether A is also an element of B.
2. There exists a set ∅, known as the empty set, which contains no elements, i.e., for every object x we have x ∉ ∅.
3. If a is an object, then there exists a set {a} whose only element is a, i.e., for every object y, we have y ∈ {a} if and only
if y = a; we refer to {a} as the singleton set whose element is a. Furthermore, if a and b are objects, then there exists a
set {a, b} whose only elements are a and b; i.e., for every object y, we have y ∈ {a, b} if and only if y = a or y = b; we
refer to this set as the pair set formed by a and b.
4. Pairwise union: Given any two sets A, B, there exists a set A ∪ B, called the union A ∪ B of A and B, whose elements
consists of all the elements which belong to A or B or both. In other words, for any object x,
x ∈ A ∪ B ⟺ (x ∈ A ∨ x ∈ B) .
1. Main note: Union, intersection and difference of sets
5. Specification or separation: Let A be a set, and for each x ∈ A, let P (x) be a property pertaining to x (i.e., P (x) is
either a true statement or a false statement). Then there exists a set, called {x ∈ A : P (x) is true} (or simply
{x ∈ A : P (x)} for short), whose elements are precisely the elements x in A for which P (x) is true. In other words, for

any object y, y ∈ {x ∈ A : P (x) is true} ⟺ (y ∈ A ∧ P (y) is true).

1. In some way this axiom is not necessary, as we can prove that the axiom of replacement (the next one) implies
this axiom, meaning it is unnecessary.
6. Replacement: Let A be a set. For any object x ∈ A, and any object y, suppose we have a statement P (x, y) pertaining
to x and y, such that for each x ∈ A there is at most one y for which P (x, y) is true. Then there exists a set
{y : P (x, y) is true f or some x ∈ A}, such that for any object z,

z ∈ {y : P (x, y) is true f or some x ∈ A} ⟺ P (x, z) is true f or some x ∈ A.

7. Infinity: There exists a set N, whose elements are called natural numbers, as well as an object 0 in N, and an object
S(n) assigned to every natural number n ∈ N, such that the Peano axioms hold.

8. Universal specification (Dangerous, leads to Russel's paradox, this is axiom attempts to unify axiom 5 and 6): Suppose
for every object x we have a property P (x) pertaining to x (so that for every x, P (x) is either a true statement or a false
statement). Then there exists a set {x : P (x) is true} such that for every object y,
y ∈ {x : P (x) is true} ⟺ P (y) is true.

1. This asserts the existence of greater sets, like the set of all blue objects or the set of all sets.
2. If we accept this axiom then we must also accept 9, but we also end up implying 2,3,4,5,6 and even 7 if we
consider natural numbers as objects. (This is a pretty straight forward this to prove, just always define your
property to be the one pertaining to your axiom of choice)
9. Regularity or foundation (fixes Russel's paradox): If A is a non-empty set, then there is at least one element x of A
which is either not a set, or is disjoint from A.

Proof axiom 6 implies axiom 5

Let A be a set, and let P (x) be a statement pertaining to objects x ∈ A. To show that the axiom of replacement implies the
axiom of specification, we will construct the set {x ∈ A : P (x) is true} using just the axiom of replacement. Let Q(x, y) be
the statement “y = x and P (x)”. To use the axiom of replacement, we must verify that for each x ∈ A, the statement Q(x, y)
is true for at most one y. But for each x ∈ A, there is exactly one y such that y = x, so it follows that for the full statement of
Q(x, y) there is at most one y satisfying the statement. The axiom of replacement thus allows us to construct the set

{y : y = x and P (x) f or some x ∈ A}. We claim that this is the same set as {x ∈ A : P (x) is true}. We show the inclusion
both ways:

Suppose z ∈ {x ∈ A : P (x) is true}. Thus z ∈ A and P (z) is true. But this means that z = x and P (x) for some x ∈ A;
specifically, there is z ∈ A such that z = z and P (z). Thus z ∈ {y : y = x and P (x) f or some x ∈ A}.
Suppose z ∈ {y : y = x and P (x) f or some x ∈ A}. This means that for some x ∈ A, we have z = x and P (x). Since
z = x this means we have P (z) and z ∈ A as well. Thus z ∈ {x ∈ A : P (x) is true}.

Since both directions of the inclusion hold, this means that the two sets are equal.
Q.E.D.

Properties

Let A be a non-empty set. Then there exists an object x such that x ∈ A.

A ≠ ∅ ⟹ ∃x ∈ A (1)

The empty set is unique

′ ′
∀x : x ∉ ∅ ∧ x ∉ ∅ ⟹ ∅ = ∅ (2)

Singleton sets are unique:

∀a : ∃!{a} (3)

For arbitrary elements a, b

{a, b} = {b, a} (4)

For arbitrary elements a, b

{a, a} = {a} (5)

Sets are partially ordered by set inclusion:

1:

A ⊆ B ∧ B ⊆ C ⟹ A ⊆ C (6)

2:

A ⊆ B ∧ B ⊆ A ⟹ A = B (7)

3:

A ⊂ B ∧ B ⊂ C ⟹ A ⊂ C (8)

Separated set is a subset:

S = {x : x ∈ A ∧ P (x) is true} ⟹ S ⊆ A (9)

The concept of separation obeys the axiom of substitution:

′ ′
A = A ⟹ {x ∈ A : P (x)} = {x ∈ A : P (x)} (10)

Consequence of axiom of regularity:

A ∉ A (11)

Consequence of axiom of regularity:

∀A, B : A ∉ B ∨ B ∉ A (12)

Diverse random proofs and demonstrations

(1)
We prove by contradiction. Suppose there does not exist any object x such that x ∈ A. Then for all objects x, we have
x ∉ A . Also, by Axiom 2 we have x ∉ ∅. Thus x ∈ A ⟺ x ∈ ∅ (both statements are equally false), and so A = ∅ , a
contradiction.

Q.E.D.
In this proof the fact that all x are not in A is implies that A is the empty set as that's literally the definition of the empty
set.
(2)
By contradiction suppose there were 2 empty sets ∅ , ∅ . ∀x : (x ∉ ∅ ∧ x ∉ ∅ ). But by the contrapositive definition of set
′ ′

equality this means that ∅ = ∅ .′

Q.E.D.
(3)
By the definition of the singleton set we know that ∀y : y ∈ {a} ⟺ y = a . Assume that an arbitrary element b had
more than a unique singleton set. Applying the definition we would get , ∀y : y ∈ {b} ⟺ y = b and
′
∀y : y ∈ {b } ⟺ y = b . But this means that for all y , y is in both sets which on it's turn implies that b = b . Meaning
′ ′

that the singleton set of an element is effectively unique.

Q.E.D.
(4)
We can prove both sets are equal by the definition of set equality. ∀x ∈ {a, b} : x ∈ {b, a} and ∀y ∈ {b, a} : y ∈ {a, b}.
And thus {a, b} = {b, a}.

Q.E.D.
(5)
We can prove both sets are equal by the definition of set equality. ∀x ∈ {a, a} : x ∈ {a} and ∀y ∈ {a} : y ∈ {a, a}. And
thus {a, a} = {a}.

Q.E.D.
(6)
Suppose that A ⊆ B and B ⊆ C . To prove that A ⊆ C , we have to prove that every element of A is an element of C .
So, let us pick an arbitrary element x of A. Then, since A ⊆ B, x must then be an element of B. But then since B ⊆ C ,
x is an element of C . Thus every element of A is indeed an element of C , as claimed.

Q.E.D.
(7)
We know that (definition subset) every element of A is also in B and we know that every element of B is also in A. But
this is just the definition for set equality and thus A = B

Q.E.D.
(8)
Suppose that A ⊂ B and B ⊂ C . To prove that A ⊂ C , we have to prove that every element of A is an element of C .
So, let us pick an arbitrary element x of A. Then, since A ⊂ B, x must then be an element of B and we also know that
there is still an element b in B that isn't in A. But then since B ⊂ C , x is an element of C just as b is also an element of
C . Thus every element of A is indeed an element of C and A ≠ C , as claimed.

Q.E.D.
(9)
By definition of S we have that every s in S is also in A and P (s) is true. But s being in S implying that s is also in A is
just the definition of a subset. Thus S ⊆ A.

Q.E.D.
(10)
By expanding our definition of set equality we know that for any arbitrary a in A there must be a a in A such that
′ ′

a = a otherwise set equality wouldn't hold. By the axiom of substitution we have a = a ⟹ P (a) = P (a ) and this
′ ′ ′

implies that every element in a that preserves the truth of the property has an equivalent element in a which also
′

preserves the truth of the property meaning that the two sets under the property are equal and that separation obeys
the axiom of substitution

Q.E.D.
I don't like this proof, pretty sure there is a fallacy somewhere.
(11)
For an arbitrary set A we define the set {A} thanks to the singleton axiom. We also know thanks to the axiom of
regularity that there must be at least a non-set element or disjoint set in {A}. In this case we don't have a non-set
element but we have 1 set, that by axiom must be disjoint so we have A ∩ {A} = ∅. Now suppose A ∈ A , then
A ∈ A ∩ {A} , which contradicts the axiom.

Q.E.D.
(12)
Consider the set {A, B} which exist according to the pair axiom. Once again we apply the axiom of regularity just like in
 (11) to see that either A or B must be a disjoint set from {A, B}. Suppose A is disjoint, then we know that
B ∉ A ∩ {A, B} but we also know that B ∈ {A, B} and thus it must follow that B ∉ A. The same reasoning can be
applied if B is disjoint.

Q.E.D.

Sets in classic Zermelo-Fraenkel theory

Definition

ZFC axioms

Cardinality

Pure set theory

Direct copy paste from Analysis I:

There is a special case of set theory, called “pure set theory”, in which all objects are sets; for instance the number 0 might
be identified with the empty set ∅ = {}, the number 1 might be identified with {0} = {{}}, the number 2 might be identified
with {0, 1} = {{}, {{}}}, and so forth. From a logical point of view, pure set theory is a simpler theory, since one only has to
deal with sets and not with objects; however, from a conceptual point of view it is often easier to deal with impure set
theories in which some objects are not considered to be sets. The two types of theories are more or less equivalent for the
purposes of doing mathematics, and so we shall take an agnostic position as to whether all objects are sets or not.

#comeback