Sets, Relations, and Languages Flashcards

1
Q

A collection of objects ( denoted by { } )

A

Set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Objects comprising a set are called ( denoted by ∈ )

A

Elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a relative complement?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

Power set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

Binary relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

onto function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

one-to-one function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

A function that establishes a binary relationship between two sets

A

into function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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) )

A

Cartesian product

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are natural numbers?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are integers and positive integers?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

Sequence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Equivalence relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

Partition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

Denoted by ≤

A

Order relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Set A (nonempty) ordered by an order relation R

17
Q

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

A

Equinumerous sets

18
Q

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

|A| or |B|

A

Cardinality of sets

Also can be
cardA or cardB

19
Q

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

A

Finite set

20
Q

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

*Dedekind Theorem

A

Infinite set

21
Q

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

A

Countably infinite

22
Q

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

A

Cantor Theorem

23
Q

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.

A

Counting Functions Theorem

24
Q

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

A

Pigeonhole Principle

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|
Path Theorem
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.
Diagonalization Principle
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.
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)
28
The reflexive, transitive closure of a relation.
* (Kleene star)
29
Any finite set with elements that are called symbols Σ
Alphabet
30
Difference between Σ and Σ*
Σ 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 Σ
31
The simple joining of two strings by appending the second string to the end of the first. ◦
Informal concatenation
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. ◦
Formal concatenation
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.
Substring
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.
Kleene star * of a language
35
The set of all strings that can be formed by concatenating one or more strings from the language L. Excludes the empty string.
Kleene plus K^+
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)
Inverse relation