discrete-math

[gusty crag]

ah I see why @lyric pumice 's answer is right now

very clever

[dapper needle]

need help, not getting anywhere with my attempts

[gusty crag]

I think it would be helpful to rewrite the left side with $\sum$

[vital dew]

mathew_soto78:

[unreal stump]

Let Sn be the sum on the left. How can you rewrite S(n+1) in terms of Sn and n?
||S(n+1)=S(n)+2^(n+1)||

[dapper needle]

what's the -1 though?

[gusty crag]

1+2 = 2^2 - 1

[dapper needle]

ah right..

[gusty crag]

the sum of the first n powers of 2 (including 2^0) is always one minus the next power of 2

that's what the problem is asking you to show, but I recommended to write out the left side with a summation symbol because I usually find it easier to do these sort of problems when I've written it out more formally, or "mathematically"

[dapper needle]

can't believe I had to refresh on how to correctly write sigma notation but.. I got it

[gusty crag]

yep that's the left side

so show that $\sum_{k=0}^n 2^k = 2^{n+1}-1$ for all $n\in \mathbb{N}$ using induction, you need a base case and an inductive step

[vital dew]

mathew_soto78:

[dapper needle]

Oh.. okay I

I understand now.

when doing base case I didn't consider 2^0

[gusty crag]

I don't know if the way your teacher defined $\mathbb{N}$ includes 0 or not, but it works for 0 as well as 1 so it doesn't matter which one of those you take as your base case

[dapper needle]

right

[nocturne carbon]

Hey, i just started learning discrete math and have become familiar with the conjugation operator, can anyone confirm if my answer to this question is correct?

does that emoji mean yes or no...

[lyric pumice]

@delicate ridge Yes, there is.

[errant bear]

it should be good

no, talking to elephant

[nocturne carbon]

Okay thanks

[errant bear]

though a might work, its been a while though so probably want some more confirmation

[nocturne carbon]

from the examples i read, i dont think its a, but then again im the noob here

considering this question, which is supposedly really easy, i have no clue at all how im supposed to solve it

im not familiar with how to solve this type of problem in my practice sheet, does anyone know how to solve it?

[stray reef]

here's a hint: consider O_1 + O_2

[frail girder]

i got this example saying sqrt2 to the power of sqrt 2 is rational and I don't see how? It was a non-constructive proof

[unreal stump]

I think it proves (irrational)^irrational can be rational, not √2^√2

[frail girder]

yea this textbook trolled me then

[stray reef]

kobayashi are you sure you aren't misinterpreting it

[frail girder]

u want a screen shot

[stray reef]

yes

i'm like 99% sure it says
"either sqrt(2)^sqrt(2) is rational or it is not. if it is, we're done. if it isn't, raise it to the power of sqrt(2) and end up with 2"

[frail girder]

maybe im small brain

[stray reef]

if x is rational, then x is rational

[pliant horizon]

Is this a statement that even makes sense?
https://puu.sh/GsUeX/21c3b9e646.png

[pale epoch]

what do you mean by "makes sense"?

it's a statement

[pliant horizon]

I don't understand what the intersection of a set X and a cartesian product of two other sets would even be

Empty?

[pale epoch]

the cartesian product of two sets is a set

and you can intersect any two sets

for X=R^2, Y=Z=R, its not empty

its R^2

[pliant horizon]

Okay but then what would the intersection of X and Y be

For that example

[pale epoch]

the intersection of R^2 and R

[pliant horizon]

...

which would be?

I don't see them sharing any elements

[pale epoch]

then its empty?

[pliant horizon]

[pale epoch]

what's the problem?

[pliant horizon]

so it does make as little sense as i originally thought

[pale epoch]

it's a valid statement

[pliant horizon]

Wait what

We just found a counterexample

Last I checked R^2 is not equal to the cartesian product of the empty set with the empty set

[pale epoch]

yes, that does not make it less of a statement

it just happens to be wrong in this case

[nocturne carbon]

Can someone please explain What Left Identity of => is,
and what ex false quodlibet?

i know ex false quodlibet mean, from falsehood, anything

[weary tiger]

$a_1=\left{a_i:::2\le :i\le n\right}$

[vital dew]

The-Elite:

[weary tiger]

is this how you would say "a_1 can take any value of a_i where i is greater than or equal to 2 and less than or equal to n?

[elfin flume]

Can anyone help with this? I'm not sure how to even start this.

[weary tiger]

use the product rule and binomial coefficient

[stray reef]

is this how you would say "a_1 can take any value of a_i where i is greater than or equal to 2 and less than or equal to n?"

no

you're equating a_1 to the entire set {a_2, a_3, ..., a_n}

[leaden pebble]

no, should have been $\in$ @weary tiger

[vital dew]

Fractal:

[leaden pebble]

but also, the set builder notation is wrong as well

well, not the notation. the set is wrong

a_1 should be in that set

[stray reef]

not with how she specified it

[brave lava]

say I have A subset B

does this mean A and B are equal sets?

[stray reef]

no

A ⊆ B does not by itself mean A = B

[brave lava]

well

what does A subset B mean

that set A has the same elements as set B?

doesnt that make them both equal sets

[stray reef]

no

A ⊆ B means that every element of A is also an element of B

[brave lava]

right and we didnt use the proper set symbol

so we know set B doesnt have another elements that are not in set B

thus, set A and B have the same elements

and are both subsets of each other

?

[stray reef]

bruh what

i never said B was a subset of A

it is possible to have A ⊆ B without B ⊆ A yknow

for example, A = {1,2,3} and B = {1,2,3,4,5}

[brave lava]

subset is not a commutative property?

like i cant switch the sets around the symbol?

[stray reef]

symmetric*

and no obviously it isn't

would you expect the less-than-or-equal-to relation ≤ to be symmetric?

would you expect a ≤ b to be the same as b ≤ a?

[brave lava]

nope

nope

unless a and b* were equal

thanks

[zenith thorn]

Yep so basically if it’s improper ⊆, similar to what Ann said, then all elements in A are in B. If B just so happens to have the same elements in A, then that’s why there’s the bar under the subset symbol. The relation doesn’t commute because if it did, then all sets would be equal to each other. This notion is explored when you get into subset inclusion proofs where you prove two sets to be equal by proving two cases where each is a subset of each other.

[stray reef]

⊆ graphically resembles ≤

that's why i use it for containment

[weary tiger]

how do i say the set P contains values from 2 to n

where |P| >=2

[stray reef]

what do you mean

[weary tiger]

like how do i write it in math notation

[stray reef]

no, what do you mean

it's not clear

[weary tiger]

so I have a set P that contains elements from 2 all they way upto n

[stray reef]

do you mean that 2 ∈ P, 3 ∈ P, ..., all the way to n ∈ P?

oh.

[weary tiger]

where n >=2

yeah sorry

[stray reef]

is that all

[weary tiger]

ya

[stray reef]

P = {2, 3, ..., n}

[weary tiger]

but like isn't it bad to put the 3

since we don't know if ends at 2

[stray reef]

{k ∈ N | 2 ≤ k ≤ n} if you want to be stuck-up and formal

[weary tiger]

so P = {k ∈ N | 2 ≤ k ≤ n}

is it fine to put the P there

P = {k ∈ N | 2 ≤ k ≤ n}

also what is N?

[pale epoch]

the set of natural numbers

[weary tiger]

oh

so if we want to describe the elements of a set P it is fine to say P = {k ∈ N | 2 ≤ k ≤ n}?

[pale epoch]

that's set builder notation, so yes

[mint bane]

can anyone explain a state machine please

i have a textbook explanation but im curious if anyone has a different wording or something like that

[valid wave]

Discrete math is hard

I feel so lost 😦

[gritty crescent]

I've just started with discrete math

[turbid meadow]

