All Questions
14
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
0
votes
1
answer
451
views
How to prove that this relation is a partial order
Ok, so I have this discrete math question that is bugging me for a while and I cannot solve it by myself. Here is the question :
Let $R$ be a relation defined on $\mathbb{R}_+ \times \mathbb{R}_+$ ...
user764644
0
votes
2
answers
36
views
What does this relation represents ?
so i have a hard time understanding what would this relation looks like, we aren't given any precise function so it's hard to know what this would look like. We have to establish the relation and then ...
- 21
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
0
votes
2
answers
445
views
Prove a relation to be reflexive by induction
Base case ~: For all $s,s' \in S$
$$treeS \sim treeS'$$
Step case ~: for $ t \sim t', t'' \sim t'''$ and $s,s' \in S$
$$tree_s(t,t') \sim tree_{s'}(t'',t''')$$
I was able to understand what ...
- 159
0
votes
1
answer
996
views
Which one of the following is true of this relation?
Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set:
a)Symmetric b)...
- 15
2
votes
1
answer
61
views
Discrete Mathematics: Relations
Confused about this question: Describe two binary relations $R$ and $S$ on $\{1, 2, 3\}$ that are not equivalence relations, but whose composition $R\circ S$ is an equivalence relation.
- 21
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
2
answers
1k
views
How to mathematically show that the relation is transitive?
Problem:
Show that the relation $x R y$ iff $x \leq y$ is a poset over the set of integers $\mathbb{Z}$
My work:
I know that to show the relation is a poset or a post order, I have to show the ...
- 1,884
1
vote
0
answers
2k
views
Can someone verify my work for finding the following closures?
This is the problem I am currently working on
Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the
a.reflexive closure of ...
- 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
2
answers
66
views
Not sure how to do Non-Homogeneous Recurrence Relations
I have a sample exam paper, and the answer is given, but I can't work out the answer from the question:
Find the solution of:
$a_n = \frac{1}{3}a_{n-1} + 2$
using $a_0 = 4$
Given Answer: $a_n = 3 ...
