#discrete-math | Mathematics | Page 122

sleek swallow Mar 12, 2020, 4:20 PM

#

I thought we shared something special. It seems not.

#

😄

tranquil jewel Mar 12, 2020, 4:22 PM

#

so if g o f is injective then g(f(x))= g(f(y)) right, so that means both the output are the same for f as well, well x = y I mean

stray reef Mar 12, 2020, 4:24 PM

#

so if g o f is injective then g(f(x))= g(f(y)) right
no

#

the definition of $g \circ f$ being injective is as follows:

vital dewBOT Mar 12, 2020, 4:24 PM

#

Ann:

📎 183668144404037632.png

stray reef Mar 12, 2020, 4:24 PM

#

$(\forall a_1, a_2 \in A)[(g \circ f)(a_1) = (g \circ f)(a_2) \to a_1 = a_2]$

vital dewBOT Mar 12, 2020, 4:25 PM

#

Ann:

📎 183668144404037632.png

stray reef Mar 12, 2020, 4:25 PM

#

A here is, of course, the domain of g . f

tranquil jewel Mar 12, 2020, 4:25 PM

#

Mhm

stray reef Mar 12, 2020, 4:26 PM

#

don't "mhm" me. i'm trying to point out that you left out crucial details

#

anyway w/e

#

you need to show that f is injective

#

that is, for any two points a_1, a_2 ∈ A, if f(a_1) = f(a_2), then a_1 = a_2.

#

you know how to prove if-then statements, right?

#

there's almost like a template. a standard opening line to write at the beginning of the proof of a statement of this form

#

or rather, you'd first write the standard opening line for the proof of a "for all" statement

tranquil jewel Mar 12, 2020, 4:28 PM

#

Yea I think

lyric pumice Mar 12, 2020, 4:41 PM

#

@fossil pewter Hi. Is the condition for an ith box applied to all boxes or a single box?

fossil pewter Mar 12, 2020, 4:42 PM

#

All boxes like first box should have atleast 1 ball
And 5th box should have atleast 5 balls

lyric pumice Mar 12, 2020, 4:46 PM

#

Alright.

weary tiger Mar 12, 2020, 8:32 PM

#

this correct?

📎 5f49e9221e1731cc85816c491f5d5586.png

#

since it can use all letters and letters can repeat its 7^7?

uneven mirage Mar 12, 2020, 9:10 PM

#

Let a[k] = 3k+2. Find the sum a[1] + a[2] + ... + a[200]. is the answer to this 60700? im not sure if im getting it correct

weary tiger Mar 12, 2020, 9:12 PM

#

@uneven mirage yes

📎 8fe6f656ef3b381757be3695f8fc4e42.png

uneven mirage Mar 12, 2020, 9:16 PM

#

@weary tiger ty what site is that?

weary tiger Mar 12, 2020, 9:17 PM

#

i just searched for a summation calculator

#

https://www.mathsisfun.com/numbers/sigma-calculator.html

Sigma (Sum) Calculator

Math explained in easy language, plus puzzles, games, quizzes, worksheets and a forum. For K-12 kids, teachers and parents.

uneven mirage Mar 12, 2020, 9:18 PM

#

awesome tysm

near prawn Mar 12, 2020, 9:40 PM

#

@weary tiger if letters can be repeated then yea

weary tiger Mar 12, 2020, 9:44 PM

#

if it cant be repeated then i'd just use the permutation formula?

weary tiger Mar 12, 2020, 10:09 PM

#

@near prawn

📎 8d31d8466fd1664358b9b8b89cc7ee6b.png

#

is this right?

#

2 * 7 * 7 * 7 * 7 * 5
since there are 2 vowels, and 5 consonants?

near prawn Mar 12, 2020, 10:10 PM

#

if repetition is allowed then yea

weary tiger Mar 12, 2020, 10:11 PM

#

thanks!

#

actually idek if they can be repeating

#

i might have read the directions wrong lmao

sleek swallow Mar 13, 2020, 3:10 AM

#

@uneven mirage There is a nice way to determine the general formula for that sum:

$\sum_{k=1}^{n} (3k+2) = \sum_{k=1}^{n} 3k + \sum_{k=1}^{n} 2 = 3 \sum_{k=1}^{n} k + 2n = \frac{3n(n+1)}{2}+2n$

vital dewBOT Mar 13, 2020, 3:10 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 13, 2020, 3:10 AM

#

Don't memorize it, of course. Just understand the general principles.

#

@weary tiger From what I can see, your string should make use of all 7 letters listed in the set. Furthermore, it should begin with a vowel and end with a consonant. The set of vowels in that given set is just {a,e}. Repetition is not allowed because you have to use all 7 letters.

weary tiger Mar 13, 2020, 7:38 AM

#

📎 Screen_Shot_2020-03-13_at_3.38.07_AM.png

#

can someone help with this, it seems like im doing it wrong

stray reef Mar 13, 2020, 7:40 AM

#

you aren't. these terms really do grow that massive

weary tiger Mar 13, 2020, 7:41 AM

#

Oh okay, Tyvm

outer perch Mar 13, 2020, 1:23 PM

#

In how many ways is it possible to partition a set of 2n elements, into n sets of 2 elements?

tacit grove Mar 13, 2020, 1:33 PM

#

hey i'm a psych grad so my knowledge reg. math doesn't go much further than stats, but i have a friend who sent me an equation with no context and i've worked out that it's discrete math and now i'm here. Anyone mind pointing me in the right direction as to how i should go about learning how to solve this? ❤️

#

📎 unknown.png

#

that's all i've got to work with

#

plz show me how i can use logical reasoning to solve that

#

^sry just seen your next msg

#

right

#

right

#

i'm here btw just writing this down as you explain ❤️

#

so far yes just re-reading and organising my notes

stray reef Mar 13, 2020, 1:48 PM

#

{} not []

#

\ not /

#

also the elements in a set need not be numbers (even if in this particular problem they are)

#

anyway

#

A \ B can be informally described as "everything that's in A but not in B"

#

which i think is a better description than "like a list minus"

tacit grove Mar 13, 2020, 1:50 PM

#

thankyou

near prawn Mar 13, 2020, 2:06 PM

#

@outer perch did u figure it out

outer perch Mar 13, 2020, 2:07 PM

#

not yet but i think i'm omw

near prawn Mar 13, 2020, 2:08 PM

#

what do you have atm

stray reef Mar 13, 2020, 2:09 PM

#

||(2n)!/(2^n n!), no?||

near prawn Mar 13, 2020, 2:09 PM

#

yea

outer perch Mar 13, 2020, 2:21 PM

#

Yeah no idea, care to explain what is each term?

near prawn Mar 13, 2020, 2:23 PM

#

theres several ways of doing this

#

first we can arrange all 2n items in a row

#

how many ways can we do that in?

outer perch Mar 13, 2020, 2:25 PM

#

2n!

#

?

near prawn Mar 13, 2020, 2:26 PM

#

yea

#

now imagine theres imaginary lines separating the 2n items into groups of 2

#

those are your subsets

#

but since the order of each of the 2 items within a subset dont matter we have to divide that out

#

and the position of each subset in the row also doesnt matter so we also divide that out

outer perch Mar 13, 2020, 2:31 PM

#

2^n is each subset ?

#

no

#

ok i got it

#

i can't get this and it's the second week of the semester i'm gonna cry

#

thanks btw

near prawn Mar 13, 2020, 2:53 PM

#

you could also pick a random element and pick its partner in 2n-1 wyas

#

pick another element and pick its partner in 2n-3 ways.... so on

#

so its (2n-1)(2n-3)(2n-5).....5 * 3 *1

#

which is the same

#

@outer perchwait so did u get it or na

outer perch Mar 13, 2020, 3:00 PM

#

Yes

lyric pumice Mar 13, 2020, 3:57 PM

#

@fossil pewter Hello. There is no simple formula for the problem whose answer you seek.

weary tiger Mar 13, 2020, 3:58 PM

#

The oracle has spoken.

lyric pumice Mar 13, 2020, 4:12 PM

#

The result involves counting ordered sets by summing products of binomial coefficients over integer compositions where the size of each part is restricted depending upon its position.

#

@fossil pewter

fossil pewter Mar 13, 2020, 4:19 PM

#

Indeed I realized the answer would be really nasty because for a simple case like R different balls in N boxes without empty boxes already gives us a hefty series.
Thank you for trying @lyric pumice

near prawn Mar 13, 2020, 4:21 PM

#

cant you use inclusion exclusion?

lyric pumice Mar 13, 2020, 4:34 PM

#

@near prawn I'm not sure.

#

@fossil pewter @fossil pewter It appears that there may be a general formula using the principle of inclusion-exclusion, but then it must be very complex.

#

I can attempt a derivation.

fossil pewter Mar 13, 2020, 4:45 PM

#

I would not recommend lol

lyric pumice Mar 13, 2020, 4:45 PM

#

It would be a worthwhile pursuit.

near prawn Mar 13, 2020, 4:46 PM

#

i dont think its that bad

#

its just long

uneven mirage Mar 13, 2020, 5:57 PM

#

A recursive sequence is given by the following rules:
a0 = 1, a1 = 2, an = an-1 + 2an-2 + 1 for n>1
Evaluate a2, a3 and a4.

can someone check my answer i believe it is
a2 = 5
a3= 10
a4= 21

stray reef Mar 13, 2020, 5:58 PM

#

$a_n = a_{n-1} + 2a_{n-2}+1$?

vital dewBOT Mar 13, 2020, 5:58 PM

#

Ann:

📎 183668144404037632.png

uneven mirage Mar 13, 2020, 6:04 PM

#

