discrete-math

[stray reef]

what is your textbook's definition of a walk

[next valley]

No repeated edges

[nova star]

@next valley a path?

[next valley]

Oh wait the question wants walk

Sry

[nova star]

i guess textbook is wrong? @next valley

[next valley]

Idk

[nova star]

so is there an algorithm to find max possible walks/paths/trails from one point to another?

of size n?

or just trial and error?

cuz im wondering if they ll ask such a proof in exam

[dense thicket]

DFS I guess

[nova star]

wdym @dense thicket

btw is the information on this site incorrect? https://www.slader.com/discussion/question/find-the-number-of-paths-of-length-n-between-two-different-vertices-in-k4-if-n-is-a-2-b-3-c-4-d-5/

[nova star]

i tried this on a K4 graph, doesnt seem to work

[naive saffron]

Why?

@nova star

Can you show your work xD

[trim oak]

Is anyone familiar with the n-queens problem? I'm going through "Discrete Math and its Applications", and there is one part that is confusing the hell out of me.
p(i, j) is true when there is a queen on ROW i, and COLUMN j

Then the book says...

Are there errors in there?

"It must be the case p(i, j) and p(k, j) are not both true" to check rows... but that checks columns, right?

You'd have to test p(i, j) and p(i, k) for rows

[faint narwhal]

You're correct

[trim oak]

Thanks @faint narwhal! I was so convinced I was wrong, been looking at it for like an hour and a half

[nova star]

i dont get that, but dont u just use BFS for that problem?

@naive saffron oh yea sorry nvm i figured it out, some other people i asked also only found 5 combos so i got confused, at the end i just generated all possibilities using computer program to check, and @faint narwhal helped me too, so i figured out its 7 and not 5

wondering if it works for weighted graphs too

[naive saffron]

The method works to find the number of paths between two nodes

It doesn’t matter if the graph is weighted or not

I’m not sure what you mean

@nova star

[nova star]

so if u have the matrix of weighted graph, would it work to find length nodes with length of n between them

so lets say 10

[naive saffron]

???

The matrix is the adjacency matrix

It encodes the number of edges between any given two modes

This method can’t tell you the length

[nova star]

yea ok

thats wut i was wondering

[naive saffron]

If you want to find the minimum length between two nodes in a weighted graph you have to use something else

[nova star]

no problem 😃

n

no

[naive saffron]

Like bellman ford

[nova star]

i mean like number of possibilities from one node to another of length 10

in a weighted complete graph

[naive saffron]

Oh

[nova star]

for minimum length ud use somethin like dijkstras right?

i see no reason for it not to work on weighted complete graphs tbh, but not 100% sure

[naive saffron]

Yeah

[nova star]

if its greater, its useless to continue, so kill this one

[torpid void]

I seem to be having issues with inductive reasoning, some of the problems were pretty straightforward

Im having trouble proving that for any n, that n>k, n = 7a + 2b, in which a and b can be any nonnegative integer

k is 5, that part is pretty simple, but I don't know how to prove it by induction

if n > 5 and odd it can be represented by 7 + 2b, and if n is even it can be represented by 2b, im not sure where to go from here

[nova star]

i dont even get the question

[torpid void]

prove by induction that you can make any number larger than k with a combination of 7's and 2's

[nova star]

hmmm

so digits 7s and 2s?

[weary tiger]

@nova star

[nova star]

?

[torpid void]

no 7's and 2's added together

[nova star]

oh ok

[spring temple]

Stop shitposting in random channels @weary tiger

[weary tiger]

Ok sir

I shall stop

[nova star]

lemme try, though i may not succeed

so wuts the base term?

i imagine 1? or 0

[torpid void]

base term is for k+1 in this case since n>k

and you have to find k

which in this case is 5

[nova star]

base term cannot be k+1?

i mean the first step

in induction

[oak creek]

so base case of 5

[torpid void]

base case would be 6

[nova star]

it works for base case of 0 as well

[oak creek]

okay so base case where n > k and k = 6?

[nova star]

id think base case is 6 though yea

n>6

cuz u couldnt get 5

[torpid void]

it works for n>5

[nova star]

yea

[oak creek]

well you could get >5

[nova star]

sry n>= 6

[oak creek]

would you mind showing the question exactly?

or is that not possible

[nova star]

so imma just start by bruteforcing some stuff i try to get a pattern

[oak creek]

i don't think that would be necessary, you would only need base case and weak induction

[torpid void]

you have an atm that only gives out two and seven dollar bills. Claim: the ATM machine can generate any output amount n>k. Find the minimum k that makes the claim correct. Then, prove the claim by induction

[nova star]

well we can already proove it to be true for all n is even

without even doing induction

[oak creek]

ah

[nova star]

so now we gotta proove for n is odd

[oak creek]

any value where n>k

[torpid void]

oh sorry yeah k = 6

i misread

[oak creek]

no, k would be 5

because it can generate values from 6 and onwards

[torpid void]

gotcha

[nova star]

ok sooo

hmmm

[torpid void]

im not sure how to do it by induction

[oak creek]

you wouldn't be using induction on k, from what i see

you would be using it on n

[nova star]

if u have 7 then(1) + 2(x) u can make all odd numbers between 7 to 14

[oak creek]

to show that you can generate values of 6, 7, etc

[nova star]

similarly if u have 7(2) + 2(x) u can make all odd numbers between 14-21

[torpid void]

If I could choose my proof, I would have done if n is odd prove, and if n is even prove

[nova star]

yea

if n is even then u jsut go 7(0)

if n is odd u need to show using induction

[oak creek]

wouldn't this be structural induction?

[nova star]

yea strong induction

im not very good at em, just started

[torpid void]

you are asking the wrong person, our textbook only went over mathematical induction

[oak creek]

no, strong and structural are not the same

[nova star]

so i might get nowhere, and if so, sorry for wasting ur time

[torpid void]

i mean as long as you are learning

[nova star]

if u take it to be true for k<n then its strong induction

idk if i prooved it, or if im super dumb? but if u take it to be true for k-1

k>n

then u can subtract both sides by 1

and substitute

7a+2b-1 = 7a+2b-1

it seems correct according to induction logic...

buttt

seems odd

[torpid void]

n = x substitute n for x

x = x

must be true

[nova star]

wut?

so heres wut i did, tell me if im dumb

n = 6 is true

assume true for k<n

proof for k = n

::

k = 7a+2b

k-1 = 7a+2b-1

substitute

7a+2b-1=7a+2b-1