with set theory, let's say i have a set A = {1,{3,5},3,6,7} is {3,5} an element or a subset?

[pale epoch]

of A? an element

[turbid meadow]

oh i c so {{3,5}} would be a subset?

[pale epoch]

yes

[mint bane]

@gritty crescent use the MIT opencourseware on it, i started about a month ago

it goes pretty fast but im going really slow to counter it and ive liked it v much

[gritty crescent]

Yeah, I was bothered by their pace. I liked their assignments though, I might use them. Currently, I've enrolled in a different MOOC, which is also free. It's going at a manageable pace, but they're not offering a lot of courseware, so I might complement it with OCWs material.

[mint bane]

yeah what im doing is just following the OCW lectures but since they go so fast if they talk about something i missed i go back and read up do practice etc

hence, im only on lecture 4 after a month lmao

[gritty crescent]

But that's good, they do cover everything in a lot of depth.

And this also highlights MIT's own academic rigour. I guess the students over there have to grind real hard to get through their college lives.

[mint bane]

yeah probably true

im supposed to be a sophmore but taking a gap year and i go to a decent private uni in PA, super different

then again i mostly bullshitted my freshman year unfortunately but MIT seems crazy

[gritty crescent]

Freshman means first year at uni, right? Not familiar with American education terminology, sorry.

[mint bane]

yeah lol first year, supposed to be second year rn

[gritty crescent]

I see. So you're majoring in maths?

[mint bane]

we should probably talk in PM tho, dont wanna get too off topic here

[gritty crescent]

👍

[gritty crescent]

I was given an explanation in #help-8 , which seems to be the standard analogy. However, I personally struggled with understanding it, and need some intuition to understand this.

[gusty crag]

If kid 1 ordering chocolate and kid 2 ordering strawberry were different from kid 1 ordering strawberry and kid 2 ordering chocolate, then I think it would be n^r (each kid can order from any of r flavors)

but it seems like what this question is really looking for is the number of different possible orders of n ice cream cones if there are r different flavors, so the order in which the cones are ordered doesn't matter

I just checked questions-theta, I was about to give you the same explanation you're struggling with lol

@gritty crescent what about that explanation gives you trouble?

[turbid meadow]

Need to confirm my answers are right here is the context and answers:

