All Questions
17
questions
0
votes
0
answers
25
views
Computing transitive closure for relation via other relation
The closure of a relation $R$ over a set $S$ is denoted $R[S]$ and calculated via $\bigcup_{i\in\mathbb{N}}Y_i$ where $Y_0=S$ and $Y_{n+1}=Y_n\cup R(Y_n)$. ($R(Y_n)$ is the image of $Y_n$ under $R$).
...
- 9
2
votes
2
answers
741
views
What is a tuple?
In theory of computation, DFA's, NFA's, etc. are represented as a "tuple". Probability spaces are tuples. I am confused on what the notion of a tuple is and how it differs from a set?
1
vote
0
answers
73
views
Smallest partition in a set
I have a set consisting of
$$\Omega = \{a_1, a_2, \cdots, a_n\}$$
and I have to obtain another set, formed by the sum of the elements of the first set, such that the new elements do not exceed a ...
- 135
0
votes
1
answer
97
views
Uncountable Number of Mappable Functions in Computer Programs
On my homework, I'm told to argue the following claim:
There are functions from the natural numbers to the natural numbers that are uncomputable
by any computer program. What do you need to show in ...
1
vote
1
answer
31
views
How to find any element x of a set A, with three subsets B, C and D, by asking only three questions?
The main set A = {s, w, p, n, l, d, c, b} has three subsets B, C and D.
B = {s, l, n, d}
C = {s, p, l, c}
D = {w, s, n, c}
Only three yes/no questions are required to find any element x. I don't ...
- 11
0
votes
2
answers
225
views
Counting subsets of a set with $n$ elements
I am trying to understand a proposition from my textbook, which is the following:
Let $n \ge 1.$ Every set with n elements has $2^{n-1}$ subsets with an uneven number of elements and equally many ...
- 353
1
vote
1
answer
395
views
Find all the sets $A$ and $B$ such that $P(A \times B)=P(A)\times P(B)$
The last question in my exercise is to find all sets such that $P(A \times B)=P(A)\times P(B)$, where $P()$ denotes the power set. But I'm not sure how to go about finding sets which satisfy the ...
- 227
0
votes
3
answers
1k
views
Prove that the set of nonnegative numbers is denumerable
I need to show through a proof that the set of nonnegative numbers is denumerable
I know a set is denumerable if its members or elements can be put into an order and counted. I am supposed to show ...
- 263
0
votes
1
answer
716
views
Give a recursive definition of the set of points [m, n] that lie on the line n = 3m
I need to give a recursive definition of the set of points [m, n] that lie on the line n = 3m in N cartesian (cross) product N; where N = the set of all natural numbers. I need to use s as the ...
- 263
0
votes
1
answer
959
views
An encoding of non - empty sequence of strings
An exercise problem $:$
Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows:
$g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$.
Let $p_i$ denote ...
- 4,785
3
votes
0
answers
175
views
Why is this not a poset after adding zero?
The problem
Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
- 1,884
3
votes
1
answer
2k
views
Can someone verify my answers to these questions regarding this poset?
Problem:
18. Answer these questions for the poset ({{1}, {2}, {4}, {1,2}, {1,4}, {2,4}, {3,4},{1,3,4}, {2,3,4}}, $\subseteq$)
$\quad$a.Find the maximal elements
$\quad$b.Find the minimal elements
$\...
- 1,884
0
votes
1
answer
76
views
Why can the author just switch the order of the inequality without any reprecussions?
Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 2, page 598].
I understand the idea of a symmetric closure. You add all ...
- 1,884
2
votes
2
answers
460
views
Why does a set of m elements have 2$^m$ subsets?
Note: This example is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 576], shout out to @crash.
I understand why $A \times A$ has $n^2$ elements(because every member of set $A$ ...
- 1,884
1
vote
0
answers
69
views
A set system generated by a closure operator?
Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with
$$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$
...
- 47.7k