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
0answers
15 views

How to prove polynomial time reduction is reflexive? [on hold]

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.
1
vote
0answers
54 views

Is $X$ an equivalence relation? (Mendelson, $\sf NBG$..)

I follow the book of Mendelson "Introduction to Mathematical Logic" (capitel 4), a klasse $X$ is relation, $Rel(X)$, if $X\subseteq V^2$ (with $V=\{w|w=w\}$). I read in book the following definitions: ...
0
votes
0answers
10 views

Determine whether the following relation is reflexive, symmetric, antisymmetric and/or transitive?

Q is defined on P(N) by aQb iff |a ∩ b| ≥ 2. I've concluded that it's symmetric, not reflexive, not antisymmetric and not transitive. Is this right?
0
votes
1answer
15 views

Relation that is reflexive, transitive, but not antisymmetric

A = {1,2} R = {(1,2)} I was just wondering if this relation meets the criteria.
1
vote
1answer
29 views

Are R,S and T equivalence relation or partial order relation?

Let $R$, $S$ and $T$ be binary relations defined as follows R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∩B| ≥ 2$ $S$ is defined on $Q$ by $x\mathbin{S}y$ if and only if $|x|=|y|$. ...
0
votes
2answers
34 views

How to tell if the relations R, S and T are reflexive, symmetric, anti-symmetric or and transitive?

Let $R$, $S$ and $T$ be binary relations defined as follows R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∪B| ≥ 2$ $S$ is defined on $Q$ by $xSy$ if and only if |$x$|=|$y$|. (Note that ...
0
votes
0answers
13 views

Determine whether this relation is reflexive, symmetric, antisymmetric and/or transitive?

R is defined on N × N (where N are natural numbers) by (a, b)R(c, d) iff a ≤ c and b ≤ d. I think it's reflexive and transitive. Not too sure about it being symmetric or antisymmetric. Any help ...
0
votes
1answer
25 views

What is the difference between total order relations and well order relations?

I know it has to be a partial order relation in order for it to be a well order relation or total order relation, but what are the differences between them.
0
votes
1answer
16 views

What is the difference between partial order relations and equivalence relations?

From googling it i understood that a relation is both partial order relation and equivalence relation when they are reflexive, symmetric and transitive. So it appears they are the same. But as far I ...
1
vote
1answer
19 views

Write out relation from a function

I have this problem: "Let $R$ be a binary relation $(x,y)\in R$ if and only if $f(x) = f(y)$ where $f: \{a, b, c, d\} \rightarrow \{0, 1\}$ given by $f(a) = 0$, $f(b) = 1$, $f(c) = 0$, $f(d) = 0$ ...
2
votes
1answer
43 views

Functions: Relations

I'm stuck on this question and would appreciate the solution, thanks! Let $R$ and $S$ be the relations on $A = \{1,2,3,4,5\}$ given by$$R = ...
-1
votes
0answers
35 views

R is a binary function defined on P(N) by ARB if and only if |A∩B|≥ 2 [closed]

R is a binary function defined on P(N) by ARB if and only if |A∩B|≥ 2. state whether the relation is reflexive, symmetric, antisymmetric and transitive, and explain why in each case.If it is an ...
0
votes
2answers
25 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 ...
0
votes
2answers
32 views

Equivalence relation and equivalence classes given function and relation

Given a function $f : A → B$, let $R$ be the relation defined on $A$ by $aRa′$ whenever $f(a) = f(a′)$. Prove that $R$ is an equivalence relation and determine the equivalence classes. To prove that ...
0
votes
0answers
28 views

Which of the following are equivalence classes?

For example 37, I've determined which ones are equivalence relations but am having trouble on example 37: 1-7 determining which of the following are equivalence classes. I'm having trouble ...
1
vote
0answers
13 views

Symmetric and reflexive closure on positive integers

Finding the symmetric and reflexive closure of the relation $R = \{(a, b) | a > b\}$ on the set of positive integers. For symmetric closure I have: $R = \{(a, b) | a > b\} U \{(b, a) | a > ...
1
vote
2answers
23 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 ...
0
votes
0answers
29 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 ...
-4
votes
1answer
33 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)\}$. [closed]

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 ...
0
votes
1answer
11 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 ...
0
votes
1answer
18 views

Can you use constants from the domain in a First Order Formula? [closed]

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 ...
0
votes
0answers
19 views

Maximize function over a a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ let $\Gamma(S)=\left\{y\in S ,\not \exists x\in S \mid ...
0
votes
1answer
18 views

Finding equivalence classes in a set of functions with a condition

I can't seem to work around this problem... Let $n$ and $m$ be two positive integers. $F$ is the set of functions from {1,..,n} to {1,...,m}. We define the relation $R$ as: $f R g$ if and only if ...
0
votes
0answers
11 views

Determining if Poset based on Domain and Comparison Operator?

Can someone help me with how to think about the below problem? I know that a poset is a relation which is reflexive, antisymmetric, and transitive, but unless I'm dealing with finite sets I have a lot ...
0
votes
1answer
21 views

Let A, B, C be sets, with B ⊆ C. Prove that (A x B) ⊆ (A x C).

I understand why this is true but I need help answering it in a mathematical way, not just using common sense.
0
votes
1answer
13 views

Determine if given relation is an equivalence relation, and describe the partition?

Can someone walk me through how to do these types of problems in my Discreet Mathematics II Textbook? (ex.): Determine whether the given relation is an equivalence relation on the set. Describe the ...
1
vote
1answer
3 views

Finding pairs with respect to lexicographic order that meet a condition from a set?

I am working some problems out of my textbook for Discrete Mathematics II and was wondering if someone could tell me how to think through and go about solving the following type of problems (there are ...
1
vote
2answers
17 views

Question about the exclusive or operator

Let $R_1$ be the “less than” relation on the set of real numbers and let $R_2$ be the “greater than” relation on the set of real numbers, that is, $R_1 = \{(x, y) | x < y\}$ and $R_2 = \{(x, y) | x ...
0
votes
2answers
25 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
32 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
29 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
9 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
29 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
42 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
39 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
26 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
23 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
19 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
21 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
45 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
12 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
17 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
30 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
136 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
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
43 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 ...