Context:
U={1,2,3,4,5,6,7}
A={1,7}
B={1,2,4,6}
C={1,3,5,7}```

Answers:

1. C-A = {3,5}
2. A∩ B′= {7}
   3)(A∩B)∪C′= {2,4,6}
   4)(A∪B)′= {3,5}
3. (C-A)'∩B={1,2,4,6}

Thanks in advance :))

[shell jewel]

Only mistake is in the third one

You shoukd have 1 in this set too

@turbid meadow

[turbid meadow]

oh i c, i was confused about 3

ty!

[shell jewel]

Any time :)

[weary tiger]

how do i go about this problem

[pale epoch]

read the definitions

[weary tiger]

I have such that if x is in A and B then x is in a and x is in b but I do not know how to prove something is a subset of something else

I need direction on how to start

[pale epoch]

you take an element from the left hand side and show that it is also an element of the right hand side

[weary tiger]

so x is an element of a and b. Hence, x is an element of a and x is an element of b. Therefore x is an element of b and AandB is a subset of B?

This was what I answered previously before consulting this channel

[pale epoch]

ye

[weary tiger]

Ok thank you!

[pale epoch]

your argument works for every x, this then shows A and B subset B

[robust light]

yo can someone explain how to draw hasse diagrams

im very confused

i'm looking at this question and my brain is drawing a blank

[weary tiger]

hi is someone here able to help me with some discreet?

discrete*

[robust light]

i think i have an idea of how to solve it

but i dont know if i'm right

is anyone here?

[errant bear]

draw a circle

and then draw however many more

[robust light]

yea, i just have questions regarding formatting and whatnot

I have to draw a hasse diagram of natural numbers less than or equal to 10

And the divides are “|” whatever that means

I just feel like this isnt right because i dont think 8 would be the maximal?

[haughty garden]

8 isn’t the only maximal

So is 10, 6, 7 and 10

[weary tiger]

if i have a function that maps i to a_i and they're all the same values, how do i write that in set notation?

i was thinking $a_i=\left{i\in N:::1\le i\le 4\right}$

but idk if that's right

[vital dew]

The-Elite:

[weary tiger]

<@&286206848099549185>

[fallow raft]

$A_{i} = {X | X \in \mathbb{N}, 1 \leq X \leq 4}$ might work

[vital dew]

Swagger:

[fallow raft]

$\frac{a}{b}

[ember sky]

Well if u can relate something to something else is that is certainly true, then the subrelation must be true as well, dont you think?

[fallow raft]

I guess in this case sure?

[ember sky]

Well there is little context here for me, so theres not to much to go off of.

But that would be my main argument ^^^

[fallen osprey]

Hey, is there anyone that could help me with a concept?

I've been stuck on this concept for quite some time now

[last sigil]

[fallen osprey]

I asked in questions #help-4

[fading abyss]

hey i had a question

is overflow possible when adding two binary numbers?

[orchid jasper]

Depends

But yes if you have a limited number of bits there will be overflow at some point

[gritty crescent]

@gritty crescent what about that explanation gives you trouble?
@gusty crag I've figured it now, initially I had trouble processing it.

[gusty crag]

what made it click?

[dapper mason]

hello all

in this NFA, the prof said it accepts an epsilon input

but I thought in a NFA you have to take the epsilon path if it is an input

[gritty crescent]

what made it click?
@gusty crag I took a look at the visual of separating by sticks again, and then all of a sudden the idea started making sense. I still have a minor doubt though.

[ember sky]

Bro i love ur pfp @dapper mason

[dapper mason]

lol thanks

[dapper mason]

issue has been resolved, NFAs aren't forced to traverse epsilon transitions

[devout stone]

Hi, can someone explain to me about Quantifier?

[stray reef]

what about them

[devout stone]

I do not understand when to use for all and there exist formula in the word statements

[stray reef]

can you show an example of what you're struggling with

[stray reef]

okay yeah some of these are not obvious

[devout stone]

How to know which one to use in this statements?

[gritty crescent]

(d) seems to be a case for "there exists" quantifier.

The other three all seem to be "for all" statements since any passenger/man/woman/student qualifies if they meet the given criterion. I could be wrong though. 🤷‍♂️

What have you tried so far?

[devout stone]

The first three I put it as forall then the last one as there exist

[solid nacelle]

Could someone check my work? I'm going through the Book of Proof Section 1.4 and I'm having a difficulty solving question 12. Now, if I'm reading this correctly, X is an element of that powerset but 2 must be an element of X. 2 isn't the same as {2} right? Which would mean that the answer is an empty set since there's none. I'm not sure if I'm right though so if there's someone that could help me understand, that would be fantastic.

[stray reef]

\in, by the way

also, no

your set is the set of all subsets of X which have 2 as an element

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

[solid nacelle]

these questions confuse me a lot but I think I got it now, I wish it was part of the solutions so that I didn't have to ask. Thank you for clarifying my concerns @stray reef

that makes so much sense now

@stray reef Also another question if you don't mind, if the rule was something like |X| ≤ 1, does that mean the set would be any element that only has a size/cardinality of less than or equal to 1? For instance, the question would be {XeP({1,2,3}):|X| ≤ 1} and the answer would be { {}, {1}, {2}, {3} }, am I doing this right?

[gritty crescent]

Sounds good to me.

[solid nacelle]

@gritty crescent Thank you!

[stray reef]

that wording will get a grumble grumble from me but otherwise fine

[gritty crescent]

In how many ways can one move from (0,0) to (5,5) on the Cartesian plane, making only unit movements to the right or upwards?

For instance, one such path would be (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(3,2)->(3,3)->(4,3)->(5,3)->(5,4)->(5,5)

I'm not aware of any systematic method of solving this problem, and I guess there are too many possibilities for brute force.

[unreal stump]

10c5?

10 steps will always be required to do that

You have to choose which 5 will be upward

[gritty crescent]

Yes.

That's it?

[unreal stump]

I think so

[gritty crescent]

Wolfram says this is equal to 252, which does sound like a compelling number.

I'll try solving it for a simpler case, then try to generalise and see if I catch up with your result.

[gritty crescent]

@cunning thistle Help me on this one.

[cunning thistle]

Can i see the question?

[gritty crescent]

In how many ways can one move from (0,0) to (5,5) on the Cartesian plane, making only unit movements to the right or upwards?

[cunning thistle]

I don't know a formal way of doing these type of questions but i guess counting manually won't be such a bad idea.

[gritty crescent]

Fr? Drake suggested the answer's 252- how am I supposed to count that?

[cunning thistle]

Ohh man.

Ok let me think about it.

[gritty crescent]

I understood Drake's solution. Nvm.

The idea is that you're going to make 10 moves in all, so you choose(without loss of generality) which 5 of these will be upwards.

This gives you 10C5, hence 252.

[cunning thistle]

Are you certain that 252 is the correct answer?

[unreal stump]

Should be

[cunning thistle]

Idk. It just seems like alot.

[gritty crescent]

Yes, that's the correct answer.

Now a bit trickier part: We still need to move from (0,0) to (5,5) using rights and ups, without crossing the diagonal joining (0,0) and (5,5)[touching the diagonal is permissible, but crossing it isn't]. In how many ways can this be done?

I've been suggested the answer's $\binom{10}{5}-\binom{10}{6}=42$, but I don't exactly understand where the latter term comes from.

[vital dew]

TedNowKaczynski:

[last sigil]

@gritty crescent learn about the catalan numbers

can't directly help rn cause in class

[gritty crescent]

Np, and yes this answer is supposed to be linked to Catalan numbers but the instructor didn't explain the how-and-the-why, so I'm looking up in different books now.

[stray reef]

admittedly the only way i know of to derive the catalan number formula is through generating functions

[gritty crescent]

Above and below the diagonal, yes. Touching the diagonal is permissible but crossing it isn't.

admittedly the only way i know of to derive the catalan number formula is through generating functions
I see. I guess generating functions will appear only very later in my current course sequence, so I might have to wait till then to get a satisfactory answer.

The instructor did some weird explanation by saying one possible way of crossing the diagonal is RUU|RURRURU. The diagonal is crossed after the UU. He then said he'll take "the complement" after the seperator to get RUU|URUURUR. Then he claimed there are 6 Us and 4 Rs, which give C(10, 6) combinations of crossing the diagonal, which can now be subtracted from C(10, 5) to get 42.

I didn't understand the explanation at all.

[cunning thistle]

Idk how this would help but i suggest you dig up on Andre's principle of reflection. It has a close relation to problems of Random Walk as well as that cashier problem.

@gritty crescent

[gritty crescent]

Yeah, one of the books talks about this reflection too but I'll pass on this problem for now. There's far too much I don't know atm, so I'll wait for a while to get to the gist of this solution.

There is?

Nor do I. 🤷‍♂️ The reasoning seems too contrived.

What could be a possible way to count crossings?

Every crossing path will either go this way (n-1, a)->(n,a)->(n+1,a) or (b, n-1)->(b,n)->(b,n+1), right?

0<a<5 and 0<b<5

One of the books used the exact same words you did lmao, I couldn't follow that line of reasoning.

Thanks! Ping me if you have any ideas.

[burnt herald]

can someone explain the difference between the two?

[cunning thistle]

https://math.stackexchange.com/questions/990747/cashier-has-no-change-catalan-numbers-probability-question

@gritty crescent

[gritty crescent]

I'll look into it.

[valid wave]

Hello peeps

discrete math is really whooping me

anyone have a good resource for learning it?

cant seem to find khan academy videos

[gritty crescent]

MIT OCW's Discrete Math course is worth looking into.

[last sigil]

don't think there is a central resource since most of the concepts in discrete math that are taught vary

I'd focus more on specific techniques/concepts you struggle with and google from there

[lyric pumice]

don't think there is a central resource since most of the concepts in discrete math that are taught vary
I'd focus more on specific techniques/concepts you struggle with and google from there
Agreed.

[burnt herald]

b.) is saying that for atleast 1 value of x in R, every single value of y in R will make P(x,y) true
@cursive elk they both sounds similar to me..

[burnt herald]

@burnt herald quite different
@cursive elk In other words,
for a, we define a range of x, then only we choose a y that satisfied the P?

and for b, we choose an x first, then only a range of y

Is it right to think that way?

[leaden moon]

What's the difference between Contraposition and Contrapositive?
Is it the same thing?

[weary tiger]

ye

i think one is the actual statement while other refers to something diff

[dapper needle]

is this possible to do using the Euclidian Algorithm?

[unreal stump]

If a and b are not coprime, integers r and s won't exist

You can use Euclidean algorithm to find integers r and s ,such that this condition is satistifed when (a,b)=1

[leaden moon]

@weary tiger o thanks for clarifying

[dapper needle]

@unreal stump is coprime another word for relatively prime?

[unreal stump]

Yes

@dapper needle

[dapper needle]

okay, do you have any idea how to begin if I wanted to use the Euclidean algorithm?

I know I could probably just assume d = common divisor and go from there

to eventually prove that it's not possible

but I was wondering if it's possible to do using the algorithm

[unreal stump]

I don't think you can

[dapper needle]

gotcha.. yeah I couldn't figure it out

thanks though

[burnt herald]

Prove using math induction: n < 2^n
Base case 1 is true for above

n = k

Induction Hypothesis: k < 2^k
Show: k+1 < 2^k+1

2(k) < 2^k * 2
2(k) < 2^k+1
k+k < 2^k+1
k+1*k < 2^k+1

Is this correct?

The last statement LHS k+1*k is "much better" / greater than k+1, which is still less than the RHS

[unreal stump]

Yes

[burnt herald]

which proves the induction as correct?

Yes
@unreal stump Thank you

[void maple]

can anyone help with some pretty simple propositional logic questions

[burnt herald]

I'm also learning it @void maple ...what kind of questions?

[void maple]

basically i need to translate the math form into plain english

[burnt herald]

maybe post them here?

[void maple]

not allowed to post directly unfortunately

hold on

So one part of it is (x=/=y) and i'm not really sure how to read that

@burnt herald

[weary tiger]

that means x does not equal to y

@void maple

[void maple]

Yeah I know that

Its hard to ask for help without context hahah

[stuck iris]

guys did I do this correctly?

[quaint star]

Yes

[stuck iris]

∃ y ∀ x (x>0 → x>y) would you say this is true? x and y are real numbers

@quaint star

[quaint star]

Yes

[stuck iris]

really ? o.O

[plucky stirrup]

For proof by contradiction
If P is our statement
We have to say the negation of P is true, and then prove that is wrong, correct?

[quaint star]

Yes

Or just arrive at anything that tou know is false

[weary tiger]

$\frac{n^2}{2n:}-1<\frac{n}{2}+1$ having trouble proving n>=2 using induction, i proved the base case made the hypothesis but am confused on how to do when n=k+1 $\frac{\left(k+1\right)^2}{2\left(k+1\right):}-1<\frac{k+1}{2}+1$

[vital dew]

The-Elite:

[plucky stirrup]

So if my P is
In a graph G with at least two vertices, there are always at least two vertices that share the same degree
Then my negated statement is
In a graph G with at least two vertices, there exists less than two vertices sharing the same degree

[weary tiger]

i can't get them to equal my assumption of $\frac{\left(k\right)^2}{2\left(k\right):}-1<\frac{k}{2}+1$

[vital dew]

The-Elite:

[quaint star]

@plucky stirrup yes, but it would just be that such a graph exists, not that all graphs have less than two...

[plucky stirrup]

So negated statement is
Such a graph G, exists where there are less than two vertices sharing the same degree? @quaint star

so my first negated statement was incorrect then

[quaint star]

Yes, it doesn't read as clearly as this does

It sounds like you're saying it's true of all graphs

[plucky stirrup]

okay got it

[stuck iris]

∀ x (P(x) → Q(x))
is true.

[void maple]

can someone help

[stuck iris]

∃ x (P(x) ∧ ~Q(x)) cant be determined right?

[void maple]

i need to write everyone has something except 1 person

x & y = all people

A(x) = x has a car

i need to write everyone has a car except John

in the like math form

@plucky stirrup could u help

[balmy turret]

@weary tiger your problem just seems to be

$\frac{n}{2} - 1 < \frac{n}{2} + 1$

[vital dew]

The Arsonist:

[balmy turret]

(subtract n/2 from both sides and it's -1 < 1 which is true)

[weary tiger]

true

thanks @balmy turret

[dapper needle]

I know that I need to invoke the Fundamental Theorem of Arithmetic, and I know that primes and perfect squares are mutually exclusive, but I'm having trouble finding a way to prove that?

[weary tiger]

you could try proving (or cite, if you've already learned this in class or whatever) that a number is a perfect square if and only if the unique primes in it's factorization are raised to even exponents

then a contrapositive argument could easily be used

if the prime factorizations of x or y contain some number of odd exponents, and x and y are relatively prime, then the factorization of xy also has odd exponents, so it isn't a perfect square

[dapper needle]

gotcha, makes sense

thanks!

[plucky stirrup]

@void maple you still need help didnt see your message till now

everyone has a car except john; can be rephrased as all people that are not john has a car

does that help?

to render except would be something like this though

∀x(P(x)∧¬J(x)→C(x)) ∧ ∀x(P(x)∧J(x)→¬C(x))

where P(x) are people, J(x) is John and C(x) is owning car

[weary tiger]

i don't understand this question

[errant bloom]

You have a set $S$ of integers up to $3n$. Now we define a new variable $N_k$ which counts how many subsets of $S$ we can form. We actually create multiple variables, one for each $k$. We call those subsets $X$, and they should fulfill two conditions: 1) their cardinality should be 2n+1. This means that X should contain exactly $2n+1$ elements from $S$. 2) the smallest element in X has to be equal to k.

The question now is, for which values of k can we create such subsets (i.e. $N_k \neq 0$) @weary tiger

[vital dew]

lyinch:

[violet geode]

If I have to show two sets are equal to each other using the laws of logic:

1. Do I have to make arbitrary sets and make the relations by using logical operators, and then use logical equalities to show that the two sets are equal to each other? And if so, do we have to use the definition of subsets to prove that both ways works?
2. Or, can i show this using set equalities?

[open narwhal]

Really dumb question cause I'm blanking, how do I prove a function countable compared to natural numbers?

[weary tiger]

show the question @violet geode

[violet geode]

@weary tiger

is this a valid answer to that question?

[weary tiger]

you just use absorption law

ya

it is

your question is literally the definition of the absorption law

[violet geode]

well the question i have is actually much harder

[weary tiger]

show it

[violet geode]

i cant

[weary tiger]

dm

i'm curious

[pliant horizon]

is finding an inverse function sufficient to prove a function is injective and surjective?

[weary tiger]

show that f is invertible

[pliant horizon]

not sure what you mean.

for example $f(x)=6x-9$. I can find an inverse function, $f^{-1}(x)=\frac{x+9}{6}$. Is that sufficient

[vital dew]

nix:

[weary tiger]

ya

that's sufficient

[naive saffron]

"Using the laws of logic"

Sorry this is pretty funny to me

[valid wave]

what the hell is being asked

[lyric pumice]

You find all the lists that are three entries long where each entry is 1 of the n possible elements.

And then consider the restrictions.

[weary tiger]

Can any show how to prove this statement is true or false:
a^(x) =(congruent) b^(x) mod m
x is a natural number

I’ve tried a few values for a counter example but those hold, not sure how to go about proving/disproving this

[lyric pumice]

Give a counterexample.

[stray reef]

m = 10, a = 2, b = 3, x = 1

counterexample

[weary tiger]

sorry I completely forgot to put the first "if"

a =(congruent) b mod m => a^(x) =(congruent) b^(x) mod m

conditions for my attempted counter examples always seem to match but maybe im just not seeing a proper counter example

[elfin flume]

So all I've been able to figure out for this problem so far is that we have 7 days in the week so we choose any one day and then go for five consecutive days and we get 7 * 6 *5 * 4 * 3 =2520 possible ways to go through the 5 days. Is that correct?

[lyric pumice]

@weary tiger You can prove it by induction.

[weary tiger]

Didn’t think of that, thanks !

[sour arrow]

@pliant horizon
It's enough to show that the function is injective and surjective on some domain and range.

Consider x², x ≥ 0. It has an inverse, √x. Of course, this is assuming the range is x ≥ 0, otherwise this isn't surjective.

[pliant horizon]

@sour arrow so going off my example from before, if i can find an inverse and show it has the same domain as the original function then its proved?

[sour arrow]

It's enough to show that the function is injective and surjective on its domain and range, but that range may not be R

If you've shown that range is R, then you got it, but that's a lot of work at this point haha

[zenith thorn]

Yeh surjective and objective functions really depend on what the function is defined by. Just remember for surjective functions all output values have at least one input value. Considering kaynex’s example, you have a simple parabola. Suppose your output is -1. Can you find an x such that when plugged into the function will map to that value? No, because the range doesn’t contain negative values for parabola; and geometrically, x² doesn’t push further down into negatives. Hence, it’s not surjective.

Surjective and injective functions^

[sleek island]

Can someone help?
How can it be written like that?

[versed summit]

Can someone explain to me why p <-> q when p is FALSE and Q is TRUE equates to FALSE? Because I know in p -> q it's still true, so what changes in if and only if?

[ember sky]

think of it as if one side does not rationalize the other side, both sides are brought down

this is essentially how the and keyword works in many programming languages

well sort of

[versed summit]

Damn see now this has also made me get confused on how normal p then q works

So how come in the bottom half of p -> q it's true?

Like why is if false then false, true?

[ember sky]

( false == false ) = true

that is really detailed ^

[versed summit]

Ah okay when you put it like that in programming terms I understand it

[ember sky]

good source

[versed summit]

It's just the wording in discrete math is confusing

My biggest issue with being a cs major is im very good at coding, not good at math

[ember sky]

I believe you can sum up -> and <-> as this:

-> as in (x == y)

<-> as in ((x == y) == (y == x))

[versed summit]

Well in -> saying F == T doesn't make sense because in the end that would be true, right?

[ember sky]

no cause its false

[versed summit]

okay so in <-> it's only true if both values are the same

so either both true or both false?

[ember sky]

yeah

[versed summit]

Alright so I sorta get why "if true then false" is false, because it's basically saying when p is true, q is false, and therefore the overall thing is false

idk if that makes sense

Like I get why "if false then false" is true because logically it makes sense when spoken, same for "if false then true"

It was just "if true then false" that was throwing me off

[ember sky]

For example

x = 2 ⇒ x^2 = 4 is generally true

but x^2 = 4 ⇒ x = 2 is not necessarily true

so isnt x^2 = 4 <⇒ x=2

because x can be -2

its like saying a square is a rectangle

but a rectangle is not a square

in one simple step

@versed summit its hard to visualize with bools

so i get your confusion

[versed summit]

Wait isn't x^2 = 4 ⇒ x = 2 true? What else could X be?

oh

-2

im dumb

[ember sky]

it can be (-2)^2

yep

[versed summit]

right right my bad

slipped my mind

okay that makes a bit more sense

[ember sky]

hope you understand what i mean

[finite wren]

i'm wondering if this is equivalent - (i typed this)

[hardy viper]

right side doesn't include the negative c's

[finite wren]

@hardy viper if we assume c is non-negative, then it is true?

[hardy viper]

yea

[finite wren]

o cool cool, thats very interesting

thank u ! :)

[naive saffron]

This isn’t right

$\sum_{c\equiv0\pmod{5}}x^a=x^a\sum_{c\equiv0\pmod{5}}$ converges only when $x=0$ and $a$ nonzero

[vital dew]

Whoever:

[naive saffron]

Ok my point is that the left hand side doesn’t depend on c and that’s a problem

Neither is the right side to be honest

So technically this is true but not the way you wanted it

$\sum_{c\equiv0\pmod{0}}x^c=\sum_{c=-\infty}^\infty x^{5c}$

[vital dew]

Whoever:

[naive saffron]

@finite wren

If you assumed c is nonnegative then it’s

$\sum_{c\equiv0\pmod{0}}x^c=\sum_{c=0}^\infty x^{5c}$

[vital dew]

Whoever:

[finite wren]

@naive saffron I’m just generating a series it doesn’t have to converge

With that, would they be equivalent?

Sorry pretend a=c

I typed it wrong

[naive saffron]

Yeah that was my point

[pliant horizon]

can some explain what the last two lines mean? https://puu.sh/GutAS/00637534b0.png

the R^n and tau of R

[hardy viper]

if R has (x,y) and (y,z), then R^2 will just have (x,z)

so like if R was x has y as a parent

R^2 would be about grandparents

and t(R) would be parents grandparents great-grandparents etc

[pliant horizon]

but $R^n$ would still be of the form $(x,y)$ if $x,R^n, y$ for elements $x,y\in X$?

[vital dew]

nix:

[pliant horizon]

or i guess maybe i should say it a different way

if R has say (x1,x2),(x2,x3),...,(x_{n-1}, x_n}, then (x1,xn) is in R^n?

[hardy viper]

that's right

[cerulean ore]

I am trying to find the time complexity of T(n) = 3T(n/4) + cn^2
The way I have learned is that you sum the work you are doing at each level.

Level 0: cn^2
Level 1: 3c(n/4)^2  = 3*c*n^2/(4^2)
Level 2: 3^2 *c*(n/4^2)^2 = 3^2 * c * n^2/(4^4)
Level i : 3^i * c * n^2/(4^(2i))
Summing up: cn^2 (1 + 3/4^2 + 3^2/4^4 + ... + 3^i/4^(2i))```

