Tag Info

New answers tagged

1

A relation is defined as a subset of the Cartesian product of some fixed number of sets. The word "necessary" in your question is thus irrelevant, as it could've also been defined in other ways. If, for example, the "relationship" you're referring to is a binary one (i.e. two elements can either be in a relationship together, or not), then defining a ...


0

I'm going to answer this on the presumption that it's sort of a (soft-question). Relations are defined to be a subset of the Cartesian product of two sets, which may not be distinct, because such a definition is simple and yet fully expressive. In other words, by defining relations that way, we can get everything else that you describe. For instance, if ...


2

Let $X=[0,1]\cap\Bbb Q$ with the usual order. Let $B=X$ and $A=\left[0,\sqrt2-1\right)\cap\Bbb Q$. Then $\sup B=1$, but $A$ has no supremum in $X$, because $\sqrt2-1$ is irrational.


1

It's easiest to show this component-wise. Using infix notation to avoid parentheses, I argue for symmetry. If $(x,y)R'(w,v)$ then it implies $xRw$, which by symmetry of $R$ implies $wRx$; likewise the definition of $R'$ implies that $ySv$, which in turn implies $vSy$. Therefore $((w,v),(x,y))$ is a pair that satisfies the conditions of $R'$. Reflexivity and ...


0

Edit: Im sorry, i thought you defined the relation with the set you wrote. I am now looking into it further (with your full definition of $R$). Edit 2: Well, What i wrote still holds for the arithmetic definition of your relation $R$. Try show transitivty with the definition of $R$ and the axioms of The field $\mathbb R$ . (Hint: $(x,y) \in R $ iff $ x=y$) ...


0

See more: https://en.wikipedia.org/wiki/Function_(mathematics) A function is defined by an input-output relation; there must exist an ordered pair for $(x,y) \in X \times Y$. Moreover, your relation is not a function because of the $+/-$ sign in front of $\sqrt{x}$; assuming one substitutes a certain value of $x$ one can get two different values for $y$.


1

I would start by writing out what it means for 3 to divide a number, that is, $3 | n$ if and only if $\exists k$ s.t. $n = 3k$. When does $3 | (x - y)$ is the next question we should ask ourselves. As suggested in one of the comments on your post, often this is where it helps to come up with some examples, for instance, does $1R5$? does $5R8$ ? does $8R5$ ? ...


1

A relation, say $R_1$ or $R_2$, is symmetric if for any ordered pair $(x,y)$ in that relation, then (what?). Take any point $(x,y)$ in $R_1\cap R_2$.   When given that $R_1, R_2$ are symmetric, can you show that (what?)?


0

The idea here is that when you divide an integer by another, via the euclidean algorithm, there's a unique remainder. So, dividing by 3 gives us a unique remainder that is 0, 1, or 2. The equivalence relationship here is that two numbers have the same remainder. Here's the reason: $x=3q_1+r_1$, $y=3q_2+r_2$, where $q_1,q_2$ are the quotients and $r_1, ...


0

$$\begin{array}{ccc} 3k&3k+1&3k+2\\ 0&1&2\\ 3&4&5\\ 6&7&8\\ 9&10&11\\ 12&13&14\\ 15&16&17 \end{array}$$ Got the idea? The columns are the equivalence classes.


2

You can solve the problem directly without making use of the hint. Just 'define' relation $T$ on $A/S$ by stating: $$[x]T[y]\text{ if and only if }xRy$$ It must be checked now wether this relation is well-defined and at that point the compatibility of $R$ with $S$ comes in. Based on it we find that there is no dependence on the representatives $x$ and $y$, ...


3

Hint: symmetric relations on $\Bbb N$ are in bijection with subsets of $\{(a,b)\in\Bbb N^2:a\le b\}$. Alt route: any subset of $\{(c,c)\in\Bbb N^2:c\in\Bbb N\}$ is a symmetric relation.


0

Okay, I know that what follows basically repeats what responders have been trying to tell me, but hitherto, I was still misunderstanding the notation of $\le$. Thus, I merely post this answer as an expression of my understanding (finally!). I refer to the definiton: Let $(A,\le)$ be a partially ordered set and let $B$ be a subset of $A$. To say ...


2

You don't care anymore about 4 elements, so only 6 remaining. That's why the cardinality of your quotient should be $$2^6=64.$$ If you want to prove it formally show that $\overline{A}\mapsto A\setminus P$ is a bijection between the quotient $Q$ and $P(X\setminus P)$. Hence we have $$|Q|=|P(X\setminus P)|=2^{|X\setminus P|}=2^6=64.$$


2

No, because $4 \not \leq 6$ by the relation we are using, which is divisibility. $4$ does not divide into $6$ evenly. The $\inf$ of $4$ and $6$ is the largest number which divides them both, the $\gcd$, which is $2$


1

The notation of $\leq$ is often used in mathematics as a general partial order. Not just the usual ordering on the natural/integers/rationals/reals. But in this context, $\leq$ is really just $\subseteq$. So you are being asked to find the maximum and minimum elements of $(\mathcal P(C),\subseteq)$.


