discrete-math

[sand halo]

i mean to say suppose i know the equivalence of q-> p how do i draw it without it looking the same as ~p v q

and yes

[coral parcel]

Just switch around the inputs?

[sand halo]

q would go first?

[zealous elbow]

what do you do if you get an exponent you can't compute for encrypting with RSA

[coral parcel]

Are you looking for something like this?

[zealous elbow]

i assume you use eulers theorem but im not sure how to apply it

[coral parcel]

What do you mean "get an exponent"? If you're generating a key and you find your favorite e won't work, then you either start over with new primes or pick a different e.

[zealous elbow]

umm so say m = 53 and i want to encrypt it and n = 143 and e = 17 it would be 53^143 (mod17)

or is that wrong

[coral parcel]

That is wrong -- you've switched around the roles or e and n.

[zealous elbow]

oh right

yeah that makes more sense thanks again lol

[sand halo]

would it look something like this

and does it matter if ~h is first

where my arrow is pointing

[sand halo]

wouldnt there be a AND

[coral parcel]

Yes, that's one way to do it.

[coral parcel]

yes. but you hadn't talked about that yet.

[sand halo]

oh ok

thanks lots

[pearl hull]

I HATE SUBSETS

[chrome slate]

Hello, I have a task where I have describe sentences with the help of predicate formulas and quantifiers.
I have the sentence: "The only integer which squares to zero is zero"
I tried writing it as:
(∀x∈Z)(x² = 0 → x = 0)

Is that valid?

[pale epoch]

looks good to me

[chrome slate]

I was wondering if I am supposed to use the uniqueness quantifier

[pale epoch]

"there exists exactly one"?

[chrome slate]

I apologize for not responding, I got help from a TA :/

[pale epoch]

👍

[tall oxide]

If A'v C and C'. Can I conclude directly that A' by Disjunctive syllogism?

[weary tiger]

Well yeah, that's exactly disjunctive syllogism

[weary tiger]

yall mind if i put a whole homework question ?

[lusty garnet]

hey all, would {A|A⊆{a,c,e}and|A|≠ 2} just be {a,c,e} in roster notation? if not, why?

[brave rock]

You have missed out subsets of size 0 and 1

In fact you have made a more fundamental error

This set will contain sets, not the elements a, c, and e.

I think you have a more fundamental misunderstanding if you think that a,c,e will be the elements of the set described above. Is that what you're saying?

[lusty garnet]

yeah unfortunately it is

[brave rock]

OK then I think you need to try again.

Are you clear on all the symbols being used there?

[lusty garnet]

kind of, im trying to understand them as i go

[brave rock]

OK that's not great. You must understand the literal meaning of each symbol before you do this question.

Which ones don't you know properly?

[lusty garnet]

would somehting like this be correct: A⊆{a,c,e} is the same as A⊆B if B={a,c,e}

this one ⊆

[brave rock]

Yes but this isn't saying anything interesting; this would be true for any meaning of ⊆.

[brave rock]

A ⊆ B means "A is a subset of B"

What does it mean to be a subset? A is a subset of B if every element of A is also an element of B.

E.g.

{} ⊆ {1,2,3}

{1,2} ⊆ {1,2,3}

{3} ⊆ {1,2,3}

But it is not true that {4} ⊆ {1,2,3}, since 4 is not an element of {1,2,3}.

N.b. it is true that {1,2,3} ⊆ {1,2,3}.

All clear now?

[lusty garnet]

yeah thank you that makes sense, very helpful

[brave rock]

That's great to hear. Try the question again, and justify your answer this time.

[lusty garnet]

so like {A|A⊆{a,c,e}and|A|≠ 2} would be {a} or {{a,c,e}}

because it can't have 2 elements in it and if it had 3 it wouldn't be a subset

[brave rock]

OK this isn't a matter of something or something else

The notation there is specifying a single set.

Are you saying that this set might be equal to {a}?

[lusty garnet]

yeah

set A is {a}

[brave rock]

That is one subset of {a,c,e}, but you need to consider all subsets of {a,c,e}.

Let's start with something simpler.

Compute {A | A ⊆ {a,c,e}}.

That is, write the set of all subsets of {a,c,e}.

Does that make sense?

Do you see why that's what {A | A ⊆ {a,c,e}} means?

[lusty garnet]

all the subsets would be {{a,c},{a,e},{c,e},{a},{b},{c}}

is right?

answer to your question

[stray reef]

where did b come from? also the set {a,c,e} itself ought to be included surely

because 3 isn't 2

[lusty garnet]

the b is a typep

typo

meant to be e

[brave rock]

You missed out two subsets that I mentioned earlier.

[brave rock]

See here.

[lusty garnet]

{{a,c},{a,e},{c,e},{a},{e},{c},{}}

[brave rock]

You've missed out another subset. I'm really not wanting to keep going back and forth on this.

Please go back and read all the examples that I gave.

[lusty garnet]

{{a,c,e},{a,c},{a,e},{c,e},{a},{e},{c},{}}

ahh yes i forgot the full one

[brave rock]

OK

Great.

[lusty garnet]

so that is also the answer to this one too right?{A|A⊆{a,c,e}and|A|≠ 2}

[brave rock]

No.

Do you know what |A|≠ 2 means?

[lusty garnet]

the number of distinct elements in A is not 2?

[brave rock]

That's right.

So now

what are the elements of {A|A⊆{a,c,e}and|A|≠ 2}? Describe them in words.

If you do not know, just tell me.

[lusty garnet]

i dont know what you mean

like what do you want me to describe in words

[brave rock]

OK

What I mean is

Let's say I have some set.

How do I know whether or not it's an element of {A|A⊆{a,c,e}and|A|≠ 2}?

What would need to be true for it to be contained in the set

In fewer words: describe the elements of {A|A⊆{a,c,e}and|A|≠ 2}

Again, if you do not know, tell me.

[lusty garnet]

the elements are gona be a subset of {a,c,e}

[brave rock]

Is there any other property that those elements need to have?

[lusty garnet]

they need to be a set of length 1 or 3

?

just NOT 2

[brave rock]

What you said first is wrong, but what you said afterwards is correct.

You forgot that you can have a set of size 0

[lusty garnet]

ahhh right

[brave rock]

So OK

You've said that the elements of {A|A⊆{a,c,e}and|A|≠ 2} are subsets of {a,c,e} that are not of size 2.

So... write them all out!

[lusty garnet]

{{a,c,e},{a},{e},{c},{}}

thats the answer??

[brave rock]

Perfect. Well done

That's it.

[lusty garnet]

mate thank you so much

[brave rock]

No worries.

[lusty garnet]

you're a massive help

made me understand thing stuff a lil more big thanks

but so like, can you write this out {A|A⊆{a,c,e}and|A|≠ 2} in normal words?

would it be somehting like, a set A, such that set A is a subset of {a,c,e} and each subset is not a length of 2?

[brave rock]

{A|A⊆{a,c,e}and|A|≠ 2} means:
a set, whose elements are the things A such that A ⊆ {a,c,e} and |A| ≠ 2.

Btw we don't use the word "length" for sets. A typically used word is "size," and when we're being technical, "cardinality."

[lusty garnet]

ahhh so A are the elements, not the set

[brave rock]

Yes.

[lusty garnet]

gotchu, thank you so much

i really appreciate the tutorial

[brave rock]

no worries

[atomic goblet]

really curious here

How would one go about making a curve using discrete math

Something, like say the gamma function in discrete time

[little prism]

well a curve is something continuous. so that's pretty much the opposite of discrete math

[atomic goblet]

sure, but you can approximate a curve with discrete math, just like you can approximate integrals and derivatives with discrete math.

[little prism]

Well I wouldn't really call that discrete math. That's more just techniques we use to get around physical limitations and stuff. Discrete math as a field considers completely different things

But then to your question I guess the answer is, just plot a bunch of points and connect them. Just like we plot everything essentially. Unless I misunderstood your question

[atomic goblet]

https://en.wikipedia.org/wiki/Discrete_calculus
is discrete calculus in a different field of math than discrete math?

[atomic goblet]

Well, what i want to do is have an input that can change which if it were constant would create a certain curve if i just keep calling the same math function. Like it would do one step on the curve and then another, etc.

[pearl hull]

Can someone explain me what is a Cardinality>

[weary tiger]

Hello

How do I use quantifiers and predicates?

[shut bolt]

am i able to use definition of exclusive or for this proof even tho it has implication signs on it or would I have to simplify the implications using def of implication to use exclusive or?

[remote crane]

Can I prove this by constructing a~b for any k in z, and would this be enough to show that there are infinitely many equivalence classes for this equivalence relation

[stray reef]

what is it that you're trying to prove?

uncrop please @remote crane

[remote crane]

sorry, just saw your message. Define an equivalence relation on $\mathbb{Q}$ by $a\sim b$ if $a-b=\frac{k}{3^n}$ for some $k,n \in \mathbb{Z}$ and $n>0$

[vital dew]

Mirinim

[stray reef]

uh huh.

[remote crane]

My idea was just to set b = 0, and a = k/3^n and its possible for any k and n to have an equivalnce relation this way

so there would be infinitely many equivalence classes this way

[stray reef]

congratulations you have demonstrated a complete misunderstanding of what the equivalence relation at hand is

[remote crane]

oh

[stray reef]