How do I sum this series?

[hardy viper]

are you summing infinite terms or just up to i?

[cerulean ore]

@hardy viper Just up to i.

[hardy viper]

ok that's a geometric series, because each term is multiplied by 3/16

a1 is the first term, let's say 1, and r is 3/16

[cerulean ore]

Argh :\

I didn't check b^2 = a*c, and rejected considering it as GP.

thanks!

[finite wren]

is this step mathematically right?
i just havent worked with summations like this before

[weary tiger]

the idea is correct but you misused the exponent rules

[finite wren]

@weary tiger so is the wrong part that I made x^45?
should i keep x^30 , 10 , 5 in each summation?

[weary tiger]

$x^{30a}\neq x^{30}\cdot x^{a}$

[vital dew]

HoboSas:

[finite wren]

o right

its x^30^a

oh oim kinda stupid

thank u @weary tiger

[weary tiger]

yes

but you can still do what you did

you only get something slightly different

[weary tiger]

how do you solve this? anyone can give a hint?

[tepid jacinth]

Can anyone help me understand polynomially larger because im having a hard time understanding a question on one of my homeworks.

[stray reef]

context?

[last sigil]

Post the whole question and we may be able to help better

[stray reef]

nah poco don't you know, we're all supposed to be telepaths who magically know the entirety of every question ever /j

