Set Theory

Question 1

what is the set B (stylised)?

Answer 1

binary numbers - {0,1}

Question 2

why can sets with elements listed in a different order/with duplicates be considered equal?

Answer 2

a set is defined solely in terms of its members

Question 3

A = B iff…

Answer 3

A ⊆ B and B ⊆ A

Question 4

¬(A⊆B)

Answer 4

A ⊈ B

Question 5

the universe of discourse consists of

Answer 5

all elements under consideration

Question 5

what are the 3 properties of the subset relation?

Answer 5

reflexive, antisymmetric and transitive

Question 6

describe how the subset relation is reflexive

Answer 6

A ⊆ A for all sets A

Question 7

describe how the set relation is anti-symmetric

Answer 7

if a and b are related in both directions, they must be equal. e.g iff A ⊆ B and B ⊆ A, A = B

Question 8

describe how the subset relation is transitive

Answer 8

if A ⊆ B and B ⊆ C, A ⊆ C

Question 9

what is the least set with respect to inclusion?

Answer 9

the empty set since it is contained in any other set

Question 10

how to use set builder notation to define B, the subset of A

Answer 10

B = { x ∈ A : x has property P }

Question 11

write { Dan”, Felix } using set builder notation

Answer 11

{ x : x = Dan or x = Felix }

Question 12

what is Russell’s paradox

Answer 12

the set of sets that do not contain themselves CANNOT exist in naive set theory

Question 13

the importance of Russell’s paradox in set theory

Answer 13

it should not be possible to construct sets of all sets

Question 14

two sets are disjoint if…

Answer 14

they have no elements in common

Question 15

the intersection of two disjoint sets

Answer 15

the empty set

Question 16

|A|

Answer 16

the cardinality of A

Question 17

what is the inclusion-exclusion principle

Answer 17

|A U B| = |A| + |B| - |A ∩ B|

Question 18

A \ B in set builder notation

Answer 18

{ x ∈ A : x ∉ B }

Question 18

x ∈ { A \ B } iff

Answer 18

x ∈ A and x ∉ B

Question 18

construct the set A’ using only the universe discourse and the set A

Answer 18

U \ A

Question 19

P(A)

Answer 19

the set containing all subsets of A (including the empty set and itself)

Question 20

a set of 4 elements has how many subsets

Answer 20

16

Question 20

what trick can you use to figure out the number of elements in a powerset?

Answer 20

Pascal’s Triangle

Question 20

what is a family of sets F?

Answer 20

a collection of sets (where every element in F is a set)

Question 21

what is the union of the family of sets F?

Answer 21

{ x : x ∈ A for some A ∈ F }

Question 22

what is the intersection of a family of sets?

Answer 22

{ x : x ∈ A for all A ∈ F }

Question 23

both the union and intersection of a family of sets are..

Answer 23

sets of elements (arbritrary x’s)

Question 24

Alternative way to write U F if F = {A, B, C }

Answer 24

U{A, B, C}

Question 24

if F = {A,B,C}, what is U F shorthand for?

Answer 24

A U B U C

Question 25

U{A, B} in written english

Answer 25

the union of all sets within the family {A,B}

Question 26

what is an ordered pair?

Answer 26

a pair of objects with a first coordinate and a second coordinate

Question 27

(a,b) ∈ A ✕ B iff

Answer 27

a ∈ A and b ∈ B

Question 28

two ways to denote the cartesian product across all real numbers

Answer 28

R ✕ R or R^2

Question 29

R ✕ R denotes the set of..

Answer 29

points in the xy plane

Question 30

key value pairs are always ordered pairs from..

Answer 30

the Cartesian product Keys ✕
Values

Question 31

A^n corresponds to

Answer 31

the cartesian product of n copies of the set A (e.g an R vector over 4)

Question 32

the number is elements in a product is

Answer 32

the product of each individual set’s cardinality

Question 33

|A ✕ {}|

A ✕ {} |

Answer 33

0

Question 34

A ✕ {}

Answer 34

{}

Question 35

X ⊆ Y
Hence X\Y =

Answer 35

{}

Question 36

X ⊆ Y
Hence X’ U Y =

Answer 36

The universal set

Question 37

from the identity (P ⇒ Q) ⇔ (¬P ∨ Q), we get the identity P ⊆ Q = …

Answer 37

P’ U Q = universe set

Question 38

property of sets that corresponds to the contrapositive law

Answer 38

A ⊆ B iff A’ ⊆ B’