or is it a2=3, a3=6, a4=11 ?

stray reef Mar 13, 2020, 6:28 PM

#

no, you had it right the first time around, assuming my transcription of your recursive thing was correct

uneven mirage Mar 13, 2020, 6:30 PM

#

@stray reef ty

weary tiger Mar 13, 2020, 7:12 PM

#

I want to show that $2^{n+1} is O(2^{n}).$. I started with $2^{n+1} \leq{2^{n} + 2^{n}}$

vital dewBOT Mar 13, 2020, 7:12 PM

#

presmo:

📎 673594150649593879.png

weary tiger Mar 13, 2020, 7:13 PM

#

how can i continue from here

pale epoch Mar 13, 2020, 7:14 PM

#

what's your definition of O(2^n)

weary tiger Mar 13, 2020, 7:14 PM

#

Its the big O notation

#

Algorithmic complexity in other words

#

I have to show that |f(x)| <= C|g(x)| forall x > k

#

where g(x) is 2^n and f(x) = 2^n+1

#

Can i do $2^{n+1} \leq{2^{n} + 2^{n}}\leq{2^{n}(1+1)}\leq{2^{n}*2}$

vital dewBOT Mar 13, 2020, 7:15 PM

#

presmo:

📎 673594150649593879.png

pale epoch Mar 13, 2020, 7:17 PM

#

yes, all of those can also be = signs

weary tiger Mar 13, 2020, 7:17 PM

#

oh right, tyvm

weary tiger Mar 13, 2020, 8:07 PM

#

📎 can.png

#

can someone explain what happens in step 3?

#

where does the squared go?

pale epoch Mar 13, 2020, 8:08 PM

#

factored out

#

(k+1) is common term to both summands

weary tiger Mar 13, 2020, 8:08 PM

#

oh

#

i totally missed that

#

tyvm

#

📎 Screen_Shot_2020-03-13_at_4.22.52_PM.png

#

i dont understand this one either, in step 3

near prawn Mar 13, 2020, 8:25 PM

#

they just collected like terms?

weary tiger Mar 13, 2020, 8:27 PM

#

pog ty

weary tiger Mar 13, 2020, 9:26 PM

#

if im using warshall's algorithm to compute all the paths between towns, i.e. town a b c d e f, and i want to find all the distinct pairs that have a path containing 3 distinct streets is that matrix 3 of warshall's algorithm i.e. 3 possible intermediates?

#

in this case that matrix seems to match the transitive closure im not sure if thats right considering the path (a, b) is in the relation so it doesnt have intermediates

#

also how do i do warshall's algo by hand

azure lichen Mar 13, 2020, 10:34 PM

#

it’s a pretty tedious algorithm to do by hand (yay O(n³))

#

but uh, you give each node a number (or letter I guess, as you did)

#

then you make a table with a row and a column for each node

#

put a 0 on the main diagonal, a 1 between any neighbors and ∞ anywhere else

#

then you make a new table, which now allows “a” as an intermediate node

#

for each cell (x,y), check which of these is smaller: the entry in the same cell on the previous table, or the entry (x,a) plus the entry (a,y)

#

repeat that until you run out of things to add

#

obviously you can shortcut things (e.g. 0s, 1s and 2s will never be improved so you only have to check things with a 3 or higher)

#

but it’s tedious af anyway

weary tiger Mar 13, 2020, 11:06 PM

#

dam

#

and what about that first part of my question, how do i determine from matrix 3 of warshall the ones that have 3 distinct towns in their path

#

Hey guys! I've been trying to wrap my head around a problem involving 7 digit numbers, as I'm preparing for my discrete math final exam

#

The problem asks: how many 8-digit arrangements can you have, with each digit ranging from 0-9, such that the sum of all digits in each arrangement equals to 16？

#

Any help would be greatly appreciated!

near prawn Mar 13, 2020, 11:30 PM

#

you can turn this into an equation maybe

weary tiger Mar 13, 2020, 11:33 PM

#

@neon thorn so in a way, manipulate it using inclusion exclusion?

#

@near prawn the concept described by disc?

near prawn Mar 13, 2020, 11:35 PM

#

erm no

#

I dont think inclusion exclusion is the way to go, sounds tedious

#

what I meant was writing the digits as
x1+x2+x3+.....x8=16 where 0<=xi<=9

#

and then finding the number of sols of that

#

thonk

#

hm

weary tiger Mar 13, 2020, 11:37 PM

#

Would that not take a while to solve, given the sheer amount of params?

near prawn Mar 13, 2020, 11:38 PM

#

finding the number of integer solutions to that equation is straightforward

weary tiger Mar 13, 2020, 11:38 PM

#

Oh sorry, was directing that at Lemon

near prawn Mar 13, 2020, 11:38 PM

#

it's the same as the number of eays of distributing 16 identical objects into 8 distinct boxes

#

with those conditions applied

weary tiger Mar 13, 2020, 11:39 PM

#

How come would they be identical?

#

Yeah, 16 has multiple ways it can be broken down no?

near prawn Mar 13, 2020, 11:49 PM

#

its identical cuz u can just imagine the 16 as 16 identical 1s and group them into boxes

#

where each box is a variable

sour arrow Mar 13, 2020, 11:49 PM

#

Oh this is stars and bars, isn't it?

near prawn Mar 13, 2020, 11:49 PM

#

yea

#

I think this works for this question

sour arrow Mar 13, 2020, 11:53 PM

#

Oh wait, no it doesn't since no number can be 10 or higher

#

You can always just get rid of those cases, I suppose

near prawn Mar 13, 2020, 11:56 PM

#

yea I said with conditions 0<=xi<=9

sour arrow Mar 13, 2020, 11:57 PM

#

The number of ways to write n as an ordered sum of r numbers is:
(n+r-1)Cr

#

That's a common form we use a lot, it's worth remembering. That being said, I just had to look it up. I'm feeling very slow today.

#

Actually, you can't use 10 or higher, can you?

near prawn Mar 13, 2020, 11:59 PM

#

no cuz it says 8 digit arrangements

sour arrow Mar 14, 2020, 12:00 AM

#

So it's just 23C8 right?

#

I'm having a slow brain day D:

#

Wait no you can't have a 0 as the leading digit, can you?

weary tiger Mar 14, 2020, 12:02 AM

#

It says you're allowed to

#

@sour arrow

sour arrow Mar 14, 2020, 12:03 AM

#

Oh cool so yeah that's the answer in my "expert" opinion. @near prawn Am I doing a dumb?

weary tiger Mar 14, 2020, 12:03 AM

#

0 as a leading digit is included

near prawn Mar 14, 2020, 12:04 AM

#

erm

#

pretty sure inclusion exclusion is involved here

#

cuz of the upper bounds

#

that answer over counts

#

but it's fine cuz a max if 1 digit can be >9

weary tiger Mar 14, 2020, 12:06 AM

#

So we have to somehow eliminate digits larger than 9?

sour arrow Mar 14, 2020, 12:07 AM

#

Oh fk yes you can have those. We have to count the cases with a 10, ect

weary tiger Mar 14, 2020, 12:08 AM

#

Oof, how would that work? Because I haven't worked much with something of the sort rip

sour arrow Mar 14, 2020, 12:08 AM

#

Luckily we can do that pretty easy. Let's say there's a 10 in the number. The other 7 digits then must sum to 6

#

How many ways can 7 digits sum to 6?

weary tiger Mar 14, 2020, 12:10 AM

#

A heck ton

#

Hmm, lemme see

#

Or am I wrong?

#

Wait big dumb

#

My brain's not working xD

sour arrow Mar 14, 2020, 12:13 AM

#

Yeah everybody has a day off today it seems lol

#

The number of ways to write n as an ordered sum of r numbers is:
(n+r-1)Cr

weary tiger Mar 14, 2020, 12:13 AM

#

Oh right

sour arrow Mar 14, 2020, 12:13 AM

#

In this case, to use 7 numbers to sum to 6:
(6 + 7 - 1)C7

weary tiger Mar 14, 2020, 12:14 AM

#

12C7

sour arrow Mar 14, 2020, 12:14 AM

#

So 792 ways

#

But I'm leaving something out. There's 8 different places that 10 could have appeared. So it's actually 8 times that many.

#

These steps make sense?

weary tiger Mar 14, 2020, 12:15 AM

#

Ohhhh

#

Right right

#

Right, so we subtract 8*792 from 23C8 to get the total amount of combinations excluding ones with 10

sour arrow Mar 14, 2020, 12:16 AM

#

Exactly, you've got the idea!

weary tiger Mar 14, 2020, 12:16 AM

#

And we repeat this with every number greater than 9 that is smaller or equal to 16

sour arrow Mar 14, 2020, 12:16 AM

#

Yeah it's a bit of work at this point, but I don't see an easier way

weary tiger Mar 14, 2020, 12:17 AM

#

mmm

#

If this question comes up in my final, or something similar

#

I'm so doomed xD

sour arrow Mar 14, 2020, 12:17 AM

#

It's worth knowing the stars and bars method in general. It handles combinations with repetition

weary tiger Mar 14, 2020, 12:17 AM

#

Mhm

#

So, just to be clear

#

I'm looking at my textbook

#

And the principle is described as

#

📎 Screenshot_20200313-171905_Drive.jpg

#

The formula in the box

#

Is that the specific formula we're using?

#

Because (n+r-1)C(r) doesn't follow that format

sour arrow Mar 14, 2020, 12:20 AM

#

The number of ways to put n similar balls into r distinct bins is (n+r-1)Cr

weary tiger Mar 14, 2020, 12:21 AM

#

So it's a different concept?

sour arrow Mar 14, 2020, 12:21 AM

#