[tepid jacinth]

Sorry I was eating lunch. The question was about comparing if n/log(n) is pollynomially less than nlog(n)
n/log(n) <(p) nlog(n)
I dont really know how I should show this, he showed an example where he stated that this is equivalent to
n*n^E/log(n) = O(nlog(n)) , where E > 0 but I dont know if I just show that if i can cancel the n's on both sides just show that n^E/log(n) = O(log(n))

[balmy turret]

Not too sure, but maybe you could do smething lazily like: n/log(n) < nlog(n) n < n(logn)^2 (* logn) 1 < (logn)^2 (/ n)

[gray ingot]

i need help proving set identities. question is (R\S)\T=R\(S\T)
i know the answer is true but i just don't understand how i'm supposed to say it's true

[pallid lintel]

should be deduced from some list of axioms in your notes your given. (screenshot them and post them here maybe?)

[velvet junco]

hmm is boolean algebra fair game here?

if so:
I need to factor this ~w*x*z + ~v*w*x*~y*~z + ~v*~x*y*~z for a fan-in of 2

Not really seeing a clear way

[elfin egret]

Hey can anyone help me prove that the cardinality of ZxZxZ is the same as that of Z

I tried to find a bijection but it's getting a bit difficult to find such a function

[stray reef]

do you want an explicit one?

cause if not i'd first show that Z is equipotent with N, then use that to show Z^3 is equipotent with N^3, and then make a bijection from N to N^3

[elfin egret]

Yes I tried that but it seems that it was a bit long and may be extra work... Maybe we can find an injection from Z to Z3 and then Z3 to Z

Maybe we don't need to go for N

[stray reef]

injection from Z^3 to Z will take some work

actually you can just make a bijection from Z^3 to N

[elfin egret]

How so?

[stray reef]

split Z^3 into a countable collection of finite sets

one way to do this would be as follows: $$\bZ^3 = \bigcup_{k=0}^{\infty} C_k$$ where $C_k = { (n_1, n_2, n_3) \in \bZ^3 : \max(|n_1|, |n_2|, |n_3|) = k }$

[vital dew]

Ann:

[stray reef]

you can imagine the C_k as being cubes made of lattice points

like C_0 is just the origin, C_1 is the 3x3x3 cube surrounding the origin (without the origin itself), C_2 is the 5x5x5 cube surrounding C_1, and so on

basically like an infinite matryoshka of cubes

do you get what im talking about

[elfin egret]

I got the definition of Ck, and a bit of geometrical intuition but how can it give a bijection from Z3 to N

[stray reef]

i'm gonna make it N -> Z^3

basically as an enumeration of the points of Z^3 in a sequence

you start with the origin

then the points of C_1

then the points of C_2

then C_3,

and C_4, and C_5, and so on

each of them is finite (in fact, |C_k| = 24k^2 + 2 for every k ≥ 1) so you'll always exhaust each C_k before moving onto the next

[elfin egret]

Can you express it in functional notation... Like f(n) =?.. Sorry I'm a beginner in this subject

[stray reef]

i was trying to avoid doing that

i mean honestly what im giving here isnt even a concrete description

but if you wanna make it concrete, you could list the elements of each C_k in lexicographic order

[elfin egret]

I think it isn't a function in the first place... Many triplets have same k... So starting with a natural number n, many triplets can be found

[stray reef]

Many triplets have same k...
??

ok like let me be clearer

i'm not mapping the number 1 to the entirety of C_1

C_1 is mapped to the numbers 2 through 27

(if we start N at 1)

C_2 is mapped to 28:125

C_3 is mapped to 126:343

and so on

the ranges grow with the sizes of C_k

[elfin egret]

Okay I got you now...