0

In your case, the least element is an element of $A$, hence a subset of $C$ that is contained in all subsets of $C$. (Apply your definition in the second highlighted paragraph with $A=\mathcal{P}(C)$ and $B=A$), and so this set, I guess, is the empty set. Now, for the greatest element of $A$, what is the subset of $A$ that contains any subset of $A$?


3

A relation $R$ is transitive if any time we have pairs of the form $(a,b)$ and $(b,c)$ in $R$, it must also be the case that $(b,c) \in R$. As you have observed, $(1,2) \in S$ and $(2,3) \in S$, so these are two pairs of the form $(a,b)$ and $(b,c)$, but $(1,3) \notin S$, which is required by transitivity. So by definition, the relation is not transitive. ...


1

Okay, first of all let me say something about the relationship between graphs and relations. You have given the graph $$0 \rightarrow 1 \rightarrow 2 \leftarrow 3,$$ and a graph is not a relation, and your question seems to show some confusion about this relationship. We can interpret a graph as a relation (and conversely, when given a relation, we can ...


0

The only difference between a partial order and a total order is that in a total order any two elements can be compared. But if every set of two elements has a maximum, by definition of maximum it means those two elements can be compared.


0

HINT: Turn your argument around. Suppose that $A$ is not totally ordered. Then there are $x_1,x_2\in A$ such that $x_1\not\le x_2$ and $x_2\not\le x_1$. What can you say about the set $\{x_1,x_2\}$?


1

The usual ordering on $\Bbb{R}$ can be uniquely defined as the total order $\lt$ on $\Bbb{R}$ that satisfies the following two properties: (Let $a,b,c \in \Bbb{R}$) 1) $c \gt 0 \iff c$ is positive. 2) $a \lt b, \ \ 0 \lt c \implies ac \lt bc$ Proof that this defines uniquely $\lt$: Suppose that $\lt'$ also satisfies these properties and is a total ...


2

There are several reasons why, in computer science, it is common look at order relations that are only pre-orders. These may be called "total orders" in the jargon of the field. Similarly, in the context of mathematical logic it is not too rare to see someone call a reflexive, transitive relation a "partial order", even though partial are often required to ...


0

It's certainly 2. - the authors didn't get the definition right. You could say that it's a total order on the quotient {Argument}/{(x,y) | c.compare(x,y) == 0}. Also note that this is the quotient and not {(x,y) | c.compare(x,y) == 0}. The latter is an equivalence relation. Good catch!


0

Sadly, the documentation is as confused as you think it is. There's even more wrong than you've described, since the quotient is not, as they say, the equivalence relation that turns the preorder into an order, but the set of its equivalence classes (on which the order is defined).


1

The "usual order relation" is a creation of laziness. It's the order relation that your intuition comes up with first when you have to define an order relation on the space it's attached to. So for $\Bbb R$, it's the ordering of numbers, for $\{1,2\}$ it's the only "sensible" ordering "up to renaming of the elements" (i.e., $1 < 2$). I hope that clears ...


2

Hint: If you investigate the questions like: "is $R$ and equivalence relation on set $A$?" then often (even stronger: almost always) it is very handsome to look for a function that has $A$ as domain and satisfies $$aRb\iff f(a)=f(b)\tag1$$ If you have found such a function then you are allowed to conclude: $R$ is an equivalence relation on $A$. The ...


0

Well, the equivalence class of $n$ (say the largest digit of $n$ is $k$) would be the positive integers whose largest digit is $k$. Now $k$ can be any number from 1 to 9 (you must omit 0 because a positive integer must have a positive digit). So for Question 3, you just need to find the number of integers between 100 and 1000 whose largest digit is 7.


1

You should look again at what "reflexive" means. It is stated as: $$\forall a\in A [a\leq a].$$ Notice that we are only choosing one object - so you've gone wrong if you've already taken two objects $a$ and $b$. In doing it with one object, you won't need to take $a=b$ for granted, you'll just need to take $a=a$ (which is clearly okay to do). Also, it ...


2

You know that $<$ is transitive and antisymmetric. Now you define the reflexive extension of $<$ to be $\le$ with $a\le b$ iff $a<b$ or $a=b$. You need to prove that $\forall a\in A: a\le a$ (reflexivity), and this is obvious since $a=a$ (and therefore $a\le a$ by definition of $\le$). As for inequality, it is symmetric. You can show that the ...


0

It's an error in the text; your count of antisymmetric relations is correct. You counted one trichotomous relation too many; $\{(a,a),(b,b)\}$ isn't trichotomous. There are $2^{n(n-1)/2}$ trichotomous relations, since we must have exactly one of $(x,y)$ for all $x\ne y$, and we mustn't have $(x,x)$ for any $x$.


1

1) In all parts of the definition of the relation $m$ O $n$, the integers $m$ and $n$ could possibly be the same - there's nothing ruling it out. 2) and 3) If the relation is the empty relation, then it is indeed symmetric and transitive! This is related to the fact that an implication "if $p$ then $q$" is indeed true if $p$ is always false - we call such ...