Your book says
(k + n - 1)Ck

#

Same formula

#

So think of it this way:
You have 16 balls and 8 bins. How many ways to put them in?

weary tiger Mar 14, 2020, 12:23 AM

#

(16+8-1)C8

sour arrow Mar 14, 2020, 12:23 AM

#

The bins end up being the digits of your number, and the balls ensure they sum to 16

weary tiger Mar 14, 2020, 12:24 AM

#

Ahhh

sour arrow Mar 14, 2020, 12:24 AM

#

Which is why this also describes the number of ways to take r numbers that sum to n

weary tiger Mar 14, 2020, 12:24 AM

#

I see, thanks!

#

:D

sour arrow Mar 14, 2020, 12:24 AM

#

Cool cool, glad it makes sense. I was having trouble with it like 10 minutes ago lol

weary tiger Mar 14, 2020, 12:25 AM

#

Yeah, I'm in a long car ride and my head can only take so much as well hahaha

weary tiger Mar 14, 2020, 5:31 PM

#

how can i use a transitive closure to determine this: "show all pairs of distinct towns that have a path containing three distinct streets"

weary tiger Mar 14, 2020, 6:22 PM

#

also how am i supposed to draw big hesse diagrams? i have a relation with like 30 relations and the set upon which the relation is is a powerset containing 16 elements i cant draw it neatly what kind of shape do i draw

weary tiger Mar 14, 2020, 6:38 PM

#

also also (sorry for all the questions just answer any of them) how do i show the equivalence class for this relation {(x, y) | xy >= 0, x and y are integers} currently I have something like {a element of integers | a >= 0}

weary tiger Mar 14, 2020, 7:15 PM

#

📎 d904a1f2a1251452be2594489cbb8a15.png

#

is this right

#

7 choose 4

#

yes

#

Hello

#

If I suppose 3 | (n^3 - n)

#

Does 3 divide n^3 - n + 3n^2 + 3n

#

Nvm, just typing it out I realized that every term is a factor of 3

near prawn Mar 14, 2020, 7:48 PM

#

nice

dry patrol Mar 14, 2020, 9:43 PM

#

Alrihgt I have a question about Regular expressions

#

📎 unknown.png

#

I have to create a regular expression with those three conditions

static creek Mar 14, 2020, 11:25 PM

#

i forgot the mathy/CSy notation for regexs, but in practical applications, this regex works:

[Aa-z](\-?[a-zA-Z]+)*

weary tiger Mar 14, 2020, 11:47 PM

#

how do i show the equivalence class for this relation {(x, y) | xy >= 0, x and y are integers} currently I have something like {a element of integers | a >= 0}

sour arrow Mar 14, 2020, 11:56 PM

#

x is related to y only if xy is positive. That only happens if x and y are both positive OR if x and y are both negative.

#

@weary tiger

#

Those are your two classes. All positives are related to eachother, and all negatives are related to eachother.

weary tiger Mar 14, 2020, 11:58 PM

#

how do i write that im confused about notation

sour arrow Mar 14, 2020, 11:58 PM

#

Depends on what your teacher wants. I just wrote it above in English

weary tiger Mar 14, 2020, 11:59 PM

#

he wants like a set builder thingy probably

#

"algebraic"

#

english definitely wont be right

sour arrow Mar 15, 2020, 12:01 AM

#

Oh fk I missed something. Everything is related to 0, and so this is not transitive and not an equivalence relation.

weary tiger Mar 15, 2020, 12:02 AM

#

huh?

#

but like if xy >= 0 and yz >= 0 then shouldnt xz >= 0

sour arrow Mar 15, 2020, 12:04 AM

#

Not if y = 0

weary tiger Mar 15, 2020, 12:04 AM

#

ohh

#

if x were 1 and z were -1 and y were 0

#

it wouldnt work

#

dam ok

sour arrow Mar 15, 2020, 12:05 AM

#

Exactly, that. If the question said > and not ≥ that would fix it

weary tiger Mar 15, 2020, 12:05 AM

#

ok let me hit you with the real hard one though

#

im like 99% sure this one is an equivalence relation

#

{(a, b) | a and b were born in the same year, a and b are students in the US}

#

how are the equivalence classes written

sour arrow Mar 15, 2020, 12:06 AM

#

Is that an "and" or an "or"

weary tiger Mar 15, 2020, 12:06 AM

#

such that?

#

which thing

#

(a, b) such that a and b were in the same year and a and b are students in the US

#

its an and

sour arrow Mar 15, 2020, 12:06 AM

#

Gotchya, good

#

Yes this is an equivalence relation

#

"or" would fail transitivity

weary tiger Mar 15, 2020, 12:07 AM

#

gotchaa

#

yeah its an and

#

so then the classes

#

how's that written

#

like [a] = {x | x was born in the same year as a AND is a student in US}?

sour arrow Mar 15, 2020, 12:18 AM

#

@weary tiger
Wait, what's the set that this relation is on? Is it the set of all students? Then this is not an equivalence relation, because non-us students aren't related to themselves

weary tiger Mar 15, 2020, 12:19 AM

#

thats all i was given

#

'{(a, b) | a and b were born in the same year, a and b are students in the US}'

#

my teacher rushes through shit so fast

#

maybe the second part is the set

#

so the set of all US students?

#

and then they're related via birthyear i suppose

#

this homework is so poorly written

sour arrow Mar 15, 2020, 12:20 AM

#

If it is the set of all US students, then it is an equivalence relation. But yeah you'd need to know the set that this relation is on

weary tiger Mar 15, 2020, 12:21 AM

#

lets assume us students

#

i just need to "show the equivalence classes"

sour arrow Mar 15, 2020, 12:24 AM

#

Well, two students are in the same class if they were born in the same year

weary tiger Mar 15, 2020, 12:33 AM

#

but how is that written im just not getting the

#

notation

#

equivalence classes are sets right?

#

so how would that be written in set builder notation

#

would i just copy the condition

#

[a] = {x is a student in the US | x ~ a}

#

[b] = {x is a student in the US | x ~ b}?

sour arrow Mar 15, 2020, 12:35 AM

#

Yeah that's essentially it

#

And will always be it

weary tiger Mar 15, 2020, 12:35 AM

#

alrighty

#

im just gonna put that down and move on

#

my teacher is absolutely trash

#

thanks for your help sorry if i sound stupid

sour arrow Mar 15, 2020, 12:36 AM

#

Lol no, you clearly get the ideas

weary tiger Mar 15, 2020, 12:37 AM

#

i like to think so

#

some of this stuff is pretty interesting if i were actually learning it correctly

#

can you help me with another question while you're here?

#

its about transitive closure/warshall algorithm

sour arrow Mar 15, 2020, 12:38 AM

#

Yes, all of the best structure stuff uses equivalence relations. Get this down and you'll be doing some cool quotient stuff

weary tiger Mar 15, 2020, 12:39 AM

#

basically im given this set {A, B, C, D, E, F} and im asked to find the pairs of distinct towns that have a path containing three distinct streets

#

so im assuming one of the matrices of warshall tells me that information

#

since there'd be 6 and each one is another intermediate step or something

#

like no intermediates, 1 intermediate,....

#

but i dont get how to read it because matrix 3 has a path that is a direct path so clearly does not have 3 nodes in between

#

because its uh

#

cumulative or whatever

#

it builds from the last matrix

#

let me just tell you the relation maybe we can bullshit this and just let it directly

#

{(A, B), (A, C), (B, D), (C, B), (D, C), (D, F), (E, C), (E, F)}

#

my answer is that only (A, F) has a path containing three distinct streets

#

once i drew out the directed graph of that relation and traced my finger along each thing that seemed to be the only one

#

A->C->B->D->F

#

(A, C), (C, B), (B, D), (D, F)

sour arrow Mar 15, 2020, 12:43 AM

#

What on earth is the question? Lol

weary tiger Mar 15, 2020, 12:43 AM

#

ikr

#

jesus man this homework

#

and he has this one question where im expected to draw a hesse diagram with 16 elements and like 40 fucking relations

#

and i am "absolutely not allowed to have any extra space besides the designated area" which is microscopic

sour arrow Mar 15, 2020, 12:43 AM

#

That's a bit intense but doable

#

Oh

weary tiger Mar 15, 2020, 12:43 AM

#

yep

#

so if you take streets to mean edges

#

then i think (A, F) is the only one with three distinct streets between A and F

#

well i guess thats 4 actually...

#

ugh

#

so then A->B->D->F

#

thats three streets (A, B), (B, D), (D, F)

#

isnt there a way to use warshalls algo to figure this out?

#

i mean that's what its doing right its building all of the paths with no intermediates, then all of the paths with 1, ....?

weary tiger Mar 15, 2020, 1:30 AM

#

am i on the right path?

#

this seems really long

#

📎 JPEG_20200314_213114.jpg

#

,w rotate

#

,rotate

vital dewBOT Mar 15, 2020, 1:32 AM

#

📎 673594150649593879.png

weary tiger Mar 15, 2020, 1:32 AM

#

to reiterate, am i on the right path? this seems long

burnt acorn Mar 15, 2020, 4:52 AM

#

Hello, I'm new here. I was just working through a problem and I think I have the answer but I'm looking for another opinion

burnt acorn Mar 15, 2020, 5:10 AM

#

I have worked it out to 1/(n-k+1)!-(n-k+1)!

📎 nCr.PNG

stray reef Mar 15, 2020, 5:11 AM

#

what's the original problem

burnt acorn Mar 15, 2020, 5:11 AM

#

The picture

stray reef Mar 15, 2020, 5:11 AM

#

and also why did you doublepost

#

don't do that

burnt acorn Mar 15, 2020, 5:11 AM

