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
29 views

How to find inverse of a relation if the inverse isn't a function?

I am trying to find the inverse of the following function $f:\mathbb{Z}^+\rightarrow \mathbb{Z}$ given by $f(a)=\frac{(-1)^a(2a-1)+1}{4}$. I switched $x$ and $y$ and then tried solving for $y$. This ...
0
votes
2answers
46 views

define a relation $R$ on $S$?

Let S be the set of humans. 1) Define a relation $R$ on $S$ that is reflexive, symmetric, and transitive but not antisymmetric 2) Define a relation $R$ on $S$ that is symmetric and antisymmetric ...
0
votes
0answers
11 views

Clarification on a reflexive function

$R_1 = \{(a, b) | a ≤ b\}$ is a reflexive function, but I'm confused on why it is. $a≤b$ but doesn't that not necessarily mean that there is an $a$ that will equal $b$? Couldn't all of the $a$ very ...
1
vote
2answers
32 views

Confusion on sets and relations

I'm confused on how the number of subsets equals the number of relations. If set A = {1, 2} then AxA would be {}, {1}, {2}, {1,2}. I'm confused on how there are $2^{n^2}$ subsets of $A$ x $A$ because ...
0
votes
0answers
17 views

Understanding Fuzzy Composition operations

There are two common forms of composition operation in Fuzzy Theory: max–min composition max–product composition Let R be a relation that relates elements from ...
2
votes
1answer
30 views

For a given relation in $\mathbb{N}\times \mathbb{N}$ find the number of elements in it's equivalence class

The whole problem goes like this: We define the relation $R$ in $\mathbb{N}\times \mathbb{N}$ in the following way: $(a,b)R(c,d)$ iff $a-d=c-b$ First find proof the it's a relation of equivalence (...
0
votes
1answer
80 views

A relation that is both reflexive and irrefelexive

I didn't know that a relation could be both reflexive and irreflexive. However, now I do, I cannot think of an example. So what is an example of a relation on a set that is both reflexive and ...
0
votes
1answer
41 views

Why is $x \mid y$ over $\Bbb N$ a partial order but not total order?

I understand why $x \mid y$ is an example of a partial order relation over $\Bbb N$. But can someone explain why its not a total order relation? By definition a total order relation on a set $A$ is a ...
0
votes
1answer
33 views

Why is the Relation R3 Transitive?

Given $A = \{1,2,3,4\}$ in the Relation $\mathcal{R} = \{(1,1),(2,2),(3,3),(4,4)\}$ I understand why $\mathcal{R}$ is Reflexive, Symmetric but why is it also transitive? In my understanding for a ...
0
votes
1answer
26 views

Equivalence relations and composition, intersections of them

I've been having some trouble with this one, I hope someone get's it. Let S and R be equivalence relations within X. Prove that if R∘S is an equivalence relation, then it is equal to the ...
0
votes
0answers
21 views

Binary relations between any two sets

I have some doubts regarding relations and binary relations in particular.This is what I understand : 1) The graph $G_R$ of a relation R on X and Y is the subset of X × Y defined by $G_R$ = {(x, y) ∈...
0
votes
1answer
32 views

Deteremining whether the relation R on the set of all Real Numbers is Reflexive, Symmetric, Antisymmetric, Transitive, and/or Irreflexive

I am attempting to work out a problem from my Discreet Mathematics Textbook and am a little stuck on part of this one question. I was wondering if someone could walk me through (b) and (c) on the ...
1
vote
1answer
20 views

How many $(a,b)\in\Bbb Z^+\times\Bbb Z^+$ are there so that $(a,b)\mathrel{S}(n,n)$?

Let $n \in \mathbb Z^+ = \{1,2,3,\dots\}$. How many $(a,b) \in \mathbb Z^+ \times \mathbb Z^+$ are such that, $(a,b)S(n,n)$ where $$(a,b)S(c,d) \iff a + b ≤ c + d$$ In our case, $(a,b)S(n,n) \iff ...
0
votes
1answer
19 views

Is following Relation from $X$ to $Y$ is a Relation or not?

$$X=\{1,2,3,4,5\} \text{ and } Y=\{1,3,5,7,9\}$$ $$R=\{(x,y)\mid y=2+x,x\in X, y\in Y\}$$ my textbook says it is a relation from $X$ to $Y$. But for $x=2$, $y=4$ but $4$ is not in $Y$. How is that ...
1
vote
2answers
48 views

Definability of the $<$ order relation on the natural numbers using addition. [closed]

Show that the usual order relation $<$ on the natural numbers is definable in the structure $(\mathbb{N}, +)$ with only addition. My teacher has clarified this for me and quantifiers can be used. ...
0
votes
0answers
13 views

Determine the given relation is Equivalence Relation or not.

$R_{1} \oplus R_{2}$ I know that $R_{1} \oplus R_{2} = R_{1} \cup R_{2} - R_{1} \cap R_{2}$, and $R_{1} \cup R_{2}$ is not necessarily an equivalence relation but $R_{1} \cap R_{2}$ is always an ...
1
vote
1answer
20 views

Give an example that the following condition does not imply WARP

I know how to prove that Weak Axiom of Revealed Preference (WARP) implies the following condition: if $a\in B_1, B_1 \subseteq B_2, a\in C(B_2)$, then $a\in C(B_1)$. $C$ here is a notation for choice ...
0
votes
2answers
32 views

A property of reflexive transitive closure

Suppose $R$ is a binary relation on a set $S$. Let $R^+$ be the reflexive transitive closure of $R$. That is, $R^+$ is minimal relation which includes $R$ and is both transitive and reflexive. By ...
1
vote
1answer
141 views

Show that the set of powers of ten is countably infinite

My question asks: An $x \in \mathbb{N}$ is called a power of ten if there exists a $y \in \mathbb{N}$ such that $10^y = x$. Show that the set of powers of ten is countably infinite. I understand that ...
1
vote
1answer
21 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
47 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
21 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
89 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
35 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
40 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
10 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
36 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
25 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
16 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
50 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
28 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 Y={1} ...
0
votes
1answer
22 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
23 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
16 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
26 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
54 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
18 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
73 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
33 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
78 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
36 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
22 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,...