This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

0
votes
1answer
32 views

Help with a relation to Congruences Modulo 5?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
0
votes
0answers
28 views

Set notation help

I'm working on this questions: Let $A= \{-2,-1,0,1,2\}$. Let $R$ be the relation defined by $xRy$ if and only if $y=-x$. Let $S$ be the relation defined by $xSy$ if and only if $y = |x|$ Whilst ...
0
votes
1answer
37 views

Help with functions and relations?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
0
votes
0answers
175 views

Proof of relation property (transitive/symmetric closure)

I'm struggling with one exercise. I got a little bit stuck here: A call graph is a relation RC and a pair (f, g) of function names is in RC, iff the body of function f calls the function g. For ...
0
votes
1answer
39 views

Is the relation A = {(a,a), (c,c), (d,d), (b,a)} transitive?

I'm working on a discrete math problem to solve for reflexive, symmetric and transitive and I'm stuck on the transitive one. How do I solve for the transitive of the following? A = {(a,a), (c,c), ...
0
votes
2answers
39 views

Help with Relations and Functions?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
0
votes
1answer
29 views

Help with Relations and Functions in Discrete Mathematics.

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
0
votes
0answers
22 views

Relations and quantifiers

When talking about relations, we know that the relation is anti-symmetric if "for all x: for all y: R(x,y) AND R(y,x) IMPLIES (x=y)". But can i rewrite this as "for all x: for all y: R(x,y) EXCLUSIVE ...
1
vote
1answer
99 views

Composition of relations: A ∘ B

Solve: Composition of relations: A ∘ B A = {(1, 1), (1, 2), (4, 1), (4, 2)} B = {(1, 1), (2, 1), (1, 4), (2, 4)} When i solve mentally i get A ∘ B = {(1, 1), (2,2)} But when I draw an ...
-3
votes
1answer
32 views

Show that if S and R are sets then $S^R$ is also a set. [closed]

So I have to show that if S and R are sets then $S^R$ is also a set.
-1
votes
2answers
39 views

Function examples [closed]

I have the following: Give example of sets F, G, R, S so that: F $\subseteq $RxS and G={(y,x): (x,y) $\in$ F) and : F and G are not Functions. F is a Function but G is not. F is not a Function but G ...
1
vote
1answer
38 views

How do I prove that for all sets $A$, $B$, and $C$, if $A \prec B$ and $B \prec C$, then $A \prec C$?

If $A \sim B$, it means there is a one-to-one and onto function from $A$ to $B$. If $A$ and $B$ are sets, then we will say that $B$ dominates $A$, and write $A \precsim B$, if there is a function $f : ...
2
votes
2answers
51 views

Show that $R \cap R^{−1}$ is an equivalence relation on $X$?

Let $R$ be a reflexive and transitive relation on $X$. Show that $R \cap R^{−1}$ is an equivalence relation on $X$. I am stuck and feel like I am doing something wrong, any help would be much ...
3
votes
3answers
577 views

Prove that f is surjective

The problem: Prove or refute the following: If $f,g,h: \mathbb{R} \to \mathbb{R}$ and $f \circ g \circ h$ is surjective then $f$ is surjective. My solution: (The definition of surjective: iff ...
0
votes
3answers
38 views

The relation $(m,n) \mapsto 2^{m-1}(2n-1)$

Show that relation $(m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection of $\mathbb{N}\times\mathbb{N}$ on $\mathbb{N}$. Can anyone explain how to show this?
1
vote
1answer
23 views

Question about structural induction and predecessor relation

I have two questions, about structural induction and the predecessor relation. Why can't a relation be well-founded if it has an infinite descending chain, provided that it has a maximum element? How ...
5
votes
0answers
75 views

Is there a first-order formula expressing this property?

Suppose $R$ is a binary relation on $\{0,1\}^*$ (where $\{0,1\}^*$ is the set of all finite words over the alphabet $\{0,1\}$), and for all $x$, the number of $y$ such that $xRy$ is finite. Is there ...
0
votes
1answer
38 views

Discrete mathematics set relations anti symmetric

Take the set $A=\{1,4,5,7\}$ with the relation $R=\{(1,4),(1,5),(4,7)\}$. My teacher said that this relation is anti-symmetric but I don't get how there isn't any $x; y$ that belongs to $A$ where ...
0
votes
3answers
169 views

Discrete Math Equivalence Relation

Let $f$ be some function with domain $S$ and range $T$. Define a relation $R$ by $x R y$ to mean $f(x) = f(y)$. Prove that $R$ is an equivalence relation. If $4$ is a member of $S$, what are the ...
1
vote
1answer
35 views

number of relations when set is simultaneously reflexive and symmetric

I have this problem: You are given the set A = {a, b, c, d, e}. Find the number of relations R ⊆ A × A, which are 10pt simultaneously reflexive and symmetric. and this is my solution: ...
0
votes
1answer
58 views

all subsets of R are reflexive?

Prove or refute: If R is reflexive than all subsets of R are reflexive. This my solution: Let {1,2,3) in R --> We know that R is reflexive -> R = ...
-4
votes
1answer
59 views

Relation Proof - Reflexive, Symmetric, Transitive

$A$ is the "absolute value" relation on $\Bbb R$: For all real numbers $x$ and $y$, $x A y\Leftarrow\Rightarrow |x| = |y|$. Determine whether the given relation is reflexive, symmetric, or ...
-1
votes
1answer
43 views

Proving pairs of natural numbers is partial order

I'm having trouble with this question, for question one, do I prove that the statement satisfies reflexivity, antisymmetry, and transivity? Would $m < m'$ satisfy reflexivity alone or do I have ...
1
vote
2answers
36 views

Prove that $M/{\sim}$ forms a partition of $M$.

My attempt: Suppose $\sim$ is an equivalence relation on $M$. If $a \in M$, let $\bar{a}=\{m \in M \,|\, m\sim a\}$. Since each element $a$ of $M$ is in its own equivalence class $\bar{a}$, the union ...
1
vote
1answer
16 views

Show that the following Set $\Lambda$ is a Partition

Consider the two sets $$A_r = \{x \in \mathbb{Z} \enspace | \enspace x \enspace = \enspace 5q + r, \enspace 0 \enspace \leq \enspace r \enspace < \enspace 5\}$$ $$\Lambda = \{A_r\}$$ We must ...
3
votes
1answer
29 views

Checking if a Relation is Transitive

I have $$R = \{(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,4),(4,1),(3,1),(2,1),(4,4),(4,2),(3,2),(4,3)\}$$ Is this relation transitive? I think since $(2,1), (1,4) \in R$ to be transitive $(2,4) \in R$ ...
0
votes
0answers
52 views

Finding the domain and range of the a Relation

i have this question Let $A=\{1,2,3,4\}$, $B=\{1,4,6,8,9\}$ and $aRb \iff b=a^2$. Find the domain, range of the relation $R$. My answer is Domain=(1,2,3) Range=(1,4,9).Is this correct?
0
votes
1answer
43 views

Asymmetric relation on finite set

The set $X$ has $n$ elements. A relation $R$ on $X$ is asymmetric if $(x,y) \in R \to (y,x) \notin R$ for all $x$ and $y \in X$. Determine how many asymmetric relations $R$ there are in $X$, for ...
0
votes
0answers
69 views

How to Prove that a Choice Structure Satisfies WARP?

Would you please help me to prove the following statement? If R is a rational binary relation on a finite set X, then $(B, c_R)$ is a choice structure satisfying WARP. Note: Only for clarification, ...
0
votes
0answers
44 views

If a choice structure satisfies WARP, then the underlying binary relation is rational.

Would you please help me to prove the following proposition: If $(P(X), c_R)$ is a choice structure that satisfies WARP, then $R_c$ is a rational binary relation? Clarification: For any nonempty ...
1
vote
1answer
103 views

Need Examples to Understand Choice Function and Choice Structure.

Would you please give me a concrete example for the following definitions? Specifically I don't understand why a choice function is defined as $c: B \rightarrow P(X)$. For any nonempty set $X$, let ...
-1
votes
1answer
71 views

$(P(X), C_R)$ may be a choice structure even if $R$ is not a rational relation.

Would you please give me an example to show that $(P(X), C_R)$ may be a choice structure even if $R$ is not rational (i.e., complete and transitive). Clarification: For any nonempty set $X$, let ...
0
votes
1answer
47 views

Relations and their properties

I'm studying relations and their properties and trying to understand how to deal with more difficult examples. Given the following properties: Reflexive Transitive Symmetric Antisymmetric ...
0
votes
1answer
33 views

Question on equivalence relations

In set theory a relation is said to be equivalence if the relation is,. Reflexive Symmetric Transitive I would like to know if the following relation is an equivalence one. $R = \{ (m,n) \in Z ...
0
votes
3answers
63 views

Why isn't upper bound unique?

If there is an upper bound $a$ of a set $A$, and an upper bound $b$ of the set $A$ and $b>a$, why doesn't that mean that only $b$ is the upper bound of the set since it's "more upper" than $a$?
1
vote
1answer
44 views

Discrete math: how to start a problem to determine reflexive, symmetric, antisymmetric, or transitive binary relations

I need to determine if the following relation is reflexive, symmetric, antisymmetric, and/or transitive. I have been reading a lot of similar posts about these topics on here, but I am still stumped. ...
0
votes
1answer
57 views

Proof involving $R^n$ and the transitivity of a relation

I want to prove: R is the relation on the set A. If R is transitive, then $R^n$⊆$R^{n-1}$ for n = 2, 3, 4,... I'm having trouble approaching this proof, I've started my proof by induction in ...
3
votes
2answers
66 views

Mathematical definition of a relational database

I'm reading a very verbose textbook on database design, but I suspect that much of the book could be condensed into a few pages if the authors were not trying to avoid mathematical language. What is ...
1
vote
0answers
21 views

Interesting relation on element of matrices, is it an equivalence relation?

Let $A\in \Bbb F^{n\times m}$. Let $\operatorname{neighborhood}(x)$ denote the elements surrounding $x$ ($x$ included). Let $a,b,c\in A$, $k\in \Bbb F$. I've come across the following relation: ...
1
vote
2answers
66 views

Not sure how to proceed: If $f: B \cup C \rightarrow A$ is a function, then $f = f_{[B]} \cup f_{[C]}$

I'm using Charles Pinter's A Book of Set Theory and I'm given the following theorem to prove. Theorem 2.15: If $f: B \cup C \rightarrow A$ is a function, then $f = f_{[B]} \cup f_{[C]}$ The book ...
0
votes
1answer
69 views

Symmetric and transitive but not reflexive

I am trying to do an exercise in Munkres' Topology where I am supposed to show the mistake in the following proof about equivalence relations: ...
0
votes
1answer
80 views

How to determine whether a set (R) is reflexive, symmetric or transitive

Trying to figure out what the differences between reflexive, symmetric and transitive are. Could do with a bit of help with the following examples. Like what makes it reflexive, what makes it ...
1
vote
2answers
47 views

Length of angle bisector in a regular polygon?

How can I find a relation describing the length of angle bisector of regular polygon expressed as a function of its side's length? For a equilateral triangle and a square with a side of length $a$, ...
0
votes
1answer
38 views

understanding of different definition of transitive closure

I'm familiar with the definition of transitive closure, how to find it and its general properties. However, I've run across a different way of defining transitive closure and it is not so intuitive ...
0
votes
0answers
61 views

Partial order and total order

Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Define a relation $L$ on $A×B$ as follows: $L=\{((a,b),(a',b'))\in (A×B)×(A× B) \mid aRa', \text{and if } a=a' \text{ then } ...
1
vote
2answers
56 views

Preference Maximizing Choice Rule

Definition: A Choice Rule is a function $ C: \mathcal{P}(X) \to \mathcal{P}(X) $ such that $ C(B) \subset B, $ $\forall B \in \mathcal{P} (X) $ and $ C(B) \neq \emptyset $ if $ B \neq \emptyset $ The ...
1
vote
2answers
176 views

Function or relation: y^4 = 8x^2

The question under debate: Is $y^4=8x^2$ a function or a relation? We disagree. I say, it's a relation because when I substitute in points I get two outputs for most inputs, and thus it's not a ...
-2
votes
1answer
30 views

Relations and functions

$$ g(x) = e^x-1, x\in\mathbb R\\ h(x) = \ln(\ln x),x>1\\ $$ By restricting the domain of $g$ to $(\alpha, \infty)$, where $\alpha \in \mathbb R$, find the smallest value of $\alpha$ in exact form ...
3
votes
1answer
20 views

Type of relation (between relations)

Is there a word for the type of relation $R$ and $S$ are with respect to each other, if $xRy \iff ySx$? Reciprocal relations?
0
votes
1answer
29 views

Alegebra- Function or NOT a function

if you have a relation with the domains: 0,1,2,3,4 and a range of: 3,1,2,4,2 does this mean it is not a function because there are two outputs of the number 2? Or can it only not be function if there ...