#

Um sorry I'll delete the other one, I just didn't know which channel to ask in

stray reef Mar 15, 2020, 5:12 AM

#

anyway

#

uh

#

all the picture contains is an expression

#

what are you asked to do with it

burnt acorn Mar 15, 2020, 5:13 AM

#

The textbook says to "compute each expression"

stray reef Mar 15, 2020, 5:13 AM

#

can you take a pic of the textbook where it lists the problem

#

so that we don't have to keep playing broken telephone

burnt acorn Mar 15, 2020, 5:13 AM

#

Yes no problem.

#

📎 nCr2.PNG

stray reef Mar 15, 2020, 5:15 AM

#

o_O

#

jeez that is some weird phrasing

burnt acorn Mar 15, 2020, 5:16 AM

#

So the form is says to use for these types of problems is n!/n!(n-r)!

stray reef Mar 15, 2020, 5:16 AM

#

i can tell you for sure that this doesn't equal $\frac{1}{(n-k+1)!} - (n-k+1)!$ though

vital dewBOT Mar 15, 2020, 5:16 AM

#

Ann:

📎 183668144404037632.png

burnt acorn Mar 15, 2020, 5:16 AM

#

yeah, and that is why i think it is 1/0

stray reef Mar 15, 2020, 5:17 AM

#

it's not

#

what does the answer key say? n(n-1)(n-2)...(n-k+2)?

burnt acorn Mar 15, 2020, 5:18 AM

#

this particular problem is not in the answer key, sorry.

stray reef Mar 15, 2020, 5:18 AM

#

it's weird how you're asked to ""compute"" this and not, say, "simplify" or "rewrite w/o factorials"

burnt acorn Mar 15, 2020, 5:19 AM

#

Yeah, let me show you another snip, you don't mind do you?

#

📎 nCrformula.PNG

#

This is how I came up with n! / (n-k+1)!(n!-(n-k+1)!), with that wouldn't the n! in the numerator and denominator cancel, since we are technically multiplying these expressions?

stray reef Mar 15, 2020, 5:46 AM

#

n! / (n-k+1)!(n!-(n-k+1)!),
bad

burnt acorn Mar 15, 2020, 5:49 AM

#

What do you mean "bad"? Isn't that the form it should be in to continue working it?

stray reef Mar 15, 2020, 5:55 AM

#

it's just bullshit, is what i'm saying

novel quartz Mar 15, 2020, 2:54 PM

#

Hey anyone active in here I think I have a fairly simple question

stray reef Mar 15, 2020, 2:54 PM

#

justask

novel quartz Mar 15, 2020, 2:55 PM

#

Okay its about pascal encoding,
would the length part of the string be the number of bytes or characters?

stray reef Mar 15, 2020, 2:56 PM

#

uhh

#

what

novel quartz Mar 15, 2020, 2:56 PM

#

oh wrong place maybe

weary tiger Mar 15, 2020, 5:29 PM

#

Hello @weary tiger

fiery pivot Mar 15, 2020, 5:35 PM

#

Hmm

#

Sounds interesting

#

I"ll have a think

weary tiger Mar 15, 2020, 5:36 PM

#

Why ping?? PanGPingRee

#

@Prealgebra

#

bccrazypinged

weary tiger Mar 15, 2020, 5:54 PM

#

Am I right if I say

#

(3x)/2 + 1 is O(x) with C=4 and k=0.4

stray reef Mar 15, 2020, 6:20 PM

#

seems so?

weary tiger Mar 15, 2020, 7:44 PM

#

how could i remove the transitive relations from a binary matrix?

stray reef Mar 15, 2020, 7:51 PM

#

thonk

weary tiger Mar 15, 2020, 7:58 PM

#

ok i think i figured it out

#

you use the square of the binary matrix and if there's a corresponding non-zero value you set the value to 0

#

im tasked with drawing the hesse diagram for {(a, b) | a subset of b and a and b are subsets of {1, 2, 3, 4}}

#

so then i calculated the binary matrix relation from the powerset given that a is a subset of b, then i remove all of the reflexive relations (just zero out the diagonal), and finally i remove the transitive relations by finding the square of the matrix and if the i-th row and j-th column are non-zero in both the square of the matrix and the matrix itself then the value is set to 0

#

and now FINALLY i can draw the stupid diagram which is going to be a disgusting web of 16 nodes

#

and im a horrible artist

#

so now my question to all of you is how do i draw a 16 node directed graph? i dont get how to organize these graphs so they're clean

#

do i use some sort of 16-gon shape or something?

#

i realize now that there's a pattern here where the relation will always be to all sets with exactly 1 more element :/

#

all that work

#

Why is n^(1/10) big O of (log2(n))

#

if I plot both, the log function is an upper bound on the exponent function

hardy viper Mar 15, 2020, 8:15 PM

#

nah n^1/10 gets bigger eventually

weary tiger Mar 15, 2020, 8:21 PM

#

when?

#

log is in base 2

hardy viper Mar 15, 2020, 8:26 PM

#

here woke

📎 unknown.png

#

to convince yourself n^c always beats log, try to think about how they increase at really big numbers

#

like from 2^100 to 2^101, log increases by 1

#

~~but n^1/10 gets multiplied by (2^100)^(1/10)=1024~~ nvm it gets multiplied by 2^1/10, close enough

weary tiger Mar 15, 2020, 8:41 PM

#

Ahh I see, thank you

weary tiger Mar 15, 2020, 9:53 PM

#

Hey guys, I'm having a hard time following the explanation given by this practice test

#

The following questions involve preparing lunches for your 4 kids using 6 different types of fruit (apples, oranges, bananas, kiwis, pears and mangoes).

#

📎 unknown.png

#

Why is it that we have 5 * 4 permutations when we pick 3 apples?

#

oh wait

#

Now that I think about it, I just figured it out hahaha

#

big brain

near prawn Mar 15, 2020, 9:59 PM

#

np

weary tiger Mar 15, 2020, 10:57 PM

#

would anyone mind helping me with this

#

📎 Screen_Shot_2020-03-15_at_6.43.23_PM.png

#

i dont understand the reccurance relation a_n found

#

where does 2^(n-2) come from

weary tiger Mar 15, 2020, 11:29 PM

#

$(n \geq 1) $

vital dewBOT Mar 15, 2020, 11:29 PM

#

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

📎 673594150649593879.png

charred cargo Mar 16, 2020, 12:15 AM

#

can someone help me proving by contradiction that there is no largest rational number

faint narwhal Mar 16, 2020, 1:34 AM

#

What have you tried?

sleek swallow Mar 16, 2020, 2:46 AM

#

@charred cargo

charred cargo Mar 16, 2020, 2:47 AM

#

I assume that there is

#

that would mean that if T is the largest rational number then it would be greater than x/y and x and y can be any number

sleek swallow Mar 16, 2020, 2:49 AM

#

$y \neq 0$ and $T \geq \frac{x}{y}$ for all rationals $\frac{x}{y}$

vital dewBOT Mar 16, 2020, 2:49 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 2:49 AM

#

Go on

charred cargo Mar 16, 2020, 2:50 AM

#

i dunno what to do from here

#

am i supposed to divide by something

sleek swallow Mar 16, 2020, 2:50 AM

#

Well, consider this

#

Is T+1 rational?

charred cargo Mar 16, 2020, 2:50 AM

#

yes?

sleek swallow Mar 16, 2020, 2:51 AM

#

And is T+1 > T?

charred cargo Mar 16, 2020, 2:51 AM

#

hmmm

#

simple

#

ok

#

i get it

#

wait

#

but thats not proof by contradiction

sleek swallow Mar 16, 2020, 2:51 AM

#

Yes. So, by your hypothesis, $T \geq T+1$. That's a contradiction.

vital dewBOT Mar 16, 2020, 2:51 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 2:52 AM

#

Understand?

charred cargo Mar 16, 2020, 2:52 AM

#

yes

#

but dont go

#

i have just a few more questions

sleek swallow Mar 16, 2020, 2:53 AM

#

The idea is that T+1 is rational, so $T \geq T+1$, which is exactly your assumption. But that's a contradiction, since T < T+1

vital dewBOT Mar 16, 2020, 2:53 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 2:53 AM

#

Ffs

#

Then, it remains to be proven that T+1 is actually rational. This is a relatively simple thing to do and I'll let you do that on your own.

#

@charred cargo Sure, ask away. I'll answer if I have time lol

charred cargo Mar 16, 2020, 2:54 AM

#

one sec

#

alright

#

so since im only just now getting past the first one

#

ill post the question

#

then try to solve it then when i get stuck you can pitch in

#

thank you

#

"Using the method of proof by contradiction, prove that if a
product of two positive real numbers is greater than 1,000,000, then at least
one of the numbers is greater than 1000."

sleek swallow Mar 16, 2020, 2:57 AM

#

Okay.

charred cargo Mar 16, 2020, 2:57 AM

#

wait

#

let me try to explain it

sleek swallow Mar 16, 2020, 2:57 AM

#

Actually, let me give you a bit more to deal with.

#

Consider the product of two positive real numbers $r_1 r_2$. Let that product be greater than a number $m$. Then, prove that at least one of the numbers is greater than $\sqrt{m}$.

#

^Prove this instead.

charred cargo Mar 16, 2020, 2:58 AM

#

no

#

im doing homework

#

i have to finish this

sleek swallow Mar 16, 2020, 2:58 AM

#

It's the same problem

charred cargo Mar 16, 2020, 2:58 AM

#

but i can atleast learn

vital dewBOT Mar 16, 2020, 2:59 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 2:59 AM

#

But alright, explain what you have