you are confusing the infinitude of the set of equivalence classes with the infinitude of numbers within one equivalence class

[remote crane]

ok wait I'm confused

so each unique combination of k/3^n is a new equivalence class right?

[stray reef]

no

[remote crane]

ok nvm

[stray reef]

two numbers differing by something that looks liks k/3^n are in the SAME equivalence class.

[remote crane]

hm ok I will look at the definitions again thanks

[edgy vine]

Kinda irritates me why they define multigraphs only with multiplicity 0,1.

So if I have 3 edges between two nodes, I thought multiplicity is 3. But do we here just treat it as one edge, and say the multiplicity is 1?

[coral parcel]

That's not what it says.

It says that IF a multigraph has multiplicities only 0 and 1, THEN it's also a graph.

A multigraph can perfectly well have higher multiplicities. That just means that it's actually "multi-".

[edgy vine]

aahh oops

ok

ty for clearing my thought. I was totally confused by misreading that line

[edgy vine]

Just to clarify. It does not matter right if {u,v} collapses to u, or to v. The graph would look the same upto the name of one node.

Because later I get to see an algorithm:

where I am thinking what they mean with min{u,v}. I assumed there is a strict order on the nodes V.

[glad panther]

The set R of real number is complete.
True or false?

[coral parcel]

The choice of survivor nod "does not matter" in the sense that the results are isomorphic between the two picks.
But one may still feel that to have an "algorithm" you ought to specify some deterministic way to make the choice.

[coral parcel]

Do you have a concrete definition of the word "complete" that you can test against?

[glad panther]

No , In discrete mathematics

[coral parcel]

Do you mean you don't have a definition of the concept you're asking about?

[glad panther]

Yh , without a concept just the question is
real number is complete or not.

[coral parcel]

R is Dedekind-complete as an ordered set. It is also complete as a metric space. But if you don't have a definition to refer to, then for all we know it might not be either of those two (different) concepts you're talking about; it could be something else entirely.

[glad panther]

ok thanks I understand it.

[brave rock]

The real numbers are not complete, because they have a long-lost love that they still pine after, but they don't feel they can approach them and tell them how they feel 😔

Putting that aside

If this is a question you've been asked to discuss, clearly you need to think about what that means yourself.

I don't think anyone can give you a proper answer to that haha

I think mine's pretty close though

[coral parcel]

Tune in tomorrow where we will discuss whether the real numbers are a complete infinity or merely an unbounded concept!

[vale cairn]

Let's discuss potential vs actual infinities and address the Münchausen trilemma

[lusty garnet]

question: i am faced with the following in which i have to write it in set builder notation, is my answer correct?
The set of all pairs where the first element of the pair is an element of S and the second element of the pair is a subset of S that does not contain the first element of the pair.
ANSWER: {x,y | x ∈ S, y ⊆ S ≠ x}

if not correct please don't share the answer, just tell me where i am wrong in my thinking, thank you 🙂

[weary tiger]

x and y are pairs, are they just pairs or ordered pairs?
You should think about how to represent that in your set builder notation in either case.

second, think about the representation of the condition for y

[sweet thunder]

Does this work for a). How can I explain that Z—>Z+? How do I include the negative values?

[stray reef]

are you trying to make a bijection {intgers not divisible by 3} -> {positive integers} or the other way around?

it's kind of annoying to write one down here in either direction actually...

[clever sage]

If n equivalent to 1 mod 3, map to evens, if n equivalent to 2 mod 3, map to odds?

[sweet thunder]

Yes integers not divisible by 3 to positive integers

[sweet thunder]

Yea that didn’t work as well as I had hoped. I don’t see a pattern with what I have.

[clever sage]

I found it helpful to plot to visualize a bijection, i.e. (1,1), (2,2), (4,3), (5,4)

and that'll allow you to not have any overlap

hmm

but that doesn't allow for negatives

[sweet thunder]

I drew a visual to help me. If I do the functions I have listed where f(n) is the piecewise function where 3(n)-1 is used for odds and 3(n)-2 is used for evens, could I just use -(f(n)) for the negative integers?

This is a suggestion from a friend.

[clever sage]

negatives of 1 mod 3 2 mod 3 get mapped to positive integers 1 mod 4 2 mod 4, positives get mapped to positive integers 3 mod 4 0 mod 4?

[chrome slate]

Is it possible to write S as:
S = {(x, y): x ≥ y}∈ N " ?
Or do I have to include the iff in it?

[pale epoch]

this doesnt work but not for the reason you state

S is certainly not an element of the natural numbers

[chrome slate]

So what if I write it like this?

[pale epoch]

that is less wrong and probably fine

the "correct" way would be ${(x, y) \in \bN^2 : y \geq x}$

[vital dew]

Lochverstärker

[chrome slate]

ohh that makes sense

[pale epoch]

generally when you use set builder notation you can only define subsets of some larger set

so to the left you have to denote "where the elements come from" and to the right some proposition that they have to satisfy

in this case they are tuples from N^2 and have to satisfy some order relation

[chrome slate]

what's the difference between N and N squared?

I don't know how to search it without only getting results of square numbers

[pale epoch]

N is the natural numbers, N^2 is the set of tuples consisting of natural numbers

[chrome slate]

ohh thanks <3

[weary tiger]

can someone help me with this?

[weary tiger]

<@&286206848099549185>

[brave rock]

#❓how-to-get-help

[weary tiger]

i already did go into oneo f the channels

no one helped me

@brave rock

[chrome slate]

How do I create a bijection between Z and {n ∈ N : 2|n} ?
I tried creating a function: f(x) = 2|x| however that would not be 1 to 1 as -1 and 1 both map to 2.
Can I split it so all negative numbers map to 2(2k+1) and positive numbers map to 2(2k) ?

[pale epoch]

sure, why not

[chrome slate]

[elder berry]

to obtain the matrix of R^-1 from R, you transpose the matrix (meaning the number of zeroes or ones don't change, there place in the matrix is altered)

for b), think about what happens when you look at the matrix of complement(R) versus the matrix of R

anytime you have an element in R, you won't have it in complement(R) and vice versa. now formalize this in terms of 1's and 0's

[weary tiger]

solved it, thanks @elder berry

[lapis bough]

Can someone help me solve this

[stray reef]

have you done as instructed for part (a)?

[gleaming minnow]

If anyone here knows set theory well, please check out help-#2. I'm struggling

👀

[analog marsh]

#help-2

[remote crane]

Is this just $(-\infty, -1]\cup 0\cup [1,\infty)$?

[vital dew]

Mirinim

[remote crane]

am i supposed to put a set symbol around 0 or no

if its just a single point

[weary tiger]

No shot that's it.

[sick grail]

Also yes you do need to write {0}

That c is so small I missed it at first

[weary tiger]

oh lol

[sick grail]

So it actually is correct

[haughty laurel]

@chrome slate han læreren løste den oppgaven i en av timene våre

[chrome slate]

hjelpelærer eller?

[haughty laurel]

jeg?

[chrome slate]

Hvilken lærer? husker ikke å ha sett dette før

[haughty laurel]

glen, faen husker ikke hvilken panoptic video det var

men han gikk hvordan man finner en bijeksion

tror det var den nyligste faktisk

[chrome slate]

Kan jeg DMe deg?

[haughty laurel]

sure

[lapis bough]

No I haven't please help

[lapis bough]

Anyone

[stray reef]

http://google.com/search?q=how+to+plot+a+function+in+mathematica

[night stream]

hi! can some please make sure i did this correctly

[brave rock]

You have not shown all your work; you've just shown a calculation without any justification.

Use your words to explain why the calculation shows what you want to prove.

[wind stream]

What is the expansion of (x + x^2 + x^3 + x^4 + x^5 + x^6)^n using multinomial coefficients?

Or more specifically. What is the coefficient of the term x^k

[pearl hull]

UGH, tomorrow I have an exam

I hate you discrete-math

[remote crane]

discrete-math still loves you

[remote crane]

I'm trying to do #3, does rationals of the form [1/p] where p is prime form an equivalence class?

[dry stirrup]

is there ever a case where the power set of a set has the same number of elements of the cartesian product of a set and itself?

so |P(A)| = |A X A|

[harsh osprey]

@dry stirrup yes

|P(A)| = 2^|A|

|A X A| = |A|^2

so if A has two elements this should work

and as an example, let A = {1,2}

then P(A) = {{},{1},{2},{1,2}} and |P(A)| = 4

and A X A = {(1,1),(1,2),(2,1),(2,2)}

and |A X A| = 4

[dry stirrup]

ahh makes complete sense

so there's no other set that would satisfy this right?

as in a set with cardinality 2

[harsh osprey]

well for finite set sizes you’d need 2^x = x^2

and 2 is the only integer there

I don’t think you’re looking for infinite set sizes but I may be wrong? but I don’t think any infinite set sizes do this

[dry stirrup]

yeah i mean for finite sets

u cleared it up for me thanks a lot

[harsh osprey]

hello

I’m looking for help with the following problem, please tell me where to go if not here

I’m looking for a function where I can input a binary number and it outputs the following

for each digit of the binary number, read left to right, if that digit is 0 it adds nothing to the output, and if that digit is 1 it adds 2^(i-1) * a^j to the output, where i is the digit placement read left to right, a is a constant, and j is the number of 1s to the right of that digit

so for example it would take as input 101101 and output 2^0 * a^3 + 0 + 2^2 * a^2 + 2^3 * a + 0 + 2^5

