Sets, Relations, and Languages

Question 1

A collection of objects ( denoted by { } )

Answer 1

Set

Question 2

Objects comprising a set are called ( denoted by ∈ )

Answer 2

Elements

Question 3

What is a relative complement?

Answer 3

For sets A and B, x is an element of A and not an element of B

Question 4

What is the set of all subsets ( denoted by 𝒫(A) or 2^A )

Answer 4

Power set

Question 5

Any set R such that R ⊆ A x A is called

A set of ordered pairs, (m, n), where m is from the set M, n is from the set N, and m is related to n by some rule

Answer 5

Binary relation

Question 6

A function that maps every element in the codomain to an element in the domain

Answer 6

onto function

Question 7

A function that maps each input value to a unique output value

Answer 7

one-to-one function

Question 8

A function that establishes a binary relationship between two sets

Answer 8

into function

Question 9

The set of all ordered pairs where one element is from the first set and the other is from the second set ( A and B (a, b) )

Answer 9

Cartesian product

Question 10

What are natural numbers?

Answer 10

N = { 0, 1, 2, 3, … }

Question 11

What are integers and positive integers?

Answer 11

Z = { …, -3, -2, -1, 0, 1, 2, 3, … }
Z+ = { 1, 2, 3, … } ( Also called positive natural numbers N+)

Question 12

An ordered list of numbers (called “terms”) that often follow a specific pattern or rule, where the order of the terms matters

Answer 12

Sequence

Question 13

A relationship on a set, generally denoted by ∼ , ≈, or ≡ that is reflexive, symmetric, and transitive for everything in the set

Answer 13

Equivalence relation

Question 14

A division of a set A is a grouping of non-empty, disjoint subsets whose union equals A

Answer 14

Partition

Question 15

A binary relation on a set that is reflexive, antisymmetric, and transitive

Denoted by ≤

Answer 15

Order relation

Question 16

Set A (nonempty) ordered by an order relation R

Answer 16

Poset

Question 17

Sets that have a one-to-one and onto (bijective) correspondence between their elements.

Answer 17

Equinumerous sets

Question 18

A relationship between sets which compares their relative size
Sets are equipotent A ~ B

|A| or |B|

Answer 18

Cardinality of sets

Also can be
cardA or cardB

Question 19

A set that contains a specific number of elements, where the number of elements is a non-negative integer.

Answer 19

Finite set

Question 20

A set that contains an unbounded or limitless number of elements.

*Dedekind Theorem

Answer 20

Infinite set

Question 21

A set has the same cardinality as the set N natural numbers
|A| = |N|

Answer 21

Countably infinite

Question 22

For any set A, the power set of A has a strictly greater cardinality than A itself

There is no one-to-one correspondence between A and P(A), meaning P(A) is always larger than A, even if A is an infinite set

Answer 22

Cantor Theorem

Question 23

If you have two sets A and B, the number of functions from set A to set B is |B|^|A|

The total number of possible functions from A to B is calculated by raising the size of B to the power of the size of A. Each element in A has |B| choices for its image, so the product for all elements of A gives the total number of functions.

Answer 23

Counting Functions Theorem

Question 24

If n items are placed into m containers, and n > m, then at least one container must contain more than one item.

Answer 24

Pigeonhole Principle

Question 25

Let R be a binary relation on a finite set A with a, b ∈ A
If there is a path from a to be in R, then there is a path of length at most |A|

Answer 25

Path Theorem

Question 26

To prove that certain sets, such as the set of real numbers, are uncountable by constructing an element not in any assumed complete list through differing values along a diagonal.

Answer 26

Diagonalization Principle

Question 27

Property of a set with respect to an operation, where performing the operation on elements of the set always results in an element that is also within the set.

Answer 27

Closure

i.e.
Natural numbers are closed under addition (nat num n + m will equal nat num)
Natural numbers are not closed under subtraction
(nat num n - m could not equal nat num [negative num])
Integers are closed under subtraction
(int n - m can equal a neg num)

Question 28

The reflexive, transitive closure of a relation.

Answer 28

• (Kleene star)

Question 29

Any finite set with elements that are called symbols
Σ

Answer 29

Alphabet

Question 30

Difference between Σ and Σ*

Answer 30

Σ refers to the set of individual symbols or characters (the alphabet)
Σ* refers to the set of all possible finite strings (or words) that can be formed using the alphabet Σ

Question 31

The simple joining of two strings by appending the second string to the end of the first.

◦

Answer 31

Informal concatenation

Question 32

The precise operation of combining two strings from a formal language, creating a new string by appending all symbols of the second string to the first, preserving order.

◦

Answer 32

Formal concatenation

Question 33

A sequence of characters within a word that can be written as v in w = xvy, where x and y are potentially empty strings.

Answer 33

Substring

Question 34

The set of all strings that can be formed by concatenating zero or more strings from L. It is specific to formal languages and operations.

Answer 34

Kleene star * of a language

Question 35

The set of all strings that can be formed by concatenating one or more strings from the language L.
Excludes the empty string.

Answer 35

Kleene plus K^+

Question 36

Relation consists of all ordered pairs where the first and second elements are swapped. If R contains (a, b), then this contains (b, a)

Answer 36

Inverse relation