charred cargo Mar 16, 2020, 3:00 AM

#

ok so the statement is if (a+b > 1000000) then one of the numbers is greater than 1000

sleek swallow Mar 16, 2020, 3:00 AM

#

product of two positive real numbers

charred cargo Mar 16, 2020, 3:01 AM

#

the contradiction would be that if (a+b > 1000000) then none or both of the numbers is greater than 1000

#

right?

sleek swallow Mar 16, 2020, 3:02 AM

#

No! You're being asked to show that $ab > 1000000 \implies a > 1000 \lor b > 1000$

vital dewBOT Mar 16, 2020, 3:02 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 3:03 AM

#

product of two positive real numbers
You used a+b

charred cargo Mar 16, 2020, 3:03 AM

#

oh

#

the contradiction would be that if (a*b > 1000000) then none or both of the numbers is greater than 1000

sleek swallow Mar 16, 2020, 3:04 AM

#

what

#

You're asserting that at least one of the numbers is greater than 1000. That's the assertion being made by the question. So, you begin by assuming that neither is greater than 1000

#

That's the start of your proof by contradiction

charred cargo Mar 16, 2020, 3:07 AM

#

if (a*b > 1000000) then (a < 1000 and b < 1000)

sleek swallow Mar 16, 2020, 3:07 AM

#

?

charred cargo Mar 16, 2020, 3:08 AM

#

neither a or b is greater than 1000

#

thats what you said

sleek swallow Mar 16, 2020, 3:09 AM

#

Okay. I'm going to spell this out for you. Make sure you tell me if you're not understanding anything:

Let $a,b \in \bR$. $a \cdot b > 1000000 \implies [a > 1000 \lor b > 1000]$.

So, you assume that $a<1000$ and $b < 1000$.

vital dewBOT Mar 16, 2020, 3:09 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 3:10 AM

#

What do you do from there?

charred cargo Mar 16, 2020, 3:10 AM

#

is that not what i just did

#

(a < 1000 and b < 1000)

amber hill Mar 16, 2020, 3:11 AM

#

What? Is this proof by contradiction or?

sleek swallow Mar 16, 2020, 3:11 AM

#

if (a*b > 1000000) then (a < 1000 and b < 1000)
This is what you wrote. It changes the entire assertion being made. Typically, we don't change the implication when we use proofs by contradiction.

#

Yes, this is a proof by contradiction.

#

Anyways, kozzmic, continue.

amber hill Mar 16, 2020, 3:12 AM

#

Where is the problem btw?

sleek swallow Mar 16, 2020, 3:12 AM

#

Scroll up.

amber hill Mar 16, 2020, 3:13 AM

#

\sqrt{m}?

sleek swallow Mar 16, 2020, 3:13 AM

#

"Using the method of proof by contradiction, prove that if a
product of two positive real numbers is greater than 1,000,000, then at least
one of the numbers is greater than 1000."

amber hill Mar 16, 2020, 3:13 AM

#

Are you looking for a solution?

sleek swallow Mar 16, 2020, 3:13 AM

#

Kozzmic is attempting the question.

charred cargo Mar 16, 2020, 3:14 AM

#

ok

#

i get it

#

one sec

sleek swallow Mar 16, 2020, 3:15 AM

#

Okay.

#

Delete that, fourier.

#

Wait for them to show their proof.

amber hill Mar 16, 2020, 3:16 AM

#

How do I delete the bot's input?

sleek swallow Mar 16, 2020, 3:16 AM

#

Click the red bin icon

amber hill Mar 16, 2020, 3:17 AM

#

Umm okay, so you were not looking for a solution?

charred cargo Mar 16, 2020, 3:17 AM

#

wouldnt i just input something less than 1000

#

then test it

sleek swallow Mar 16, 2020, 3:17 AM

#

Kozzmic is the one who's showing their proof to me. So, we're waiting for them to show it.

#

Kozzmic, that doesn't prove it generally.

amber hill Mar 16, 2020, 3:17 AM

#

okay, lol.

sleek swallow Mar 16, 2020, 3:17 AM

#

Sure, if you try all of them, then that would definitely prove it. But there's a faster way to do it that doesn't involve trying all of them.

amber hill Mar 16, 2020, 3:18 AM

#

you tutoring him?

sleek swallow Mar 16, 2020, 3:18 AM

#

No. Just assisting with the problem.

amber hill Mar 16, 2020, 3:19 AM

#

Ah, I see.

#

Got any unsolved problems(on the server)?

sleek swallow Mar 16, 2020, 3:19 AM

#

Generally, we don't give out answers in this server. For me, I write full proofs only as an illustration for someone getting into proofs.

#

#challenge-problems

charred cargo Mar 16, 2020, 3:19 AM

#

uhh

#

how do i explain this

sleek swallow Mar 16, 2020, 3:20 AM

#

You've assumed that a<1000 and b<1000

#

What can you say about the products of those two numbers?

charred cargo Mar 16, 2020, 3:20 AM

#

i could show that 1000 * 1000

#

is 1000000

#

so any a or b less than that cant get that high

#

i think i said that wrong

sleek swallow Mar 16, 2020, 3:21 AM

#

In other words

charred cargo Mar 16, 2020, 3:21 AM

#

do you get what im trying to say

sleek swallow Mar 16, 2020, 3:21 AM

#

ab < 1000000

#

Is that what you're trying to get at?

charred cargo Mar 16, 2020, 3:22 AM

#

yes

sleek swallow Mar 16, 2020, 3:23 AM

#

Do you see why that's a problem?

charred cargo Mar 16, 2020, 3:23 AM

#

yes

#

it contradicts

sleek swallow Mar 16, 2020, 3:23 AM

#

Do you see why ab<1000000 is a contradiction?

#

Good

#

So you've proven the result

#

And what I was trying to get at earlier is that there's a more general result here:

$ab > m \implies [a > \sqrt{m} \lor b > \sqrt{m}]$

vital dewBOT Mar 16, 2020, 3:24 AM

#

Abhijeet Vats:

📎 340191992636243968.png

charred cargo Mar 16, 2020, 3:26 AM

#

ive got another question

#

just give me a sec to write

#

i'll ping you if you are willing

sleek swallow Mar 16, 2020, 3:26 AM

#

Sure.

charred cargo Mar 16, 2020, 3:34 AM

#

@sleek swallow

#

u there

#

what does this mean

#

f : R+ �→ RR>2

#

nooo

#

where did you goo

sleek swallow Mar 16, 2020, 3:35 AM

#

??

#

What's RR?

charred cargo Mar 16, 2020, 3:35 AM

#

wait

#

📎 15dbd82fab18059537f7f584baadcdb4.png

#

all positive real numbers

sleek swallow Mar 16, 2020, 3:36 AM

#

That's just a function that maps the elements of one set to the other set. Both sets, in this case, have been specified.

#

$\bR_{R > 2} = {x \in \bR: x > 2}$

vital dewBOT Mar 16, 2020, 3:36 AM

#

Abhijeet Vats:

📎 340191992636243968.png

charred cargo Mar 16, 2020, 3:36 AM

#

I dont get what the one one te right

#

oh

sleek swallow Mar 16, 2020, 3:38 AM

#

I mean, I assume that that's what it means. It seems like a reasonable assumption. I've not seen that notation being used in the books that I use.

charred cargo Mar 16, 2020, 3:38 AM

#

📎 7cc0beb5c630caff6b8fdccd3e9e8134.png

#

I dont understand how that would relate to the equation though

#

i can prove that the equation is one to one using a horizontal line test on the graph

sleek swallow Mar 16, 2020, 3:40 AM

#

Well, note that $\sqrt{x}$ is only defined when $x \geq 0$. Furthermore:

$\sqrt{x} > 0$

$2+\sqrt{x} >2$

vital dewBOT Mar 16, 2020, 3:40 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 3:41 AM

#

Now, keep in mind, you're considering only the positive real numbers. 0 is not a positive real number, which is why $\sqrt{x} > 0$.

vital dewBOT Mar 16, 2020, 3:41 AM

#

Abhijeet Vats:

📎 340191992636243968.png

amber hill Mar 16, 2020, 3:42 AM

#

Since domain is positive real numbers, the corresponding range is unique for given FE, and for range= codomain.

#

so, bijective.

charred cargo Mar 16, 2020, 3:42 AM

#

so basically i just have to prove that the function is bijective

sleek swallow Mar 16, 2020, 3:42 AM

#

Lmao that is precisely the question.

#

You're being asked to show that it is injective and surjective. In doing so, you can show that it's bijective.

charred cargo Mar 16, 2020, 3:43 AM

#

k i thought all that R stuff was extra steps

#

i can use the horizontal line test

sleek swallow Mar 16, 2020, 3:43 AM

#

That 'R stuff' is important.

charred cargo Mar 16, 2020, 3:43 AM

#

or is there a more discrete math way to do this?

sleek swallow Mar 16, 2020, 3:44 AM

#

? Discrete math way?

amber hill Mar 16, 2020, 3:44 AM

#

Wait, which level problem is this?

sleek swallow Mar 16, 2020, 3:44 AM

#

There's an analytical way to do this, certainly

charred cargo Mar 16, 2020, 3:45 AM

#

i feel like horizontal line test is not the way im supposed to do it

#

could you give me a hint as to what the analytical way is?

sleek swallow Mar 16, 2020, 3:45 AM

#

You're not wrong. It's the geometric way of seeing why it might be true but it does not constitute a proof

#

Well, what're the definitions of injectivity and surjectivity?

amber hill Mar 16, 2020, 3:47 AM

#

I truly wish I had teacher like @sleek swallow .

sleek swallow Mar 16, 2020, 3:47 AM

#