hence prooved???

lol idk it seems dumb af, am i going wrong somewhere??

it seems right according to how inductions work..

@torpid void ??

[torpid void]

thats just adding 1 to both sides

[nova star]

yea but thats wut induction is usually supposed to do

u take hypothesis true for k<n or n = k-1

and proove for n = k

by substituting hypothesis

[torpid void]

the problem is I need to find a way to have k affect both sides

[nova star]

i dont think u need it too

to*

although im not 100% sure tbh

[torpid void]

you have to prove that k+1 = 7a +2b

not 7a+2b+1

[nova star]

ah ok

gimme a sec

hmm

so u end up getting 7a+2b+1 = 7a+2b?

[torpid void]

keep in mind a and b are not constants

[nova star]

yea

[torpid void]

they just mean there exists Z

[nova star]

hmm yea

ok i have an idea

u take any number

lets say m

can u get m+1

say m = 7a+2b = 22

how would u get m+1 = 23

by manipulating 7a and 2b

and u have to proove this via induction?

[torpid void]

this is what I have

        {n is even: a = n/2; b = 0;
for n > k :{ 
        {n is odd: b = 1; a = (n-7)/2

[nova star]

u dont even need to proove that

just assume true for n>k

and btw u shud use k instead of n in the equation u wroth

b=1??

[torpid void]

oh I have them backwards on here

b is 7b

a is 2a

[nova star]

wutt?

its still not = 1

[torpid void]

yeah it is

not necessarily

but it can be and it makes the math easier

all odd numbers greater than 5 can be represented by 7 + 2b

[nova star]

no?

they can?

[torpid void]

7 is b=0

9 is b = 1

[nova star]

ohh yea

nvm they can right

i mean ur proof is right if u aint using induction i guess

but yea so lets just try solving it for

7+2a

bruh theres somethin odd

k = 7+2a

[torpid void]

n > k

[nova star]

yea

(k-7)/2 = a

now for k+1

k+1 = 7+2(k-7/2)

k+1 = k

lol

[torpid void]

a = 2k+7

[nova star]

a = 2k+7?

[torpid void]

2a = k-7

[nova star]

yea

[torpid void]

2a + 7 = k

[nova star]

a = k-7/2

[torpid void]

i mistyped

[nova star]

ok

but if u substitute

into the k+1

ull get k +1 = k..

[torpid void]

because a and b arent constants

[nova star]

yea

i get it

[torpid void]

if k changes a and b change

[nova star]

i just dont get how u handle it using induction

[torpid void]

same

[nova star]

u have to use induction??

[torpid void]

if thats what it says

[nova star]

i guess wut if u check for divisibility instead?

so any number 7+k = 2a

yea that might work

proove that 7+k is divisible by 2

omg ofc

yea

no w8...

why is -7+k =/= 2a ???

[torpid void]

because thats only true when k is odd

[nova star]

oh ok

but is that mathematical induction then??

[torpid void]

prove its true for k

base case is true

prove that for all k, k+1 is true

[nova star]

so if i take base to be true

n=k

[torpid void]

it doesnt work well with this

[nova star]

and then want to proove for n = k+1

so in n= k

u have

-7(1)+k = 2a if odd

-7(0)k = 2a is even

if* even

so for n = k+1

u have

-7+k+1 = 2a

fuck idk man im sorry

this is weird

i shud get to my studies, spent too much time on this and it aint working

real soz

[torpid void]

I solved it

dont worry

[nova star]

how>?

lol

[torpid void]

Case 1: the n dollar amount contains a 7 dollar bill, to increase by 1$ replace a $7 note with 4 two notes
Case2: there are only $2 bills, since n>k and the base case is k=5, there will always be 3 $2 bills at least so replace 3 $2 bills with a 7$ for k+1

[vital dew]

ForgedSnow:

[nova star]

wtf..

[torpid void]

wut

[nova star]

thats not iduction

its basically wut we said lol

[torpid void]

both cases for k+1

[nova star]

so basically ur odd and even solution?

i didnt think itd be that simple lol, or even if thatd be accepted lol

[torpid void]

k is 6 = 3 $2

minimum

[nova star]

yea

[torpid void]

so if theres a seven k+1 would be 4 2$ instead of a seven

if theres no seven, just replace 3 2$ with a 7$

[vital dew]

ForgedSnow:

[nova star]

does anyone know more problems like these on planar graphs?

need to practise the proofs

[torpid void]

so base case v = 3

3 vertices means 3 edges and 2 faces

2(3 edges) >= 3(2 faces)

theres your base case proved

[nova star]

u dont need to proove it using induction i think

but i guess thats a valid approach too

btw this one, wut would the proof be?

[torpid void]

i have no idea what that is

[nova star]

each time u add a vertex of degree 2

u get 1 face

degree means number of edges coming out of vertex

[torpid void]

wouldnt that mean there would only be two faces

[nova star]

yea thats wut im thinking too

cuz anything more than 2 faces requires more than a degree of 2

[torpid void]

I guess 4 vertices of degree 2 could make 4 faces

wait nvm

[nova star]

yea

i think its just 2

cuz ull have a polygon

and the outer region

oh ok

so i guess those are the only proofs

well not too hard :0

😃

[torpid void]

lame

[nova star]

lol.. isnt

part b is cool

@torpid void can u solve part b?

[torpid void]

i dont know what any of that is

sorry gotta do my notes

[queen remnant]

I have a graph coloring problem where the goal is to maximize the number of connected nodes that are different colors, and there are only 2 colors. Is there some other NP problem that this could be simplified into?

[faint narwhal]

Probably 3 sat

Definitely 3 sat

[pale epoch]

what

if there are only 2 colors available, this is not an NP problem

or am i misunderstanding the question

[nova star]

@queen remnant so basically u wanna convert graph into bipartile?

or just tell if graph is bipartile?

or all possible combos of whether it is biparile?

any graph that has k3 as a subgraph cannot be bipartile ofc

any cycle with odd vertices cannot be bipartile

for that matter

so i guess u could count how many odd cycles there are in the graph, all of those will have to have 2 neighboring nodes of same color. other than that u would wanna check if two cycles of odd no.of vertices have common edges, code those same color instead of something else, and fill the rest of the graph red and blue, and it should work

[pale epoch]

determining whether a graph is bipartite can simply be done using DFS or BFS

it will either return a valid coloring, or an odd cycle

in linear time

[nova star]

yea but he wants to maximize non-similar nodes

i guess bfs and dfs work, but i almost feel like dp or devide n conquer would work even better, atm idk how ud approach it with those though tbh

but the standard check for bipartile graphs has some theorems, most important of which is that u cant have a cycle of odd number of vertices

[pale epoch]

with just 2 colors, the coloring is unique, unless there are isolated verteces

[nova star]

i dont get wut u mean?

unique?

[pale epoch]

he said 2 colors

[nova star]

yra sorry read it wrong, but i still dont get wut u mean

[pale epoch]

and if you color a graph with 2 colors, the coloring is unique

[nova star]

unique?

[pale epoch]

so i dont see what you can maximize

[nova star]

no u definitly can maximize it

[pale epoch]

yes, all 2-colorings of a graph are the same

unless there are multiple isolated verteces

[nova star]

imagine two 5 vertex cycles joined together by 1 common edge

u wouldnt wanna just willy nilly coat em red and blue

[queen remnant]

another representation would be with binary labels, 0 or 1, where the goal is to maximize the difference between connected labels

[nova star]

ud make the common edge all blue

[pale epoch]

this is not a 2-coloring so?

[nova star]

difference between labels?

[queen remnant]

i.e. the number of edges that connect two different labels/colors

[nova star]

basically u want to have as even ditribution of red and blue right?

[pale epoch]

as i said, if the graph is connected, a 2-coloring is unique

as soon as you color 1 vertex, the color of all verteces is already decided

(for a 2-coloring)

[nova star]

ok lemme try ur idea on 2 pentagons

[pale epoch]

pentagons are not 2-colorable?

[nova star]

exactly

[queen remnant]

this isn't exactly a "graph coloring problem" since it's allowed for two connected nodes to be the same color

[nova star]

thats wut im saying

^^

so u try to maximize the losses in edges

so if two pentagons or triangles are connected, u coat the shared edge red

[pale epoch]

maybe try reading what i said

[nova star]

so that u end up with 5 losses then 6

yea maybe im getting it wrong but, as he said, u can color em as u want

I have a graph coloring problem where the goal is to **maximize the number of connected nodes that are different colors, **

[pale epoch]

he already clarified

[nova star]

^^

yea

[pale epoch]

its not a graph coloring problem

not in the mathematical sense

[nova star]

maybe

[pale epoch]

he doesnt want a valid coloring

[nova star]

but as he said, the easiest way seems to be just to check wut i said

ohh fuck w8

u can have

nodes between the shapes

@pale epoch still an interesting problem

[pale epoch]

maybe

but i dont know the solution to it

[nova star]

thats the point? u think

[pale epoch]

or even a good approach

[nova star]

yea its kinda hard, but i bet somethin would work

[queen remnant]

that's why I was wondering if it might be equivalent to some different better studied problem

[nova star]

i mean conventionally if u wanna optimize

u use dp

[pale epoch]

i assume it is NP

[nova star]

sometimes devide and conquer but 99% of time dp

[pale epoch]

but i also cant think of a reduction out of the top of my head

[nova star]

wut if u did somethin like dijkstras?

[pale epoch]

well, you can solve the problem with linear programming

you assign a weight to each edge

1 if nodes are different colors

0 otherwise

and maximize the total wieght of the graph

[nova star]

but how do u

u come to know if its colored/uncolored as u go

[pale epoch]

its integer linear programming

each noder is either 0 or 1

[nova star]

yea?

[pale epoch]

add weights as explained

run linear program

but integer linear programming is still NP

[nova star]

im sorry but idk wut u mean by linear programming first

[pale epoch]

its a general approach to solve such problems

[faint narwhal]

This problem can be reduced down to 3SAT so

[nova star]

ok got it

[faint narwhal]

it's NP

[queen remnant]

is it something other than a brute force approach?

[nova star]

yea

couldnt u just do like a bfs though?

sry dfs**

[faint narwhal]

no wtf

[nova star]

i was thinking of it, almost seems like u could

well i guess @pale epoch idea might work, but i dont have much clue wut it is

[pale epoch]

it works

but it still has bad runtime

if you just want to approximate

use regular linear programming, which is fast

[queen remnant]

would a linear programming solution run faster than O(2^n) (the number of nodes)?

[pale epoch]

and round non-integer nodes to nearest integer

no

not if you are looking for integer solutions only

[queen remnant]

is it any better than just exhausting every combination and choosing the optimal one

[pale epoch]

in practice it might be

people have put some thought into optimizing ILP's

[faint narwhal]

There are decently fast 3sat solvers just use one of those

[nova star]

yea problem in even trying dfs is that idk wut the cutoff condition would be

@queen remnant so i did some experimenting, and wut i said seems to hold so far, if u color all vertices of common edges of cycles that have odd vertices, u usually end up at optimal result

i havent tried for enough, but i tried some stuff

idk if it will always work though, something for u to test i guess

[queen remnant]

what if the graph is a triangulation? wouldn't that just color everything but the outer edges?

[nova star]

is there a better way to do it?

[queen remnant]

one node should never be surrounded by nodes of the same color, just changing its color would improve the evaluation by the number of adjacent nodes

[nova star]

ok lemme think for a sec

[queen remnant]

consider a graph with one node at the center connected to a bunch of other nodes, and the only edges are connecting the center node to the others. the optimal case would be that all of the outer nodes are the same color and the center node is a different color.

[nova star]

hmm yea

right.

[queen remnant]

it would still be optimal if the outer nodes were connected in a ring (which would also turn it into a triangulation)

[nova star]

idk, but imma continue thinking i guess, seems to be fun problem

@queen remnant i guess if u dont need full optimal u could always go greedy

[spring helm]

If anyone is up, I have the problem "x is congruent to 5 modulo 2"

would the correct way to write this be

x = 2n + 5?

[ivory badge]

yes, but consider a simpler method

[karmic copper]

what are the most efficient approaches to solving an mtsp?

[stray reef]

mtsp?

[karmic copper]

multiple traveling salesmen problem

[nova star]

@karmic copper ?

[karmic copper]

What

[twilit valve]

<@&268886789983436800> where can I post this question I was asked this in an interview today but didnt know the answer
can someone answer it please
if it takes joe 5 days to finish a peice of software and mary takes 10 days to finish a piece of software how long will it take for both of them working together to finish the same software?

[ivory badge]

bruh there's literally a big channel labeled #❓how-to-get-help

and is only mentioned in the big channel titled #rules but ya know why read that

[jolly pulsar]

ouph

[sudden knot]

🤔

[naive saffron]

Why did you tag mods tho

[ivory badge]

beats me

[jolly pulsar]

coz mods deserve to get pinged

[naive saffron]

15 days

Cause programmers don't work together

They simply can't

[jolly pulsar]

nah its a triangular inequality

[naive saffron]

I'm one so I know how it feels

[jolly pulsar]

programmers working together causes more confusion

[naive saffron]

Yes

[jolly pulsar]

and needless argument about ide choices and code layout

[marsh crater]

im more confused how this was an interview question

[naive saffron]

Also variable names xD

Ugh

[ivory badge]

@marsh crater same

[jolly pulsar]

yeah its probably one of those "we're different from all those other companies" places

and tries to be like google but doesn't have the employees or the talent to follow them

[naive saffron]

@marsh crater same

[jolly pulsar]

so just types in 'google interview questions' and dumbs them down

but how is this related to discrete maths

[marsh crater]

well for many people, they might not realize its a math question

its discreet math

[naive saffron]

cAuSe ThIs MaN jUsT fAiLeD hIs InTeRvIeW

[jolly pulsar]

ah yes

discreeet

[naive saffron]

Wait he's muted

What does that mean

[jolly pulsar]

ha nice

[marsh crater]

woog woog'd him

[naive saffron]

To #chill now I guess

[nova star]

lol

too many coders spoil the code?

[nova star]

honest question though, can coders like EVER work together?

[dusky hazel]

@odd carbon

[wheat ledge]

Q implies P questions goes here?

[pale epoch]

question about implication? try #proofs-and-logic maybe

[weary tiger]

Let the "universal set" just be the union of all the sets we are interested. With "equinumerosity" being an equivalence relation on the power set of the universal set, my book describes a single cardinal number as an equivalence class in the power set of the universal set with the aforementioned relation. Would this be the usual definition of what a "cardinal number" is? What is the typical definition? If its relevant to know, ive only been exposed to finite sets in the context of cardinal numbers.

Also, my book says that if the set A is equinumerous to a subset of B we say that " A is dominated by B" or that "B dominates A". Is this the normal term for such a thing? The symbol my book uses is $ A \precsim B $ to symbolise this

[vital dew]

$Hydrεig∅n360:

[weary tiger]

My book also uses the word "similar" as a synonym for "equinumerous"

[weary tiger]

I'm also trying to find a way to prove that $ A \precsim B $ and $ B \precsim A \implies $ A is equinumerous to B.

[vital dew]

$Hydrεig∅n360:

[weary tiger]

With A and B being bijective as conditions for equal cardinality

I dont suppose cardinality can be reduced to anything more fundamental than a bijective relation, I wonder. Theres the intuitive notion of size to it all but I dont know if that can be formalised in any other way than bijective relations.

[nova star]

@weary tiger shudnt u go into like number theory or somethin?

category theory maybe, idrk tbh tho

[faint narwhal]

@nova star this is a fine place for this question

@weary tiger these are pretty standard definitions yes

[weary tiger]

sweet

Right now im just trying to figure out this proof 😩

[faint narwhal]

Do they tell you anything about equinumerous other than it's an equivalence relation

Like do they tell you how the equivalence relation is actually defined @weary tiger

[weary tiger]

I know what an equivalence relation is, I never went through the motions of proving equinumerousity is an equivalence relation . I have a feeling that perhaps proving the transitivity of the equinumerous relation might be somewhat similar to what I have to do for this proof @faint narwhal

I suppose proving transistitivity would require using the composition of two already existing bijective functions

[faint narwhal]

That's not what I'm asking

[weary tiger]

o

[faint narwhal]

Do you know when two sets are equinumerous

[weary tiger]

Yeah when there exists a bijective function on one of them onto the other one

I dont know what the case is for infinite sets though

[faint narwhal]

It's the same

[weary tiger]

Would the set of natural numbers and the set of real numbers be equinumerous?

[dense thicket]

no

[weary tiger]

I see

[faint narwhal]

Cantor's diagonal argument

[weary tiger]

I found this just now http://prntscr.com/oekml7

oops at highlighting

[faint narwhal]

@weary tiger Anyways, the proof you're trying to do is pretty difficult

I think the easiest path is to use the https://en.wikipedia.org/wiki/Schröder–Bernstein_theorem

Or at least, what you're trying to prove is exactly the theorem

[weary tiger]

ah I see

thank you

I love how wikipedia descibes some things

" However, its various proofs are non-constructive, as they depend on the law of excluded middle, and are therefore rejected by intuitionists."

And one hyperlink later you can arrive at " in the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fundamental principles claimed to exist in an objective reality"

[weary tiger]

Ok so

I think ive got what I need to do for a proof

kinda convoluted

[weary tiger]

Let $ h = g \cap D \times E $ and its trivial to show that $ h : D \mapsto E $ and is injective. Let $ I = f \cap E \times D $ and its trivial to show that $ I : E \mapsto D $ and is injective. This implies that both functions $ h $ and $ I $ are bijective. With that, we can see that $ g^{-1} \circ h \circ f : A \mapsto B $ and is bijective

[vital dew]

$Hydrεig∅n360:

[weary tiger]

^second pargraph

Start of with $ A \precsim B $ and $ B \precsim A $ and show that it implies that $ A \sim B $. $ A \precsim B \iff \exists D $ such that [ $ D \subseteq B \land \exists f $ such that $ f : A \mapsto D $ and f is bijective. ] Using identical reasoning $ B \precsim A \iff \exists E $ such that [ $ E \subseteq A \land \exists g $ such that $ g : B \mapsto E $ and g is bijective. ]

[vital dew]

$Hydrεig∅n360:

[weary tiger]

^first paragraph

somethings off about my last two sentences in the second paragraph

[weary tiger]

I have to prove this to do it https://en.wikipedia.org/wiki/Schröder–Bernstein_theorem

[opal obsidian]

https://cdn.discordapp.com/attachments/592294218806853633/599858485232009216/unknown.png

r = 2t/root(29) i + 1 - 3t/root(29) j + 5 + 4t/root(29) k

correcto right?

<@&286206848099549185>

[modest zealot]

15 minute rule, and this hsouldnt be in discrete math

anyways, what does it mean to parametrize with respect to arc length

[opal obsidian]

wait what

15 minute rule?

o0hh

15 min rule

sorry

[modest zealot]

post this in #multivariable-calculus

ill help u there

[cerulean ore]

Guys, I am struggling with Set theory

Trying to find a book that has multiple practice questions with answers for that

Can someone please help?

[weary tiger]

I got you bro

I love you and care

Here

For free

https://cdn.discordapp.com/attachments/579044989728981032/600893487772205092/THE_LIST.txt

No charge

[cerulean ore]

@weary tiger So, Set Theory. A First Course - Daniel W. Cunningham?

[weary tiger]

Si senor

[cerulean ore]

Let me check, thank you for the quick help!

Pardon me, I didn't tell that what types of questions I am looking for

In a class of 25, 12 have taken economics, 8 has taken economics but... < these types of questions

That book is more theoretical

[weary tiger]

i just realized what your pfp is lol i thought it was a duck

quack

quack quack

it is indeed more theoretical

but its general

so it has what you need and more

the first 4 chapters should be enough for your class though

the rest after 4 chapters is more pure math orientated

[cerulean ore]

will I be able to solve that type of questions if I deeply go through the first 4 chapters?

[weary tiger]

most definitely

for the set theory part of discrete math atleast

oh wait

you go over countability

[cerulean ore]

;-; Let me start it if you insist

[weary tiger]

then youd have to do up to chapter 6

[cerulean ore]

this is my syllabus

[weary tiger]

yeah chapter 6

but you dont have to do all the exercises

[cerulean ore]

I will be studying too much man for this much syllabus*

don't you think?

[weary tiger]

its only 154 pages

and it covers like half the syllabus

like i said you dont have to do the exercises

I dont think CS majors do math proofs

[cerulean ore]

We have to just prove principle of inclusion and exclusion

A union B, A union B union C out of all the principles

[weary tiger]

yeah then you dont need to do the exercises

just read the contents from chapter 1-6

the definitions, theorems,lemma,corollaries, and maybe the proof or examples if you don't get it

shouldnt take long

[cerulean ore]

the definitions, theorems,lemma,corollaries, and maybe the proof or examples if you don't get it skip them?

[weary tiger]

learn them

skip the exercises

[cerulean ore]

As you say!

[weary tiger]

basically read content of the book dont do exercises

[cerulean ore]

I hope I will be able to solve those types of questions after going through it.

[weary tiger]

alright gl

[cerulean ore]

Thank you!

[regal lantern]

Hello guys

I am going through Rosen's book before I start by degree as I heard that it was pretty good

I am doing a standard 3 year undergrad course in comp sci that has some discrete maths content in it

and I was wondering if this book would cover a good chunk of everything up to second year content or if I should go through something else to supplement it?

[sharp rock]

depends on the university, you should be fine in most unless you are taking stuff that is super math/theory heavy

[oak creek]

oh, i remember going through that book myself for my courses

it's pretty gentle with the language in it, and i feel like it's kinda cs/engineer oriented. not super mathy

it'll prolly cover what you'll need for a great deal of your major

[torpid wolf]

Oh Rosen, good memories, very recommended, especially for CS.

[trim oak]

Rosen is our req text in Discrete for CS :) really good so far!

Does that correctly represent the set of all odd integers?

Unambiguously

[faint narwhal]

Yes

[trim oak]

Thanks

[torpid wolf]

Honestly there is no need for the x belongs to Z in the beginning, but it is still correct 😄

[trim oak]

Oh ok, because K has to be an Integer

[torpid wolf]

Exactly

x can’t be non integer in that way 😃

[weary tiger]

Is this correctly how you create set builder notation?

I have the set {0,10,20,30,...,1000}

I believe this set can be built by

{n in N: 10n and n <= 100}

Is this correct?

Another example:

I have the set {-3, -1, 1, 3, 5, 7, 9}

I believe this is then

{n in Z: 2n+1 and -2 <= n <= 4}

[mossy palm]

you're essentially correct but you're using 'n' twice

its better written {m in N: m=10n for some n<=100}

[weary tiger]

Why is it better to introduce a new variable?

[storm raft]

That's wrong definitions

Try to read out ... There are two ways to define a set

$\left{ x \in E, P(x) \right}$ and $\left{ f(x), x \in E \right}$

[vital dew]

Astréas:

[storm raft]

First reads : Set of all x such that property P(x) is true.
Second reads : Set of all f(x) when x lives in E

[weary tiger]

If I were to read mine it would be "The set where elements are 10 * n and n is a natural number up to and including 100"

[storm raft]

If you try to read your first proposition {n in N, 10 n and n smaller than 100}

It is the set of all n in N such that property "10n and n smaller than 100" is true

The fact that n is smaller than 100 can be true or false, that's fine

But "10n" is not a property, it cannot be true or false

[weary tiger]

But midnight's response "ts better written {m in N: m=10n for some n<=100}" seems to be problematic because how do we know what n is? If it s any real number then we obviously have an infinite set, same for if it is an integer.

[storm raft]

but if n was any real number, m = 10n wouldn't be in N

$\left{ m \in \mathbb{N}, \exists n \leqslant 100, m = 10 n \right}$

[vital dew]

Astréas:

[storm raft]

This reads : The set of all m integers such that there exists a n less than 100 such that m = 10 n

[weary tiger]

Should the statement then be for all n<=100?

[storm raft]

The property is "There exists n less than 100 such that m = 10n". This can be rather true or false depending on the value of n

[weary tiger]

Because then how do we know that we are counting by 1?

Is it not true that {m in N: m=10n for some n<=100} could be the set {0,10,550}?

[storm raft]

The first set is much bigger than the second one

[weary tiger]

But I'm saying that {m in N: m=10n for some n<=100} defines many sets

[storm raft]

Is m = 100 in the first set, let's call it E

In other terms, does there exist some n less than 100 such that 100 = 10*n ?

[weary tiger]

yes, for n = 10

[storm raft]

So m=100 is in E

Since the property P(m) is true

[weary tiger]

so should {m in N: m=10n for some n<=100} be instead {m in N: m=10n for all n<=100}

[storm raft]

Let's call your second set F

[weary tiger]

Or is it the very nature of set builder notation that the set will include all elements who's condition is met?

[storm raft]

$\left{ x \in E, P(x) \right}$

[vital dew]

Astréas:

[storm raft]

this set will include all the values of x where P(x) is true

[weary tiger]

oh I see, that is where my confusion comes from.

so if I were to make up something on my own like the set of all even numbers is then

{k in Z: n = 2k}

[storm raft]

How do you read this

[weary tiger]

what I wrote?

[storm raft]

yep

The set of all integers k such that ... ?

[weary tiger]

such that n is 2 times k

[storm raft]

what is n ?

[weary tiger]

n is 2k

n is an integer

[storm raft]

Let's try

k is in your set if the property "n = 2k" is true

So let's try ... like 2 ... is the property "n = 4" true ?

[weary tiger]

yes

[storm raft]

So 3 now

[weary tiger]

yes

[storm raft]

3 is in the iff "n=6" is true ?

but

how come n=6 and n=4 at the same time ?

[weary tiger]

for different values of k

[storm raft]

So you should define n

[weary tiger]

n in this case is all numbers

[storm raft]

n is absolutely not defined

You need to put quantifiers before your variables

Is it, the set of k such that for all n, n = 2 k

Or the set of k such that n = 2k for some n

n can't simply exist because you have written it down

[weary tiger]

why not the set of n such that for all n, n = 2k

[storm raft]

what does "for all n = 2k"

mean*

[weary tiger]

I mean for all n, n = 2k

[storm raft]

What does the = mean here ? Is it definition ?

Or is it something that can be true or false ?

[weary tiger]

it is definition

like x = 5 is the definition of x

[storm raft]

Ok fine

But then you need a property P

{k in Z such a certain property P(k) is true}

If the = means definition then it is not a property that can be true or false

[weary tiger]

So {k in Z: all n where n = 2k}?

[storm raft]

There are 2 quantifiers ... "for all" and "there exists" or "for some", please use them

[weary tiger]

okay

[storm raft]

If the sentence doesn't make sense in english, then what you're trying to say mathematically is probably wrong

[weary tiger]

{k in Z: all n for some n = 2k}?

If I were to define the set of even numbers in plain english I'd say it is the set of numbers divisible by 2

[storm raft]

I'd say the set of integers n such that there exists an integer k such that n = 2k

Because an even number can be written as n = 2k

n is an integer iff there exists an integer k such that n = 2k

Or if n = 2k for some integer k is an other way to say things

[weary tiger]

okay I'm trying to understand how to build that then. {k in Z: all n, n = 2k}

[storm raft]

"all n" is not a quantifier

[weary tiger]

no?

all k then?

for all values of k

{k in Z: all k, n = 2k}

[storm raft]

"The set of integers k such that all k, n=2k"

Is that a proper english sentence ?

[weary tiger]

yes?

[storm raft]

What does "all k, n=2k" mean then ?

[weary tiger]

it means any value k can take, n is equal to 2 times those values

so if k can be 1,2,3 then n can be 2, 4, 6

[storm raft]

Oh shouldn't it be "for all k, n = 2k" then ?

[weary tiger]

i think all and for all is the same thing

"All balloons that are blue are mine" is the same "For all balloons that are blue, they are mine", aren't they?

[storm raft]

All something is followed by a verb, or at least is the subject (or related to the subject)

After "All balloons", you expect a verb

After "For all ballons", do you really expect a verb ? I mean I don't really know

But I'd rather say no

[weary tiger]

I think I am getting more confused now to be honest. If I am to follow the idea of {x in E: P(x)} and I want to create the set of even numbers, I first need to establish some value k that can be any integer, then some n that is k times 2, right?

and I need to make it clear the set should be built using each value of n, where n is calculated based on each value of k

[trim oak]

I'm getting confused now haha

[storm raft]

$\left{ n \in \mathbb{N}, \underbrace{\exists k \in \mathbb{N}, n = 2k}_{P(n)} \right}$

[vital dew]

Astréas:

[storm raft]

P(n) is a property that can be either true or false

[weary tiger]

So {..., -2, 0, 2, 4, 6, 8, ...} = {k in Z: for all k, n = 2k}

[storm raft]

You still haven't defined n

[weary tiger]

n is defined to be 2k, is it not?

[storm raft]

If it is defined to be 2k, then where is the property that is supposed to be true or false ?

[weary tiger]

{k in Z, n in Z: for all k, n = 2k}? Do you need to define all variables first?

[storm raft]

You define variables by putting a quantifier before them

[weary tiger]

but k was defined without a quantifier

[storm raft]

In case you haven't seen it. This channel is being used.

Yeah ... basically, k is definedwhen you say "The set of all k such that" ...

A bit peculiar

[trim oak]

K has the existential quantifier doesn't it?

[weary tiger]

so how is it that (some k in N, n = 2k) can be true or false?

[storm raft]

This sentence will be true if and only if n is in your set

[weary tiger]

but I don't know if n is in my set because I am building the set

and n represents the values in the set being built

[storm raft]

Yes, and the property will be true iff the value n is going to be in your set

If you pick particular values of n

[weary tiger]

okay so n = 3 is not in the set for instance?

hi

why wasn't my discrete math problem answered

[storm raft]

Say n=1, is n in your set ? Meaning is P(1) : "There exists some k such that 1 = 2*k" true ?

Hi, next time you don't read rules, you get a ban 😃

[weary tiger]

ah then the answer is false

[opal crescent]

cause it's not discrete math

[weary tiger]

what is it then

[opal crescent]

#prealg-and-algebra i guess

[storm raft]

or go to #❓how-to-get-help

But for instance, n=2 will be in your set since P(2) will be true !

P(3) is false ... so n=3 is not on your set

The n's that will be in your set will be all the n's such that P(n) is true ...

[weary tiger]

so the set of odd numbers is then {n in N: for some k in N, n = 2k +1} P(n) is "for some k in N, n = 2k+1"

So then you say this in English as

"The set of values n, for some k in N where n = 2k+1 is true"?

[storm raft]

I'd read this that way "The set of values n such that there exists some k in N such that n = 2k+1"

Or

"The set of values n such that n = 2k+1 for some integer k"

[weary tiger]

I think I finally get it!

[storm raft]

$\left{x \in E, P(x) \right}$

[vital dew]

Astréas:

[storm raft]

"The set of elements x of E, such that P(x) is true"

We don't always say "is true" ... P(x) already means "P(x) is true" :x

[weary tiger]

why is true striked out?

oh okay

any example set you can give me so I can try to build it and see if I actually understand?

[storm raft]

Hm

1. The set of perfect squares
2. The set of perfect squares that can be expressed as the sum of 2 squares.
3. The set of functions that does not have any zeroes, except maybe at x=0

And the other way around

[weary tiger]

okay let's see if I tackled this right for the first one:

{n in N; for some m in N, n = m^2}

actually m needs to be in Z

[storm raft]

\begin{enumerate}
\item $\left{ n \in \mathbb{N}, n^n \leqslant 2019 \right}$.
\item $\left{ r \in \mathbb{Q}, \exists n \in \mathbb{N}, r^2 = n \right}$.
\end{enumerate}

[weary tiger]

{n in N; for some m in Z, n = m^2}

[storm raft]

Both are correct

[weary tiger]

ooh! they would make the same set

what is Q?

[storm raft]

m can be in Z or in N, its square will be the same 😃

rationnal set

[vital dew]

Astréas:

[storm raft]

Didn't like the last one :c

[weary tiger]

okay so the general formula will be {value in set, some value in set, function(val1, val2)}

[storm raft]

Er

Oh yeah, bad examples

I should have included a set that uses that other quantifier

[weary tiger]

for all?

[storm raft]

Ok so 3. will be $\left{ n \in \mathbb{N}, \forall p \in \mathbb{P}, n | p \right}$

[vital dew]

Astréas:

[weary tiger]

what is P?

[storm raft]

Set of prime numbers

[weary tiger]

oh okay

okay so the set is all natural numbers n where n can be divided by some prime number

[storm raft]

Nop

[weary tiger]

some number that is divided by all prime numbers?

[storm raft]

where n can be divided by all prime numbers

[weary tiger]

so {0}?

[storm raft]

Hmm

Didn't check what you said ... p is divisible by n ... not the opposite

[weary tiger]

it reads n/p so p is a divisor to n

so n is divisible by p, right?

like 4 is divisible by 2

because 2 is a divisor to 4

therefor 4|2

[storm raft]

2|4

[weary tiger]

??

but that reads 2 is divisible by 4?

I always thought the | is representing a dividing sign so 4/2 is the same as 4|2

but it would also make sense if 2|4 is to be read as "2 divides 4"

[storm raft]

Erm no

2|4 means 2 divides 4 😃

[weary tiger]

ooooh wow

[storm raft]

It's not the 2/4

[weary tiger]

that explains a lot of confusion in my textbook

so the set is then {1}?

[storm raft]

yeah

[weary tiger]

aha!

Thank you for all your time and effort, I really do appreciate it. I have been struggling in my discrete math class and I really am trying to pick up the pace and actually sit down and understand it.

The library I'm in is closing now so I must go. I hope you have a good night!

[storm raft]

I think the thing is to express everything in proper english

[weary tiger]

I'm not very good with English, that may be why haha

[storm raft]

With some ... codes "for all" and "there exists" or "for some"

Oh then in your mother tongue

If you feel like you needed to add something to the translated version, then you should probably add it in the maths version

[weary tiger]

Oh no, English is my native language, I am just not very good at it. (I never finished high school)

[storm raft]

Oh I see

Well good night and good luck

[weary tiger]

Thank you!

[trim oak]

Hi, sorry to ask again.
After reading that discussion, do I need to add a quantifier to k for this to be correct?

I think I just confused myself trying to follow along

{ x | x = 2k + 1, k in Integers }, should it be { x | x = 2k + 1, for some k in Integers }

[tropic cedar]

Your syntax seems fine to me
If you want to be more accurate maybe:

${x \in \mathbb{Z} | \exists k \in \mathbb{Z}, x=2k+1}$

[vital dew]

Mat:

[trim oak]

Okay thanks, I want to try and learn it as accurate as I can I guess haha

Also, would it be for SOME or for ALL k?

2 *0 + 1, 2 * 1 + 1, 2 * 2 + 1... 2 * n + 1 seems to be for all, so would I use the universal quantification?

${x | \forall k \in \mathbb{Z}, x=2k+1}$

[vital dew]

Nokk:

[tropic cedar]

For each x in Z, for x to be included in the set, you just need one k to exists satifying x=2k+1

There is a specific k for each x in the set

[trim oak]

ohh ok

thank you again

[weary tiger]

Can anyone tell of the " $ A_1 $ " contructed here works for proving the schroder bernstein theorem https://en.wikipedia.org/wiki/Schröder–Bernstein_theorem

[vital dew]

$Hydrεig∅n360:
Compile Error! Click the reaction for details. (You may edit your message)

[weary tiger]

$ f : A \mapsto B $ and $ g : B \mapsto A $ with both functions being injective. Prove that there exists a bijective function $ h $ on A onto B. Suppose $ \exists A_1 $ such that $ A_1 \subseteq A $ and $ g[ B - f [ A_1 ] ] = A - A_1 $ , in which case we can define a $ h $ such that $ h : A \mapsto B $ where $ x \in A_1 \implies h(x) = f(x) $ and $ x \in A - A_1 \implies h(x) = g^{-1} (x) $ with h being bijective. Constructing the h is dependent an $ A_1 $ which satisfies $ g[ B - f [ A_1 ] ] = A - A_1 $ . Let $ A_1 = \bigcap { A_0 | A - g [B] \subseteq A_0 $ and $ g [ f[ A_0 ] ] \subseteq A_0 } $

[vital dew]

$Hydrεig∅n360:

[faint narwhal]

By f[A_1], do you mean the image of A_1 under f

[weary tiger]

yeah

Wanting the $ A_1 $ to satisfy the property $ g [ f[ A_1 ] ] \subseteq A_1 $ seems obvious as a direct consequence of injectivity from the statement $ g[ B - f [ A_1 ] ] = A - A_1 $

[vital dew]

$Hydrεig∅n360:

[weary tiger]

And the property $ A - g [B] \subseteq A_1 $ probably stems from the fact that if every element in A that is not in the range of g is not inside of $ A_1 $ then we could end up having a blindspot in constructing $ h $ to be bijective since we're using h(x)= f(x) for $ x\in A_1 $

[vital dew]

$Hydrεig∅n360:

[spring helm]

Hey, I have the problem "Determine if the congruence 2x (congruent) 11(mod 8) has a solution for x"

can anyone help out?

[tropic cedar]

Two possible ways:
-find out the set {2[x]: [x] in Z_8}
and see if [11]=[3] is in the set
-think about units in the ring Z_8

[ivory badge]

alternatively, you could just write out the congruency thing explicitly which should make it nice

[spring helm]

I checked the GCD and the GCD was 1

so I guess that would prove it is no solution?

[tropic cedar]

gcd between which integers?

[spring helm]

Im sorry, I did the wrong numbers for the GCD of that

[tropic cedar]

It was a good idea, were you finding gcd(8,11) ?

[weary tiger]

ok help no longer needed
I've figured out that the definition for A_1 above works for proving the theorem

[nova star]

so i have n warehouses and k farmlands, on a graph. I want to collect crops from farms and store them in warehouses. crops have an ammount that they produce, and warehouses have a capacity. What would be a way to calculate shortest path between warehouses and farmlands to store all the crops (assuming crops produced<total capaacity of warehouses)?

[trim oak]

Is this proof of any kind?

I don't know how rigorous he wants anything... (First week of discrete) sorry if it's super dumb

[pale epoch]

2nd line below the pic, you should use different variables probs

C instead of B

Generally a mathematical proof contains words

but the arguments are there

[weary tiger]

U got the proof nokk @trim oak

[nova star]

thaz my problems with proofs, u never know how rigorous the examiner would want em

and either u end up wasting time trying to proove some shit

or u dont end up proving it enough

[weary tiger]

Am I interpreting this question correctly?

https://imgur.com/a/rkkqUqn

It is describing the intersection of the sets {1}, {1,2}, {1,3}, {1,2,4}, and {1,5} (thus the answer is {1})

[glossy adder]

{1} is not the set of all integer multiples of 1

etc

[weary tiger]

It's not?

[faint narwhal]

no

[weary tiger]

Isn't 1 only divisible by 1?

[faint narwhal]

that's true

[weary tiger]

ah so then I am misunderstanding what a multiple is

An example: If i is 4, then A(4) is the set of all integer multiples of 4. Is that not 1,2, and 4?

Is it actually 1, 2, 4, 8, 16, etc?

[faint narwhal]

not quite that either

[weary tiger]

so it is really {i in Z| i^n, n in Z+}

[faint narwhal]

multiples

[weary tiger]

yes?

[pale epoch]

what are the multiples of 1?

[weary tiger]

1

[pale epoch]

2*1 is a multiple of 1, surely?

[weary tiger]

why would it be?

1 is a multiple of 2, yes. But 2 doesn't seem to be a multiple of 1

[pale epoch]

you got that backwards

[weary tiger]

2x = 1 cannot be solved by an integer, right?

oh I see

[pale epoch]

the multiples of 1 are all numbers of the from k*1

the multiples of 2 are of the form 2*k

and so on

[weary tiger]

so multiples of 2 are all evens?

oooh okay

[pale epoch]

yes

[weary tiger]

What word was I thinking of then

Divisors?

[pale epoch]

in other words, the multiples of i are all numbers evenly divisible by i

i think you were thinking of divisors, yes

it's a related concept

the multiples of i are the numbers that have i as a divisor

[weary tiger]

okay, my apologies

[pale epoch]

so the multiples of 1 are all integers

for example

no

5 is a divisor of 10

so 10 is a multiple of 5

[weary tiger]

10 is a multiple of 5?

ahhh

okay

because 5 * 2 = 10

[pale epoch]

yeah

[weary tiger]

so 10 is a multiple of 2 and 5

[pale epoch]

yes

[weary tiger]

100 is a multiple of 10, 2, 5, 20, 25, 4, 1, 50, etc

[pale epoch]

i think you got it

[weary tiger]

thanks! I don't even think that's discrete math lol my English isn't very good I guess

[pale epoch]

it can appear in an introductory discrete math class i guess

[weary tiger]

yeah I'm in an early discrete math class

it's the prerequisite for all the senior level math classes

[trim oak]

Does "surjective" just mean that the range of the function is equal to the codomain of the function?

So that every element in the codomain has a mapping to the elements of the domain?

[pale epoch]

yes to the first question

the second question i'm not sure i get

every element in the codomain has a (at least one) pre-image in the domain

every element in the codomain gets mapped to by an element in the domain

[trim oak]

Only if it's surjective?

Or is that always true?

The book seemed to say that the example function is surjective because each codomain element has a mapping from an element in the domain, but if we added an element to the codomain that wasn't mapped to from the domain, then the function would cease to be surjective

But I've probably totally misunderstood haha

[pale epoch]

i gave alternative definitions of surjective

in general, not every element in the codomain gets mapped to, your book is correct

[trim oak]

Ok thanks heaps

[pale epoch]

you can always add an arbitrary element, if you want to

you can also always make a function surjective, if you restrict the codomain to the range of the function

[faint narwhal]

practice

[faint narwhal]

literally everything

yep

[dawn widget]

Help

[faint narwhal]

Usually if you're trying to do it algebraically

You should start with the more complicated side and simplify it into the simpler side

[dawn widget]

What can I do about the left hand side algebraically

how can I get rid of the sigma

[faint narwhal]

Write it out

See what happens

[dawn widget]

?

[faint narwhal]

Okay, what if you combine all the fractions

Least common denominator

[dawn widget]

everything would end up getting multiplied by r

or is it r!

LCD would be r!n!

[dapper rose]

Inducting on r worked for me

[lean leaf]

If |A ∩ B| = 25, it is true that A and B have at least 25 elements, right?

[next valley]

I guess so

[lean leaf]

And if |A - B| = 18, it is true that A has at least 18 elements (therefore at least 43 elements)?

[reef thistle]

hmm, yeah, A-B consists of elements contained in A.

and elements not contained in B
[EDIT: elements contained in A and not contained in B]

[oak creek]

yep

[reef thistle]

and A intersect B consists of elements contained in A and contained in B.

So, isn't that all elements of A?

[oak creek]

it's all elements shared between A and B

while A-B is all elements in A not shared with B

write it out using inclusion exclusion

[reef thistle]

yeah, so 18+25 would be all elements of A

[oak creek]

i think it might make a little more sense

yeah

[lean leaf]

Hum? Wouldn't it be just the minimum cardinality for A, not the total?

[dapper rose]

yes wait

[lean leaf]

Yeah. If the problem was Given |A ∩ B| = 25 and |A - B| = 18, find |A|., you wouldn't be able to tell exactly what |A| is.

[dapper rose]

you can

[lean leaf]

Oh, right.

lol

[stray reef]

$A = (A \cap B) \cup (A - B)$, and $(A \cap B) \cap (A - B) = \varnothing$

[vital dew]

Ann:

[coarse sphinx]

S is a relation on A={1,2,3,4} where S={x+y is a even number}, is S a transitive relation.

I have tried to solve this in a number of ways and always come to the conclusion that S has to be transitive but the answers to the exam says it is not.

[pale epoch]

your notation for S is weird?

but if i get you, you are correct

[coarse sphinx]

It's copied from the exam but I agree that it is strange. 😃

[pale epoch]

a relation on A should be a subset of AxA

but if that means that (x,y) is in S iff x+y is even

then it's transitive

[pale epoch]

maybe this is a trick question

and the answer is "S is not a relation"

🤷