and I don’t know how to write this function in a more easily manipulateable form, or even if there is a way to do that

I don’t know how to formalize “the number of 1s to the right of a digit” like that

hell, I don’t know how to formalize something that acts on each digit depending on its place in the sequence and whether it’s a 1 or a 0 either

if this isn’t the best place to ask please let me know

it would also be helpful to have a function that counts the total 1s in the string too

note it doesn’t have to be 1s and 0s

any ordered list with each item having 2 options is sufficient

a binary number simply seemed the most natural way to do that to me

[last timber]

this would be something like hamming distance

if there are only two options then take hamming distance between your string and string consisting from not 1

otherwise it would be
length of string - hamming distance (your string, string of only 1's of the same length)

informally speaking ofc

[last timber]

well ig the best defn here would be recursive

[harsh osprey]

I eventually found a way of writing it down concisely but I still don’t have a way to manipulate it

I wrote it as a sequence of terms and summed them all up by index

[last timber]

yes like that

[harsh osprey]

it’s just that I still can’t manipulate yt

I don’t think I can get better than this though, unfortunately

I’ll try more later by playing around with numbers & seeing if there’s any sort of useful pattern, but...

[pearl hull]

FUCK YEAH, I PASSED THE TEST!!! WOOO

[brave rock]

Well done 👏

[harsh osprey]

ohhhh I just had an ideaaaaa

I now have a function which I can use to count the total number of ones

and I’m close to being able to count the total number of 1s past a certain point

but i’m gonna need to play with it more with paper once I can get paper

or more accurately once I can get light, my roommate is asleep lol

[weary tiger]

Can anyone explain how I can simplify this using the identify rules?

xy + x'z + yz

Here is what I did. I am not sure if it is correct.

xy+ x'z + yz

xy +x'z + yz(x+ x')
xy + x'z + xyz + x'yz

xy(1 + z) + x'z(1 + y)

xy (1)+ x'z (1)

xy+x'z

[elder berry]

That's good, you can't simplify further

[weary tiger]

Ok thank you very much.

[last timber]

#discrete-math message

[harsh osprey]

not recursive

I’m experimenting with just representing the string as an n-dimensional vector, because then dotting it with itself counts the number of 1s

[brazen coral]

If I have planar graph
And I know it's triangle-free
So I get
m<=2(n-2)
And if it's a normal planar graph I get
m<=3(n-2)

But what about square-free & triangle-free planar graph?

I can't find a way to bound the number of edges

I try to use Euler's.where you get n+f=m+2 where f is the number of faces

[floral field]

If I want to find the chromatic polynomial of the Circle Graph with 4 vertices, would I have to consider the cases where the corners are/are not the same colors?

My first guess was
k^2 (k-1)^2

[remote crane]

I want to prove part iii), showing that there are infinitely many equivalence classes for this equivalence relation.

Does this work?

[vale cairn]

Your argument doesn't seem too clear to me - what exactly is the contradiction?

[remote crane]

I was trying to show that each 1/p and 1/q arent in the same equivalence class

[vale cairn]

I also assume there is a typo lurking there as you say "there's no k"... but then pq/(q-p) doesn't involve k

[remote crane]

oh my god

[vale cairn]

Yes, but what is the contradiction used in your argument

[remote crane]

ok my argument is still the same I think

I think it should be $k=3^n\frac{pq}{q-p}$

[vital dew]

Mirinim

[remote crane]

Suppose that k/3^n = 1/p-1/q

after algebraic manipulation, 3^npq is odd, q-p is even

so there is no whole number k that this equation can work

sorry, I typed that up badly

I fixed it here:

[vale cairn]

That's a nice argument then!

:)

Only thing is I'd say "each fraction of the form 1/p is in a distinct equivalence class" or something

But cool - I'd have given a really different argument (but not shorter) so this is nice to see

If you're interested: Suppose there are only n classes and let $a_i$ be the least positive element of the ith class. Then the least element of ${a_1,\dots,a_n}$ is a least positive rational number, a contradiction

[vital dew]

potato

[remote crane]

that is rly smooth

[vale cairn]

Oh thanks but yours is really quick too

If you know any topology, there's another way to see this I guess

[remote crane]

Probably later then, my topology class just started, barely covered bases and stuff

[viral turret]

??

[weary tiger]

A signal x[n] = {1, 2, -2, k} was applied to the input of an LTI discrete system. The registered output was y[n] = {1, 5, 3, (-5+k), (8+3k), (-6-k), 3k}. What is the h[n] impulse response of this system?
I'm trying to learn this stuff but my brain is melting. I can't seem to think of a way to calculate the impulse response. Would appreciate a if someone could give some direction

[thin galleon]

Consider a 6 ×6 square whose side length is 6 units. Suppose we are given 33 points in a 6 ×6 square. Must there be three points whose
pairwise distances from each other are at most √5 units?

Can anyone give me some hints on this?

I guess it is right

So I have tried dividing the square into pieces to apply PHP

[austere cedar]

That is the right approach. You need to find the right pieces. If you want a hint, first ||try to find out how many pieces you want to get|| and then ||try to cover the 6x6 with that number of pieces||. A good idea is also to ||choose congruent pieces that have not an ugly shape||

[lavish dagger]

Do any of you know how to solve 3b)? I am trying to help my little sister to solve it, but I am very rusty and haven't seen that notation before, so I could use some help/guidance if anyone in here has some resources to share.

[coral parcel]

Which notation is it you have problems with?

$R\circ S$? Or $\mathbb N^2$?

[vital dew]

Troposphere

[lavish dagger]

the circle between R and S. I am not really sure what it means

[stray reef]

composition of relations

[lavish dagger]

Does that mean that the task is to prove that R and S "put together" is the same as N^2? Sorry if that sounds weird, english is not my first language.

[stray reef]

"put together" is a little vague and also sounds like a different thing with a different name

composition is a pretty nontrivial operation

would not blame you for not knowing what it means off the top of your head

$R \circ S = { (x,y) \in \bN^2 \mid \exists z \in \bN: (x,z) \in R, (z,y) \in S}$

[vital dew]

Ann

[stray reef]

this is the definition

with some more general parts of it specialized to your case

[lavish dagger]

Thank you so much for explaining, I think I'll be able to make some sense of that!

[severe owl]

hi can someone explain why ~T v ~U got negated?

[severe owl]

NVM I GET IT

[spring elk]

can i get help with this? trying to prove it by contradiction (not a union b is not equal to universe)

nvm i thibk i figured it out. can someone let me know if its rigjt?
what i did was say let x be the element of not A and also an element of B
since x is al element of not A it is therenore not an element of A.
But if x is an element of B but not of A then A cant be a subset of B

therefore not A union B has to be the universe.

[thin galleon]

Solved. Thank you.

[sick grail]

"If x is an element of B but not of A then A can't be a subset of B"?

Why not

[remote crane]

nvm im dumb

[spring elk]

hm.. my bad. in that case what I need is x to be an element of A but not of B and then I can draw that conclusion

[sick grail]

You would draw the conclusion that A is empty

[spring elk]

how can i draw that conclusion

[sick grail]

You can't draw the conclusion that A is not a subset of B

You can draw the conclusion that no such x exists

[spring elk]

ah right.

[sick grail]

This is assuming that you're getting x from somewhere else

[spring elk]

yeah. Ill give it another try and see if i can reach this conclusion

cant manage to solve it.

is doing this proof by contradiction a good approach?

[sick grail]

If would do it directly

So like "Suppose A subset B. Consider x in U. (Show x is in not A u B, so U equals that). Now suppose not A u B = U. Suppose x in A. (Show x is in B, so A subset B)"

[spring elk]

if i consider x in U then to show x is in not A u B what i can do is:
Since x is in U then x is also an element of A union not A so x is an element of A or an element of not A. If X is an element of not A then its also an element of not A u B

is this valid?

this would be for case 1. still have to do second case

for case 2 i still cant manage to do it directly. and even if i could prove it directly I still have to show that these 2 cases only hold for these conditions since its an if and only if.

[viral turret]

Does anyone know how to solve knights and knaves questions?

[hollow siren]

What is the first math topics i should go for to master programming and Machine Learning?

[verbal crystal]

I just started doing some set stuff. Did I get these questions right?

I'm really not that sure about the last 2

[forest quartz]

the order of a set doesn't matter hence you did the second last question right

[verbal crystal]

Nice, I just assumed. Good to know I was right. For the very last one, it only contains {a} on the interval from [a,a] so I think that is right, but I'm not sure

[elder berry]

[a, b] = { {a}, {a, b} } while [b, a] = { {b}, {a, b} }

the above do differ

[forest quartz]

they do but in a set an order doesn't matter

[elder berry]

The first set has {a} as an element, whilst the second has {b} as an element, given distinct {a} and {b} they are not the same

[verbal crystal]

Would it not be this?

[a, b] = { {a}, {a, b} }
[b, a] = { {a, b}, {a} }

[forest quartz]

yeah, but order doesn't matter

[elder berry]

no, where did you conclude [b, a] = { {a, b}, {a} }

[verbal crystal]

because the a by itself denotes the {a}

and the b is {a, b}

[elder berry]

how is b suddenly {a, b}?

[verbal crystal]

they are sets within a set right?

[forest quartz]

yeah

[verbal crystal]