Let $f:A \to B$ be a function between two sets $A$ and $B$. Then, it is injective iff:

$f(x) = f(y) \implies x = y$

Of course, $x,y \in A$. Then, it is surjective iff:

$f(A) = B$.

vital dewBOT Mar 16, 2020, 3:47 AM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 16, 2020, 3:47 AM

#

Lol why

charred cargo Mar 16, 2020, 3:49 AM

#

one sec

sleek swallow Mar 16, 2020, 3:50 AM

#

Sure.

charred cargo Mar 16, 2020, 4:02 AM

#

@sleek swallow thank you for all your help

#

i'll continue tomorrow

#

now i must rest

sleek swallow Mar 16, 2020, 4:03 AM

#

You're welcome. Rest well.

fiery pivot Mar 16, 2020, 11:51 AM

#

@weary tiger I figured out your problem

#

It's actually kinda not hard

#

But it took me going to sleep to figure it out

#

Wait hmm

#

Nevermind I did a silly

#

Clearly need to wake up more :?

#

It works for some cases but

#

Maybe other cases are possible

#

Ok there are definitely at least some other cases

#

Wait nvm

#

No they aren't

#

Ok

#

It does work

#

I didn't do a silly

#

Hint 1: ||for which number of vertices can such a graph exist?||

#

Hint 2: ||Apply an arbitrary starting point and direction to the hamiltonian cycle||

weary tiger Mar 16, 2020, 5:27 PM

#

📎 Screenshot_from_2020-03-16_13-27-32.png

#

Could someone help why is this O(9n) ?

#

I tried to put "f(n) = 9n" in my calculator to see if they ever meet but didn't find anything

stray reef Mar 16, 2020, 5:38 PM

#

you mean O(9**^**n)?

weary tiger Mar 16, 2020, 5:38 PM

#

Ah jeez I misread the textbook

#

Yea O(9^n)

#

why do we drop the 2n and 3n for just n ?

#

same thing as 3n is O(n) right ?

fluid zealot Mar 16, 2020, 5:43 PM

#

for all sufficiently large values of x, the absolute value of f(x) is at most a positive constant multiple of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x_0 such that
|f(x)|≤Mg(x) ,∀x≥x_0

weary tiger Mar 16, 2020, 5:45 PM

#

so 3n is O(n) because with M=4, 5 n is greater than 3n

#

why is log(n^2) big O of log(n)

#

I can't put a M infront of log(n) that would make it greater than n^2 ?

azure lichen Mar 16, 2020, 5:49 PM

#

log(n²) = 2log(n)

weary tiger Mar 16, 2020, 5:50 PM

#

Ah, basics

#

Got it, thanks

near prawn Mar 16, 2020, 10:18 PM

#

dont multipost

weary tiger Mar 17, 2020, 12:07 AM

#

wouldnt this just be Natrual Numbers?

📎 dgdgsdg.png

reef thistle Mar 17, 2020, 12:15 AM

#

You are talking about the second question?

#

@weary tiger

weary tiger Mar 17, 2020, 12:15 AM

#

the first one

primal sluice Mar 17, 2020, 9:47 AM

#

Isn't "binary numbers" the same set as natural numbers*? If so, then "rationals", "reals", "integers" should contain binary numbers, while natural number is the only (non-strictly) subset of it.

*assuming "natural numbers" is meant to include zero, but even if it doesn't the answers above wouldn't change

stray reef Mar 17, 2020, 9:51 AM

#

wtf is a "binary number" in this context

reef thistle Mar 17, 2020, 12:33 PM

#

Maybe it's just 0 and 1

short wyvern Mar 17, 2020, 1:56 PM

#

What would be an example of an element of $\bQ^{3} set?$
Can I just say it’s a 3D point with each of its coords in Q?

stray reef Mar 17, 2020, 1:56 PM

#

bad tex

vital dewBOT Mar 17, 2020, 1:56 PM

#

PiqueKirill:

📎 339368222526537728.png

stray reef Mar 17, 2020, 1:56 PM

#

still bad tex

short wyvern Mar 17, 2020, 1:57 PM

#

:/

stray reef Mar 17, 2020, 1:57 PM

#

but yes Q^3 is just the set of all ordered triples of rational numbers

#

for example, (1/2, 1/3, 1/4)

short wyvern Mar 17, 2020, 1:57 PM

#

So there is no trick behind such a question? It seemed odd and out of place among all the other questions in the hw

stray reef Mar 17, 2020, 1:58 PM

#

what's the exact wording of the question

short wyvern Mar 17, 2020, 1:58 PM

#

State an example of a Q3 element

stray reef Mar 17, 2020, 1:58 PM

#

that's it?

#

all you were asked for was an element of Q^3? no other requirements?

#

do you have a pic of the question

short wyvern Mar 17, 2020, 1:59 PM

#

Ye

#

It’s in Russian tho

stray reef Mar 17, 2020, 1:59 PM

#

well you're in luck

#

i'm a russian native

short wyvern Mar 17, 2020, 1:59 PM

#

One sec 😂

#

📎 image0.jpg

stray reef Mar 17, 2020, 2:01 PM

#

а какие еще там пункты, ради интереса?

#

так-то да, Q^3 - это множество точек в трехмерном пространстве с рациональными координатами, тут никаких странностей нет

short wyvern Mar 17, 2020, 2:03 PM

#

📎 image0.jpg

stray reef Mar 17, 2020, 2:03 PM

#

ага, вижу

short wyvern Mar 17, 2020, 2:04 PM

#

Просто был небольшой завал с другими предметами и немного выпал из дискры

#

Пытаюсь разобраться

steel parcel Mar 17, 2020, 4:32 PM

#

Hello, I was wondering if someone could assist me in completing this practice problem? I have a test friday and im trying to cover some problems in my textbook for assistance. I'm kind of behind in my class because of personal issues.

📎 unknown.png

obtuse lance Mar 17, 2020, 4:35 PM

#

show how much you can do on your own

steel parcel Mar 17, 2020, 4:40 PM

#

not much, I had surgery recently so ive been behind in my classes, and with the coronavirus outbreak, I can't exactly go see my professor or even go to my campus library. I just want to understand but because my resources are limited I can't. That's why I came here, so I could understand. I'm not asking anyone to be like "Gimme the answers" just a small explanation is what I want. I've tried looking at the textbook's explanations too, I just don't get it.

lyric pumice Mar 17, 2020, 5:16 PM

#

@steel parcel Can you identify a subset?

steel parcel Mar 17, 2020, 5:16 PM

#

I got it, i had to ask my friend. thanks. And yeah.

sleek swallow Mar 17, 2020, 5:46 PM

#

What have you tried?

#

Do you know what $\bZ \cross \bZ$ means?

vital dewBOT Mar 17, 2020, 5:48 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 5:49 PM

#

what

#

$\bZ \cross \bZ = {(x,y) | x \in \bZ \land y \in \bZ }$

vital dewBOT Mar 17, 2020, 5:49 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 5:50 PM

#

So, your function is mapping an integer to each ordered pair in $\bZ \cross \bZ$

vital dewBOT Mar 17, 2020, 5:50 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 5:51 PM

#

Do you understand me so far?

#

@weary tiger

#

Okay

#

Now, you want to try and show that the function is not injective

#

So what do you have to do?

#

No. That's not a counterexample.

#

The given function is injective iff:

$f(x_1,y_1) = f(x_2,y_2) \implies (x_1,y_1) = (x_2,y_2)$

vital dewBOT Mar 17, 2020, 5:53 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 5:54 PM

#

Now, consider $x_1 = y_1 = 2$ and $x_2 = y_2 = 3$

vital dewBOT Mar 17, 2020, 5:54 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 5:54 PM

#

Can you see why this is a counterexample?

#

Yeap. At the very least, it was an alternate name for injectivity in the text I used. Hence, I'm following that.

#

Well, if it wasn't a counterexample, then the assertion would be that (2,2) = (3,3). By a theorem on ordered pairs, that would imply that 2 = 3

#

Yes

#

Understand?

#

You can generate any number of counterexamples.

#

Well, the ordered pairs (1,1) and (2,2) would certainly form counterexamples.

#

It would be a counterexample. So, (1,1) and (3,3) are counterexamples.

#

Yes. You're trying to find two ordered pairs $A$ and $B$ such that:

$f(A) = f(B) \implies A = B$

Is false. So, you need two ordered pairs to be able to do that.

vital dewBOT Mar 17, 2020, 6:13 PM

#

Abhijeet Vats:

📎 340191992636243968.png

weary tiger Mar 17, 2020, 6:22 PM

#

do you know what onto means?

sleek swallow Mar 17, 2020, 6:23 PM

#

What does it mean

weary tiger Mar 17, 2020, 6:23 PM

#

hint: x²>=0 for all x in Z

sleek swallow Mar 17, 2020, 6:23 PM

#

State the definition

#

No

#

A negative integer will be a counterexample since there are no integers x and y such that x^2+y^2 = negative integer

#

No! Suppose that we have a function between two sets $f:A \to B$. Then, $f$ is onto or surjective iff for all $b \in B$, there exists an $a \in A$ such that f(a) = b.

vital dewBOT Mar 17, 2020, 6:25 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 6:26 PM

#

So, in this case, you need to find an integer z for which there does not exist any integer values of x & y so that f(x,y) = z

#

You need to find an integer. Not ordered pairs.

#

No.

#

I'm starting to think that you do not understand what surjectivity is or what the question i asking of you.

#

So, go and read up on that first before attempting the question.

#

No!

#

First of all, it's:

$f(1,-2) = 1^2+(-2)^2 = 5$

vital dewBOT Mar 17, 2020, 6:30 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 6:30 PM