Though I need some time to write it formally but it gives a well defined bijection... Thanks👍

[carmine widget]

is this true or false?

[unreal stump]

True

[wild flame]

Can anyone make sense of this proof?
https://i.imgur.com/TiYr1a7.png

The highlighted portion is what's confusing me.

They're checking surjecting by picking one variable n (that is a positive integer) and another variable m ( that is another positive integer)

and somehow these two equal each other?

[unreal stump]

*injectivity

If f(n)=f(m) => n=m the function is injective

[wild flame]

Ah. I thought 'onto' meant surjective. My bad.

[unreal stump]

One-one is injective

[wild flame]

OH

[unreal stump]

And in your marked passage,he says one-one

[wild flame]

Yeah brainfart.

Thanks a lot.

[finite wren]

is this true?

it was originally summ 0 to infinity x^(a+2b+30c)

[naive saffron]

Don't use the same index for different sums in the same formula

no it is not. The current expression doesn't even quite make sense

[finite wren]

@naive saffron mb pretend the index things are unique

[naive saffron]

Then sure

Yes

[finite wren]

it was originally summ 0 to infinity x^(a+2b+30c)
@finite wren

Yes
@naive saffron I'm just not sure if what i have is multiplication or "repeated summation things"

like basically is
is the shape () () () = () () () (equal obviously)
or (1(2(3))) = (1(3(2))) (equal??)

Are these repeated summations, or are you trying to multiply the three summations?
@worthy palm is there a difference - i think thats what im trying to ask

[spring mica]

@pale epoch how does this set builder notation specify mapping

it just says that all of the tuples in the set has to come from A B and C

it dosen't specify all combinations

[lyric pumice]

It does specify all combinations.

There are |A||B||C| objects in the set.

[spring mica]

@lyric pumice are there any exmaples of A being a subset of powerset(A)

other than the powerset(emptyset)

[gray ingot]

how would i go about these?

i know the best way to start would be to assign different sets to each value and then work from there but tbh i don't really understand the logic

[lyric pumice]

@spring mica No. Prove that there are none.

[spring mica]

i don't know how luh mao

@lyric pumice

[spring mica]

gotcha

[versed summit]

https://cdn.discordapp.com/attachments/551211051975180301/757765757039018095/image0.png

i have no idea what im doing

my answer for A looks like minecraft enchanting table so I'm not sure if it's correct

this is a cry for help

[gritty crescent]

You could see this unfold step by step.

[vital dew]

TedNowKaczynski:

[gritty crescent]

This is my analysis and it could be incorrect

@versed summit

[zinc robin]

Hi, I was wondering if anyone could help me with this proof

I'm not exactly sure what it's trying to have me prove, or where to start with writing the proof

[stray reef]

prove that if m has no prime divisors up to its square root then m is prime

or equivalently that any non-prime will have a divisor less than or equal to its square root

[zinc robin]

ohh ok lmao

it's probably just too late

for some reason I couldn't think of how to do the contradiction

or wait that's contrapositive

[short lantern]

I'm not sure how we get from the step before to the one with an arrow, could anyone explain?

[stray reef]

21 - 3*(48-2*21) = 21 - 3*48 + 3*2*21

@short lantern

[short lantern]

Ooh thanks alot lol

[alpine owl]

Need help with this question -
Count the number of ways in which n identical items can be distributed into n identical boxes such that no group has more than 2 items each

To be clear, this is a homework question, so I don't want the final answer, just want help with how to approach it

There's 1 way in which every group has 1 item, 1 way in which there will be one group with 2 items and another with 0 while the rest all have 1, and so on

So do I just need to enumerate that?

You need to have an even number of pairs of 2-0 groups so it will be a different value of odd and even n

Or am I missing something

[versed summit]

Can someone verify if I did this correctly?

Would equal

(~p^~q) v (p^r)

[silver raptor]

correct but are you supposed to simplify?
~(pvq) v (p^r)
hmmmm ... actually it does not simplify further ...

I am a "bit" surprised at that 😁

[silver raptor]

@backgrounddeep
here is another way to view the problem:
n=1: one way, all 1s
n=2: three ways: 2 with one zero in it, 1 with no zeroes: specifically { (0,2), (2,0), (1,1) }
n=3: 7: six ways with one zero in it, one way with no zeroes
n=4: two zeroes has 4 choose 2 arrangements, one zero has 4x3 arrangements, no zeroes is still 1, so 19 ways total
n=5: two zeroes has 5x4 ways to place zeroes and 3 ways to place the 1 so 60, one zero has 5 places for the zero and 4 for the 2 so 20, and then there is all 1s, so 81 total
so what is the inductive pattern, how can this sum of sums be converted into a formula in terms of n? Do odd values of n need to be treated differently from even n, requiring two inductive rules, two formulae?

[versed summit]

@silver raptor you're right, my bad

Secondary question

What does consitent mean?

Would
r t ~r ~r v t
T T F T
T F F F
F T T T
F F T T

be inconsistent because there's no line where it's all T

[versed summit]

or does ~r not count?

[fallow raft]

How many ways are there to put m distinguishable elements into n different locations, given the locations and elements are different? Also, there can be more than 1 element in a location

I thought it would be $m^{n}$, but wasnt sure if its that or the normal permutation equation

[vital dew]

AH:

[sour arrow]

@versed summit
The statement ~r v t is consistent because there is a way to make it true.

Take your first element. There's n different places it could go. That's n choices.

Take your second element. There's n different places it could go. That's n choices.

Take your third...

You get n×n×n×... (m times) choices. That's n^m@fallow raft

[versed summit]

@sour arrow so if a statement is a tautology is it also consistent

[wild flame]

These proofs are kicking my ass.
https://i.imgur.com/N7vcrVf.png

How in the world are they mapping d1 to d11?

https://i.imgur.com/VxCfiV0.png

OH

I just got it

[dire void]

https://cdn.discordapp.com/attachments/488104216678760469/758120383856640020/162017091996745728.png

[inner lava]

Is there a python package that lets you easily generate a random eularian graph with N nodes?

[winged bramble]

quick question: what does a uniqueness proof look like? im not entirely sure what one looks like

[hardy viper]

@winged bramble depends on context, but one common way is assuming u and u' satisfy the conditions, and concluding u=u'

[winged bramble]

so is it bascially saying "only this particular thing makes this particular thing true?"

[sonic path]

hello does it matter which premise i start with for this problem?

[dire void]

quick question: what does a uniqueness proof look like? im not entirely sure what one looks like
@winged bramble https://docs.google.com/document/d/1Bc1rAp1EN9_UIpnCaVKKlPpNtwq8h62WHYVrknwpig4/edit

another uniqueness proof: https://docs.google.com/document/d/1UDMAeoEkKbqGNXPTQlwIXLRKId_qq4yX_N0Gbb6vHqU/edit

[winged bramble]

oh, so its showing something exists and then has that unique property?

[dire void]

well. i combined the proofs of existence and uniqueness.

but there are two sections in the proofs: one section proves existence. the other section proves uniqueness.

[versed summit]

Can someone explain to me Idempotent law and Absorption law? I don't get them at all.

[dire void]

Can someone explain to me Idempotent law and Absorption law? I don't get them at all.
@versed summit

https://docs.google.com/spreadsheets/d/11rri7XubkLaX6ZXxDDhuE0y79u_Of34fSLOXxNebev4/edit#gid=141306215

Refer to 3, 8, and 12\

[versed summit]

So why is it that A or (A and B) = A?

[dire void]

do a truth table?

[versed summit]

oh weird

that hurts my brain haha

[dire void]

do a truth table for A
do one for B

use excell, google sheets

[versed summit]

No i got it haha

it's just weird to me

[dire void]

i guess. i dont even think about it anymore, i just follow along and use it

[versed summit]

yeah this stuff is really hard to me

