discrete-math

[river yarrow]

No it doesnt

[azure lichen]

proof?

if it doesn’t work, give a counterexample

[river yarrow]

oops, i read that as 6 and 7

nvm

[azure lichen]

anyway, I have to continue working

[river yarrow]

it works for every number though

im not sure what your getting at

[stray reef]

you pick some subset of {1,…9}. let’s say for example, you pick some subset with 8 elements. are there now two numbers in there which add to 10? 
well, yes. you picked all but one of the numbers, so one of the pairs is in here for sure
does this also work with 7 elements? 6 elements?

[river yarrow]

Yes, and yes

[stray reef]

@river yarrow does it work with any smaller number of elements?

if yes, what's the minimum? if not, why?

no

a 1-sphere is a circle.

and a 0-sphere is two points.

no

a 2-sphere is the boundary of a 3-ball

care must be taken not to confuse a ball and a sphere

there is a world of difference

a sphere is the set of all points at a fixed distance from a center

a ball is the set of all points within a fixed distance from a center

it's the boundary of a 1-ball

which is an interval

that's the equation of a circle aka a 1-sphere

not the points it encloses no

no

1-sphere != 1-ball

ffs

i said

care must be taken not to confuse a ball and a sphere

and then you did anyway

what do you mean by the boundary

no

i'm not

at what point did i say anything about flattening anything out

at what point did i say anything about flattening anything out

at what point did i say anything about flattening anything out

at what point did i say anything about flattening anything out

at what point did i say anything about flattening anything out

a 0-sphere is the boundary of a 1-ball. a 1-ball is a ball in 1-dimensional space. a ball in 1-dimensional space is an interval.

sigh

dont become emotional
fuck you

[normal ginkgo]

if you're questioning the vocab I would suggest you also explore some sites such as google which may aid you there

then don't take out your frustration at those trying to answer

[stray reef]

and how is a ball in 1-d space an interval when its a filled in circle
a ball is the set of all points within a fixed distance from a center

fuck you for insisting i've done anything of use to you

because i didn't

clearly

[river yarrow]

@stray reef Im still lost and i do not know how to answer your question

[river yarrow]

Oh wait. Im not sure but I think I got it. Confirm for me:...

The question asks for the minimum amount of numbers that needed to be selected in order for two numbers to add to 10.

(1,9),(2,8),(3,7),(4,6),(5)

these are all the pairs that add up to 10

