Cardinalities and Relations

Question 1

What type of set is the empty set?

(Finite, Infinite etc?)

Answer 1

Finite

Question 2

If a bijection exists between set X and set Y, what can be assumed about these sets?

Answer 2

|X| = |Y|

They have the same cardinality.

Question 3

Define a Finite set.

Answer 3

A finite set has either no elements, or forms a bijection with a set of the form {1,2,…n}, for some fixed positive integer n.

Question 4

Define an Infinite set.

Answer 4

An infinite set is non-empty and there does not exist a bijection with a set of the form {1,2,…n}, for some fixed positive integer n.

Question 5

Every infinite subset of ℤ⁺ has the same cardinality as?

Answer 5

ℤ⁺

Question 6

Define Countably Infinite.

Answer 6

A set is countably infinite iff it has the same cardinality as ℤ⁺

ℤ⁺, 2ℤ

Question 7

Interval notation:

[1,4]
(1,4)
[1,4)

What are these sets?

Answer 7

[1,4] = {1,2,3,4}
(1,4) = {2,3}
[1,4) = {1,2,3}

Question 8

A set is Countable iff?

Answer 8

It is Finite or Countably infinite

Question 9

Let B ⊆ A and let A be finite.

Is B Countable?

Answer 9

Yes. Any subset of a countable subset is countable.

A is finite, hence A is countable

Question 10

Let B ⊆ A and let A be infinite.

Is B Countable?

Answer 10

No. Any subset of an uncountable subset is uncountable.

A is infinite, hence A is uncountable

Question 11

What is the Schroder-Bernstein Theorem?

Answer 11

If |X| ≤ |Y| and |X| ≥ |Y|, then |X| = |Y|

If there exist one-to-one functions f : X → Y and g : Y → X, then there exists a bijective function h : X → Y.

In other words, if two sets can be injected into each other, they have the same cardinality.

Question 12

Why is the Schroder-Bernstein Theorem Useful?

Answer 12

This theorem is particularly useful in set theory to prove that two sets have the same size without explicitly constructing a bijection between them.

Question 13

What are the ways to show |X| = |Y|

Answer 13

Injective function X → Y and Surjective function X → Y
OR
Injective function X → Y and Injective function Y → X
OR
Surjective function X → Y and Surjective function Y → X

Question 14

Given sets A and B, a Binary Relation R from A to B is a..?

Answer 14

Given sets A and B, a Binary Relation R from A to B is a subset of A x B

If x is related to y, it is not necessary that y is related to x.

Question 15

A relation is a generalisation of a..?

Answer 15

Function

All functions are relations, but not all relations are functions.

Question 16

Let ⍴ be a relation on set A:

⍴ is Reflexive iff?

Answer 16

∀x ∈ A, x⍴x

Question 17

Let ⍴ be a relation on set A:

⍴ is Symmetric iff?

Answer 17

∀x,y ∈ A, if x⍴y then y⍴x

Question 18

Let ⍴ be a relation on set A:

⍴ is Transitive iff?

Answer 18

∀x,y,z ∈ A, if (x⍴y and y⍴z) then x⍴z

Question 19

Define an equivalence relation

Answer 19

A relation that is:
1. Reflexive
2. Symmetric
3. Transitive

Question 20

Define an Equivalence Class

Answer 20

Given a set S and an equivalence relation ⍴ on S, an equivalence class for an element a ∈ S is the subset of all elements in S that are related to a by ⍴. It is denoted as [a] and defined as:

[a] = {x ∈ S | x ⍴ a}

All elements in an equivalence class are related to each other, and two distinct equivalence classes have no elements in common.

Equivalence classes partition the set S into non-overlapping subsets, where each element of S belongs to exactly one equivalence class.

Question 21

Let ⍴ be a relation on set A:

⍴ is Antisymmetric iff?

Answer 21

∀x,y ∈ A, if (x⍴y and y⍴x) then x = y

or

If x⍴y, then y is not related to x unless x = y

Question 22

What is a Partial Order?

Answer 22

A relation that is:
1. Reflexive
2. Antisymmetric
3. Transitive

Question 23

A relation R on set S is a Total Order Relation iff R is?

Answer 23

A relation R on set S is a Total Order Relation iff R is:
* A Partial order, and…
* Any 2 elements of S are comparable

Question 24

Is the relation ≤ on ℝ a Total Order?

Is the relation of division over ℤ⁺ a Total Order?

Answer 24

Is the relation ≤ on ℝ a Total Order: Yes

Is the relation of division over ℤ⁺ a Total Order: No, but a Partial Order. (3 does not divide 5 and 5 does not divide 3, hence not comparable)