0.4 Discrete structures set theory  (Page 2/6)

Following this definition, the set of natural numbers N can be obtained as follows: First by (1), 0 is put into N.

Then by (2), since 0 is in N, 0 + 1 (= 1) is in N.

Then by (2) again, 1 + 1 (= 2) is in N.

Proceeding in this manner all the natural numbers are put into N. Note that if we don't have (3), 0.5, 1.5, 2.5, ... can be included in N, which is not what we want as the set of natural numbers.

Basics of set

Definition (Equality of sets): Two sets are equal if and only if they have the same elements.

More formally, for any sets A and B, A = B if and only if ∀x [ x ∈A ↔ x ∈B ] .

Thus for example {1, 2, 3} = {3, 2, 1}, that is the order of elements does not matter, and {1, 2, 3} = {3, 2, 1, 1}, that is duplications do not make any difference for sets.

Definition (Subset): A set A is a subset of a set B if and only if everything in A is also in B.

More formally, for any sets A and B, A is a subset of B, and denoted by A ⊆B, if and only if ∀x [ x∈A → x ∈B ] .

If A ⊆B, and A ≠B, then A is said to be a proper subset of B and it is denoted by A⊂B.

For example {1, 2} ⊆ {3, 2, 1}.

Also {1, 2} ⊂ {3, 2, 1}.

Definition (Cardinality): If a set S has n distinct elements for some natural number n, n is the cardinality (size) of S and S is a finite set. The cardinality of S is denoted by |S|. For example the cardinality of the set {3, 1, 2} is 3.

Definition (Empty set): A set which has no elements is called an empty set. More formally, an empty set, denoted by ∅, is a set that satisfies the following:

∀x x ∉ ∅, where ∉ means "is not in" or "is not a member of".

Note that ∅ and {∅} are different sets. {∅} has one element namely ∅ in it. So {∅} is not empty. But ∅ has nothing in it.

Definition (Universal set): A set which has all the elements in the universe of discourse is called a universal set.

More formally, a universal set, denoted by U, is a set that satisfies the following: ∀x x ∈U.

Three subset relationships involving empty set and universal set are listed below as theorems without proof.

Note that the set A in the next four theorems are arbitrary. So A can be an empty set or universal set.

Theorem 1: For an arbitrary set A A ⊆U.

Theorem 2: For an arbitrary set A ∅ ⊆A.

Theorem 3: For an arbitrary set A A ⊆A.

Definition (Power set): The set of all subsets of a set A is called the power set of A and denoted by 2A or P(A) .

For example for A = {1, 2}, P(A) = {∅, {1}, {2}, {1, 2} } .

For B = {{1, 2}, {{1}, 2}, ∅} , P(B) = {∅, {{1, 2}}, {{{1}, 2}}, {∅}, { {1, 2}, {{1}, 2 }}, { {1, 2}, ∅}, { {{1}, 2}, ∅}, {{1, 2}, {{1}, 2}, ∅} } .

Also P(∅) = {∅} and P({∅}) = {∅, {∅}} .

Theorem 4: For an arbitrary set A, the number of subsets of A is 2|A|.

Mathematical reasoning

Mathematical theories are constructed starting with some fundamental assumptions, called axioms, such as "sets exist" and "objects belong to a set" in the case of naive set theory, then proceeding to defining concepts(definitions) such as "equality of sets", and "subset", and establishing their properties and relationships between them in the form of theorems such as "Two sets are equal if and only if each is a subset of the other", which in turn causes introduction of new concepts and establishment of their properties and relationships. Proofs are the arguments for establishing those properties and relationships. At the bottom level these arguments follow the inference rules of propositional and predicate logic, that is the conclusion of the theorem being proved must be derived from its hypotheses, axioms, definitions, and proven theorems using inference rules. However, at the bottom level they become tedious and inefficient as one can easily imagine. Thus in actual proofs short-cuts are taken using already proven theorems, using multiple inference rules in one step without explicitly mentioning them individually, omitting "obvious" proofs, and so on.