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

1
vote
1answer
19 views

Rewrite “x > a” in Iverson brackets as Heaviside function

Let's say I have a Heaviside function defined like this: $$ H(x) = \begin{cases} 0, \text{ if } x < 0\\ 1, \text{ if } x \geq 0 \end{cases} $$ Then I have a so called Iverson brackets: $$ ...
1
vote
0answers
44 views

LEN-Model equivalency

Starting position is a principal-agent-model with incomplete information (moral hazard) and the following properties: Agent utility: $u(z)=-e^{(-r_az)}$ Principal utility: $B(z)=-e^{(-r_pz)}$ Effort ...
0
votes
1answer
27 views

Prove that if $(a, b) \in \rho$ then $[a]_{\rho} = [b]_{\rho}$

Given an equivalence relation $\rho$ over the set $A$. Prove that if $(a, b) \in \rho$ then $[a]_{\rho} = [b]_{\rho}$. Also prove that if $(a, b) \notin \rho$ then $[a]_{\rho} \cap [b]_{\rho} = ...
1
vote
0answers
16 views

equivalence class of kernel relation of floor function

By taking particular values of $k$, I found that equivalence class of $k$, $[k]=\{k,k+1,k+2,...,2k-1\}$, equivalence class of $2k$, $[2k]=\{2k,2k+1,2k+2,...,3k-1\}$ and so on, but how to present it ...
1
vote
1answer
33 views

Suppose that R and S are reflexive relations on a set A. Prove or disprove each of these statements.

I am doing this question with my own attempt. Can anyone help me with the formal way of proving? Thanks! Suppose that $R$ and $S$ are reflexive relations on a set $A$. Prove or disprove each of ...
0
votes
1answer
13 views

Determine whether each of these combinations of R 1 and R 2 must be an equivalence relation.

I have this question but not really sure how to do it when there is union and interception symbol. I am easily confuse when this 2 symbol appear. From my understanding I know that equivalence relation ...
1
vote
0answers
33 views

Let $R_1$ and $R_2$ be the “congruent modulo 3” and the “congruent modulo 4” relations, respectively. Find $R_1\cap R_2$ and $R_1 \cup R_2$.

I have this question and would need help on how to find $R_1 \cup R_2$. My working for $R_1 \cap R_2$ is shown below: Let $R_1$ and $R_2$ be the “congruent modulo 3” and the “congruent modulo 4” ...
-1
votes
1answer
30 views

Determine whether the relation is reflexive, symmetric, anti-symmetric, and/or transitive?

Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) ∈ R if and only if a) everyone who has visited Web page a has also ...
0
votes
1answer
28 views

What are the values of the sum?

what are the values of $\sum_{j \in S} 1$, where S = {1, 3, 5, 7}. if we have $\sum_{j = 1}^{n} 1$ then the answer will be n. But what happens if this a set?
1
vote
0answers
9 views

Number of symmetric relations

Let set $A=\{1,2,3\}$ Find number of symmetric relations that can be defined on $A$ containing ordered pairs $(1,2)$ and $(2,1)$ is? Can someone give me some hint for this question?
1
vote
0answers
32 views

How Galois connections between powersets correspond to binary relations?

How to show the well-known bijective correspondence between Galois connections (or rather polarities) between two powersets on some (fixed) sets with binary relations between these sets? You can also ...
0
votes
1answer
22 views

Can a tuple be defined as an instance of a relationship?

SO let's say x and y are in relation. Is (x,y) a tuple and an instance of a relation ? Is a n-tuple an instance of a n-relation?
0
votes
1answer
13 views

What is a minimal relation?

I was reading this definition of transitive closure of a relation, where is written that the transitive closure is minimal: the transitive closure of a binary relation R on a set X is the ...
2
votes
1answer
45 views

A book or Source to further study Relations

I have completed a course on Discrete Mathematics and really enjoyed studying the chapter on relations. In fact I went back and finished what we hadn't covered in class. I did basic stuff like n-ary ...
1
vote
2answers
24 views

Having problem with finding the number of ordered pairs.

Y and Z are proper subset of X this means that X is having all the elements of Y and Z and also Y$\ne$X and Z$\ne$X (This is because we are talking about proper subset and not just subset). Let ...
0
votes
1answer
21 views

Listing the elements of an equivalence class

Say you have x = {1,2,3,4,5}, y ={2,5}, and c = {2,3} and the relation R: ARB iff AUY = BUY ...
0
votes
0answers
17 views

Hasse Diagrams and partially ordered sets

3) Define U = {1, 2, 3, 4, 5}. Consider the following subsets of U: P = {2, 3, 5}, O = {1, 3, 5}, E = {2, 4}, S = {3} a) Create the Hasse diagram using $\subseteq $ as the partial order on sets E, ...
0
votes
2answers
12 views