#

Secondly, that's not a counterexample because 5 is an integer

#

I'm going to reiterate this slowly.

Let $A$ and $B$ be sets. Then, let $f:A \to B$ be a function. Now, f is said to be onto or surjective iff for all $b \in B$, there exists an $a \in A$ such that $f(a) = b$.

vital dewBOT Mar 17, 2020, 6:32 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 6:32 PM

#

Now, translate that to your problem.

$f:\bZ \cross \bZ \to \bZ$ is surjective iff for all $c \in Z$, there exists an $(a,b) \in \bZ \cross \bZ$ such that $f(a,b) = c$.

vital dewBOT Mar 17, 2020, 6:33 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 6:33 PM

#

Now, $f(x,y) = x^2+y^2$. So, let $c = -1$. Then, we can see that $x^2+y^2 = -1$ has no solutions in the integers.

vital dewBOT Mar 17, 2020, 6:33 PM

#

Abhijeet Vats:

📎 340191992636243968.png

sleek swallow Mar 17, 2020, 6:33 PM

#

You are not listening to me

#

Why are you not listening to me?

weary tiger Mar 17, 2020, 6:35 PM

#

a counterexample to surjectivity is in the codomain not on the domain, so in this case its not an ordered pair but an integer..

sleek swallow Mar 17, 2020, 6:43 PM

#

What does it mean for the relation to be reflexive?

weary tiger Mar 17, 2020, 6:44 PM

#

a relation is not a function (in general)

#

no that is wrong

#

xRy doesn't have to be true for all x and y in T

#

No.

#

do you know what a relation is?

#

that's not a proper definition tho

sleek swallow Mar 17, 2020, 6:50 PM

#

That's not a definition at all

#

@weary tiger Go and review what a relation is first. Then, come back with questions.

#

Giving a 10 minute lecture on what it is is going to be useless.

weary tiger Mar 17, 2020, 7:08 PM

#

Hey guys! Does anyone know how to program truth tables in c++?

#

Could you elaborate?

#

I need to program a truth table based off of how many propositions and premises I'm given.

#

So like for $P\implies Q$ you have to enumerate all the possible truth values?

vital dewBOT Mar 17, 2020, 7:16 PM

#

N/𝔄:

📎 241958658294939648.png

weary tiger Mar 17, 2020, 7:17 PM

#

Yeah, so.. Say I'm given an argument that says..
p and q, therefore p. I need to print a table that checks if it's valid.

#

So I'm moreso proving if a logical inference is valid.

#

Would sound like a recursive algorithm to me

#

So in FOL you have 3 elementary connectives

#

My professor gave me a hint saying that I would have to convert to binary.

#

Does he mean encode true or false in binary?

#

So 1 for true and 0 for false

#

Yes

#

Say I have 2 propositions, the amount of columns I would have for my truth table is 2^2, which is 4, right?

#

Dunno, in C++ you have true and false as bool types so idt that's needed

#

Right

#

All combinations

#

Yeah, I need to print out all combinations and all I know is that I need a dynamic 2D array

#

and that I need to convert numbers to binary.

#

Binary is not a hint but rather a requirement?

#

I did ask if I should use bools but she said that binary is more efficient?

#

Wtf they are literally the same

#

The compiler optimizes for bools

#

Uses the least space

#

And there is even special types for bools like vectors

#

That are optimised

#

Anyways, where are you stuck on your assignment?

#

Yeah, idk. We all asked if we should use bools but she said that binary would be easier for us.

#

We're all not advanced, btw.

#

Ah alright I suppose uint8_t would also suffice

#

I just don't know how to print out all the variations for each of the propositions. She gave us a code snippet if you'd like to see?

#

Sure

#

How do I do the little code box again?

#