b was always {a, b} right?

[a, b] = { {a}, {a, b} }
            a,    b

[forest quartz]

oh and u got the second question wrong

[elder berry]

I wouldn't listen to the above user...

[verbal crystal]

can we get a 3rd person in here to validate someone lol

because idk what to think right now

[elder berry]

The definition of [x, y] is { {x}, {x, y} }.
Do we agree that [a, b] is { {a}, {a, b} } @verbal crystal ?

[forest quartz]

get ur fundamentals right man its okay to be mistaken

[forest quartz]

we do

[verbal crystal]

yes

[elder berry]

Great, do we agree that [z, w] is { {z}, {z, w} }?

[verbal crystal]

yes

[forest quartz]

yes

[elder berry]

Then, it is perfectly reasonable to say [b, a] = { {b}, {b, a} }

agreed?

[forest quartz]

yes

[verbal crystal]

so the variables of the sets within the set get changed?

[elder berry]

The order in {b, a} or {a, b} doesn't matter, what matters is now that {b} is an element that is alone

[b, a] = { {b}, {b, a} } = { {b}, {a, b} }

does that make sense so far?

[verbal crystal]

yeah im following

[elder berry]

now, when you compare [a, b] = { {a}, {a, b} } and [b, a] = { {b}, {a, b} }, you need to compare if every element on the left is an element on the right

[forest quartz]

{b,a} acts as an element in the set

[elder berry]

{a, b} are both there, that we can all agree

however, whenever {a} is distinct to {b}, you are missing those terms in each of those sets

for the sets to be equal, both of them need to be { {a}, {b}, {a, b} } which is not the case

[forest quartz]

i see i see

[elder berry]

so [a, b] and [b, a] are not the same

[verbal crystal]

alright I guess that makes sense also. I didn't realize the variables would be changed around as well

[forest quartz]

this

[elder berry]

your last answer is correct!

[a, a] = {{a}}

[verbal crystal]

nice

[elder berry]

btw, what the authors of this problem are hinting towards, is the ordered pair, the very definition of [a, b] is actually how some people define the ordered pair (a, b) (not to be confused with the interval between a and b, very different things)

[forest quartz]

yes- the reason is all the elements in a set are distinct

[verbal crystal]

what about the other answers? anything else look wrong?

[elder berry]

I quickly glanced at those before your last two answers, and I didn't find anything faulty

[verbal crystal]

at least I understand some of it lol

[forest quartz]

The question was asked in roaster method, i think set builder would suit the element's correspondence more accurately

[verbal crystal]

so it is an ordered pair and not an interval?

[elder berry]

it's an ordered pair, that is why (2, 3) and (3, 2) are different, because order here indeed matters

More here if interested: https://en.wikipedia.org/wiki/Ordered_pair#Kuratowski's_definition

[verbal crystal]

that makes sense. thanks!

[elder berry]

np

[verbal crystal]

New question, is this a sound proof?

I tried to use double inclusion, but idk if I did it right

[brave rock]

I'm not sure why you're using triple equals. You oughn't.

You haven't really shown double inclusion, at least I don't see it.

[verbal crystal]

It reads as "equivalent to" right?

[brave rock]

If you're talking about sets, this is not defined.

You should just say =. They are equal.

[verbal crystal]

Oh I see

[brave rock]

There are three cases that I see triple equals used:
(1) For a formula which holds for all variables involved, such as x + y = y + x — although this is rare further on.
(2) For logical equivalence of propositions.
(3) For modular arithmetic.

Also I'm not convinced by your proof.

You kind of just state the definition, and then claim that the conclusion is true.

If you want to prove double inclusion, take an arbitrary element of one set and show it is also an element of the other.

(and vice versa, of course.)

[verbal crystal]

So would you say the definition I wrote before the "this means" part is correct?

[brave rock]

The bit after the "then" is by definition

The equality you wrote just after that is also correct, it is true that y in (B u C) is equivalent to (y in B) or (y in C)

You claim that the rest follows, but I think you should do more work to show that.

[verbal crystal]

Gotcha, I'll try again and post the updated one in here to see if I got it right, thanks

[verbal crystal]

@brave rock Is this one good?

I did it for both sides this time

[brave rock]

I will check in a moment.

[verbal crystal]

no rush

[sick grail]

I would change the 'since' in the light blue to 'if'

[brave rock]

I agree with that

Yes this is one inclusion.

I would maybe just

Well actually nvm.

This works.

[verbal crystal]

Nice, but still would say change the since to if?

or the blue "since" rather

[sick grail]

'Since P, Q' usually means P is true

But it doesn't have to be here

Sometimes y in B, sometimes y in C

[verbal crystal]

I see

Alright changed that, does everything else look good?

[sick grail]

The proof is correct and doesn't skip steps

[verbal crystal]

Nice, thanks guys

[sick grail]

At best there could be minor improvements to style but a) that doesn't really matter and b) I find proofs like this flow weirdly anyway so it's wouldn't be much of an improvement

And c) it's subjective so it's really just my opinion

[verbal crystal]

Gotcha, I've done less than 10 proofs so far, but I'm sure I'll get better with practice. I appreciate the help again

[strong plank]

I need to proof that domination number ≤ independence number for all Graphs.
Idea: A maximum Independence Set is a dominating set (all vertex are dominated). Let G be a Graph with V = (G,E) and U is a maximum independent Set (Which would be the independence number because of highest k) For all vertex in V \ U, if one vertex is left then there is a bigger Independent Set U. This is a contradiction because U is a Maximal. So U is a maximum dominating Set.

From here it gets difficult for me how to build a connection to domination numbers. My Idea would be that there could be a Subgraph with has less vertexes then independence number and if so case 1 follows: domination number < independence number
Case 2: There is a equality so dn = inn
In the following dn ≤ inn but i think that is not legal.

[verbal crystal]

Where does the n(n+1)/2 come from in this: 1 + 2 + 3 + ... + n = n(n+1)/2?

[strong plank]

its the gaussien sum. If you sum until a specific number until n you are caulculating (1+n)+(2+n-1)+(3+n-2)+... what all is n+1 and this calculation is done n times which leads to n(n+1) throgh the addition in front in back you have to divide it by 2 -> n(n+1)/2

[verbal crystal]

Ah thanks

[strong plank]

maybe that will help you

[verbal crystal]

So if I am trying to prove by induction 3 + 6 + 9 + ... + 3n = 3n(n+1)/2, would I do the proof by factoring out the 3, or would I keep it in?

[verbal crystal]

This is what the questions said

I wrote this:

Did I do it right?

[true venture]

Is there a name for graphs whose nodes lie on a hexagonal grid and are only able to be connected to their eight neighbors?

Some examples of what I'm trying to describe.

[coral parcel]

