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
2answers
15 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
25 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
67 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
53 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
38 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: [7]=[4]...
0
votes
2answers
65 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
30 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 e.g....
0
votes
0answers
35 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, 1)(1,2)(1,2)(2,4)(4,1)(4,4)(2,2)...
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
19 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 F((f_1,...
0
votes
1answer
98 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
42 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
32 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
26 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
102 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
31 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
479 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 = 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
51 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
69 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 ...
1
vote
1answer
37 views

What are ordered tuples?

I've been asked to explain the concepts of relations and I'm unable to find what Ordered Tuples are on the internet. Could the answer please be given in the most basic form as I'm not brilliant at ...
-5
votes
1answer
51 views

Graphing Relations and Their Properties [closed]

I am working on a homework assignment for a discrete math course and am completely lost on relations. I'll put up some examples of problems, could somebody please push me in the right direction or ...
1
vote
1answer
17 views

Relation and proving reflexivity

The relation R is defined on integers by $xRy$ if and only if $x^2y=ymod6$. Prove that $R$ is reflexive. So far I have: Let $x=y$ $x^2x=xmod6$ I don't know how to go from here... because $x^2=...
0
votes
1answer
30 views

Relations and equivalence classes example

I'm studying discrete mathematics in my course at university and I'm going through notes on relations, equivalence relations and classes and such. I've come across an example on equivalence classes ...
0
votes
1answer
26 views

Initial condition for recurrence relation

I have a question regarding the solution of this problem. The problem is: Suppose that we have n dollars to use to buy either orange juice for 1, milk for 2, or beer for 2, and the order in which we ...
1
vote
1answer
28 views

How can an antisymmetric relation be not reflexive? [duplicate]

Reading a book (I do not know if I can mention its title) I found these definition (the following is exactly the quotation from the pages of the book): "For a binary relation R on a set Y, that is, R⊆...
0
votes
1answer
57 views

Equivalence Relations on Products

Let $G$ be a group, $p$ a prime dividing $|G|$ and $X = \{(x_0,..., x_{p−1})) ∈ G_p:∏_i x_i = 1\}.$ Let $E$ be the relation defined on $X$ by $(x_0, ..., x_{p−1})E(y_0,..., y_{p−1})$ if there exists $...
1
vote
2answers
52 views

Which of the following are partitions of $\mathbb R^2$

Is my answer correct? Can someone provide me better explanations for (a) ,(c) and (d)? Which of the following collections of subsets of the plane $\Bbb R\times\Bbb R$ are partitions? $(a)$ $\...
1
vote
1answer
20 views

How do find if a relation is a function algebraically

Is there a way to see if a relation is a function without having to do a "vertical line test" (where you draw a vertical line on the graph and if there line touches two points then it's not a function)...
0
votes
0answers
74 views

Prove that any relation that is a partial order / equivalence is identity relation

Prove that any relation that is both an equivalence relation and a partial ordering is the identity relation. That is, if X is a set and R is a relation on X that is both a partial ordering and an ...
0
votes
0answers
54 views

Relation on a set of relations with these limitsprove equivalence / partial order

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R=\{(\mathscr P,\mathscr Q)\mid \mathscr ...
1
vote
0answers
59 views

Is this relation $\mathscr R$ on the set of relations, reflexive?

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R = \{(\mathscr P, \mathscr Q) \mid \...
0
votes
1answer
218 views

Bijection preserves equivalence relation

Suppose f is a bijection between two sets A and B. Then x, y ∈ A gives us f(x), f(y) ∈ B. Prove that bijections preserve equivalence relations. That is, if R is an equivalence relation on A, then R' ...
2
votes
2answers
37 views

Show given relation $R$ is equivalence relation on $S$

I will display the exact problem, then my questions. I have searched to the extremes to figure this out and can't: Show that the given relation $R$ is an equivalence relation on set $S$. $S$ is the ...
0
votes
0answers
19 views

Relation and Cartesian Product

Let $A=\{-1,2,5,8\}$, $B=\{0,1,3,6,7\}$ and $R$ be the relation is one less than form $A$ to $B$. Then, 1) Find $R$ as a set of ordered pairs 2) Find domain and range of $R$. 3) Find $R^{-1}$ as a ...
1
vote
1answer
34 views

The maximum possible size of $R$ is_____?

A function $f : N^+ → N^+$, defined on the set of positive integers $N^+$, satisfies the following properties: $f(n) = f(n/2)$ if $n$ is even $f(n) = f(n+5)$ if $n$ is odd Let $R = \{i|∃ j : f(j) = ...
0
votes
1answer
52 views

How can I find the maximum/minimum and maximal/minimal elements of a poset?

My teacher has given us really unclear definitions for all these terms, and now I have this assignment due where I have to find the maximum, minimum, and maximal/minimal elements of this poset: $$A=\{...