and my professor doesn't really teach us

just tells us to learn it before the next quiz

[sonic path]

can someone explain to me how they went from 2 to 3 here, says law of implication on 2 but i don't get it

[hardy viper]

@sonic path that's the definition of the -> sign

seems like they applied it wrong though O_o

[sonic path]

how so?

[hardy viper]

p->q is -p or q

[robust mango]

@iron crescent What's the whole question? I mean, is it state that it's true/false?

[robust mango]

typo i think, they meant doesnt belong prolly

[gritty crescent]

...it was a proof by contradiction

[robust mango]

Yeah now that I see it

x is in the intersection of all the intervals

that's our assumption

and that can only happen if 0 < x < 1/n for every n (for every interval that is), but then by the Archimedean property, we find that there is a N such that 1 / N < x, or there is an interval which doesn't contain x.\

np!

[gritty crescent]

Is the collection of all circles in a given non-Euclidean plane a set?

I'm tempted to think it's not, since circles may not be well defined in non-Euclidean geometries, but I don't know if that's true.

[stray reef]

circles are well-defined so long as you have a metric

[gritty crescent]

I see. So this is a set?

[stray reef]

why wouldn't it be

[gritty crescent]

Aight, thanks!

[wide agate]

someone pls help me

[weary tiger]

is K_n a subset of K_j where n<j?

where K_n is the complete graph

[stray reef]

these are graphs, not sets

K_j does contain K_n as a subgraph if that's what you actually meant

[zenith thorn]

Well, for the expected value, usually it’s ∑x(f(x))

[weary tiger]

ya true Ann

thank you

[stray reef]

"usually"
you mean in the discrete case @zenith thorn

[zenith thorn]

Oh yah, my bad for clarity

[fathom pond]

hi may i please get help for this question? Is it right to assume that
p: n is an integer and 𝑛^2 + 1 ≤ 2^n
q: 5 ≤ 𝑛 ≤ 7

[quaint star]

You are trying to prove that: 5<=n<=7 implies n^2 + 1 <= 2^n

[fathom pond]

@quaint star so can i use proof by contraposition (indirect proof) in this case? which means i assume that n^2 + 1 not less than or equals to 2^n (n^2 + 1 > 2^n) and show that n < 5 and n > 7

i'm sorry if i'm not making sense lol

[stray reef]

you're kinda overcomplicating it

there are only three integers between 5 and 7 inclusive

5, 6, 7

[fathom pond]

meaning to say i just have to show that n is not 5, 6 or 7?

[stray reef]

you're still overthinking it

why use indirect proof when you can just... not

[fathom pond]

so trivial proof

[stray reef]

direct proof

by explicit computation

[gritty crescent]

Suppose that the following propositions are true:\if $x\in A$ and $y\in B$, then $y\in A$;\if $x\not\in A$ or $y\in A$, then $y\not\in B$\What simple conclusion can be drawn from this?

[vital dew]

TedNowKaczynski:

[gritty crescent]

I guess it's $A\cap B=\emptyset$, but not completely sure.

[vital dew]

TedNowKaczynski:

[gritty crescent]

Even this doesn't make much sense I guess :3

[pale epoch]

why not?

[gritty crescent]

This was my first hunch but I couldn't put this thought down on paper

[pale epoch]

seems true, but there is more you can say i guess

[weary tiger]

Hi, I have some questions about discrete mathematics

[gritty crescent]

My head's spinning, I really don't know what else I can conclude.

Feel free to ask here, I'll bang my head against my question laters lol.

[weary tiger]

Kk, sorry if I'm disturbing yah 😅

https://media.discordapp.net/attachments/442470054978650122/758349044056588378/unknown.png

For this compound proposition, I've already written out a truth table and I've discovered that this is a tautology

But how do I prove this using logical equivalence? Could someone walk this through with me because I'm looking at the list of laws and I'm just not sure how to apply it to this case. I am very new to discrete mathematics and I'm not used to applying these laws yet

[pale epoch]

use the fact that $(p \rightarrow q) \equiv (\neg p \lor q)$

[vital dew]

Lochverstärker:

[weary tiger]

hmmmmm...

🤔

The thing is there is 3 implications on this so I'm just a bit confused. "P" is a compound proposition too

[pale epoch]

just start with any of them

[weary tiger]

Do I use rules of inference in here too?

[pale epoch]

like $(p\land \neg r) \rightarrow q \equiv \neg(p\land \neg r) \lor q$

[vital dew]

Lochverstärker:

[weary tiger]

Ah

[pale epoch]

what's that

[weary tiger]

Okay that's starting to make sense

I'll try that and then I'll post what I got

I'm writing this out and

I can either continue with the

distributive laws or the de morgans law

https://s3.us-west-2.amazonaws.com/secure.notion-static.com/0f994fcf-2bb7-40ef-a36c-c7af8ccf5a76/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20200923%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20200923T153953Z&X-Amz-Expires=86400&X-Amz-Signature=dacee3cd735925fb1c19273ac8873b6c8bbb0938c199b6772e2204de80887738&X-Amz-SignedHeaders=host&response-content-disposition=filename %3D"Untitled.png"

however both laws doesn't have any negations in them

https://media.discordapp.net/attachments/496785905474994186/758351139716071491/382564543085281292.png?width=1922&height=220

This one has

[pale epoch]

and that is a problem because?

[weary tiger]

how do I convert them if there is a negation inside?

or rather how do I convert them with the negation?

[pale epoch]

convert to what

[weary tiger]

I've seen my lecturer done it but he has never clearly explained how he is able to do that with the negation

I want to apply the distributive law or the de morgans law

[pale epoch]

you can just do that

well

you can't distribute in this case

but de morgan tells you how to "move" the negation into the parenthesis

this will also remove the need to distribute anything in this case

[weary tiger]

can you show me an example?

[tame hound]

Hi i need help for a really difficult question

Number 7

[pale epoch]

there is an example listed in that picture

[tame hound]

I would really appriciate it if anyone could help me with this as soon as possible

[pale epoch]

$\neg(p \land q) \equiv \neg p \lor \neg q$

[vital dew]

Lochverstärker:

[pale epoch]

also notice that $\neg\neg p \equiv p$

[vital dew]

Lochverstärker:

[weary tiger]

so would it just be...

$\neg p \lor \neq\neg q$

is that the right answer 🤔

oooh that wasn't what i intended

[vital dew]

Wumbo:

[pale epoch]

the answer to what

[tame hound]

Anyone?

[weary tiger]

nvm i'm just gonna try to solve it myself

[pale epoch]

yes that was the goal, i just told you how

[weary tiger]

I don't know how to apply it correctly

[pale epoch]

then either ask precise questions or go back to easier questions and study first

(and its not like you will find a better way to solve it)

btw the statement is not a tautology from what i can tell

e.g. if p, q and r are all false, it's false as well

[tame hound]

If not maybe the truth table for it?

[versed summit]

I'm still a bit lost on this.

