Maths 2F

Question 1

The power set of X denoted P(X) or 2^{<strong>x</strong>} is the set whose?

Answer 1

Members are the subsets of X.

Question 2

The union of A and B, denoted A ∪ B, is the set of?

Answer 2

All objects belonging to at least one of the sets.

A ∪ B = { x : x ∈ A or x ∈ B }

Question 3

The intersection of A and B, denoted A ∩ B, is the set of objects belonging to?

Answer 3

Both of the sets

A ∩ B = { x : x ∈ A and x ∈ B }

Question 4

The complement or relative complement of B in A, denoted A\B or A−B, is the?

Answer 4

Set of members of A which do not belong to B

A \ B = { x ∈ A : x ∈/ B }

Question 5

Let X, Y and Z be sets, and let f: X → Y and g: Y → Z be functions. Then the composite

g ◦ f = gf : X → Z

…

Answer 5

Is the function given by

g ◦ f(x) = g f(x)

Question 6

For any set X there is an identity function…

Answer 6

Id = Id_X : X → X given by Id_X (x) = x

Question 7

A function f : X → Y is injective or an injection or one-to- one if?

Answer 7

f(x₁) = f(x₂) ⇒ x₁ = x₂

Question 8

A function f : X → Y is surjective or a surjection or onto if for every…

Answer 8

y ∈ Y there exists x ∈ X such that f(x) = y

Question 9

A function f : X → Y is bijective or a bijection or a one-to-one correspondence if?

Answer 9

It is both injective and surjective

Question 10

Let f : X → Y be a function. If A is a subset of X then the image of A is the?

Answer 10

Subset f(A) of Y given by

f(A) = {f(a) : a ∈ A}

Question 11

If B is a subset of Y then the inverse image or preimage of B is?

Answer 11

The subset f⁻¹(B) of X given by

f⁻¹(B) = { x ∈ X : f(x) ∈ B }

Question 12

Let X be a set. If there is a bijection n → X for some nonnegative integer n then?

Answer 12

X is finite

Otherwise X is infinite

Question 13

A set E is countably infinite if?

Answer 13

There is a bijection from ℕ to E

Question 14

A set E is uncountable if there is?

Answer 14

No injective function from E to ℕ.

Question 15

If f : X → Y is injective and Y is countable then X is?

Answer 15

Countable

Question 16

If f : X → Y is surjective and X is countable then?

Answer 16

Y is countable

Question 17

Let X be any set. Is P(X) to X countable or uncountable?

Answer 17

Then there is no injective function from P(X) to X.

In particular P(ℕ) is uncountable.

Question 18

Is the set of real numbers countable or uncountable?

Answer 18

Uncountable

Question 19

Let ∼ be a relation on a set X

x ∼ x for all x ∈ X is?

Answer 19

One says then that ∼ is relexive

Question 20

Let ∼ be a relation on a set X

If x ∼ y then y ∼ x is?

Answer 20

One says then that ∼ is symmmetric

Question 21

Let ∼ be a relation on a set X

If x ∼ y and y ∼ z then x ∼ z is?

Answer 21

One says then that ∼ is transitive

Question 22

Let ∼ be an equivalence relation on a set X, and let x be a member of X. Then the equivalence class of x is the set?

Answer 22

[x] = { y ∈ X : x ∼ y }

Question 23

Let d, a, b, m, n be integers such that d | a and d | b. Then?

Answer 23

d | (ma + nb)

Question 24

Let a and b be integers not both zero. Then there are integers m and n such that?

Answer 24

gcd(a, b) = ma + nb

Question 25

Two integers are coprime or relatively prime if?

Answer 25

Their greatest common divisor is 1

Integers m,n such that ma + nb = 1

Question 26

A prime number is an integer p > 1 with?

Answer 26

No positive integer divisors other than 1 and p

Question 27

The least common multiple of two integers a and b is the?

Answer 27

Smallest natural number m such that m divides a and m divides b

Question 28

One says that a and b are congruent modulo m

a ≡ b mod m if?

Answer 28

if a − b is divisible by m

Question 29

If a ̸≡ b mod m then?

Answer 29

a − b is not divisible by m

Question 30

a ≡ b mod m ⇒?

Answer 30

a = b + km

for some integer k

Question 31

f a ≡ b mod m and c ≡ d mod m, then?

Answer 31

a + c ≡ b + d mod m

a − c ≡ b − d mod m

ac ≡ bd mod m

Question 32

Let m,a ∈ Z, m > 0. Then gcd(a,m) = 1 if and only if there is?

Answer 32

An integer r such that

ra ≡ 1 mod m

Question 33

Let a ∈ Z, m ∈ N. An integer r such that ar ≡ 1 mod m is called?

Answer 33

An inverse for a modulo m

Question 34

Let X be a set. A permutation of X is a?

Answer 34

Bijective function from X to X

Question 35

The set of permutations of X is denoted?

Answer 35

Perm(X)

Question 36

An equivlence relation is thus if and only if?

Answer 36

It is reflexive, symmetric and transative

Question 37

State a formula relating the cardinalities of A,B, A ∪ B and A ∩ B

Answer 37

|A ∪ B| = |A| + |B| - | A ∩ B |

|A x B| = |A| x |B|

Question 38

The Pigeonhole principle states that there can only be an injection…

Answer 38

A x B → A ∪ B if

|A x B| ≤ |A ∪ B|