You mean six neighbors?
(And no, I don't know of a name -- neither for the equivalent concept on a square grid).

[true venture]

Oh yes, 6 neighboors

[true venture]

Thanks, I'm trying to think of a concise way to describe these. But I guess I can just explain how I said above.

[remote crane]

Is this problem just asking me to show that f(phi(z)) is injective

or maybe im just reading notation wrong

[last timber]

it may depend on what order of evaluation of ф o f your book suggests

if ф о f = f(phi(x)) then you are correct

but it might by that you have phi(f(x))

@remote crane

oh wait

[remote crane]

uh i think it's from right to left

oh no

I should double check lol

oh yea

its phi(f(z))

[last timber]

ф has X as domain, so f(z) should be evaluated first

so ф(f(z))

[remote crane]

yea forgot about that but how can this be true?

can't there be 2 z that map to an element in x

and then even if X injective it doesnt matter

[last timber]

to show injectivity you should show that if
Ф(z_1) = Ф(z_2) then z_1 = z_2

or contrapositive

if z_1 != z_2 then Ф(z_1) != Ф(z_2)

[remote crane]

so phi is injective, so f(x1)=f(x2) implies x1=x1. but there are no restrictions on f

so I am confused about that

[last timber]

assume Ф(z_1) = Ф(z_2)

then ф(f(z_1)) = ф(f(z_2))

since ф is injective then f(z_1) =f (z_2)

[remote crane]

ok wait are z_1 and z_2 in X?

[last timber]

wait no i am wrong

no z_1, z_2 are in Z

ok lemme think

actually you are wrong here

you are not showing that ф o f is injective

you are showing that mapping of f to ф o f is injective

[remote crane]

[last timber]

ф o f itself might be not injective

[remote crane]

oh ok that makes more sense lol

[last timber]

so assume there are f_1 and f_2 such that ф o f_1 = ф o f_2

you have to show that f_1 = f_2

[remote crane]

ty ill try it

[last timber]

or contrary if f_1 != f_2 then ф o f_1 != ф o f_2

i mean then it would imply that
ф f_1 z = ф f_2 z for all z

assume this fails for some z*

[last timber]

like we have f_1 and f_2 such that ф o f_1 = ф o f_2
.

if f_1 != f_2 then there is some z* such that
ф o f_1 z* = ф o f_2 z* and f_1 z* != f_2 z*

but you can see from here that it contradicts injectivity of ф

@remote crane

[remote crane]

thanks I'm trying to see it for myself 💀 too many symbols get confusing but i kinda get it

[last timber]

ask if you need additional help

[chrome horizon]

https://media.discordapp.net/attachments/423244559682764800/1022458217764233296/20220922_161138.jpg

[chrome horizon]

Can you solve this questions

[coral parcel]

Probably. Do I have a good reason to try, though?

I do have a moment to point and laugh at question 2, though -- it says \propto when it meant \alpha.

And question 7 switches variable between n and x and becomes nonsense as a result.

[brave rock]

I hope you at least read #rules :)

[outer kayak]

Does this proof suffice?

this is my first proof I have ever done, I need to study more

[elder berry]

I assume the claim is for every positive integer > 1, otherwise the claim is false

By which definition do we have that for any integer p > 1 is either prime or composite? (your last sentence)

[outer kayak]

this was the prompt

[outer kayak]

i believe by the definitions of prime and composite

[coral parcel]

"Every integer > 1" is not the same as "every positive integer".

[elder berry]

I'm not really convinced by the arguments, you just stated the definitions and said it's trivial. A little more work is necessary.
Anyways look at what happens with the positive integer 1

[outer kayak]

ah youre right

[outer kayak]

I see ughhh

[outer kayak]

if im not mistaken one is the edge case that would make this statement false

[elder berry]

ye

[outer kayak]

is this an ok conclusion "1 is a positive integer that does not fit into any of these definitions, which invalidates the claim."

[elder berry]

Sure, you can also explain why that is. 1 fails the definition to be a prime because a prime number must be greater than 1; and also it is not composite since it does not have a divisor other than 1 and itself.

[dense glade]

Is this correct

[vapid blade]

Okay I am trying to figure out subsets and elements. I've got this set S={3,4,5,6,7}. And I can' figure out which are incorrect and correct. I have: 4 ∈ S , 4 ⊂ S , {4} ⊂ S , {4} ∈ S. I don't know the difference between them and it's driving me crazy!! Any help is appreciated!

[vapid blade]

I did say that 4 ∈ S is correct and I also said 4 ⊂ S is correct but I'm unsure

[coral parcel]

4 ∈ S is true indeed.

But 4 ⊂ S means "every element of 4 is also an element of S" -- but 4 isn't a set, so it doesn't make sense to speak of "elements of 4". The claim 4 ⊂ S is so wrong that it's not even false but nonsense.

(ZFC pedants please shut up here).

With me so far?

[vapid blade]

Yeah so far!

[coral parcel]

Similarly {4} ⊂ S means "every element of {4} is also an element of S". Now {4} is a set, in contrast to 4, so this claim at least makes sense. What are the elements of {4}?

[vapid blade]

Would it be 4 and that empty element? (Looks like a zero with a line through it)

[coral parcel]

Half right.

4 is an element of {4}, but there are no other elements of {4}.

By definition the notation {4} means "the set such that 4 is the only thing that is an element of it".

So since 4 is the only element of {4}, is everything that's an element of {4} also an element of {3,4,5,6,7}?

[vapid blade]

I want to say it is but then again I'm not sure.

[coral parcel]

It is.

4 is an element of {3,4,5,6,7}, and that is the entirety of what "{4} is a subset of {3,4,5,6,7}" means.

[vapid blade]

Ohhhhhh it makes more sense to me now!

If I was dealing with Ø could I apply the same logic?

[coral parcel]

I want to say yes, but it really depends on whether your idea of "the same logic" is correct.

[vapid blade]

Like if I replaced that 4 with Ø. Or if I applied Ø into how you explained what the symbols mean in english.

[coral parcel]

Okay. Ø has no elements, so if we ask "Ø is a subset of {3,4,5,6,7}" it turns out there is no conditions to check! So it is true by default.

The only way Ø can avoid being a subset of some A (as long as A is a set in the first place) is if we can find a thing that is an element of Ø, but is not an element of A. Even the first of those conditions is impossible in itself, so there is nothing that can prevent Ø from being a subset of A.

[restive marsh]

Hey all i'm trying to solve the following.
Give an example of three sets A,B and C such that A ∈ B, A /∈ C and B U C = ∅.

So far I have A = (1,2) B = ((1,2,)), C = (3,4) but I can't figure out how to get BUC = ∅.

Any advice?

[coral parcel]

That looks impossibe.

If A is an element of B, then A is also an element of B union C, and then that union is not empty.

[restive marsh]

oh so im not wrong to be confused lol

[dense glade]

Any help? Lost on the last

And 3rd unsure

[dense glade]

Any thoughts

[coral parcel]

The thoughts I had were:

If A is an element of B, then A is also an element of B union C, and then that union is not empty.

[dense glade]

Beautiful

[lusty garnet]

hey all, the following statement is true right? Ifg:A→B is serjective and f:B→C is also serjective, then f◦g is serjective.

if not, why?

[coral parcel]

Yes.

[lusty garnet]

can you explain why real quick? im not fully confident about why i think it's a true statement

[coral parcel]

You should be able to prove it yourself -- it is a straightforward definition chasing proof.

[lusty garnet]

i only did with the drawings,

how woul dyou do it with set notation?

[dense glade]

Apply definition of surjective to fog

I think

[thorn mirage]

can someone explain what inside the red circle means?

[lusty garnet]

am i right in thinking that the following f :R→R, given by f(x)=x2 +10. is an injective function?

[last timber]

domain of proposition i guess

[unreal yew]

can someone help me with a

[coral parcel]

Count lettuce and carrot plans separately and multiply.

[wintry merlin]

is it a surjective fucntion?

[stray reef]

what do you think?

(a) "I think it is surjective"
(b) "I think it is not surjective"
(c) "I know what a surjective function is, but I'm not sure whether this one is"
(d) "I don't know what a surjective function is"

[sonic snow]

he's definitely option d

i was on d

then googled "surjective function"

and then i was like "oh"

[vivid bison]

was working on this question

For a) I got 3^n since there are 3 possible values for each number we input in f making it have 3^n possible answes so |T_n|=3^n
i dont know how to do b) and c) since it asks a bijection from S_n to T_n. So S_n is just an ordered pair, so it can be any integer A, B.
But I dont quite get what the output of g should loook like....

[stray reef]

S_n is not "just" an ordered pair

S_n consists of ordered pairs of sets...

[vivid bison]

damn

[stray reef]

given a pair of sets (A,B) where A subset B subset {1,2,...,n}, your job is to construct a function from {1,2,...,n} to {1,2,3} that reflects this pair of sets somehow

[vivid bison]

can I try an example first, i still feel confused

So suppose we have (A, B) = ({1, 2}, {1.. 6})

So g(({1, 2}, {1..6})) = f: {1 .. 6} -> {1, 2, 3}???

[stray reef]

what value of n are you going for

[vivid bison]

was going for n=6

but B doesnt need to have n right

[stray reef]

of course it doesn't

anyway... idt i can give any hints for this construction w/o just disclosing it entirely

so here goes

for a pair of sets A subset B subset {1,...,n}, create a function from {1, ..., n} as follows:
send all elements of A to 1,
send all elements of B that aren't in A to 2,
and send everything else to 3

[vivid bison]

everything else means elements that is not in A and B right?

[stray reef]

everything else means points that don't belong to B, yes

saying "not in A and not in B" is redundant

anything not in B will also not be in A automatically

[vivid bison]

ohhh i see

So in reverse bijection we do something similar? We need to distribute {1, 2 ...n } into three sets A, B, C?

[stray reef]

not quite

for the inverse you are now given a function f: {1,...,n} -> {1,2,3} and need to construct a pair of sets from it where one is a subset of the other

but it is not hard to see how to go "backward" in my construction

you take A as the set of all things that f maps to 1, and B as the set of all things that f maps to 1 or 2

[vivid bison]

Yeah I think I get it now

thanks a lot!

[dry stirrup]

not sure if this is the right place to ask but why does it say n choose 20 subsets?

if its a brute force solution arent we checking all 2^n subsets?

[stray reef]

we are only checking subsets of size 20

[dry stirrup]

so would the running time be O(ncr)?

i dont really know how to determine the time complexity for that

[stray reef]

for fixed r it's O(n^r)

if r is an appreciable fraction of n it's going to be exponential

[dry stirrup]

oh ok im dumb

yeah that makes sense

thank you

[weary tiger]

p^r = inverse relation. Let p be injective. Then p is a bijection between dom(p) and ran(p). Hence p^r is automatically injective. We can then say a relation is injective [if and only if] if it is bi-injective. What’s with the redundancy?

[stray reef]

i don't think so. if you consider the relation from N to N given by rho = {(n, 2n) : n ∈ N} then it will be both injective and surjective but rho^r fails to be surjective

[weary tiger]

for any n from ran(rho^r) though we can find a b from dom(rho^r) such that b/2=n. So there is a surjection: 2 —> 1, 4 —> 2, etc…

the even numbers and N have the same cardinality too

[stray reef]

yes but ran(rho^r) is the set of all even naturals and not all of N

3 ∉ ran(rho^r)

[weary tiger]

dom(rho^r) and ran(rho^r) don’t have to have the same elements for surjectivity to occur. in rho 3 maps to 6 and in rho^r 6 maps to 3. We are just switching the elements of each tuple which doesn’t affect surjectivity or injectivity

if f is a bijection than f^-1 is a bijection

[stray reef]

you misunderstand

we are not interested in cardinality alone

ran(rho) = {even naturals} ≠ N. do you agree with this or not

[weary tiger]

yes

[stray reef]

ok wait hold on i screwed up a bit