r    t    ~r    ~r v t
T    T    F    T
T    F    F    F
F    T    T    T
F    F    T    T```

Inconsistent?

Because there's no line where it's all T?

[pale epoch]

that's impossible

r and not r can't both be true

[versed summit]

So then the statement ~r v t is inconsistent, right?

[pale epoch]

what does that mean

[tame hound]

On thing what is <=> expression wise. Is it NAND or NOR?

[pale epoch]

no

it's => and <=

[tame hound]

Wait Nand And NOR

[abstract ravine]

Hey, so im confused over one thing

lets say i have this sequece -3, 6, -9, 12... given that f(k) = (-1)^k(3k)

and i need to prove this by using induction

so the first step is the basis step, i need to prove f(k)

and then its the induction step, where i need to prove f(k+1)

once i have proven those 2 steps i have proven the sequence formula correct?

[pale epoch]

this makes no sense

what do you want to prove?

[abstract ravine]

it doesnt?

im ngl im new to the idea of induction

[pale epoch]

your description of induction is ok

but what do you want to prove

[abstract ravine]

am i not supposed to prove that the given formula does indeed give us the correct kth term in a sequence?

by using induction

so by proving that f(k) = -3

we have proven the first step

[pale epoch]

how is the sequence defined?

[abstract ravine]

lets say i have this sequece -3, 6, -9, 12... given that f(k) = (-1)^k(3k)

[pale epoch]

so by f(k) = (-1)^k(3k)?

[abstract ravine]

yes

[pale epoch]

and what do you want to prove?

[abstract ravine]

idk tbh

what is induction then

i dont understand induction i guess

i thought i knew what induction is

[pale epoch]

is this some exercise or did you make this up yourself?

[abstract ravine]

no i took it from a youtube clip

[pale epoch]

induction is a way to prove that some statement is true for every natural numbers

but if you have a sequence defined by f(k) = (-1)^k(3k) and want to show that f(k) = (-1)^k(3k), then there is nothing to do

[abstract ravine]

really?

[pale epoch]

if you assume something, then how are you supposed to prove it?

[abstract ravine]

what am i assuming?

[pale epoch]

i thought you said that you have a sequence defined by f(k) = (-1)^k(3k)

[abstract ravine]

how is that an assumption

[pale epoch]

how is it not??

[abstract ravine]

its a fact

isnt it?

[pale epoch]

well, ok, this does define a sequence and that is a fact

but then, what do you want to prove from that?

[abstract ravine]

ye thats the thing, i think i dont understand induction

yet

i thought i did

kinda lost

lol

i watched this video

https://www.youtube.com/watch?v=GdM_iA1Zek4&list=PLHXZ9OQGMqxersk8fUxiUMSIx0DBqsKZS&index=45&ab_channel=Dr.TreforBazett

he tried to prove the above sequence

oh wait he is proving that n >= 1 ?

by using induction?

[pale epoch]

no

[abstract ravine]

wtf

[pale epoch]

he is proving that the sum of the first n natural numbers is equal to $\frac{n(n+1)}{2}$

[vital dew]

Lochverstärker:

[abstract ravine]

how is that any different from the one i wrote

[pale epoch]

i.e. $1+2+3+\dots + n = \frac{n(n+1)}{2}$ for all $n \in \bN$

[vital dew]

Lochverstärker:

[abstract ravine]

what

[pale epoch]

any different from what you wrote?

[abstract ravine]

yes

[pale epoch]

your example was just a sequence

[abstract ravine]

??

it was an infinite sequence yes

[pale epoch]

the claim here is that $1 + 2 + 3+ \dots + n$ and $\frac{n(n+1)}{2}$ are actually the same thing

[vital dew]

Lochverstärker:

[pale epoch]

what is your claim?

[abstract ravine]

lets say i have this sequece -3, 6, -9, 12... given that f(k) = (-1)^k(3k)

oh wait

[pale epoch]

what is f(k)?

[abstract ravine]

just the result i guess

the output from this (-1)^k(3k)

[pale epoch]

ok

[abstract ravine]

wait what do you call the one above

[pale epoch]

and then what is the claim

[abstract ravine]

the claim i assume is that the given formula can gie me any kth term from the sequence

this is from my understanding

[pale epoch]

and how is the sequence defined then?

[abstract ravine]

now idk if thats the point

-3, 6, -9. 12....n

[pale epoch]

this is not a definition

this could be anything

[abstract ravine]

huh

[pale epoch]

"-3, 6, -9, 12" what is the next term?

[abstract ravine]

-15

[pale epoch]

why not 42?

[abstract ravine]

ok we dont know thats the point isnt it

ahh shit

ok but

what if it was -3 + 6 + (-9) + 12...+n

different story?

[pale epoch]

that's still not a clear definition

like, can you explain in words how your sequence is supposed to look

and not just put random dots somewhere

[abstract ravine]

idk i dont have a question/sqeuence

[pale epoch]

like, when you want to prove that 2 sides of an equation are equal

you first have to know what both sides are

[abstract ravine]

now i have to prove by induction

Whenever n is an integer with n ≥ 3

[pale epoch]

what does a=1 have to do with that

[abstract ravine]

idk this is literally a question

i have

from Uni

thats literally all the information i have

[pale epoch]

well, you can prove n^2-2n >= 0 for all n >= 3 with induction

[wild flame]

So I'm again having trouble making sense of Cantor diagonalization argument.

https://i.imgur.com/bXNT2r3.png

Having rouble making sense of the last part in particular: https://i.imgur.com/UDBuzc0.png

How does choosing a random decimal expansion made of 4s and 5s

and having it the placement of the 4's and 5's contingent on the real numbers in the notation.

Supposed to prove that this new real number isn't part of the list?

[pale epoch]

it's different in at least 1 place from every number on the list

[wild flame]

I don't get it. Do theese other numbers have some sort of overlap that I'm missing?

[pale epoch]

no, why?

to show that 2 decimal expansions are different it suffices to find 1 place where they differ

and the constructed number differs from the ith number on the list in the ith place

[wild flame]

Yeah. But:

0.23794102
0.44590138
0.09118764
0.80553900

The majority of these are all different in one or more spaces too. No?

[pale epoch]

yes?

[wild flame]

I'm confused as to why it matters then. If they're all sufficiently different anyway.

[pale epoch]

all numbers on the list are different

by assumption

you want to show that there is another number that is different from all those, yet not on the list

i.e. your list must be incomplete

[wild flame]

Ah. Okay. I think its making a bit more sense. So just to make sure it makes sense.

Countable numbers must be able to be shown in a sequence, such as 1,2,3,4. . . n

What Cantor's Diagonalization argument does is prove that this isnt the case with real numbers. Due to the fact that no matter what sequence you create, you can always make another sequence that does not follow the rule, right?

[pale epoch]

what's a countable number?

[wild flame]

Countable sets*

[pale epoch]

countable sets are in some sense "listable"

you can write a potentially infinitely long list

so this list does not have to terminate at n

and the idea of cantors argument is

assume that we have an infinitely long list listing all real numbers

then we can construct another real number that is not on that list

so our assumption must have been wrong

[wild flame]

Ah.

[pale epoch]

and no list of all real numbers can exist

not even an infinitely long list

[wild flame]

That makes so much sense.

so this list does not have to terminate at n

And fair. So I guess it would be more accurate to say that a countable set must at the very least be able to d oa sequence like so: '1, 2, 3,4 . . .' As opposed to with an n, which implies termination at some point.

Right?

[pale epoch]

yeah

[wild flame]

👌

[pale epoch]

in technical terms a countable set is in bijection with the natural numbers

(or with a subset of the natural numbers)

[wild flame]

So to go over one last iteration just to make sure I have a good grasp.

Basically, a countable set is an orderd listing with the same cardinality (number of elements) that is either the same or a subset of Natural Numbers. These sets have to be able to be listable. IE: (1, 2, 3,4 . . ) and can go on infinitely as you'll know which comes next.

What the argument is stating that a countable set is not possible for the set of real numbers. It proves it by showing that no matter what the listing you have in your proof, you can always make up some number that would not possibly be listable.

If so, eureka. This has been kicking my ass all day.

[pale epoch]

that's the gist of it

[cloud cargo]

eureka

[abstract ravine]

https://www.youtube.com/watch?v=IYW4iszVH3w

ok so im kinda confused, why did he do the 5th step where he added k+1 to both sides

look at the 3rd step and 5th step

from 11:00

[pale epoch]

$S_{k+1} = S_k +6(k+1)$

[vital dew]

Lochverstärker:

[pale epoch]

his 3rd step looks horrible though