Partial Order Relations with irreflexive definitions

Define a relation R on the set of real numbers by (x,y) R if and only if x - y = 0. Determine if the relation R is a partial order. If it is not a partial order, explain which property or properties ...
0
votes
0answers
22 views

Monotone Galois connections arising from binary relations

Please help to describe monotone Galois connection corresponding to the antitone "Connections on power sets arising from binary relations" described in this Wikipedia article. Also "Every Galois ...
0
votes
2answers
65 views

How many injective functions $f: A \to B$ satisfy $f(a_1) = b_1$ or $f(a_2)=b_2$?

I've been stuck on this question for hours, and am having trouble trying to start this question. If anyone could help, that would much appreciated. The question is Let $A = \{a_1, a_2, a_3, a_4\}$ ...
0
votes
2answers
51 views

Proving an equivalence relation on a $\mathbb Z\times \mathbb Z$

I am having some trouble understanding how to prove that a given binary relation is an equivalence relation. I understand that to prove that a relation is an equivalence relation, you must prove ...
0
votes
1answer
17 views

Linearly extend an induced subposet

Suppose $P$ is a finite poset with partial order $\le_P$ and $Q$ an induced subposet, its partial order being ${\le_Q} = {\le_P}\cap Q^2$. Suppose we linearly extend $\le_Q$ to a linear order ...
1
vote
1answer
34 views

Which of the following equivalence classes are equal?

Let R be the relation of congruence modulo 3. Which of the following equivalence classes are equal. [7], [-4], [-6], [17], [4], [27], [19] The answer is: ...
0
votes
2answers
54 views

Show that R is an equivalence relation and determine all distinct classes

Let R be a relation on Z define as follows: m R n <--> 3|($m^2$-$n^2$) show that R is an equivalence relation and determine all distinct equivalence classes. EDIT: I looked several places and ...
1
vote
2answers
23 views

Why is $R=\{(1,6),\,(2,7),\,(3,8)\}$ a transitive relation?

Can someone please clear me transitive relations. books too have confused some say this is not as there are no pair to look for transitivity .While the true answer is it is but i couldn't understand ...
2
votes
4answers
155 views

How do you show one way equivalences in mathematics?

In the real world, it seems you can often take a set of things and create new things with them. Let's say you want to make bread, for example. Normally, you can create bread by putting together flour, ...
1
vote
2answers
77 views

Why are the real numbers usually ordered the way they are?

How do we get the usually used form of $<$ (i.e. $\dots-3<-2<-1<0<1<2<3\dots$) on the real number field, defined as the Dedekind complete totally ordered field? Why isn't it ...
0
votes
0answers
34 views

Why are “is equal to” and “total strict ordering” mutually exclusive?

Let $A$ be a set. Let $=$ be the relation "is equal to" on $A{\times}A$, and let $<$ be a strict total ordering on $A{\times}A$. How do we prove that if $a<b$, then it's not true that $a=b$?
0
votes
2answers
21 views

Defining relations $R$ and $S$ on $A \times B$?

I've been trying to figure out a way to do this problem: Let $A = \{-1, 1, 2, 4\}$ and $B = \{1, 2\}$ and define relations $R$ and $S$ on $A \times B$ as $$R = \{(-1, ...
0
votes
1answer
25 views

Prove equivalence relationship

How would I go about doing this? I assume proving it's reflexive, symmetrical and transitive Show that the relation $R = \{(x, y):3x − 5y \text{ is even }\}$ is an equivalence relationship.
0
votes
0answers
14 views

Composing relation with identity yields original relation

