# Tagged Questions

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.

30 views

### Transivity / Binary relation? [closed]

Discuss the Transitivity of Binary Relations $\mathcal{S}$ $a$ on $\Bbb R$ defined by $a (x, y)$ $\in \Bbb R^2$--> $x \leq ay$ ( for some a $\in \Bbb R$ ) I have this assignment about ...
38 views

### Recurrence relation general solutions [closed]

how would I go about tackling this kind of question? I'm struggling with the concept of recurrence relations. Any advice would be apreciated. Find the general solution of each of the following ...
31 views

### Where is the transistivity in this equivalence relation

The following set has been given: $A = \{1,2,3\}$, and the following relation on $A$ has been given: $S = \{(1,1),(2,1),(1,2),(2,2),(3,3)\}$. The answer says this is a valid equivalence relation. I ...
46 views

### Is the following relation a partial order?

Is the relation $R$ on $A=$ the set of all word of English, defined by $R=\{(x,y)\in A\times A:$ the first letter of the word $y$ occurs at least as late in the alphabet as the first letter of the ...
33 views

### Prove the relation $R = \{(x,y)\in \mathbb{R} \times \mathbb{R}: \text{ |x|< |y| or x=y} \}$ is antisymmetric.

Prove the relation $R = \{(x,y)\in \mathbb{R} \times \mathbb{R}: \text{ } |x|< |y|\text{ or$x=y$} \}$ is antisymmetric. Proof: Suppose $x R y$ and $yRx$. Then $|x|<|y|$ or $x=y$. ...
22 views

### Antisymmetric relation between two transitive relations

My task is the following: elements in set A: {a,b,c,d,e,f} relations between them: {(a,b),(b,f),(c,b),(c,d),(d,e),(e,a),(f,d),(f,e)} Question is, is the relation between them antisymmetric and ...
10 views

### Give an example showing Ran(R1 ∩ R2) ⊆ Ran(R1) ∩ Ran(R2) may not hold as an equality.

I have managed to prove Ran(R1 ∩ R2) ⊆ Ran(R1) ∩ Ran(R2), but I am having trouble finding an example that shows it doesn't hold as an equality.
24 views

### How many transitive and symetric relations that are not equivalence are in a set of $n$ elements?

I have a Set $S$, $|S|=n$, and I need to count how many symetric and transitive relations are in $S$ that are not equivalence relations. I know how to count equivalence relations (Bell number) but I ...
28 views

### Why is this relation $R=\{ (a,b), (b,c), (a,c) \}$ transitive? [closed]

I am confused here. For the set $\{ a, b, c\}$ how is the relation $\{(a, b), (b, c), (a, c)\}$ transitive ?
25 views

### Prove transitivity or not of some relation

I'm trying to prove if this equation is an equivalence relation or not. $R =\{(x,y) \in N\times N: \mbox{There exist }m,n \in N\mbox{ such that } x^m = y^n\}$ It's relatively easy to prove both ...
36 views

### What is the term for relation whose inversion is a function?

Do we have a conventional term/name for such a relation $R$ (which is not necessarily a function) that $R^{-1}$ is a function? If not, what are your suggestions?
18 views

### How do we show that $A$ is polynomial time reducible to itself? [duplicate]

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$? I know how to prove that it is transitive, but I don't know how to prove it's reflexive. I'm aware that it's ...
35 views

### Why is this function well definded?

I have to take a look at the relation of $x \sim y: \Leftrightarrow \exists k \in \mathbb{Z} : x-y=5k$ in $\mathbb{Z}$. I have no idea how to show at $\mathbb{Z} / \sim$ that the addition is well ...
36 views

### How to derive relationship between two functions

I have two functions: $f(x) = x^2 + 200$ $g(x) = (x + 8)^2$ I am interested in the relationship between the two functions in the region between the two minimums (from x = -8 to x = 0), which ...
23 views

36 views

### Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive.

I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for. Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive ...
39 views

29 views

### Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
35 views

### Equivalence Relations and Cardinality

I'm looking at the question below from a past paper: What is an equivalence relation? Say that two sets $X$ and $Y$ are related via the relation $\rho$ if $X$ and $Y$ have the same cardinality. Prove ...
35 views

Let $f$ be the function from $A = \{a, b, c, d\}$ to $B = \{e, f, g, h\}$ given by $f = \{(a,e), (b,f), (c,g), (d,g)\}$. If $D = \{a,b\}$, what is $f(D)$? If $G = \{f,g\}$, what is $f^{-1}(G)$? If $... 1answer 14 views ### Confirming my understanding in determining if a relation is reflexive, symmetric, or transitive I think I have a grasp on how to determine if a relation is reflexive, symmetric, or transitive. Just to make sure I understand it correctly, if I have the following relation: for$(a,b) \in \mathbb{...
Say I have a First Order Signature defined like so: $N = (\{1,2,3\dots\},T)$ Where T is a binary relation symbol. Can I use values from the domain to define functions over this signature? For ...