`

#

This is the code that converts something to binary, I believe:
while(c > 0) { b[i] = c%2; i--; c = c/2; }

#

Wait why would you turn a number into binary if you are talking about propositions?

#

Are you using gödel's method?

#

For example, c would be 101 which equals 5.

#

and it would decrease depending on how many rows I need to print out

#

if that makes sense

#

But this code turns a number into its binary representation

#

c is a number and then its binary representation is stored in b

#

I think I remember her saying that it's the remainder that we need

#

so if c is 5 then my first element in the array would be 1

#

In what contex would this be used in a truth table?

#

Where would you have numbers greater than 1?

#

To print out combinations.

#

There wouldn't be numbers greater than one since we're only taking the remainders I believe

#

Right but you are turning something into a binary number

#

So do you want to store a collumn of a truth table as one number and then turn it upon use into a binary number to save space?

#

Yes!

#

Ahh

#

So this optimisation would probably come in later in the game

#

First you'd need to build the other things around that truth table I suppose

stray reef Mar 17, 2020, 7:52 PM

#

no

#

no you're both missing elements that should be there and including ones that shouldn't

weary tiger Mar 17, 2020, 7:52 PM

#

Equivalence classes are distinct sets

stray reef Mar 17, 2020, 7:53 PM

#

disjoint

weary tiger Mar 17, 2020, 7:53 PM

#

Yeah

#

What I meant 😅

#

If that is a correct equivalence class, do you think this is the answer to the question?

stray reef Mar 17, 2020, 7:56 PM

#

no, this is still missing a ton of relations

weary tiger Mar 17, 2020, 7:57 PM

#

Right and that

#

Symmetry

stray reef Mar 17, 2020, 7:58 PM

#

well for one, do you really need to do that

weary tiger Mar 17, 2020, 8:03 PM

#

Is that really what the question asks of you?

#

It just asks you to list distinct equivalence classes

#

There is a shorthand notation, no?

#

No those are numbers not equivalence classes

#

Did you mean representatives of equivalence classes?

fresh flame Mar 17, 2020, 8:10 PM

#

Correct me if I'm wrong, but isn't $a \equiv b$ (mod $n$) the same thing as $b \equiv a$ (mod $n$), as in the two are interchangeable?

vital dewBOT Mar 17, 2020, 8:10 PM

#

That guy:

📎 220727222183395329.png

weary tiger Mar 17, 2020, 8:10 PM

#

Yes those are the equivalent statements

#

Becaue the relation is symmetrical

fresh flame Mar 17, 2020, 8:10 PM

#

That's what I thought

#

just wasn't sure because I couldn't find a theorem supporting it

weary tiger Mar 17, 2020, 8:12 PM

#

@weary tiger let me ask you this way: how did your course define equivalence classes?

#

@fresh flame that's typically shown when the question comes up if the divisibility relation is an equivalence relation

#

Right so do equivalence classes contain pairs?

#

In your case

#

Did you not say it consists of elements related to 0?

#

Say you have a set $A$ with an equivalence relation $\sim$ on it and an element $a$ then the equivalence class is defined as $[a]_{\sim} := { b\in A | a \sim b }$

vital dewBOT Mar 17, 2020, 8:15 PM

#

N/𝔄:

📎 241958658294939648.png

weary tiger Mar 17, 2020, 8:15 PM

#

How many distinct such sets can you find?

#

In this case $a\sim b :\iff 4|(a-b)$

vital dewBOT Mar 17, 2020, 8:17 PM

#

N/𝔄:

📎 241958658294939648.png

weary tiger Mar 17, 2020, 8:17 PM

#

Why do you believe that it is 6?

#

Do you mean by 16,14,.. the equivalence classes, so $[16]_{\sim}$?

vital dewBOT Mar 17, 2020, 8:18 PM

#

N/𝔄:

📎 241958658294939648.png

weary tiger Mar 17, 2020, 8:19 PM

#

16-12 = 4 which is divisible by 4 therefore 4|(16-12) and 16~12 which means these two are not in disjoint equivalence classes

#

?

#

That should be it, though quite complicated written

#

So what you are looking at is the numbers mod 4

#

There is a simple way of finding the solution

#

$\bZ /(m) = {[0]\sim, [1]\sim, \dots , [m-1]_\sim}$

vital dewBOT Mar 17, 2020, 8:23 PM

#

N/𝔄:

📎 241958658294939648.png

weary tiger Mar 17, 2020, 8:24 PM

#

Where m is your modulo which is 4 in this case

#

So since your numbers exclude 0 you can exclude [0] from there

#

So you have [1] and [2]

#

As your solution

#

You could validate this yourself by looking at the remainder and how it works for values less than 4

#

And then how it works for values greater than 4

#

Those are the same

#

The same equivalence classes can be written with different reprisentatives

#

Uh oh I think I missed something

#

0 would obviously be equivalent to 4

#

So [1],[2],[3], [4]

#

Right we start counting from 0 to m-1=3 so there must be 4 equivalence classes

#

Sorry I did a mental oopsie there

#

Those are the properties of a equivalence relation so yes

#

It does look correct even though the abuse of notation

weary tiger Mar 18, 2020, 12:24 AM

#

Can you formulate an inverse function?

fallen tinsel Mar 18, 2020, 12:25 AM

#

i was thinking yes but not sure since it wasnt in an equation fomr

#

form

weary tiger Mar 18, 2020, 12:35 AM

#

So let $f(x)=(y_1,y_2) = (x, 2x)$ then $f^{-1} (f(x)) = x \implies f^{-1} ((y_1, y_2)) = x$ and how can we reach that? $2x-x=x$ therefore $f^{-1} ((y_1,y_2))=y_2-y_1$. Meaning $f^{-1} (f(x)) = 2x-x = x$ for all $x\in \bR$

vital dewBOT Mar 18, 2020, 12:37 AM

#

N/𝔄:

📎 241958658294939648.png

weary tiger Mar 18, 2020, 12:38 AM

#

@fallen tinsel

#

This is always a unique solution for any x so this function is injective and surjective

fallen tinsel Mar 18, 2020, 12:41 AM

#

thank you

weary tiger Mar 18, 2020, 3:12 AM

#

Hi, I am trying to prove that if G is a Hamiltonian graph, then L(G) is also Hamiltonian, and need a bit of help with how to go about it

weary tiger Mar 18, 2020, 5:30 AM

#

if you need to make 4 teams of 15 people out of 60, then what is the number of combinations possible?

#

I figured I'd go about it like 60C15x45C15x30C15x15C15

#

which adds up to 60!/(15!)⁴

#

but the key provided says 60!/4!(15!)⁴

#

why the 4! in the denominator?

faint narwhal Mar 18, 2020, 5:32 AM

#

what does 4! usually represent?

weary tiger Mar 18, 2020, 5:33 AM

#

the only thing i could think of is if it were perms and the 4 teams were undiscernable, then I'd divide the factorial answer by 4!

faint narwhal Mar 18, 2020, 5:34 AM

#

are the four teams undiscernable?

weary tiger Mar 18, 2020, 5:34 AM

#

yes

#

but it's combinations tho...

faint narwhal Mar 18, 2020, 5:35 AM

#

What do you mean by that?

weary tiger Mar 18, 2020, 5:35 AM

#

what do i mean by which part?

#

okay, chances are idk what i am talking about

#

yeah, that's what i am not understanding either

orchid pawn Mar 18, 2020, 5:36 AM

#

~~repetitions~~

weary tiger Mar 18, 2020, 5:36 AM

#

but doesn't it represent repetitions in permutations only?

faint narwhal Mar 18, 2020, 5:37 AM

#

sure

#

but like you said, the four terms are undiscernable here

#

if we pick the 15 people for the first team

#

its the same as if we had picked the same 15 people for the last team

weary tiger Mar 18, 2020, 5:38 AM

#

yes, i understand that bit, Disc

#

and i understand that one too, number-person

orchid pawn Mar 18, 2020, 5:38 AM

#

@weary tiger see your framework of choosing the teams

#

it's inherently counting the same kind of teams multiple times

weary tiger Mar 18, 2020, 5:39 AM

#

i didn't know that you'd have to divide the answer by a factorial even in the cases of permutations

#

okay, let me think about it

orchid pawn Mar 18, 2020, 5:39 AM

#

dump the idea of "doing this when that"

#

and take a logical approach instead

#

do whatever is needed wherever it's required, as long as you can back it up

weary tiger Mar 18, 2020, 5:40 AM

#

yeah, that's what i am gonna do and re evaluate the problem

#

imma get back when i am done doing that

orchid pawn Mar 18, 2020, 5:40 AM

#

alright

#

just think about how your "algorithm" to choose the teams works

#

you'll see the problem

weary tiger Mar 18, 2020, 5:46 AM

#

okay, let me present a dummed down version of the problem. if i have 6 things and i need to make 3 teams of 2 things. then first imma pick any 2 things with 6C2. then 4 left. 2 more, 4C2. 2 left. 2C2. And then multiply em. and shouldn't that be the end of it?

#

why shouldn't it be the end of it?

#

disc, i am not sure i follow you, friend

faint narwhal Mar 18, 2020, 5:47 AM

#

Okay, let's call them ABCDEF, the six things

#

For our first team, let's choose AB, second team will be CD, last team will be EF

#

Okay that's one way to choose the teams

weary tiger Mar 18, 2020, 5:47 AM

#

okay

faint narwhal Mar 18, 2020, 5:47 AM

#

Now, let's do another way

#

let's choose CD for the first team, then choose AB for teh second team, then choose EF again for the last team

weary tiger Mar 18, 2020, 5:48 AM

#

well they're both the same teams

faint narwhal Mar 18, 2020, 5:48 AM

#

The way you've counted it, you've counted these two as different ways to choose

weary tiger Mar 18, 2020, 5:49 AM

#

well, have i? let me think

#

ah yes!

#

i have

#

oh yeah, it's all coming together now

#

thanks, people

faint narwhal Mar 18, 2020, 5:55 AM

#

This should say that exactly 3 of the digits are 1's

#

but you have to choose which 3 of the digits to forcibly make into 1's

potent vortex Mar 18, 2020, 5:06 PM

#

So I'm looking at my teachers slides for a topic I missed one day but I'm having trouble understanding why this is true

#

📎 unknown.png

#

This was the sample problem

📎 unknown.png

#

How does the answer in the induction step solve the problem as to whether the relation and the closed form solution are the same?

#

To me it's just spitting out the the original formula but with a 'K' substituted for n?

#

Oh wait I see now. The recurrence formula was tacked on to the closed form

weary tiger Mar 18, 2020, 5:43 PM

#

📎 unknown.png

#

Is the "- n" outside of the summation ?

sleek swallow Mar 18, 2020, 5:44 PM

#

Looks like it

weary tiger Mar 18, 2020, 6:34 PM

#

📎 89983036_1863827663924013_9197605553088495616_n.png

#

What should I do at this point ? I'm not sure I did it correctly

potent vortex Mar 18, 2020, 6:45 PM

#

Will a 4 variable truth table always have 16 rows or will it be less if it can be split into two separate truth tables before bringing together?

weary tiger Mar 18, 2020, 6:46 PM

#

why split ?

potent vortex Mar 18, 2020, 6:46 PM

#

Live if it's ( P v Q) v (R ^ S)

weary tiger Mar 18, 2020, 6:47 PM

#

I haven't seen truth tables being split, not sure what you'd gain from it

potent vortex Mar 18, 2020, 6:49 PM

#

Would it be logical to do left and right halves separate like that? Or just go for the 16 row table?

weary tiger Mar 18, 2020, 6:50 PM

#

you're probably going to mix yourself up

#

if you simplify to just 2 variables and try to split that

#

for example p -> 0 and 1

#

q would have to be 1 and 0

#

like you'd have to maintain an order that covers all possibilities over 2 seperate tables

#

For what it's worth (I've only taken 1 discrete math class) I'd go for 16

#

📎 20200318_210143.jpg

#

Hi, can someone tell me how i should continue this?

#

Four subsets of E*

#

I have never seen something so annoying as this course

#

I mean the logic is there but the way to express it in terms

#

Its limiting

#

This course limits my logic

west hedge Mar 18, 2020, 7:12 PM

#

you're trying to show that E x F is empty if and only if E is empty or F is empty?

weary tiger Mar 18, 2020, 7:12 PM

#

Yea

west hedge Mar 18, 2020, 7:12 PM

#

ok

#

were you able to show one of the implications? or neither?

weary tiger Mar 18, 2020, 7:13 PM

#

What do u mean?

west hedge Mar 18, 2020, 7:14 PM

#

you need to prove (1) if E is empty or F is empty, then E x F is empty and (2) if E x F is empty, then E is empty or F is empty

#

are you stuck on a particular one of these, or both?

weary tiger Mar 18, 2020, 7:14 PM

#

Theres two steps for these?

west hedge Mar 18, 2020, 7:15 PM

#

well, the double arrow you wrote means P -> Q and Q -> P

weary tiger Mar 18, 2020, 7:15 PM

#

📎 20200318_211505.jpg

#

This is the example of thr dr gave us in class

#

But the one i am trying to prove has an = in it which changes a few things

west hedge Mar 18, 2020, 7:16 PM

#

let's just take it easy and prove one direction at a time
it looks like you started to prove that if E x F is empty, then E is empty or F is empty so let's prove this

#

do you have an idea of how to show this?

weary tiger Mar 18, 2020, 7:17 PM

#

No

west hedge Mar 18, 2020, 7:18 PM

#

ok, well I think it will be easier to think about if you consider the contrapositive

#

are you familiar with that?

weary tiger Mar 18, 2020, 7:18 PM

#

The bar part?

west hedge Mar 18, 2020, 7:19 PM

#

contrapositive as in, not Q -> not P instead of the equivalent statement P -> Q

weary tiger Mar 18, 2020, 7:20 PM

#

Yea

west hedge Mar 18, 2020, 7:21 PM

#

the contrapositive of if E x F is empty, then E is empty or F is empty is if E and F are both non-empty, then E x F is non-empty

#

do you agree?

weary tiger Mar 18, 2020, 7:21 PM

#

Yes

west hedge Mar 18, 2020, 7:21 PM

#

ok, and you know that these are equivalent right?

weary tiger Mar 18, 2020, 7:22 PM

#

Ye

west hedge Mar 18, 2020, 7:22 PM

#

ok good
the second one is easier to work with
can you try proving it?

weary tiger Mar 18, 2020, 7:22 PM

#

So we dont add xy to prove it

#

Just like that?

#

The exercise is about cartesian product

#

I think maybe we need to use xy in it like the example

#

Or is it not necessary?

west hedge Mar 18, 2020, 7:23 PM

#

yes, you should consider elements of the sets in question

#

you need to find one pair (x,y) in E x F

#

in order to show that E x F is non-empty

weary tiger Mar 18, 2020, 7:25 PM

#

Let me try putting it in steps one sec

#

📎 Screenshot_20200318-213128_Gallery.jpg

west hedge Mar 18, 2020, 7:32 PM

#

if E and F are both non-empty, then E x F is non-empty

#

we are trying to prove this

weary tiger Mar 18, 2020, 7:32 PM

#

oh

#

📎 20200318_213604.jpg

#

Like this?

#

oh behind the f should be y

#

so its x - y

#

i made it double x by mistake

west hedge Mar 18, 2020, 7:37 PM

#

ok you used the assumption that E is non-empty and F is non-empty to find x in E and y in F
this is good

#

but I don't see you finding an element of E x F