0

Hint: $I_A\,R\,f$ means that there is some $i\in A$ with $i = I_A(i) \le f(i)$. So the functions $f$ such that $I_A\,R\,f$ is false are those functions $f\in F$ such that $i>f(i)$ for all $i\in A$. How many such functions are there?


0

Note that if $X\Delta Y\subseteq B,$ then both $X\setminus Y$ and $Y\setminus X$ must be subsets of $B.$ If $Y$ is disjoint from $B,$ it follows that $Y\setminus X=\emptyset,$ which happens if and only if $Y\subseteq X.$ Hence, we need a subset $Y$ of $X$ such that $X\setminus Y\subseteq B$ and $Y\cap B=\emptyset.$ Can you take it from there? (Try playing ...


1

First try proving the statement for $X \in \mathcal{P}(B)$, where there's a fairly obvious candidate for $Y$. Then see if you can generalize.


0

HINTS: $I_A(1)=1$, and $1\le a$ for all $a\in A$, so $I_A\mathrel{\mathcal{R}}f$ for all $f\in\mathcal{F}$. $I_A(n)=n\ge a$ for all $a\in A$, so ... ? If $f$ is onto, then $f$ is actually a bijection. How many bijections are there in $\mathcal{F}$?


2

A relation-as-part-of-formal-language isn't the same thing as a relation-as-type-of-set. In the former case it's a piece of syntax--e.g. the symbol '$\in$' along with the information that it takes two term symbols to make a formula out if it. In the latter case it is a subset of the Cartesian product. Note that you can sniff out that these are distinct ...


2

$\subseteq$ relation can be written with $\in $ relation as $$A \subseteq B \text{ is defined by } \forall x (x \in A \Rightarrow x \in B)$$


4

I will assume that by $<$ you mean the "less than" relation on some totally ordered set such as the real numbers. Is there ever a situation where you have $x<y$ AND $y<x$ at the same time? No. The statement then is an example of a Vacuous Truth since the premise is always false, there is no possible way that there is a contradiction. A statement ...


2

$R\subseteq A\times A$, and $S\subseteq B\times B$, so $$R\cup S\subseteq (A\times A)\cup(B\times B)\subseteq(A\cup B)\times(A\cup B)\;;$$ $R\cup S$ is a relation on $A\cup B$.


0

A relation R on a set X(ie,R is a subset of X cross X) is said to be reflexive if xRx for all x belongs to X. Here,X={1,2,3},also given that,{(1,2),(2,2,),(3,3)} belongs to R, which means it is reflexive. A relation is said to be symmetric if xRy implies yRx,where x,y belongs to X. In the question it is given that,(1,2) belongs to R but (2,1) not belongs to ...


3

Solution for part 1 Every edge in the Hasse diagram goes from a set $S$ to a set $S \cup \{x\}$ with exactly one more element. So we can count how many edges come from each set. A subset $S \subseteq \{1, 2, 3, \ldots, n\}$ of size $k$ is the initial point of exactly $(n-k)$ edges, because there are $n-k$ possible elements $x$ to add to get $S \cup \{x\}$. ...


0

Let xMy mean that x owes money to y or that y owes money to x.Let xPy mean that x and y have at least one parent in common.


0

Q1: Indeed, you're correct. Since for all $a$ elements in your set $S$, $(a, a) \in $ your relation $R$. Q2: If you're trying to ask if you can state that it's not symmetric due to some pair not being in $R$, then indeed you can, as long as you prove why. In this particular case, $R$ is clearly not symmetric because $(1,2) \in R$ but $(2,1) \notin R$. What ...


2

Hint: Here is a directed graph representing the relation $\mathcal{R}$ with a directed edge from $x$ to $y$ iff $x\mathcal{R}y$. Is it currently transitive? What is the necessary edge(s) you need to make it transitive? Is there a natural way to partition these elements so that in the image they are "grouped" how the edges appear?


1

As you correctly point out, your problem comes from not understanding variables properly. It is invalid to use $x,y$ without stating what it is. Given any asymmetric relation $R$ on a collection $S$:   For any $x,y \in S$:     $(x,y) \in R \rightarrow (y,x) \notin R$.   For any $x \in S$:     $(x,x) \in R \rightarrow (x,x) ...


1

To expand on the others answers. This is your property : $$\forall (x,y)\in E^2, ( (x,y)\in R \Rightarrow (y,x) \not\in R )$$ So this imply that $$\forall t, ( (t,t)\in R \Rightarrow (t,t) \not\in R )$$ But you have that $$\forall t \in E, ( (t,t) \not\in R \vee (t,t)\in R) $$ Hence $$\forall t \in E, ( (t,t) \not\in R \vee ( (t,t) \in R \Rightarrow ...


1

When you say "For all x and for all y..." you are NOT assuming that x and y are not names for the same thing.


1

x and y are arbitrary variables. Just because they are denoted by different letters does not mean that they must have different values.



Top 50 recent answers are included