rho^r = {(2n, n)} is injective and surjective, but (rho^r)^r = rho = {(n, 2n)} is not.

[weary tiger]

why is rho not ;-;

[weary tiger]

a relation doesn’t necessarily have to be a subset of A x A. It could be of A x B

[stray reef]

ok sure but i am simply presenting an example

and i can have the domain and codomain be the same set if i so desire

[stray reef]

rho is not surjective. its range is the even naturals. its range is not equal to N.

[weary tiger]

alright

[grand totem]

ρ = { (x, y), (x, y') } is injective, but for distinct y, y' the inverse relation won't be

[dense glade]

What would the ss be for 3

[valid sentinel]

In a group of students, 47 speak English, 38 speak Spanish, and 29 speak Chinese. You also know that 16 speak English and Spanish, 13 speak Spanish and Chinese, and 13 speak English and Chinese. There are 6 students who speak all three languages. How many people speak at least one of the languages?

I kinda went with a statistical approach and drew a venn diagram. My answer to this was 78 but Im not entirely sure

[stray reef]

show your venn diagram

[weary tiger]

It'll be like this....if you add you get 78

[hardy pelican]

I have a question,
If i have a function : Z -> Z, defined by f(n) = n^2 -1.
How can i figure out if its injectiv or surjective ?

[brave rock]

You try to prove or disprove the definition, using your intuition and proof techniques.

[cerulean wind]

recall that x^2 is an even function.
look for any integer that is not one less than a square

[weary tiger]

hi

is anyone here able to help me

@brave rock

@cerulean wind

[pale epoch]

please dont ping random users, just ask your question

[weary tiger]

ok

Is this a correct process?

[pale epoch]

what for?

[weary tiger]

For finding the ?

[weary tiger]

The ? At the top

[pale epoch]

this is a correct truth table if ? is the formula at the bottom

its a bit hard to parse what you did and i have no idea what the question asked of you though

[weary tiger]

Yes

Given the truth values come up with the compound statement

https://math.stackexchange.com/questions/38335/finding-boolean-logical-expressions-for-truth-tables

[pale epoch]

ok, then this works, yes

[weary tiger]

R u agreeing with what it said

Or do u know it’s correct

[pale epoch]

what you did is correct

[weary tiger]

ok ty

can i leave it the way it is

or i have to simplify?

[pale epoch]

i cant answer that, im not your teacher

[brave rock]

Kindly do not ping me to demand help. I have a life outside of discord.

[dawn sandal]

How would you write out the following English sentence in a logical statement: "If Grizz is hungry, then he will bite Nate, but if he is not hungry, then if he’s awake he will bite Nate" where S = Grizz is asleep, R = Grizz is hungry, and V = Grizz bites Nate. And only using ~, ^, v, and ->? What I tried so far was (R -> V) v (~R -> (~S ^ V)).

[lusty fern]

Can someone help me understand why choosing a group of k ppl from n total people is the same as excluding k ppl from n total people?

kinda confusing to wrap my head around

[earnest breach]

i'm not sure completely sure what you mean, but excluding k people is also sort of choosing k people.

[earnest breach]

if you're excluding k people to be in a group, then you're choosing k people not to be in a group

[coral parcel]

You want a conjunction instead of a disjunction between the two parts -- neither of the implications can be allowed to fail.

[dawn sandal]

oh I apologize I meant an and instead of an or

[coral parcel]

(It's not really an English sentence but a sentence in the mock-English language that logic textbook authors translate propositional formulas to in order to ask students to translate them back to the originals).

[dawn sandal]

what about with "Grizz is hungry, or he plays fetch, but never both". i got (R ^ ~U) v (~R ^ U)

[coral parcel]

That works, but $(R\lor U) \land \neg(R \land U)$ would probably be more literal. (Their semantics are the same).

[vital dew]

Troposphere

[dawn sandal]

appreciate the help and info. for the first one I sent would it be (R -> V) ^ (~R -> (~S ^ V)) or (R -> V) ^ ((~R ^ ~S) -> V)

I am unsure how that end part of the sentence would work for "If Grizz is hungry, then he will bite Nate, but if he is not hungry, then if he’s awake he will bite Nate"

[velvet vine]

Let X = {1, 2, 3, 4, 5, 6, 7}. Define a relation R as (x, y), if y = 2x -1.
Write the domain and range of the following relation: R = {(-3, 5), (-2, 5), (-1, 5), (0, 5), (1, 5), (2, 5)}
Draw the arrow diagrams to represent the relation: R = {(4, 10), (4, 13), (4, 16), (5, 13), (6, 16)}

[coral parcel]

You can say either
$$ (R \to V) \land (\neg R \to (\neg S \to V))$$
or
$$ (R \to V) \land ((\neg R \land \neg S) \to V)$$
They're equivalent, but the first of them is a more literal representation of the mock-English. (Note that it is not one of your proposals -- there should always be a $\to V$ last).

[vital dew]

Troposphere

[dawn sandal]

great thanks so much

[lusty fern]

wow this is mind blowing

LOL

wow

[dawn sandal]

I am confused on this problem. Could you let me know which ones I did incorrectly.
● purple(x)... x is colored purple
● B(x)... x is the letter B
● C(x)... x is the letter C
● above(x, y)... object x is in a row that’s above object y
● 𝑥 ≠ 𝑦... object x is different than object y

Using the predicates above, I am using only ∨, ∧, ¬, ⇒ and quantifiers ∀, ∃ to translate the statements below.

1. All C’s are colored purple.
   • What I have tried is: ∀xC(x) ⇒ purple()
2. At least two different B’s are colored green.
   • What I have tried is: ∃x∃y(B(x)∧B(y)∧x≠y∧green(B(x))∧green(B(y)))
3. There is a B that is colored green and is above every C.
   • What I have tried is: ∃x(B(x)∧green(B(x))∧∀y(C(y)→above(B(x),C(y))))
4. Not every purple C is above a green B.
   • What I have tried is: ¬∀x¬∃y(C(x)∧purple(C(x))→above(C(x),B(y)))

[dense glade]

I proived it by induction, but not first de morgna's law

any tip? I get stuck whenever I try to apply complementation rule

[coral parcel]

Your main problem here is all the places where you write something like green(B(x)). This is a problem because B(x) doesn't stand for a thing -- x stands for a thing, but B(x) is the claim that this thing is green. The claim is either true or false but the claim itself doesn't have any color, so asking whether it is green or not doesn't make sense.
What you want to write is just green(x).

[dawn sandal]

How would I convert all those statements though? For example, number 4?

[coral parcel]

In the first line you went to the other extreme and just wrote purple() where you meant purple(x).

For 4 I would first write: $\neg \forall x((C(x) and purple(x))\to{}$ "x is above some green B").

[dawn sandal]

oh yeah four purple() I meant purple(x) lol. just forgot the x when I typed it

[coral parcel]

And then unfold "x is above some green B" to $\exists y (B(y)\land green(y)\land above(x,y))$.

[vital dew]

Troposphere

[dawn sandal]

well it wouldn't be green(y) right since its not defined. it would be ~purple(y)

[vital dew]

Troposphere

[coral parcel]

Oh, I assumed you had predicates for a whole range of colors, where green and purple were only two of them ...

[dawn sandal]

so then for something like 3 would it be ∃x(B(x)∧~purple(x)∧∀y(C(y)→above(x, y)))?

[coral parcel]

Yeah, that looks right.

[dawn sandal]

thanks, appreciate all the help and info

[dense glade]

any tip on that proof

[coral parcel]

Don't ping random people in the channel with your questions, please.

(Sure I might arguably not be a "random people", but it goes for everybody).

[dense glade]

Alright

[weary tiger]

Isn’t it impossible for the union in the theorem to be equivalent to X? Assume A contains the maximal element of X. Then the union contains every element except the maximal and hence the union does not equal X.

typo maybe?

[grand totem]

Who says X must have a maximal element? If the well-order is (N,<), then (for example) taking the subset to be the entirety of N will make the union of the initial segments also be N

[ornate vine]

Wondering if anyone could help me figure out a? I'm fairly sure its when either f is not injective or not surjective but I'm having trouble identifying which or coming up with a counterexample?

[coral parcel]

(a) just asks for yes or no, not for a precise condition for when the answer is yes.

Since part (b) strongly suggests that injectivity and/or surjectivity is important, a strategy to look for a counterexample could be to try a function that is neither.

[hearty hound]

Suppose that f(x1) = f(x2). I need to show that x1 = x2.

How do I do this given that g(f(x)) is injective?

[grand totem]

Hard to give a hint about the next step without completely giving away the solution since the proof is so short, but if you could show that (g ∘ f)(x1) = (g ∘ f)(x2); then injectivity of g ∘ f would let you conclude

[hearty hound]

We know that g(f(x)) is injective so this means that g(f(x1)) = g(f(x2)) therefore f(x1) = f(x2)

but how does f(x1) = f(x2) show that x1 = x2

[grand totem]

I believe you might have misunderstood my hint.
What I meant: We know from the injectivity of g ∘ f that if (g ∘ f)(x1) = (g ∘ f)(x2) then x1 = x2.
Since you want to prove that if f(x1) = f(x2) then x1 = x2, you may assume f(x1) = f(x2) and show (g ∘ f)(x1) = (g ∘ f)(x2). If you then add that one step I gave as a hint at the end of the proof, you can conclude with x1 = x2 and you've proven your claim.
Now can you see how to go from f(x1) = f(x2) to (g ∘ f)(x1) = (g ∘ f)(x2)?

[ornate vine]

sorry just to clarify, do you think that a) is no then? Because after thinking about it a bit more doesn't a function need to be both injective and surjective to have an inverse at all?

[coral parcel]

Ah, this isn't really an inverse.

The notation looks like it, but when $f$ is $A\to B$ and $X$ is a subset of $B$, the notation $f^{-1}(X)$ generally means ${a\in A\mid f(a)\in X}$.

[vital dew]

Troposphere

[coral parcel]

This makes sense no matter whether f is injective, surjective, both, or neither.

(Without knowing that, it's no wonder you couldn't come up with a counterexample).

[ornate vine]

Ah okay that makes more sense

[hearty hound]

Okay so. I assume that f(x1) = f(x2). Now I need to show that x1 = x2. Since g(f(x)) is injective, and since f(x1) = f(x2), g(f(x1)) has to equal g(f(x2)) by definition. And since g(f(x1)) = g(f(x2)), x1 = x2 so f is injective.

[coral parcel]

Since g(f(x)) is injective, and since f(x1) = f(x2), g(f(x1)) has to equal g(f(x2))
This step does not depend on g o f being injective -- it is simply because g is a function.

And since g(f(x1)) = g(f(x2)), x1 = x2
This is the step that depends on g o f being injective.

[hearty hound]

I see. So since g is a function, g(f(x1)) = g(f(x2)) if f(x1) = f(x2). And since g(f(x1)) = g(f(x2)), x1 = x2 because g o f is injective. So since x1 = x2, f is also injective.

[grand totem]

Yes, pedantically I would also add one more step between going from g(f(x1)) = g(f(x2)) to x1 = x2 that explicitly uses the definition of g ∘ f

[hearty hound]

I got it! Thanks!

[weary tiger]

can someone help me with these two

I already did truth table for 5

[eternal thicket]

I am unaware how to solve this problem if people are indistinguishable - 10 choose 6. Can anyone explain how to solve this problem if people are distinguishable?

[coral parcel]

Presumably each of the 6 passengers get out at one of the 5 stops, and one passenger's choice is independent of all the other choices.

[eternal thicket]

oh i really got it, thanks

[eternal thicket]

and what about this problem? how can i solve this

[coral parcel]

The only thing that immediately comes to mind for me is a big ugly inclusion-exclusion computation.

[dense glade]

how do i calculaute the 2x2 intersections

for exaple

p(AnB) here

is p(5_first_time n 5_2nd_time)

shouldn't that P(5,5,x) where x {1,2,3,4,5,6}

so 6?

[tidal tulip]

why are you allowed to write a=qn + r and b = q'n + r from just knowing a congruent b mod n?

[little prism]

That's the definition of mod. They have the same remainder

[tidal tulip]

later in the proof of n|(a-b) we get a-b=(q-q')n, from there how do you get this means a congruent b mod n?

(for proof a congruent b mod n iff n|(a-b)

(this question is about direction of n|(a-b) => a congruent b mod n

[little prism]

What's your definition of mod n if not this

[tidal tulip]

well n|(a-b) is default so you have a-b=kn, and then a=qn+r, b=q'n+r', then qn+r-q'n+r then (q-q')n+r-r', and then by uniqueness of divisuion algorithm a-b=(q-q')n, but i dont see how from there this means a congruent b mod n

[little prism]

Again, what is your definition of "a congruent b mod n" if it is not "n|a-b"

Same remainder?

[tidal tulip]

i dont know what the definition of "a congruent b mod n" other than vaguely "a and b have the same remainder when divided by n" and we are tryig to prove a congruent b mod n => n|a-b and using that as your definition without proof is assuming the proof without proving it

in this calse im trying to prove n|(a-b) => a congruent b mod n

without assumoing the proof

[little prism]

Without knowing a definition for "a congruent b mod n" you can't do shit anyway

[tidal tulip]

thats what im asking

what does ti mean

[little prism]

Let's roll with the vague "same remainder"

[tidal tulip]

ok

[little prism]

By uniqueness of division like you said we get a-b=(q-q')n+0, so r-r'=0, equivalently r=r'

[tidal tulip]

^yep

[little prism]

The usual definition of "a congruent b mod n" that I have seen is exactly that n|a-b

[tidal tulip]

(we are trying to prove this)

so basically the step of the n|(a-b) => a congruent b mod n proof im at is

the line

a-b=(q-q')n+0, so r-r'=0,

now i need to go from that step to

this means a congruent b mod n

not sure how to get to that step without assuming the proof

[little prism]

Again, without a proper definition of what "a congruent b mod n" means, you can't do shit. There is nothing to show without a proper definition of what this even means

[tidal tulip]

the textbook i use doesnt define this properly

[little prism]

Well then it's a shitty textbook. Or you missed the definition

[tidal tulip]

i think i see why

its because r=r'

so same remainder

idk

Two integers 𝑎, 𝑏 ∈ Z are said to be congruent modulo 𝑛 if they have the same remainder with respect to their division by 𝑛 ≥ 2. In this case, we write
𝑎≡𝑏 mod𝑛.

so i should show a,b when devided by n has the same remainder

to know 𝑎≡𝑏 mod𝑛.

in this case im trying to show n|(a-b) => 𝑎≡𝑏 mod𝑛.

[little prism]

Yes ok. With that definition what we have shown so far is enough

[tidal tulip]

and im at this step >a-b=(q-q')n+0, so r-r'=0,

how do i go from there to finishing it up

[little prism]

r=r', so same remainder and we are done

[tidal tulip]

a-b=(q-q')n+0, so r-r'=0 => a=(q-q')n+b getting myself in a loop. how do i know a=(q-q')n+b means a congruent b mod n

[little prism]

What?

[tidal tulip]

a-b=(q-q')n+0, via uniquness r=r' and then how do i finish the proof

i dont see how that means a congruent b mod n

[little prism]

r-r'=0. So r=r'. r is the remainder of a and r' is the remainder of b. So they have the same remainder. So a congruent b mod n

[tidal tulip]

ahh i see

ok thank you

i got in a confusion loop there

[tidal tulip]

@little prism still a little confused n | (a-b) can be written as: a-b = kn, k in Z, and going along we have (qn+r - q'n+r') = kn => (q-q')n - (r - r') = kn due to uniqueness => we have r,r' have same remainder and done but if we keep rolling we it then we have the expression (q-q')n = kn and im not sure what to do with that expression if anything in the proof

[tidal tulip]

is it once you shown r=r' you dont need to worry about (q-q')n = kn ?

[little prism]

Yes

For our purpose we got everything out of the equation that we need

[tidal tulip]

great, thank you @little prism

[grim snow]

Is this the correct channel for asking about automaton?

[coral parcel]

Yeah.

Why would, say, the real number 2 be in your set?

Oh I see, there's an or instead of an and.

I would be much tempted to declare that has to be a typo, since there's nothing else to make clear what a and b range over.

[weary tiger]

can anyone help me?

[coral parcel]

Why not all complex numbers, for example? Or just all natural numbers?

[coral parcel]

For the first question, you can't have f(a)=2 and f(a)=1 at the same time, so the assumptions in the question are impossible.

[weary tiger]

but can it be a onto function but not one on one

[grim snow]

How can we define the complement of a language?

[brave rock]

We typically talk about the complement in the set of all words over the alphabet

so if we have an alphabet A, the set of all words is denoted A*

our language L is just a subset of A*

And the compliment of a language is just A*\L

[hearty hound]

I'm having trouble with the reverse direction: surjective -> injective

[elder jasper]

having trouble with proof by induction

[chilly kayak]

if f is inyective. then every x maps to a single y. and since there are n "x" and n "y" you will end up with all "y"s mapped to some "x" which is the definition of suryective

if f is surjective. then every "y" is mapped to some "x". so you will have n mappings x->y. since f is a function, every "x" must maps to a single "y". so for every "y" you have a single "x". and since you have n "y"s and n "x"x you will end up with all "x"s mapped to all "y"s in a one-to-one relation which is the definition of inyection

[wooden moat]

how would one go about solving this?

i.e. like what would the proof by contaposition look liek?

[light oxide]

h) ∀y∃xQ(x, y)

I am having trouble with this textbook question.
It is true/False type of question
Any help would be appreciated

[cerulean wind]

the truth values are (x,0) for all x. h) is false since for non-zero y, no x satisfies x+y=x-y

[light oxide]

Ooh, thxx

[grim snow]

How do you exclude a substring in a regular expression?

or exclude a pattern

[lost hatch]

how would one write the answer to prove this?
we've had discussions on the concept/logic but not really anything on how to formally write them.

[runic ginkgo]

what would the entries of a general adjacency matrix for the following question be like?

Let $DP_n$ be the directed path on $n$ vertices. Write the adjacency matrix of $DP_n$ for $n=5$ and for arbitrary n.

even for the $n=5$ case, i'm not sure how to notate all the different $DP_5$ configurations there can be.

[vital dew]

e57721

[chilly kayak]

p: 8 divides n
q: 4 divides n

regular p->q : if 8 divides n, then 4 divides n
contraposition ¬q->¬p : if 4 doesn't divide n, then 8 doesn't divide n

[chilly kayak]

let n = 4k+{1,2,3}, we have 3 cases.

for cases n= 4k+1 and 4k+3 is clear that n != 8p for any integer p.

for the case n=4k+2.
if k is even n= 4(2p)+2=8p+2 which is never multiple of 8
if k is odd. then n=4(p+1)+2=4p+6=4m-2 which is never multiple of 8.

so we covered all cases for n!=4k and concluded that n!=8k as well.

[raw spindle]

For discrete time signals and systems, does the variable n have any units? Or is it unitless?

[severe swan]

I think this is where I should ask this. I am trying to figure out truth tables. If I have the summation function F(w,x,y,z) = Σ(8,10,12,14)

How can I create a truth table for w, x, y, z, and F?

How can I find the maxterms and minterms as well as the sum of products and product of sums?

I tried to do this but I am not sure if it is correct or not.

[coral parcel]

The table almost clarified what you mean by F(w,xy,z) = Σ(8,10,12,14), but then why do your have an 1 in the 1,1,0,1 row?

[severe swan]

Hello, I accidentally mistyped F(w, xy, z) and did not notice. F should actually be F(w, x, y, z) and not (w, xy, z)

[atomic igloo]

Hey

im just starting in discrete math and im really confused

can someone explain how to make truth tables for basic operations for me to start

[stone ridge]

I would like to ask what's q and p in this case. I kinda understand the steps, but Im confused about the negate part. What is it negating?

[chilly kayak]

you must know the basics first, AND, OR, if-then,

[lofty portal]

lol I happened to see this exact proof while scrolling reddit today https://www.reddit.com/r/math/comments/xo3au4/comment/ipx6m0d/?utm_source=share&utm_medium=web2x&context=3

hm I'm not sure why the negation is necessary

I think it should be fine to just show that either sqrt(2)^sqrt(2) or (sqrt(2)^sqrt(2))^sqrt(2) is rational?

[chilly kayak]

I think they are trying to prove by contraposition

[devout axle]

that's a direct proof

is it not?

[chilly kayak]

but the problem ask to prove that exists something that make that statement true. so you just need a single example

and it is solved

[chilly kayak]

yes, it is

[stone ridge]

So this have nothing to do with the negation nor contraposition?

[chilly kayak]

In my opinion just an example is enough

[stone ridge]

What I mean is the steps above, instead of how to solve the question. Sorry for the confusion

[chilly kayak]

if x and y are irrational, then x^y is irrational
p= x and y are irrational
q= x^y is rational

do you mean that?

[stone ridge]

what i mean is does the steps above uses the negation or contraposition. as you mentioned you just needed a single example is enough, and i notice that the steps above did give example to prove it (sqrt(2) and that kind of stuff)

[chilly kayak]

neither. is proof by cases

[nova root]

can someone provide me assistance with divisibility proofs for number theory?

[chilly kayak]

#elementary-number-theory

[astral pagoda]

Can someone help me out with a maths question i'm not sure if my premises is correct.

“Jean is from England” and “No student in my class is from England” imply the conclusion “Jean is not a student in my class” 

Let E(x) denote ‘x is from England’
Let S(x) denote ‘x is a student in my class’

Premise is ∀x(S(X)→E(X)), E(Jean)
Conclusion is ¬S(Jean)

Steps                     Reasons
1. ∀x¬(S(X)→E(x)          Premise
2. E(Jean)                Premise
3. ¬(S(Jean) → E(Jean))   Universal Instantiation from (1)
4. S(Jean) ∧ ¬E(Jean)     Logical Equivalence

But i can't seem to get that conclusion?

It's apparently ∀x(S(X)→¬E(x) then i can prove it

[rapid mural]

Can you prove by contradiction? @astral pagoda (also fyi, that should be in #proofs-and-logic)

[astral pagoda]

It's another topic so im pretty sure they don't want us to use contradiction for now

[rapid mural]

You can convert the logical form of S(X)->E(X) into

!S(X) or E(X)

Applying demorgan's laws, we get S(X) and !E(X)

[coral parcel]

You're right that the screenshot you shared does loudly state the negation of the claim, at the beginning, and does so for absolutely no reason. The proof that follows it is a direct proof of the original claim.
The best explanation I can offer is that many people seem to find "look for a counterexample" psychologically easier than "look for an example". This is so common that it includes many professors/TAs. If that way of thinking works for them, there is nothing morally wrong with it -- but it is good form not to let that inversion bleed into the proof one is actually writing down. A hand-written model solution is one of the cases where it is relatively easy to slip up, though.

[coral parcel]

I did figure that out -- but I still don't understand why the 1,1,0,1 row ends with 1. The binary number 1101 is thirteen which is not in your Σ(8,10,12,14).

[coral parcel]

Indeed, that's the right way to write down the premise. You initial attempt wrote it as first ∀x(S(X)→E(X)) and then ∀x¬(S(X)→E(x), which are both wrong.
∀x(S(X)→E(X)) claims that all your students are from England.
∀x¬(S(X)→E(x) is a strange thing to say. The strict rules of logic makes it mean that everybody in the world is your student and also is not from England -- but it's better simply to consider ∀x¬(S(X)→E(x) to be accidental nonsense. In practical uses of predicate logic, → always belongs directly under a ∀, with no intervening negation.

[stone ridge]

oic thanks for your explanation 🙏

[stone ridge]

Thank you and other who responded to my question

[midnight herald]

Hi everyone. Can someone help me out on how to solve the following ?

Suppose P(x,y,z) is a predicate where the universe for x,y and z is {1,2}. Also suppose that the predicate is true in the following cases ---- P(1,1,1), P(1,1,2), P(2,1,1), P(2,2,2) --- and false otherwise. Determine which of the following quantifed statement is TRUE.

A) ∃𝑥∀𝐲∀𝑧 P(x,y,z)
B) ∀𝑥∃𝑧∀𝐲 P(x,y,z)
C) ∃𝑥∃𝐲∀𝑧 P(x,y,z)
D) ∃𝑥∃𝑧∀𝐲 P(x,y,z)

How do I find out the solution for this question ?

What I have understood from the answer :

For example option A, There exists a x, for all Y and all Z. I am not certain how do I follow up with how to check if the quantified statement is True or False.

Any help would be appreciated 🙏

[coral parcel]

There's not much to it other than to roll up your sleeves and try all the possibilities. (The universe in the exercise is chosen small enough that this is feasible).
For A, you would check whether either ∀y∀z P(1,y,z) or ∀y∀z P(2,y,z) holds -- and each of those possibilities branch into more cases as you dig into combinations of y and z.

(This is not a "follow a solution method" exercise -- it's a "check that you have understood what the notation means" exercise).

[midnight herald]

Noted. Thank you for the help ! It helps me as a stepping stone on how to do it. I didn't understand the notation initially. Thank you so much once again !!

[weary remnant]

Hi I am stuck at this problem
how many positive integer solutions to the equation X1 * X2 * X3 * X4 = 10^6
10^6 = 5^6 * 2^6
so i have to to divide the coefficients of the power 6 to four slots
how can i do that

[astral pagoda]

Got it thanks! So in all those instance i can assume that ∀x the X means that everyone in the world

[coral parcel]

Yes, or at least everyone/everything in some not explicitly specified universe of things the formula is supposed to be understood in.

[coral parcel]

Have you learned about "stars and bars" problems? There's one of those for how to distribute the fives, an another one for how to distribute the twos.

[weary remnant]

I checked it out, Now I understand how to solve it thanks.

[brave fjord]

What will be the range of this function?

[chilly kayak]

What's the exponent of 3x?

It looks like a v

[brave fjord]

2

[chilly kayak]

In this case you need to find the minimyn value

Since it doesn't have a maximum

By completing squares you can do it

[brave fjord]

@chilly kayak can you please tell me the range of that function

[chilly kayak]

range is [59/12, inf)

[brave fjord]

@chilly kayak thanks

[sudden topaz]

How can I write my question in latex here?

[brave rock]

See #latex-help

[wintry hare]

hey guys, I need a reference book that has a lot and i mean A LOT of ordering theorems and helps me understand the concepts from the very base because my professor is going ham and i cant find any good book for the same.

[golden edge]

Not sure it's the best room to post this, but

What does those mean ? I understand that what you plug in the functions is one of the subsets of E, but then I am not sure what the functions do

[little prism]

The first function takes a subset A of E and returns the complement E\A of that subset

For the second function it returns the union of A and F. Where F is probably a fixed subset of E

[fair ember]

in modular arithmetic, if we take 2 ≡ 6 (mod 4), how is 6 / 4 = 2?

or rather how is the remainder 2

[rapid mural]

6 mod 4 = 2

2 mod 4 = 2

so yeah they're congruent

you are operating on \mathbb{Z}

[fair ember]

its all so interesting

[nimble dew]

what does red circle indicate

[stray reef]

it's the symbol $\oplus$, which does not have one universal meaning; here it is being used to denote symmetric difference as the definition immediately after it explains.

[vital dew]

Ann

[rapid mural]

Interesting, usually that's the tensor product.

I've seen $\Updelta$ being used

[brave rock]

The tensor product is usually \otimes, not \oplus.

[rapid mural]

Ah. I misread, sorry.

[coral parcel]

The addition-like notation $\oplus$ for symmetric difference comes from the fact that $(\mathcal{P}(A),{\oplus},{\cap})$ is a ring.

[vital dew]

Troposphere