Let $\phi: F\rightarrow G$ be a relation and $id_F$ be the identity relation on $F$. Then $\phi\circ id_F = \phi$ . Attempted proof: $$\phi\ \circ id_F = \{(f,g)\in F\times G: \exists f_2\in ...
0
votes
1answer
93 views

Define a relation for “is contained in”

Here is my question (should help with my understanding of this new topic): Consider two words $x, y $ and say that the word $x$ is contained in the word $y$ if it only uses characters from $y$. Only ...
0
votes
1answer
30 views

Equivalence Classes of an Equivalence Relation Confusion (definition and solution included)

The Definition of Equivalence Classes of an Equivalence Relation is given as: Suppose $A$ is a set and $R$ is an equivalence relation on $A$. For each element $a$ in $A$, the equivalence class of a, ...
1
vote
2answers
39 views

An example of a relation that is symmetric and antisymmetric, but not reflexive.

I am really stuck on if there is such an equation. The set given was A={1,2,3,4}. Is it even possible for a relation to be symmetric and antisymmetric, but not reflexive?
1
vote
2answers
31 views

Relation is a function from domain to power set of range

Let $E$ and $F$ be sets. Then $\tau$ can be considered a function from $E$ to $P(F)$ by setting, for each $x \in E$, $\tau(x) = \{y \in F: (x, y) \in \tau\}$ . This is a claim from a text, but it ...
21
votes
7answers
2k views

Proof that the empty set is a relation

In the book Naive Set Theory, Halmos mentions that the "The least exciting relation is the empty one." and proves that the empty set is a set of ordered pairs because there is no element of the empty ...
1
vote
0answers
20 views

Ensure exact partitioning when performing masked equality comparison

This question arose from an informatics problem, but I do believe Math SE is the right stack to ask because I am not asking for a algorithm in a specific language but for properties to check using ...
0
votes
1answer
25 views

Proving Equivalence Relations by providing an example based on given subsets.

Let $X$ be the set of all nonempty subsets of $\{1, 2, 3\}$. Then $X= \{\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$ Define a relation $ R $ on $X$ as follows: For all $A$ and ...
4
votes
1answer
88 views

A possible alternative to the Axioms of Pair, Union, Infinity and Replacement

In this question we assume that all formulae are in the language of $\sf ZFC$ and that $\sf ZFC$ is consistent. Recall that we say that a formula $\varphi(x,y)$ represents a set-like class relation ...
0
votes
1answer
17 views

Proving the Binary Relation is an Equivalence Relation

Let $R$ be a binary relation on a set A and suppose R is symmetric and transitive. Prove the following: If for every $x$ in $A$ there is a $y$ in $A$ such that $x R y$, then $R$ is an equivalence ...
0
votes
0answers
14 views

Prove that $L = \{((a,b), (a',b')) ∈ (A × B) × (A × B) \mid aRa', \text{and if } a = a' \text{ then } bSb'\}$ is a partial order.

I am working on a problem from Velleman's book "How to Prove it." If you are able to show the work with the "Givens" and "Goals" style like the book shows, that would be much appreciated, if not, ...
0
votes
1answer
14 views

Elements of a relation

So I proved this was a relation, but I'm having real trouble identifying the elements of the relation. I'm not quite sure what I am supposed to do. Are the elements of the relation [(0,3)] all of the ...
1
vote
2answers
38 views

Properties of given binary relation?

A binary relation R on $N×N$ is defined as follows$: (a,b)R(c,d)$ if $a≤c$ or $b≤d$. Consider the following propositions: $P: R$ is reflexive $Q: R$ is transitive Which one of the following ...
4
votes
3answers
476 views

Why is one relation transitive but the other is not?

From what I have read about a transitive relation is that if xRy and yRz are both true then xRz has to be true. I'm doing some practice problems and I'm a little confused with identifying a ...
1
vote
1answer
63 views

If $R$ is an equivalence relation, is $R = R^3$?

If $R$ is an equivalence relation, does $R = R^3$ ? I tried for about 40minutes to construct a relation $R$ that is an equivalence relation that when multiplied with itself twice, it will make $R = ...
1
vote
1answer
31 views

If $R$ is an equivalence relation, does $R^2$ too?

I think that yes, $I_A \subseteq R$ $R = R^{-1}$ $R^2 \subseteq R$ And now we can show. Reflex: $I_A = I_A^2 \subseteq R \subseteq R^2$ A lil bit struggling with symm. And trans. ...
2
votes
3answers
61 views

How many relations can you form that are Range = $B$, $A=\{1,2,..,n\}$,$B =\{1,2,..,m\}$

How many relations can you form the are Range = $B$, $A=\{1,2,..,n\}$,$B =\{1,2,..,m\}$, and $m \ge n$ From my understanding, ALL THE elements in $B$ must be in the right spot of the relation. for ...
1
vote
1answer
39 views

Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Prove that $R \cap (B \times B)$ a partial order on $B$.

Can somebody show me how to prove this? I would much appreciate it if one could show the givens and goals similar to how it is set out in Velleman's 'how to prove it' book, though any help would be ...
0
votes
1answer
62 views

Questions on equivalence relation and functions

I just found this question in my discrete math homework and just can't have the solution by looking through the textbook. The question contains two parts: a) If $R$ is an equivalence relation on ...
0
votes
0answers
15 views

Find the division set ($A / R$)and index of set $A = \{\phi : 0 \le \phi \lt 2\pi\}$

Find the division set and index of set $A = \{\phi : 0 \le \phi \lt 2\pi\}$ The relation is $\phi_1 R \phi_2 \leftrightarrow sin\phi_1 sin\phi_2 \ge 0$ and $cos\phi_1 cos\phi_2 \ge 0$ So first, I ...