So the minimum would be to pick 1 pair and pick 1 element from each of the rest of pairs. So for instance, I could pick 1 and 9 which add up to 10, and then pick 2, 3, 4, and 5 (none of which cant be paired to add up to 10. Thus, the minimum # of choices is 6

Did i get it right?

[exotic oyster]

∀n,∀x,∀y, line(n, x, y) → ∃m,line(m, y, x) with line (n, d, a) is true if there is a direct line identified by the number that allows to go from the departure city to the arrival city. For you what is the meaning of this proposal

[summer gull]

Can someone explain how you'd go about this problem?

[lilac pivot]

I mean log(n^3) is just 3log(n)

log(n) is an increasing function

so (log n)^3 must be increasing faster than log(n) (and so 3log(n))

[summer gull]

gotcha, so it would be false since log(n^3) would increase much faster than 3log(n)

[sour arrow]

Yup. No matter what positive real c is,
log(n)³ > 3clog(n) for some large n

[summer gull]

thanks!

One more question. If I'm given a bunch of different functions, how would I order them by growth rate? Just graph them, and the ones that grow fastest would be the furthest out in the list, and the ones that grow the slowest would be near the start of the list?

Or, mathematically, is there a way to see this?

[lilac pivot]

depends on how you want to order them

[summer gull]

well, i want to order them lowest to greatest

I assume just take the limits of each and order it that way?

[sour arrow]

You proved that log(n³) is log(n)³ have different growth rates

For example,
log(n) ∈ O(n)
But
n is not in O(log(n))

[summer gull]

Yeah, so it's just the limits

right?

if lim x -> inf (f(x)/g(x)) = 0 then g(x) is faster, inf, then f(x) faster, some constant then same growth rate?

Because Big O would treat a constant as O(1) which applies to all constants?

[sour arrow]

For g that are everywhere non-zero

Or, non-zero after a certain point

[summer gull]

gotcha

[sour arrow]

All constants are O(1), yeah

There are non-constants that are O(1) though

[wintry rock]

how do you convert from base 2 to base 8?

[summer gull]

It's recommended to always use base 10 as a stop point

so convert base 2 to base 10 then base 10 to base 8

@wintry rock

Also, on another note, is the function log^4 sqrt(n) valid?

it's on one of my assignments and im not sure what to make out of it

log^4(\sqrt(n))

? @sour arrow you'd save my life rn

[wintry rock]

ah but the question says I can't use base 10 haha

that's why I asked

pretty silly but what ru gonna do

[summer gull]

Can someone help me understand this problem?

please

[scarlet anvil]

You don't happen to be around @candid flicker?

[unreal nova]

2n is a lot smaller than n^2logn as n gets larger

[weary tiger]

What do these half bracket things mean

[x]

[stray reef]

floor

[weary tiger]

Thank you

[opal crescent]

@wintry rock got it?

ah shit didn't see it was 20h old...

[peak crag]

hi, i'm for some reason banned from cs server so hoping here is the next best place to ask

if you play around with it you can see that this algorithm outputs an eulerian circuit in a graph that has one:

start at arbitrary vertex u
for each neighbor v of u:
    delete edge (u, v)
    recurse from v
    output (u, v)

basically it works by "splicing together" cycles in the graph

but im not sure how to formalize the proof of correctness - does anyone have any ideas?

[earnest oxide]

can someone tell me if i did my tree/transversal right?

equation in question

[reef thistle]

looks okay

[earnest oxide]

@reef thistle ty

[slender skiff]

With something like this "(m,n)<(m′,n′)↔m<m′ ∨(m=m′ ∧n<n′)"

what does the ′ mean

[stray reef]

it doesn't mean anything

m and m' are just two different variables

[slender skiff]

oh

okay

Thanks!

[last sigil]

iirc m' is said as "m prime"

[stray reef]

yes it is

[weary tiger]

hi

what is b asking

a such that a is greater than zero?

for some b

any clarification

oh is it just 4,5,6

nvm

[shy anchor]

Yes it's just 4,5,6

[whole bluff]

Super dumb question but I also missed this lecture so I’m clueless:

The cross product {} X {} = {} right?

And the cross product {{}} X A is just {{}}?

[dapper rose]

yes

no

[whole bluff]

Lool so what’s the cross product of the second one? 😅

[weary tiger]

so how would you prove a function is injective mathematically

and how would you prove i

*it's subjective

[stray reef]

if by "subjective" you mean "surjective"

...then for both of these you would use the definitions???

@weary tiger

[weary tiger]

hm yeah my bad

that's what I meant

[stray reef]

i mean if we're being this general then there really is nothing else to use except the definitions

[iron shadow]

Ive gotten it to 2a^2+2b^2>=ab and was wondering if someone could give me a hint

on what to do from here

[last sigil]

Hold up, where have I seen this problem before?

[iron shadow]

maybe we go to the same school lol

[normal ginkgo]

@iron shadow have you heard of the AM-GM inequality?

[iron shadow]

Yeah, Im working on getting it to xy <= [(x+y)/2]^2

[normal ginkgo]

a^2 + b^2 is greater than or equal to ab already

[iron shadow]

Just feel like Ive tried everything and was looking for a hint in some way, Im not even sure what kind of hint I could get

[normal ginkgo]

let alone 2(a^2 + b^2)

[rapid herald]

hey guys, for a math assignment of mine I am looking at the shortest path in European railroads, I have implemented the Dijkstra's algorithm without using any CS and would like to add something else. I was thinking about the proof of the algorithm solely based on math. Can anyone here help me with it please?

[gentle nebula]

implemented without using cs as in?
Look up proof of correctness of dijkstra usually induction is used if thats whay you're looking for

[reef thistle]

@rapid herald Show that the n-th closest vertex from the source is the correct distance, given the 1st to (n-1)th closest vertices are.

[short wyvern]

Any life hacks on how to determine associativity without face checking all 27 combinations?

[weary tiger]

for set proofs

when do you have to prove both ways?

[sour arrow]

@weary tiger
Have an example?

If you are using identities which pre-guarentee equality, then you don't need it. Often, you can't do that though

[weary tiger]

I don't have any examples off the top of my head

I know that professor did do both ways for some examples

and only proved it one way for others

[sour arrow]

You really can't go wrong by showing each set is a subset of the other, like ever

It's an easy way to do things

[weary tiger]

alright

[opal crescent]

but sometimes the other way is the exact opposite of the first way

so you can just work by successive equivalences

it looks you're doing one way

when it isn't

[weary tiger]

could you give me an example?

[sour arrow]

There's odd cases where you have ways to work out the equivalence based on other equivalences, that's the only other case

[weary tiger]

successive equivalencies is just using the properties right?

[opal crescent]

pretty much

[weary tiger]

wish there was a clearer indication on which way to use 😦

[weary tiger]

Hello

~(s or a) = ~s and ~a right

:/

[outer ferry]

Have you tried a truth table?

You can check the logical equivalence of the statements pretty quickly.

[rapid herald]

hey! i want to numerically prove that a graph im using is connected, how would i go about doing that?

i can say that every pair has an edge between them, but is there a way with which i can prove it?

[icy ibex]

https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Computational_aspects

One of the first algorithms you might learn in graph theory.

[rapid herald]

@icy ibex can I make a tree and show that every node is connected ?

[icy ibex]

Basically, yes. https://en.wikipedia.org/wiki/Breadth-first_search

[rapid herald]

cool ty @icy ibex

[icy ibex]

np, gl

[atomic sapphire]

1. explain how to use the adjacency matrix of a simple graph and matrix multiplication to determine the number of triangles incident on any given vertex (i.e., the number of triangles which have the given vertex as one point).
2. explain how to use the adjacency matrix to determine the number of triangles in a graph.

Could anyone help me with these two questions please? I think that we have to do A^3 to get triangles in a matrix and use the diagonal vertices and add the sum of it and divide it by 6 (at least I think that's how we do it) to find the triangles of any given vertex. Am I going in the right place about this?

[ivory badge]

$(b)^*(ab)^a(a | b)^$

[vital dew]

Darkrifts:

[ivory badge]

though i've seen a couple different ways to notate the thing at the end

@whole chasm

the * means "repeat it as desired" in an informal sense

[whole chasm]

Because any combinations of those gets you to the end

Right?

[ivory badge]

anything which satisfies that expression I wrote gets you to the end I think

[whole chasm]

Yeah

What about the third one, where the paths split?

[ivory badge]

so: Any number of B's because loop to start, any number of AB because loop, a single A to get to end, any number of A or B in no particular order because loop remains on accepted state

@whole chasm do it by cases

[whole chasm]

Following yeah

Okay so

b * b * a * a * b Case 1

Or do the loops need to be in notation?

b(b) * a(a)

Oh I forgot the ab at the end

[ivory badge]

if there's a * there isn't necessarily even 1

[whole chasm]

Same with b?

bab would go through no loops on the b path

[ivory badge]

I'd write the bottom path on number 3 as $b(b)^*a(a)^b(a|b)^$

[vital dew]

Darkrifts:

[whole chasm]

Right

[ivory badge]

where the | denotes a kinda OR operation, though it's notated differently sometimes

also, you want to do the top path too

[whole chasm]

Yeah

Was just checking

Just posting to see again I put my book away lul

[ivory badge]

lmao

[whole chasm]

So top path would be a(a) * b(b) *a(a|b)

[ivory badge]

(a|b) would also get *'d but yeah

[whole chasm]

right

[ivory badge]

also don't forget the option of doing absolutely nothing at all is valid, if I'm reading it right

[whole chasm]

It is not helpful that this bus driver is driving like a maniac. Trying to focus on math but feel like I'm about to puke

[ivory badge]

so, you can write the whole thing as $(\varepsilon | a(a)^*b(b)^a(a|b)^ | b(b)^*a(a)^b(a|b)^)$ or $(a(a)^*b(b)^a(a|b)^ | b(b)^a(a)^b(a|b)^)^$ since both expressions are accepted by the same machine, though the expression on the right which doesn't explicitly mention $\varepsilon$ is not exactly the minimal way to describe it

[vital dew]

Darkrifts:

[ivory badge]

all in all, writing that one out symbolically is disgusting but whatever

[whole chasm]

Right

This question about the automata

Is b

Right?

[ivory badge]

yes

[whole chasm]

This thing scares me though lol, it's last semesters exam for the same course I'm taking

Thanks for the outline though. ^^ Really helpful

[ivory badge]

aight

[solar oracle]

Hey I'm new to learning discrete math so I'd appreciate if someone could help me with some set notation. I understand it when applied to a given set or inequalities but I'm having trouble with more abstract questions.

I understand the general form is {x | p(x)} but how do I apply it for (x,y) and the standard equation for a straight line?

[slender skiff]

Mathematical induction

if P(k) = 1+6+11+16+...+(5k-4) and
P(k+1) = 1+6+11+16+...+(5k+1)

Making the next to last explicit would result in:

1+6+11+16+...+(5k-4)+(5k+1)

Is this correct?

[stray reef]

you say P(k) = 1+6+11+16+...+(5k-4) and then you say P(k) = (5k-4)

...

[slender skiff]

That was dumb

removed it

Since P(k) is 1+6+11+16+...+(5k-4)

and P(k+1) is P(k+1) = 1+6+11+16+...+(5k+1)

making it next to last explicit

it must be 1+6+11+16+...+(5k-4)+(5k+1)

[stray reef]

i mean... really you shouldn't be using this notation for sums at all tbh

write $P(k) = \sum_{j=1}^k (5j-4)$ and there won't be any ambiguity

but yes

[vital dew]

Ann:

[slender skiff]

$1+6+11+16+...+(5k-4)+(5k+1)$

wow

cool

[stray reef]

\cdots

[slender skiff]

$1+6+11+16+\cdots \cdots \cdots+(5k-4)+(5k+1)$

[stray reef]

$1+6+11+16+\cdots + (5k-4) + (5k+1)$

[vital dew]

Ann:

[slender skiff]

oh

i see

\cdot is one

[stray reef]

yes that's the dot for multiplication

[slender skiff]

I'm confused whats with the square brackets?

[stray reef]

here they're identical to parentheses

[weary tiger]

@stray reef you should use $\ldots$ not $\cdots$

[vital dew]

Timbre:

[stray reef]

huh?

no, i'm pretty sure $\cdots$ is more appropriate there.

[vital dew]

Ann:

[weary tiger]

@stray reef why?

[stray reef]

because it's between two + signs?

$1 + 2 + \dots + n$

[vital dew]

Ann:

[stray reef]

$1, 2, \dots, n$

[vital dew]

Ann:

[weary tiger]

@stray reef oh

I always use ldots

But that makes sense actually

[stray reef]

you don't need to ping me in every message >.>

[weary tiger]

Soz bruh

[stray reef]

and don't call me "bruh"

[weary tiger]

Ok bruz

[stray reef]

...

-.-

[wintry rock]

anyone know of a discrete structures (for cs majors) text book that isn't confusing as hell

and has more examples and doesn't have nothing but walls of text

[pale epoch]

less confusing and more examples than what?

[wintry rock]

Err not really sure how to be specific, the text I have now is ("Discrete Mathematics for Computer Scientists" by Stein, Drysdale and Bogart). But it could be one that you think is easy to comprehend in general i guess

[pale epoch]

i just wanted to know what topics it covers to see if i know a better alternative

can't really seem to find a table of contents though

[weary tiger]

No felions eat tomatoes

All cats are felions

Therefore no cats eat tomatoes

Is true right

Pls

@stray reef

[stray reef]

why was i pinged

[weary tiger]

I have a question

[stray reef]

no, why was i pinged

i'm not even a helper

you're just pinging a complete stranger

[weary tiger]

Thought u were smart

[opal crescent]

wait ur not a helper

goddem

ah yeah

[slender skiff]

@weary tiger It makes sense.. No felions eat tomatoes All cats are felions Therefore no cats eat tomatoes

[weary tiger]

Help

O

[clever nacelle]

An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately, they don’t know which one. To make matters worse, the poison the spy used was very deadly; just one drop diluted even a billion to one will still kill someone. Even so, the poison works slowly; it takes a full month for the person to die. Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expending at most O(log n) of his tastetesters.

Soooooo if it takes 1 month. Is there really a way to know?

[faint narwhal]

Yes

Try to find any solution at all

Don't worry about the bound

[clever nacelle]

I am so confused, I do not know where to start

[faint narwhal]

Think

[sour arrow]

Pretty easy way to figure out, but it will kill n-1 taste testers

[clever nacelle]

I think I am getting caught up on the month. And also the fact I am very new to complexity

To mee you would need as many tasters as bottles

Or you can split the poison

[stray reef]

split the poison yes

[clever nacelle]

So you are killing more but using less

[stray reef]

for example, with 64 bottles, you can make do with 6 tasters giving each one a very specific mix of the bottles' contents

[clever nacelle]

Sorry I had to drive. But I think I got it. I'll draft up my reply

[clever nacelle]

So splitting it into binary would make it 2^n, Is there an example where using log n would work?

[faint narwhal]

why 2^n?

[clever nacelle]

oh wait. n represents the number of bottles.

Silly me

2^10=1024, therefore, log 1028 = 2, sub 1028 with n to represent any bottle, log (n)

[faint narwhal]

yeah

roughly

If you want to be careful, you have to argue the case for all n, not just when n is a power of 2

and show that it's still O(log n)

[clever nacelle]

also wouldn't it be n-1 as said above, if I have 3 testers, I can only test 7 bottles right?

not 8

[faint narwhal]

why is that?

[clever nacelle]

I guess no one could drink the 8th one, and if no one dies you know it is the 8th one

But to get the binary representation of 8 you would need 4 different samples. That was my thought.

Sorry for making this so difficult.

[weary tiger]

hey can anyone help me with this question?

I have tried (2^8 -2^4), 12 choose 8, 12 choose 8 - 2^4

[last sigil]

Why did you try those? What is the reasoning?

[weary tiger]

well I didnt it think its was 2^8 - 2^4 i just that cause I was desperate but I tried the other one because I know you have total 12 elements with 8 choices 5 - 12 but you can choose 1 - 4 so that why I minues 2^4

the resaon I didnt think it is 2^8 - 2^4 is because none of the other similar questions are like that

[last sigil]

Hmm so there is a big simplification you can make here and you are also messing up the definition of a subset

A subset doesn't need to be the same number of elements as the set

[weary tiger]

it can me the same or less

no?

[last sigil]

{a} is a subset of {a,b}

[weary tiger]

a proper subset is always less tho

wait....

[last sigil]

Tell me your answer when you think you got it

[weary tiger]

{a} is a subset of {a,b} isnt that wrong

[last sigil]

Why?

[weary tiger]

if that was true if it was like this {{a},b}

in this case you can say

a is a subset of {a,b}

not

{a} is a subset of {a,b}

[last sigil]

Mb on the notation

Okay so what numbers can you absolutely not have

[weary tiger]

1,2,3,4

cause 5 has to be the smallest integer

[last sigil]

So find the number of subsets of the set without those numbers

[weary tiger]

without those number isnt it 256

2^8

[last sigil]

Minus the full set of you want proper ones

[ivory badge]

{a} is a subset of {a, b}

{{a}} is not

[weary tiger]

i never said {{a}} is

[last sigil]

That would be a set of a set correct?

[ivory badge]

not that it matters, but yes

a may or may not be a subset of {a, b}, but it isn't in general

[weary tiger]

the full set?

is that the minus 1 you do because you dont want to include the empty set

[ivory badge]

also, you not only need the number of sets without 1, 2 ,3 ,4 in them

[last sigil]

No you mentioned proper subsets before

[ivory badge]

hint: 5 is the smallest in it

[weary tiger]

yes so I dont need 1,2,3,4

[ivory badge]

but you need something else to better refine your numbers

[weary tiger]

dont I need to like take em ouyt or something

[ivory badge]

yes, they have to not be in there

but remember, {7, 8} does not fulfill the criteria

[last sigil]

Ah good catch I would've messed you up

Ty darkrifts

[weary tiger]

why doesnt 7 and 8 fill the criteria?

they are bigger than 5

[last sigil]

Reread question

[ivory badge]

5 must be the least

think about why it's not the least element of your set {7, 8}

[weary tiger]

I am so lost sorry guys

[ivory badge]

it has to have 5 in it

{5, 7, 8} is good, {7, 8} is notr

[weary tiger]

oh I didnt think you were talking about that I thought you were trying to say that because some things 7,8 cantr be with 5

[ivory badge]

no, has to have 5

enjoy, and have fun fumbling about

||2^7||

[weary tiger]

thanks I will try

!!!

[clever nacelle]

Hey, I have this problem: (n + 1)^5 is O(n^5), I was actually provided the solution, but I do not understand the proof or why it is relevant. Can someone please point me in the right direction, either a text or video on the concepts I need to understand to solve this on my own?

[faint narwhal]

What don't you understand about the proof?

[stray reef]

can you post the proof here and tell us what part(s) you don't understand?

@clever nacelle

[clever nacelle]

Any of it. I do not understand why they are converting it to n^5, 5n^4 ... +1 and what that proves

[stray reef]

ok so like you know the definition of "f(n) is O(g(n))" right

[clever nacelle]

Right. O(g(n))= {f(n): 0<= f(n) <= cg(n) for all values n > n_0}

[stray reef]

ok uh

no

first off nobody's requiring f (or even g) to be nonnegative, even if that's often the case in practice

and second, f(n) is O(g(n)) if there EXISTS a constant c and a number n_0 such that |f(n)| ≤ c|g(n)| for all n > n_0

really a proof of f(n) being O(g(n)) mostly boils down to finding a pair of c and n_0 that works

[clever nacelle]

3. Show that (n + 1)5 is O(n5)
   Proof:
   Binomial Expansion,
   X5+5x4+103+10x2+5x+1, we will use the coefficients as constants to n5
   | n5 + 5n5 + 10n5 + 10n5 + 5n5 + 1n5 | = | 32n5 |
   32n5 Is apart of O(n5), and when n >1 it is greater than (n + 1)5

Does that make sense?

That is how I am understanding it

[craggy gale]

you don't really explain what you're doing, and it's mega hard to read

[clever nacelle]

Because of the exponents or because my logic sucks?

[craggy gale]

because of the exponent and because your "proof" goes like

"I write some calculations without explaining and magically conclude the right answer"

[stray reef]

both

[craggy gale]

that goal of a proof is to be convincing

[clever nacelle]

Because I do not understand myself why those constants can be used.

I understand, I need to show that I can apply a constant that is in the set of O(n^5)

[stray reef]

that doesn't make any sense

[craggy gale]

what do you think O(n^5) means?

[stray reef]

honestly i prefer to use the fact that f is O(g) iff f/g is bounded on some rightward ray provided g doesn't hit zero too often

[clever nacelle]

My understanding is that big-o is showing the behavior of n^5, used to describe the complexity. I am proving the behavior of (n+1)^5 is the same.

That is my understanding...

[craggy gale]

that's quite vague

how can you hope to show something is O(something) if you don't have a clear idea of what O() means?

[clever nacelle]

Okay. Just so you can understand my background on this, my professor is 70 years old and a horrible lecturer, she writes here own textbooks that do not even use exponents correctly and are extremly hard to read. My previous math background is calc 1 &2 with a 7 week course in discrete math for basic proofs, graph and set theory. We have had one lecture on this materiel and she jumped into it like we should already understand it (yesterday). I have no clue what I am doing, I have reviewed a few youtube videos and read a few texts about big O, and I felt like I understood it, but clearly not good enough to do this problem. This is due tomorrow, and I would be happy to watch or read any resources you may have to help me understand this instead of making myself look like a complete idiot here.

[craggy gale]

Have you ever seen something that looked like a definition?

because this is what you need right now

definitions

[clever nacelle]

https://xlinux.nist.gov/dads/HTML/bigOnotation.html is what I am using

[craggy gale]

the Wikipedia article about this is a bit of a mess, but it's got enough info

ewh, this page has a bit of an archaic look

if the Formal Definition part is what your teacher wants you to use, then you should focus on it

it's not the best definition, but it does the job in the particular case of your exercise

[arctic blaze]

someone today told me that weak induction implies strong induction, how does that work?

like i can see the other way around

so yeah, halp

[pale epoch]

you can use weak induction to prove the claim of strong induction

[faint narwhal]

Using weak induction to prove P(n), you assume P(k) and prove P(k+1)

You can instead create a new statement Q(n)

Which is the statement that P(k) is true for k <= n

Then, doing weak induction on Q(n) is the same as doing strong induction on P(n)

[arctic blaze]

thats pretty neat

thanks for the help

[rich viper]

How can you prove that if p is prime, then (p−1)!≡ −1 (modp)?

[stray reef]

that's called wilson's theorem, is it not

or at least that's one part of it

[rich viper]

yeah it is

[stray reef]

uh

i guess use the fact that if p is prime then everything besides multiples of p has an inverse mod p

[rich viper]

I kinda understand it. It involves with congruence modulo and relations. I can't figure out a good way to explain it

[stray reef]

oh and you need p > 2

well ok i guess it still works for 2 but the argument i've seen doesn't

[rich viper]

ok

[reef thistle]

argh

crossposted

pair up elements with their multiplicative inverse

[rich viper]

my badd

[reef thistle]

Okay, pairing elements would leave 1, and p-1 behind and pair up everything else.

Can you show that?

[rich viper]

so yeah pairing the integers up: I was pairing (2, 3, 4, ..... p-2)
Leaving 1 and p-1 since they have their own inverse

[reef thistle]

okay

we just need to show that a pairing exists, we don't need to explicitly find it

[rich viper]

yeah

oh you mean just use an actual number example to show it's true?

[reef thistle]

NO

don't use an example

you need to show a pairing exists in ALL cases

example is okay to get intuition but not as a proof

unless the question is "show that there exists (an example)..."

[rich viper]

no it's prove

[reef thistle]

yeah, so you need to show it in all cases

[stray reef]

we just need to show that a pairing exists, we don't need to explicitly find it
why not find it explicitly though? (·)^-1 is not only a bijection but is its own inverse as a function

and there's an even number of integers between 2 and p-2 inclusive

which naturally organize themselves into pairs

[rich viper]

thats what I'm having difficulty with: to explain in sentences and proving it

[reef thistle]

you need to show that the pairs don't intersect

you can treat it as the pairs forming equivalence classes

[stray reef]

i mean ok introduce an equivalence relation making two elements related if they're either the same or inverses of one another

[rich viper]

can I just prove that if such two integers x, y between 1 and p-1 are inverse of each other mod p then the theorem holds true?

actually between 2 and p-2

since 1 and p-1 are left alone

[reef thistle]

if any two integers, then yeah

[rich viper]

like xy = (p-1) is congruent to 1 mod p

[reef thistle]

???

[stray reef]

...

[reef thistle]

I am confused what you wrote there

[rich viper]

im unsure what to write to prove that two integers are inverses of each other so (p-1)! holds true

[stray reef]

...

are you even reading your own messages bc this makes 0 sense

[rich viper]

I just dont know how to explain it

[stray reef]

I kinda understand it.
then this is a lie

[reef thistle]

all you need to do is to be able to pair up 2 to p-2, via inverses, where if x and y are paired, xy=1 (mod p), so that you can show the product of all these is 1

[mint salmon]

I'm trying to figure out how to specify sets properly. at this point in my class, I'm still "supposed" to use naïve set theory. no matter what I write, it still seems like it's not clear what I'm trying to say. I want to define P as the set of all primes. This is what I have so far: Pₙ := {n∈ℕ | There exists (x > 1)∈ℕ such that ¬(ⁿ/ₓ)}

but first of all, I've already included some symbols such as \in and \not

[tranquil cargo]

p = x | x is prime

lmao

[mint salmon]

are you allowed to specify an element the way that I did, with parentheses showing that there is another constraint? or should it be more like this: {Pₙ := {n∈ℕ, x∈ℕ | x > 1 ∧ ¬(ⁿ/ₓ)}}

[tranquil cargo]

not(n/x) is meaningless

u can say

x | x has no divisors but itself and 1

[mint salmon]

I know that you can write that, but the point of the exercise is to practice writing the constraints

[stray reef]

what did you even want to say with "n/x"

[mint salmon]

I want to write "n cannot be divided by x"

[pale epoch]

n can surely be divided by n though

[mint salmon]

and I want to write that n is an element of the set of prime numbers and x is an element of the natural numbers, where n cannot be divided by x

ok true

@pale epoch

[pale epoch]

what did you do for a

[mint salmon]

Tₙ := {n∈ℕ | Es gibt x∈ℕ\{0} mit ⁿ/ₓ}

[pale epoch]

this already makes little sense

[mint salmon]

that's what I thought too

but I don't know what I should write instead of that

[pale epoch]

well, can you explain with words what the set $T_n$ is

[vital dew]

Lochverstärker:

[pale epoch]

(it's already written in the question, basically)

[mint salmon]

it would be the set of whole numbers that can divide n

positive whole numbers

[pale epoch]

ok, yes

so $T_n$ ist die Menge aller Teiler von n

[vital dew]

Lochverstärker:

[pale epoch]

wie ist ein Teiler definiert

Ein Teiler von n ist eine Zahl x, so dass...?

[mint salmon]

reden wir strikt von natürlichen Zahlen? wenn schon, würde ich etwas wie "Ein Teiler von n ist eine Zahl x, so dass die Ergebnis von n/x wieder einen natürlichen Zahl ist." sagen.

[pale epoch]

ja

ok

Die Menge $T_n$ ist jetzt die Sammlung aller natürlichen Zahlen $x$, die diese Eigenschaft haben

[vital dew]

Lochverstärker:

[pale epoch]

Oder in Mengenschreibweise: $T_n = { x \in \mathbb{N} \mid \frac{n}{x} \in \mathbb{N}}$

[vital dew]

Lochverstärker:

[pale epoch]

makes sense?

[mint salmon]

yeah that helps

[pale epoch]

you can now use T_n to solve (c)

i.e. if p is prime, then you know something about T_p

[mint salmon]

$T_p = { x \in \mathbb{N} \mid \frac{p}{x} \notin \T_p}$

[vital dew]

clockworkmurderer:

$T_p = { x \in \mathbb{N} \mid \frac{p}{x} \notin \T_p}$
```Compile error! Output:

! Undefined control sequence.
l.11 ... \in \mathbb{N} \mid \frac{p}{x} \notin \T
_p}$
The control sequence at the end of the top line
of your error message was never \def'ed. If you have
misspelled it (e.g., \hobx'), type I' and the correct
spelling (e.g., `I\hbox'). Otherwise just continue,
and I'll forget about whatever was undefined.

Preview: Tightpage -327680 -327680 327680 327680
[1{/usr/local/texlive/2018/texmf-var/fonts/map/pdftex/updmap/pdftex.map}]

[mint salmon]

ok I'm out of practice with LaTeX

[pale epoch]

well, as long as i understand you idc if you latex

[mint salmon]

I'm practicing it anyway because my handwriting is so bad

but I would guess that you can't actually use T_p within its own definition

so my idea is probably wrong

[pale epoch]

yeah

what is your definition of a prime number

[mint salmon]

this is what I was trying to write: Tₚ := {x ∈ ℕ|ˣ/ₚ ∉ Tₚ}

but anyway. a prime number is a number which can only be divided by 1 and itself

[pale epoch]

is 1 a prime number then?

[mint salmon]

also "Ein Primzahl ist einen natürlicher Zahl p, so dass p nur mit sich und mit eines geteilt werden kann."

darum wird's gestritten. Ich bin glaub ich noch nicht so weit, die Frage zu beantworten...

[pale epoch]

ok, so we do not want 1 as a prime number

for reasons that are probably not important right now

so we will define a prime number as a number that has exactly 2 divisors

1 and itself

this way 1 will not the prime

also notice that every number n can be divided by 1 and n

because n/1 = n and n/n = 1

so if a number has exactly 2 divisors, it must be prime

that means n is prime if and only if |T_n| = 2

and you can use that to define your set of prime numbers

[mint salmon]

Darauf wäre ich nie gekommen. Also den Betrag von einer Menge darf auch als eigenschaft verwendet werden...

[pale epoch]

you can use anything

[mint salmon]

yeah I sort of just realized that

[pale epoch]

you could also say n is prime if and only if T_n = {1, n} and n>1

but well, that's not as aesthetically pleasing

to me, anyways

[mint salmon]

$T_p = {p \in \mathbb{N} | p \in T_n \land |T_n|}$

[vital dew]

clockworkmurderer:

[mint salmon]

damn

[stray reef]

\{ ... \}

[mint salmon]

$T_p = { p \in \mathbb{N} | p \in T_n \land |T_n| = 2 }$

[vital dew]

clockworkmurderer:

[pale epoch]

also you are thinking way too complicated

you already defined T_p in a

it's the set of all divisors of p

so for prime numbers you should probably use a different symbol

(if you are trying to define the set of all primes)

[mint salmon]

in a the symbol is T_n though

[pale epoch]

n is a variable, you can use whatever

also in your set, using T_n makes no sense

because n is not defined

so it's impossible to know what T_n is

[mint salmon]

I thought that you can use sets that you defined previously within a new set you want to define

[pale epoch]

yes, you can

but it's not cleat what T_n is supposed to be

because n is not defined

[mint salmon]

so in that case I would just use T instead of T_n and instead of T_p the set could be called anything else like K_p?

[pale epoch]

what is T supposed to be?

the T_n in (a) is only defined for a specific n

you can think of it like a function, maybe

you give it a number n as input and the output is the set of its divisors

so T_2 = {1,2}

T_6 = {1, 2, 3, 6}

but just writing T_n without knowing what n is, makes no sense

how are you supposed to know if p is in T_n, if you do not know what n is

[mint salmon]

I understand what you're saying. but I don't understand how I can use the set from (a) in the answer for (c) if using T_n causes confusion. There should be no upper limit for the set of prime numbers, meaning that if I use some specific n (a known prime number for instance) the set definition still makes no sense

so what about this; I set the symbol M to be defined as the set T_n as defined in (a)

and then use M instead

[pale epoch]

then it will still not be clear what the set M is

because it still depends on n

so

i am not sure if i can help you further to get to the solution

i can give you the solution and explain it

and you sleep over it and think about it again tomorrow

or you can sleep over it without knowing the solution and possibly ask someone else again tomorrow

what do you want?

[mint salmon]

well for this particular case it's alright; I'm working on the problems that will be discussed during the Übung on wednesday. so if you tell me the answer today it's not like cheating on homework because I'll get the answer on wednesday anyways.

so you can tell me the answer and maybe it will help me do the next problem anyways

[pale epoch]

personally i wouldn't care if you cheated on your homwork

it's your personal decision

so, as i said above

and as you agreed

$n \in \mathbb{N}$ is prime if and only if $\lvert T_n \rvert = 2$

[vital dew]

Lochverstärker:

[pale epoch]

so if it has exactly 2 divisors

now you can use that to define the set of prime numbers $\mathbb{P}$ as

[vital dew]

Lochverstärker:

[pale epoch]

$\mathbb{P} = {n \in \mathbb{N} \mid \lvert T_n \rvert = 2}$

[vital dew]

Lochverstärker:

[pale epoch]

i.e. all natural numbers, that have exactly 2 divisors

[mint salmon]

alright. so is it "implicit" what T_n means if you write it like that?

[pale epoch]

i get the definition from (a)

[mint salmon]

so the problem that I had was that I was trying to define another symbol p which is first of all unnecessary because based on (a) any number that p could be mapped to was already mapped out by T_n

and second of all messed up my definition because n was not defined anywhere

[pale epoch]

in your definition it would be impossible for me to check if a number, lets say 7, is prime

go ahead and try it

you would have to test if $7 \in T_n$ is true or something like that

[vital dew]

Lochverstärker:

[pale epoch]

but you don't know what n is

so you can't do it

in my solution everything is clear

if you want to know if $7$ is prime you just look at $T_7$

[vital dew]

Lochverstärker:

[pale epoch]

notice that $\lvert T_7 \rvert = \lvert { 1, 7} \rvert = 2$

[vital dew]

Lochverstärker:

[pale epoch]

so yeah, 7 is indeed prime

[mint salmon]

👌 thanks for your help!

[elfin lagoon]

Can a term in product notation ever be equal to 0?

pi notation

[faint narwhal]

Why not

[stray reef]

yeah why not

[arctic blaze]

so i have to prove that there are countably infinite number of programs

that doesnt make sense to me

wont there be a finite number of programs, provided we have a finite number of characters

and only a finite number of permutations from those characters

well i said something very dumb here

i realize that now :/

[obtuse lance]

gate keeping your question only hurts you

[neat siren]

Anyone know chernoff bound?

[faint narwhal]

What's your question

[rich condor]

What does it mean for a graph to be Euclidean but not hamiltonian ?

;-;

[reef thistle]

Hamiltonian is "there is a cycle passing through all the vertices"

Euclidean means "this is a weighted graph and we can assign a point on the plane to each vertex so that the weights are distances between points"

@rich condor

So, "this is a weighted graph and we can assign a point on the plane to each vertex so that the weights are distances between points, but there no cycle passing through all the vertices"

[rich condor]

ah @reef thistle cycle means that you can traverse the vertices exactly once right

[reef thistle]

each vertex appears exactly once (until you reach where you started), yes

[reef thistle]

Eulerian, not Euclidean

@rich condor

[rich condor]

oh crap

thanks for noticing that

@reef thistle for a eulerian graph, the degree of the vertices have to be even ?

while a humailtonian the degree of each vertex can be odd or even ?

[reef thistle]

yeah

Hamiltonian, by the way

[static pagoda]

basic discrete noob here

how do you prove something is irreflexive

like lusts just take an easy problem like a>b

[rich condor]

@reef thistle thanks!

[reef thistle]

Reflexive is aRa for all a

@static pagoda

Irreflexive is (a, a) not in R, for all a

@static pagoda

[static pagoda]

I get that but I'm not sure how to show it in a proof @reef thistle

[rich condor]

Rip man T.T

are u cs as well ?

[static pagoda]

ye

discrete math is kicking my ass and its only the first class

[rich condor]

okay im bad at discerte as well but i may know a little bit of what im saying lol

https://en.wikipedia.org/wiki/Reflexive_relation

Jump to Examples

They have examples of reflexive and irreflexive

[static pagoda]

This is how our teacher wants it to be done

Not really sure how to do that tho

For ireflexive

[rich condor]

Okay do you understand

what ur teacher did

?

for that note

[static pagoda]

yep

the og problem was for when x divides y

[rich condor]

maybe u can tell us the problem

or a problem set

for irreflexity

and someone can help

[static pagoda]

yeah i was trying to do a>b in that form but had no clue how for irreflexive lol

our teacher skips a lot for my class its annoying -_-

[reef thistle]

@static pagoda clearly, a>a is false for all a, so (a, a) not in >.

Just state this unless they give a definition for >.

[static pagoda]

Ya thats probably all that will be needed

Thank you @reef thistle and @rich condor

[rich condor]

i didnt do anything

lmao

@static pagoda

[vestal isle]

Quick question, can this problem be solved using combinatorix? https://leetcode.com/problems/beautiful-arrangement/

it really feels like you can solve this using only math

[reef thistle]

@vestal isle O(N2^N) solution can be found easily

[vestal isle]

I meant a constant time, constant space solution

kind of like to the fibonnacci sequence

[reef thistle]

idk if it exists

[atomic sapphire]

Guys quick question, there are actually warshall algorithms that when used, is still possible to still have 0's in the adjacency matrix when it's finished right?

Wait nvm I just answered my own question lol

It can still have 0's at the end

[vital dew]

HeeysamH:

[slender skiff]

^

Since (k+1) is bigger then 3 we can say:

$k! * (k+1)$ \
and then
$(k+1)!$
QED

[vital dew]

HeeysamH:

[pale epoch]

why is 3^k * 3 = k! * 3

also what you mean by "we can say"

what follows is not a statement that you can assign a truth value to

[weary tiger]

Is this just n1 or n2 to leave and then to come back the following day it must be n4 right?

Because if you stay the afternoon in Washington then it goes against the rule saying to return the following day

But I'm prob doing this wrong as it's asking for pairs of flights

Any help is appreciated

[slender skiff]

I'm a bit confused what does "Give iterative and recursive algorithms for the nth term of the sequence
defined by" is it a programming algorithm or?

[reef thistle]

iterative, i.e. a loop

recursive, i.e. a function that calls itself (or a function that uses itself in the definition)

@slender skiff

[olive dragon]

Hello, could someone please help me with this question? Thanks

I don't understand how this works:
a[0] = 2[0]+a[0-1] = 2

a subscript 0-1 that is

[stray reef]

the recurrence does not apply for n=0

it says right there, "for $n \geq 1$"

[vital dew]

Ann:

[stray reef]

$a_0$ is defined separately

[vital dew]

Ann:

[olive dragon]

Well they asking me for a1 to a3 but how did they get 2 for a0 its confusing

[stray reef]

they didn't

it's part of the data

[olive dragon]

Okay

Then I would have to start from a[1] which would be:
a[1] = 2(1) + a subscript 1-1

what does the part "a subscript 1-1" mean though?

[stray reef]

$a_{1-1}$ is $a_0$.

[vital dew]

Ann:

[stray reef]

because yknow

1-1 = 0

[olive dragon]

Okay, then this would be:

 a[1] = 2(1)+2 = 4

and then:

a[2] = 2(2)+4 = 8

a[3] would be:

a[3] = 2(3)+8 = 14

Thank you @stray reef now I understand it

[olive dragon]

Could someone please explain how this works? thanks

Instructions say to "Find the values of each of the sums"

Does it mean that for each i there is j?

[stray reef]

...no?

[olive dragon]

(1-1)+(1-2)+(1-3)+(2-1)+(2-2)+(2-3)+(3-1)+(3-2)+(3-3)

[stray reef]

yes it's like this

[mint salmon]

well doesn't the sigma notation just mean that you count from the number below to the number above?

ok yeah

like you said

interesting though

I've never seen that kind of problem before, where there are two sigmas next to each other and an "argument"

[olive dragon]

so the total summation is just 0

[pale epoch]

you can think of it as two nested for loops

if you know some programming

[mint salmon]

that's what I was imagining when I saw it

[olive dragon]

same, first time encountering such problems

[mint salmon]

(int i = 1; i <= 3; i++)

this is how I read it...

[olive dragon]

Yeah, programming is involved with my class, it makes sense that way I guess

[mint salmon]

I'm glad you're here Lochverstärker

[pale epoch]

s=0 for int i=1 to 3 for int j=1 to 3 s += (i-j)

[mint salmon]

I'm trying to prove this statement Zu zeigen: Für alle Mengen $M$, $N$ und $P$ gilt: Aus $M \subseteq N$ und $N \subset P$ folgt $M \subset P$.

[vital dew]

clockworkmurderer:

[pale epoch]

that's how i would explain it to my students

[mint salmon]

but I can also wait, I don't want to hijack the discussion

[pale epoch]

well, what have you tried

[mint salmon]

my thinking is that I can just use the definitions of the symbols ⊆ and ⊂

[pale epoch]

there isn't really much else you can do

[mint salmon]

but now I just don't really know whether I'm going about it correctly.

if I say this: Die Aussage $M \subseteq N$ gilt genau dann, wenn für alle Objekte $a$ aus $a \in M$ folgt $a \in N$.

[vital dew]

clockworkmurderer:

[mint salmon]

wie kann ich zeigen, dass a überhaupt in den beiden Mengen enthalten ist?

genügt es, dass der Symbol so definiert wird?

[pale epoch]

naja, du nimmst ja das a aus M

also ist es in M

und per definition von $\subseteq$ ist es dann auch in N

[vital dew]

Lochverstärker:

[mint salmon]

ah.

so einfach geht das...

[pale epoch]

also um das zu zeigen nimmst du halt ein beliebiges a aus M

und zeigst, dass es in P ist

für $M \subseteq P$

[vital dew]

Lochverstärker:

[mint salmon]

also sobald man gezeigt hat, dass a auch in N enthalten sein muss, darf man dies als Annahme fürs nächste teil der Beweis einfach so nehmen?

[pale epoch]

ja, hast du ja gezeigt

deine annahme ist a in M und alles was daraus folgt, kannst du dann natürlich weiter nutzen

[mint salmon]

ok gut. Ich begriffe die Sache endlich ein bisschen

Zu zeigen: Für alle Mengen $M$, $N$ und $P$ gilt: Aus $M \subseteq N$ und $N \subset P$ folgt $M \subset P$.\
Beweis:
\begin{enumerate}
\item Die Aussage $M \subseteq N$ gilt genau dann, wenn für alle Objekte $a$ aus $a \in M$ folgt $a \in N$. Per Definition der Symbol $\subseteq$, für ein beliebiges $a \in M$, folgt $a \in N$.
\item Die Aussage $N \subset P$ gilt genau dann, wenn für alle Objekte $a$ aus $a \in N$ folgt $a \in P$. Per Definition der Symbol $\subset$, für ein beliebiges $a \in N$, folgt $a \in P$.
\item Dadurch wird es gezeigt, dass $a \in M$ auch in $P$ enthalten ist. Also gilt $M \subset P$.
\end{enumerate}
\hfill $\square$

[vital dew]

clockworkmurderer:

[mint salmon]

bin ich überhaupt auf dem richtigen Spur?

[pale epoch]

nunja, es ist richtig

außer dass die definition in 2. nicht stimmt

und die folgerung in 3 nicht ganz

$A \subset B$ genau dann wenn $A \subseteq B$ und $A \neq B$

[vital dew]

Lochverstärker:

[pale epoch]

du hast gezeigt, dass $a \in M$ auch in $P$ enthalten ist, also $M \subseteq P$

[vital dew]

Lochverstärker:

[pale epoch]

jetzt brauchst du noch ein Element in P, dass nicht in M ist

[mint salmon]

ok, geht einfach vermute ich. Def. der echte Teilmenge, darf x in P nicht in N auftauchen und analog nicht in M

da N nicht gleich P ist

[pale epoch]

jo

mit dem formulieren musst du bisschen aufpassen

weil einmal wählst du ein a in M beliebig

und einmal wählst du ein x aus P, dass nicht in N ist (das ist insbesonder nicht beliebig, sondern existiert nur nach der Def von echter teilmenge)

[mint salmon]

wie lautet sowas dann konkret richtig?

weil ich weiß, dass Quantoren die Sache aufklären, aber ich "sollte" die noch nicht verwenden

noch eine Frage, da ich jetzt auch die Problem mit der Logik erkenne: ich will ja zeigen, dass M nicht gleich P ist. Da würde es auch reichen, nur einen Element in P zu zeigen, die nicht in M vorkommt

aber wie schreib ich das, ohne meine Behauptungen kaputt zu machen?

[pale epoch]

quantoren sind generell nur abkürzungen

das kann (und sollte man) mit worten sagen in einem mathematischen text

Da würde es auch reichen, nur einen Element in P zu zeigen, die nicht in M vorkommt

genau das brauchst du

du musst $N \subset P$ nutzen, also weißt du, dass es ein element in $P$ gibt, dass nicht in $N$ liegt

[vital dew]

Lochverstärker:

[pale epoch]

und damit dann weiter argumentieren

[mint salmon]

\begin{enumerate}
\item Die Aussage $M \subseteq N$ gilt genau dann, wenn für alle Objekte $a$ aus $a \in M$ folgt $a \in N$. Per Definition der Symbol $\subseteq$, für ein beliebiges $a \in M$, folgt $a \in N$.
\item Die Aussage $N \subset P$ gilt genau dann, wenn $N \subseteq P$ und $N \notequal P$. Per Definition der Symbol $\subseteq$, für ein beliebiges $a \in N$, folgt $a \in P$. Da $N \notequal P$ gilt, gilt es für ein $x \in P$, dass $x \notin N$.
\item Es gelte $x \notin N$ und $M \subseteq N$. Dann gilt soeben $x \notin M$ und $M \notequal P$. Insbesondere gilt $M \subset P$.
\end{enumerate}

[vital dew]

clockworkmurderer:
Compile Error! Click the reaction for details. (You may edit your message)

[mint salmon]

ok whatever

it compiles just fine on my computer

is notequal somehow not part of this compiler?

[pale epoch]

maybe you defined it

the standard would be $\not\equal$ i guess

[vital dew]

Lochverstärker:
Compile Error! Click the reaction for details. (You may edit your message)

[opal crescent]

it would be \neq

[pale epoch]

or equal doesnt exist

yeah, but you can in general preface stuff with \not for stuff like that

[opal crescent]

$\not = \qquad \neq$

[vital dew]

emeric75:

[opal crescent]

lel

[mint salmon]

it could be a part of a sublime text package I'm using

but \neq works just fine and it's easier to type anyway

I'm also using the xetex builder

at any rate, I'm tired of working on this for today. thanks for your help!

[weary tiger]

aye can anyone help me with understaidning this question a little more like right now my idea is to use contradiction to proof it if the contradiction is true then the statement is false ane I have supplied the counter example and if the contradiction ends up being contradictory then the statement is true and I have shown my proof

also not sure if this should be in here or in the proofs and logic

yes i know that is false but it says provide a counter example does that mean that like I have to prove the opposite statement is true?

[opal crescent]

just give an example with 3 sets A,B,C where you have A included in B, B not included in C, and A included in C

that's it

[weary tiger]

A = {1, 2, 3} B = {1, 2, 3, 4, 5, 6, 7, 8} C = {1, 2, 3. 4}

like this, this is all I do no proof?

[opal crescent]

p much

i mean you have to show that your example is indeed a counterexample

[weary tiger]

this way from my understanding B is not a subset of C but A is still a sub set of C

[opal crescent]

but that's fairly trivial here

[weary tiger]

okay okay that was simplier than I thought thank you!

[opal crescent]

👌

[weary tiger]

can anyone help me with f and h for f my inital thoghout was flase but the more I think about it the more confused I get and for h there is nothing in C compliment "intersect" D so I am confused

[tranquil cargo]

try writing them out

[weary tiger]

I use the venndiagram system my teacher taught me

so there is actually multiples of 4 in question h

from my understanding

since C compliment = {1, 3, 4, 5, 7, 8, ...}

and D has multples of 4 I could be wrong but this is how I see it

but I am not sure about B compliment now

does B compliment include C and D or nah cause the way my think works when i visualize it is throught venn diagrams

[tranquil cargo]

B compliment includes all integers not =8n for some integer n

integers that cannot be divided by 8

write some of its elements

and see

[weary tiger]

wait so C compliment cant have 4 in it?

[tranquil cargo]

is 4 divisible by 8

if yes then its C

if no then its not in C

[weary tiger]

wait I am confused

I am not talking about B compliment I am talking about C compliment

Can it have 4 in it

[tranquil cargo]

oh C

yea

4=2(2)

4=2n for some integer n

[weary tiger]

so C Compliment cant have 4 in it

[tranquil cargo]

yea

[weary tiger]

since B compliment can have anything divisble by 8 I am assuming C compliment cant have anything divisble by 2

[tranquil cargo]

yea thats according to its definition

C coitnans all integers that are equal to 2n for some integer n

means divisible by 2

contains*

[weary tiger]

therefore

C compliement "intersect" D have nothing right

[tranquil cargo]

well

[weary tiger]

because the set C compliment shares nothing with the set D

[tranquil cargo]

are all numbers divisible by 4 divisible by 2?

[weary tiger]

yes

[tranquil cargo]

therefore?

[weary tiger]

beacsue D = 4n

therefore they have nothing shared

since C compliment cand Have anything it in divisible by 2

so it only contains things like

1, 3, 5, 7, 9, 11, ...

[tranquil cargo]

yea

good job

[weary tiger]

thefore the C compliment "intersect" D is an empty set

does B compliment have empty set from my understadnign all sets have an empty set right?

[tranquil cargo]

the empty set is a subset of any set

but no

not all sets contain the empty set as an element

[weary tiger]

Oh it’s a subset okay okay makes sense thank you!!

[tranquil cargo]

np

anything elsee?

[weary tiger]

Coudl you give me some clairfication on this from my prespective question A means

A "subset of" B "union" C "subset of" D = C "subset B "intersect" D

here is the question

[tranquil cargo]

if A is a subset of B

and C is a subset of D

then A intersects D is a subset of B intersects D

whats giving you problems

[weary tiger]

like I need to prove that so i need to put in a equartion

so like is my equation correct

[tranquil cargo]

what equation

[weary tiger]

A "subset of" B "union" C "subset of" D = C "subset B "intersect" D

[tranquil cargo]

ok

[weary tiger]

basically I dont know what the statement means 😅

[tranquil cargo]

well

it means if A is a subset of B

C is a subset of D

then A intersects C is a subset of B intersects D

what can you not understand

you know the operation

intersect yea?>

[weary tiger]

then is a logical implication or logical equivalnece here

?

yeah intersects turns into AND right?

[tranquil cargo]

A intersects B = {x | x is in A and x is in B}

[weary tiger]

yes yes

sorry I didnt include the x in part but yeah

and

A union B = {x| x is in A or x is in B}

[tranquil cargo]

yea

so ok

now try taking an element

in A intersects C

and showing that its also in B intersects D

thats like

the sketch of your proof

[weary tiger]

but like is this = or only logical implication?

and

is the equation like

[tranquil cargo]

thats subset

https://media.discordapp.net/attachments/496785905474994186/638882019002023946/clairfy.PNG

[weary tiger]

I am talking about thw word 'then'

it is saying

If A is a subset of B and C is a subset of D then it is equal to A intersect C is a subset of B intersect D

am I right on what it is saying?

[tranquil cargo]

subset

not equal

[weary tiger]

okay from my understanding

lets say we had thr statment

[sour arrow]

"If A then B"
Is a logical implication.
A → B

[weary tiger]

okay so it only one way

makes sense

[sour arrow]

You can also take that to mean "subset"

[weary tiger]

for example if it was equal it would be

A subset of B and

B subset of A

type thing

[sour arrow]

Then A and B are the same set

Equal, yeah

[weary tiger]

but its a logical impliucation not logical equicalence so I dont need to prove backwords

only prove left hand side not right hand

I think I understand thanks!

[summer gull]

Can someone help me understand a reccurence relation problem?

I'm trying to even understand where to begin

I'm getting an answer but I'm not sure if i even handled it correctly. Truth be told I'm kind of confused on the different ways to do this all.

[sour arrow]

Can you write the recurrence for T(n/2)?

[summer gull]

Yeah, I got this... one sec. Excuse my LaTeX

(7^k)(T(n/2^k)) + (1/(4^(k-1)) * kn^2

@sour arrow

[sour arrow]

Where's the = sign? What's k?

Maybe you're a step ahead of me

[summer gull]

I might just be confused on how to even tackle these

sigh

[sour arrow]

If you write the recurrence in terms of T(n/2) instead, you can write:
T(n/2) = 7T(n/4) + (n/2)²

Which is the same thing as the question stated, just with n/2 subbed in. I hope you'll agree there's nothing complex there

[summer gull]

right yeah

that make sense, sub in n/2 as n because that's the easiest thing to sub in right?