discrete-math

[sharp rose]

I thought it was prove "P->P" given "P->P^P"

[muted basin]

when P is my hypothesis the only thing I can do to it from what I see is addition but that gives v instead of ^

[sharp rose]

uh i dont think it specifies in your tables but is P->P an axiom

[fossil mural]

...why would you need that

[sharp rose]

You need some starting point

[muted basin]

i'm not sure if this is a case of my prof not choosing good practice problems from the textbook (this isn't homework, just weekly practice from our textbook) or if it's just something I am misunderstanding

the only rules we've learned are the ones I've sent

[sharp rose]

i get that those are the inference rules, but what are the axiom(s)

[muted basin]

(done some predicate logic since then but not really related to this problem the way it wants me to solve it)

we haven't learned that

[fossil mural]

well no, there's one other rule that you've used in your proofs that isn't explicitly stated in the screenshots

which is that if you're trying to prove an implication "P -> Q", you can use P as a hypothesis

[sharp rose]

that's a higher level mp

[fossil mural]

and in this case, once you have P as a hypothesis, there's a proof of P ^ P in one step

[fossil mural]

...no it isn't??

[sharp rose]

it's the same as saying P->P is an axiom

[fossil mural]

...that's also false

[muted basin]

are you introducing a second P as a temporary hypothesis like those other problems so that it fits P, Q from the rule set?

[sharp rose]

It's modus ponens but operating at turnstile level

rather than logical implication level

introducing P->P as an axiom should have the same effect afaik

[fossil mural]

...it doesn't

and also this is different enough that calling it any kind of "modus ponens" just seems ridiculous

[sharp rose]

okay i should not have used that terminology, it was confusing i agree

[muted basin]

here's my setup so far as barebones as it is

Step 1: P - hypothesis

that's all i got

I can create PvP with addition but not P^P

[fossil mural]

well that's the correct first step

[muted basin]

as for introducing temp hypotheses and discharging on anything but an "A -> B" I haven't learned yet

in class we only did a single discharge and it was identical to the problem I sent just unexplained

[sharp rose]

You can, you have to be a bit clever i think

[fossil mural]

...well not with the addition rule, that produces a disjunction

[sharp rose]

Like using demorgans laws and then using the fact that you also know P

hold on i'm curious let me work it out on my own

[fossil mural]

that's not going to work using the addition rule, it would be using whatever rule you have for using a disjunction as a hypothesis

but also that's overcomplicated because you literally can do this in one step, unless there's a random pointless restriction on the proof system that specifically excludes this case

[muted basin]

wouldn't that lead to having P , P' and then P ^ P' as a conjuction

[fossil mural]

you can just use the conjunction rule directly to prove P ^ P

[muted basin]

but we only have P as a hypothesis

I need a Q

which is going to end up just being P but

I have to use a rule from that list to prove this

[fossil mural]

...?

[sharp rose]

oh yeah lmao

[fossil mural]

ok you got like halfway through reasoning it out and then said "i need to use a rule from that list", when we are using a rule from that list

[sharp rose]

i actually didnt see that rule in the list

[fossil mural]

the conjunction rule is in the list and it is the only rule we need to apply here

[muted basin]

when I declare that I got P^P from a conjuction, I need to point to two steps for justifying that

[sharp rose]

the "Q" is P

[fossil mural]

yes you do

so first we need a step that proves P

so which step proves P?

[muted basin]

step 1 which is just a hypothesis

[fossil mural]

alright

so secondly, we need a step that proves P

(because it's P ^ P, so "Q" is just also P)

so which step proves P?

[muted basin]

but I can't just write step 2: P^P - conj 1, 1 right?

[fossil mural]

why not? :)

[muted basin]

intuition and the black and white thinking of my flavor of autism

[fossil mural]

you pointed to two steps: step 1, and step 1

step 1 is a proof of P, and step 1 is a proof of P

[muted basin]

i guess it just feels wrong in my mind to be able to infinitely add / reuse things in logic

[sharp rose]

okay im actually curious if theres a way to prove w/o conj rule

im trying rn

[fossil mural]

well i mean, we're talking about truth here

do you have a problem with infinitely reusing your beliefs about the world?

if you look outside and think "oh it's raining, therefore probably things will be wet", did this reasoning consume your knowledge that it's raining outside, so that if you want to deduce "i should take an umbrella" you have to observe again that it's raining, so that you have a second copy of "it's raining outside"?

[muted basin]

it makes sense when you word it out but it also is hard to wrap my head around

for some reason I cannot drop the idea of things "Cancelling" out in a sense

simplifcation, etc whatever to call it

such as boolean algebra laws where you are minimizing functions

or maybe im just confusing myself

[sharp rose]

You can cancel things in your formulas but that doesn't mean you can't refer to the past formulas

[sharp rose]

Anyway proving ~P -> P^P is possible but idk if P -> P^P is possible

[muted basin]

if I had to describe it with an example, when I see A ^ A->B ^ B -> C

[fossil mural]

uh

[muted basin]

in my head I turn A, A->B into just B

and then I read it as if it's just B ^ B->C

[fossil mural]

¬P -> P^P isn't true if P is false

unless you mean that you proved P -> (¬P -> P^P)

[sharp rose]

yeah sorry this is what i meant

forgot to say having P as a hypothesis

[pliant horizon]

ah. yeah i imagine if you had (i,j) in R means M_R has a 1 in the ji entry then maybe it would go the opposite direction? but from all the tests i've done if you have (i,j) as a 1 in the ij entry, then i think
MSMR=M(RoS)

[muted basin]

is my proof gor 30 right

for

excuse my not symbols im realizing now i drew them like doodoo

[shell yew]

can someone explain what this splitting condition has to do with atomlessness (ignore the foundation stuff, I'm trying to learn forcing)

I know that a being an atom means that there is a least element 0 such that 0 <; a

[little bloom]

Is anyone here ?

[brave rock]

I’d suggest just asking your qn.

[little bloom]

Please help me understand this meme 😭😭

I just guessed that I have been bamboozled

@brave rock help

[vital dew]

Anyaki

[sullen vessel]

Maybe don’t ping people just to get them to explain memes

The joke here is just that you can diagonalise some matrices and they have their eigenvalues as the entries of the main diagonal

Im not sure if this is the right place to ask this or not but I think it is just a counting problem at its core:

"Let $\Sigma$ be a set of 8 points in $\mathbb{P}^2$ such that no more than 5 points in $\Sigma$ are colinear. Show there exists a line containing exactly 2 points from $\Sigma$."

[vital dew]

Nope

[sullen vessel]

I think it must come down to some sort of pigeonhole argument but Im not seeing quite how to go about it

Something along the lines of, any 2 pairs of points defines a unique line. We've got 8 points, choose 2, 28 such pairs so that gives us 28 lines. Then I guess we think about lines which contain 3 points, and use the fact that if the intersection of any of those lines with the 28 on 2 points is more than a single point theyre equal, but ive got no idea how to do this

Another idea I had was to do some sort of inductive type thing, assume 5 points lie on L_1, say P_1,...,P_5, then take L_2 to be the line passing through P_6 and P_5. This is distinct from L_1, so we have that none of P_1,...,P_4 are in L_2

That seems somewhat productive but im not sure what happens next

[raven heart]

For all real numbers x, there exists an integer y so that ⌊xy⌋= ⌊x⌋ ⌊y⌋.

https://cdn.discordapp.com/attachments/1006319012021539087/1335382002324471818/IMG_0237.png?ex=679ff6e7&is=679ea567&hm=74868c73c196824b67fa32afe878a673083a2a8dab32414c79c0d9fb5b2c7540&

Do I need to add more to my proof

[oblique pelican]

I'm confused what your process was here. You assumed what you are trying to prove and also didn't say anything about what x is

[muted basin]

can someone confirm this

[sharp rose]

I mean can't you just say y=1?

[viscid hollow]

can someone help with this. I am stuck with writing the expression when I am only given the variable f

[weary tiger]

I think this should do it:

Let I be the set of all insects.

There exists x in I and y in I such that (x != y) and (B(x) and Y(x)) and (B(y) and Y(y)).

I'm assuming in answering this that we are looking for at least two distinct yellow bees, not exactly two.

[viscid hollow]

Am I allowed to write there exists when the domain is all insects?

[weary tiger]

Is the domain the universe of discourse here, or do you mean you have to use the universal quantifier?

[viscid hollow]

universal quantifier

[sharp rose]

Does it have to be two bees exactly?

Or can there be more than two bees

[viscid hollow]

yes

[sharp rose]

Can there be more than two bees in general

[viscid hollow]

For this expression I think not, this is what I am instructed to do "Given the predicates and domains in each problem, express each of the following sentences in terms of the predicates, quantifiers, and logical operators."

[sharp rose]

,, \exists x . \exists y . (x \neq y \land B(x) \land B(y) \land Y(x) \land Y(y) \land \forall z . (z \neq x \land z \neq y \implies \lnot (B(z) \land Y(z)))

[vital dew]

qiuzlm

[sharp rose]

texit not coming in clutch

[sharp rose]

Ok if there can only be two bees in general then change $\lnot (B(z) \land Y(z))$ to $\lnot (B(z) \lor Y(z))$

[vital dew]

qiuzlm

[sharp rose]

Btw I think you can simplify my result a lot

[viscid hollow]

I wrote this

but i know it is wrong but I just gave up 😭

[sharp rose]

What's 2

[viscid hollow]

2 bees

[sharp rose]

okay well you can't just introduce numbers for free

[sharp rose]

Yeah I can think of a way to simplify it a ton

Basically you need at least two bounded variables representing the two bees

So just having "f" isn't enough

I think you need three bounded variables

[weary tiger]

I think three, if you're going for exactly two insects are yellow bees.

[sharp rose]

Yeah

[viscid hollow]

and still using the all of quantifier?

[weary tiger]

Also - this is probably overanalyzing the sentence - but we are saying there are exactly two bees? Or exactly two yellow bees?

What I mean is you could use the third variable to say "at most two bees", so allowing for the possibility that z is a yellow insect that isn't a bee

[weary tiger]

What quizlm suggested is how you would do it. You cannot arbitrarily introduce numbers - what your solution says is all insects are bees that equal 2, which is not, of course, what the sentence is saying.

[viscid hollow]

Oh I see

[weary tiger]

Yeah. So, for the solution offered by quizlm, the first part is saying there are at least two yellow bees. The second part is saying, basically, that any insect which isn't one of the two bounded by the existential quantifiers is not a yellow bee (this is the "at most two" part), so there are exactly two yellow bees. Does that make sense?

Using quantifiers for "natural" sentences like this is always sorta tricky, for me anyways.

[viscid hollow]

I see now, I was just really stumped since all the the other questions in my problem set had different variables making it easier for me to write the expression

But yes thank you, now I understand the meaning of the question

[weary tiger]

This isn't the subject for a math server, but opaqueness in everyday language - trying to sort out what claims are being made when arguing about metaphysics or whatever - is also looked at by philosophers (I was first exposed to predicate logic in a Phil class a while ago now)

Also, you don't have to reuse the free variable in the predicate - and you probably shouldnt in cases like this to avoid confusion.

[sharp rose]

i don't really like the question because it isn't clear if the bees and/or the yellowness is at most multiplicity 2

[muted basin]

is my proof correct

[oblique pelican]

looks good to me

[solar marsh]

Any tricky basic set theory exercises (no proofs)?

[wary falcon]

Does any set multiplied by the empty set = the empty set?

And are real numbers a subset of complex numbers where the coefficient of i = 0 or is it separaye

[slim ferry]

im solving this by using recursive tree then subsituting but im confused what to do at the end here now

[true parcel]

I'm pretty sure there is a table you can refer to

[cerulean wind]

the cartesian product of a set with the empty set is empty, yes

[cerulean wind]

yes, that is correct

[wary falcon]

Thank you

[slow warren]

i get everything up to the point Given h : X → Z, define g = h ◦ f −1. Then φ(g) = h ◦ f −1 ◦ f = h, so φ is surjective. can someone explain that

think of me as dumb as i can be

nvm i think i got it:

g is well...defined as h o f^-1 wich means that f-1 is basically applied on an X and not an Y

then phi(g) is defined as g o f wich in turn is again defined as h o f^-1 so it gets substituted into h o f^-1 o f

right?

[buoyant vale]

is the simplification part legal or i can't do that

[modest comet]

can someone look at help-35 please

[grand totem]

The claim is that given an arbitrary h : X -> Z, there is some g : Y -> Z such that phi(g) = h. They proved this by noticing that h . f' : Y -> Z is one such witness for g, as phi(h . f') = (h . f') . f = h . (f' . f) = h . id = h.

[oblique pelican]

I misread

[oblique pelican]

Yeah that all looks good

[compact pivot]

can someone help me better understand these instructions please, im not sure how im supposed to derive each expression into proving whether or not they are equivalent

[oblique pelican]

So you can make a proposition for each statement. A real number can only be rational or irrational, so you could have a proposition R(x) meaning "x is rational". Then you can say the proposition ~R(x) means "x is not rational" or "x is irrational". So using this, you can create a symbolic statement for both bullet points and then use logic rules to show they are equivalent.

[slow warren]

yeah i realized that after some time haha, because there was smth confusing i didn tget but i figured it out, thc for the help tho :3

now for the next question

[fossil mural]

...given that i already know the answer, i can kind of see how to read what you said as being the correct answer

but if i didn't already know why that formula works i don't think reading what you said would help much

so, at minimum you need to be way clearer

...it's also possible that in fact the approach you had in mind is wrong, or missing an important step, and the vague messy explanation is hiding the mistakes

[compact pivot]

Thank you so much! I was unsure how to make it apparent which would be Rational vs Irrational, thank you for the help

[livid gazelle]

Dunno if this is the right place for this, but I'm dealing with a puzzle and have fallen down a rabbit hole

If I have the sum of the first k powers of an integer b, thats a geometric sequence, which means the sum is (b^k-1)/(b-1)

Which means that b^k-1 is a multiple of b-1

And I can't possibly be the first person to have noticed or studied this fact. It made me think of Fermats little theorem, but thats specifically for primes, but b-1 isn't necessarily prime here

[oblique pelican]

Yes, you get [b^k-1=(b-1)(1+b+\dotsc+b^{k-1})] by rearranging the sum.

[vital dew]

Dilly

[oblique pelican]

I believe this comes up in the derivation for the finite geometric sum

I don't think this identity has a name because it follows from the sum

[livid gazelle]

Hmmmm ok i see

[oblique pelican]

It is an interesting result tho, maybe theres a number theory theorem relating to it like you say

[livid gazelle]

I fell down this rabbit hole cuz I'm dealing with a programming puzzle (for a given integer n, find the smallest base b such that n's base-b representation is all 1s)

And one problem I'm dealing with is the fact that while the sum itself won't overflow, the intermediate calculation b^k can, which forced me to start digging out really old stuff

Although the equation you just laid out gives me ideas on how to simplify

So [b^{k-1}-1=(b-1)(1+b+\dotsc+b^{k-2})] right?

That didn't turn out how i wanted

[oblique pelican]

Use brackets to enclose the exponents

{}

[vital dew]

Stevie-O

[oblique pelican]

Ye

[livid gazelle]

I have x=b^(k-1)

So if i do (x-1)/(b-1) + x

That should give me the correct sum, right?

I'm on the train atm. Typing LaTeX on mobile is a real pain

[oblique pelican]

What's sum are you trying to get

[livid gazelle]

n

I plan to try various values of k and use newton's method to locate the root of (b^k-1)/(b-1)-n = 0 and see if it's an integer

Since n>2 there is always a solution with b=n-1

[oblique pelican]

ah I see

yeah thats right

So you want n = 1 + b + ... + b^(k-1)

for some b and k

[livid gazelle]

Well, I want the minimum b for a particular n>2

[oblique pelican]

yeah makes sense

[livid gazelle]

I can find that by fixing k and using newton's method to find a root to the above equation and either:

• find an integer b for that n and k, or
• prove thay the b lies between two integers, in which case I can try another k

The upper bound for k is ceil(log3(n)) - b=2 is trivial to check (see if n+1 is a power of 2)

[brittle tangle]

Helloo

i am struggling with these type of questions any recommendations on a yt vid that can help

[neon harbor]

hmm, none of those options are correct

[brittle tangle]

[livid gazelle]

I just realized that if you use swap b and b-1 for b+1 and b, residue classes make it obvious

b+1=1 (mod b)

1^k= 1(mod b)

1-1=0(mod b)

(b+1)^k - 1 = nb for some integer n

[oblique pelican]

Recall the implication and distributive laws

[oblique pelican]

Ah I see, that's a nice way to get there

[livid gazelle]

Unfortunately my previous plan was too slow so I need a new strategy

Are there any common rules for sums of consecutive powers of a positive integer? For an example of what I'm thinking of, example, (b^k) and (b-1) are coprime

[oblique wigeon]

just started discerete math two days ago, and today I got a sudoku puzzle as my homework 🗿

[brave rock]

Cool!

[livid gazelle]

Now calculate the number of boards that are isomorphic to yours up to relabeling, symmetry, and permutation of stacks and bands and columns/rows within stacks/bands

[merry storm]

now prove np-completeness

[oblique wigeon]

👺

[sharp crypt]

just reduce it to hamiltonian cycle problem, duh

[plush lotus]

why am I getting this incorrect?

can someone help?

[sharp crypt]

binary number 11010 is just $1 * 2^{4} + 1 * 2^{3} + 0 * 2^{2} + 1 * 2^{1} + 0 * 2^{0}$

[vital dew]

Mike

[sharp crypt]

not sure which one is wrong but im too lazy to calculate all of them /retype them to calculator

@plush lotus

[fossil mural]

111111110 is not 254

although i can see how you got confused given that 11111110 is 254

[plush lotus]

alright no worries thanks

[sharp crypt]

yeah its gonna be 254 + 256

[plush lotus]

ya it worked

[merry storm]

when u prove hardness u need to reduce something hard to ur problem

[sharp crypt]

oh sorry, wrong way then

[plush lotus]

can someone help me for the last one?

[viscid hollow]

I do not know what else is next for this 5 step proof

[viscid hollow]

these are all the options^

nevermind i got it

[wary falcon]

are real numbers a subset of complex numbers or do complex numbers have to have non zero real and imaginary part

[cerulean wind]

the real numbers can be thought of as the subset of the complex numbers with imaginary part equal to zero

complex numbers do not have to be of the form a + bi with a != 0 and b != 0

a and b can be any real numbers, including 0

[wary falcon]

ok

[merry storm]

its not really a subset

u rather can build a bijection from x (in R) to x+i*0

[stray reef]

they are a subset yes

in all ways that matter

[merry storm]

actually yes it doesent matter

but formally its not

[stray reef]

honestly there is very little point to trying to distinguish real numbers from complex numbers with zero imag part

[cerulean wind]

i intentionally did not bring this up because i didn’t want to overcomplicate things. it was a simple question lol

[stray reef]

otherwise you are forced to treat 3 the natural, +3 the integer, +3/1 the rational, +3.000... the real number & +3.000+0.000...i as 5 distinct objects that shouldn't be identified

which frankly would be dumb

[merry storm]

idk at least its important to know that C is euclidian space and how it differs from R^2 for example

[cerulean wind]

they are topologically the same

[stray reef]

as a space sure but dropping that to the level of individual points is just needlessly pedantic

[merry storm]

yes.

[cerulean wind]

wot

wot juss happened

[merry storm]

?

[cerulean wind]

why did i of all ppl just get sullied lmao

[merry storm]

??

chill

[cerulean wind]

i’m chill 😭
what made you think that i’m not?

[merry storm]

ok maybe i didnt get it

[final cliff]

With the R subset of C thing earlier, you can very easily build R' via dedekind cuts (or whatever construction you prefer), then C from R' and then just define R as the embedding of R' in C rather than as R' itself. There's no actual issue with calling R a literal subset of C because of this. Typically when an algebraist (or some other mathematician says) "we identify X with Y", they mean something along these lines to begin with.

[simple pagoda]

In mathematics is there any odd perfect numbers

[brave rock]

We do not know

Nobody knows

This is a famously unresolved question

[twilit pendant]

hi guys

(¬p ∨ q) ∨ (¬q ∨ p) = ¬p ∨ q ∨ ¬q ∨ p

can i say this ?

[twilit pendant]

?

[lethal linden]

You just did! Equality brings up a bunch of metaphysical issues, though. Better to use ⇔

[vestal bronze]

it's tru

[young crest]

disjunction is associative so you can add or remove brackets and it's the same value

[valid thicket]

explain

[bleak spade]

this is the worst type of maths

fr

even worse than conic

[quick folio]

@umbral cape
common notation is to draw a line above the repating part

of two dots between the two

[umbral cape]

right yeah

[vital dew]

HChan

[umbral cape]

like i know this part, but how would i type it out like in a text box like how multipication is '*' or addition is '+' how would i type a recurring decimal? would it be like 0.'3' or like 0.--333-- or like what

[quick folio]

well, what are you typing in would be my question

[umbral cape]

google

[quick folio]

google doesn't accept latex, so just type it in as a fraction

[umbral cape]

i was gonna search "is 0.7 recurring = 2*0.35recurring"

and i didnt know how to write it

[quick folio]

answer is no

a quick trick you can use

is that if the recurring happens immediately after 0, then its fraction is just the recurring part over a bunch of 9's

[umbral cape]

but:

[quick folio]

so 0.77777 = 7/9, 0.35353535... = 35/99

[quick folio]

I don't know what you're trying to get at with that

[umbral cape]

im not sure either my brain is so fried

like

isnt half of 0.3recurring = 0.1515151515151515...

because then like

[quick folio]

no

you cannot do that

one is 3/9

and the other is 15/99

[fossil mural]

if you take 0.151515151515... and double it then you get 0.3030303030303030...

[quick folio]

check that they are not the same

0.33 /2 alone is not equal to 0.1515

[fossil mural]

half of 0.3333333333333... is 0.166666666666666666...

[umbral cape]

right

but

how

am i too stupid for math

[quick folio]

no, just try avoid doing arithmetic with infinite decimals

you need to be really careful with them

just convert into fractions and worth with those

[fossil mural]

...what? it's not actually that hard

you can just do normal long division, the same way you would for a terminating decimal expansion

[umbral cape]

im getting so distracted i have 6 hours to do like 6 subjects of work and im spending it running down a rabbit hole of fractions of recurring decimals

[fossil mural]

the difference is just that it will never finish, but eventually you can tell that you're in the same situation you were at some earlier point

[umbral cape]

i never understood long division

i hate division

wait i just learned long division

thanks guys

still dont know what the fuck discrete math is but i dont have the time or energy to figure it out

how is math discrete

its everywhere

[bleak spade]

please stay away from discrete maths

its my advice

[quick folio]

lmao, I can tell you about it later, it's very cool despite what the other guy's saying

[bleak spade]

whattt?

no way

@quick folio can you pweese explain to me also? I suck at discrete mathematics

[quick folio]

what discrete maths have you seen so far

[bleak spade]

sets

venn diagram

thats it

[quick folio]

yeah that's not exactly discrete maths

[bleak spade]

whats that?

tbh

i hate it because there are 1000 different set combinations with the most absurd names in this universe

[stray reef]

discrete math includes basic set theory stuff

[stray reef]

what "set combinations"?

what thousands of set combinations are you seeing

[quick folio]

it does, I meant it in the sense that it's not representative at all

I never set it's not discrete maths

[umbral cape]

now im curious

[haughty garden]

discrete is really broad and covers a lot of different topics which extend to larger topics that you might see later on

[bleak spade]

Proposition
Predicate
Contrapositive
Converse
Inverse
Tautology
Contradiction
Contingency
Biconditional
Negation
Conjunction
Disjunction
Exclusive
Implication

LIKE WHAT THE F?

[stray reef]

these are

... not... "set combinations"...

[bleak spade]

okk i knwo. true false stuff

[stray reef]

these are names for logical objects and relations

[bleak spade]

okayy? its still hard

[stray reef]

they're vocabulary that you have to learn and know

no way around it

[bleak spade]

exactly

thats why it is harder than calculus

[bleak spade]

have you memorized all these terms?

[stray reef]

well i guess i have

except for "contingency" idk what that refers to

[bleak spade]

continegency is um.... difficult to explain

its.. neither true nor false everytime

[stray reef]

so it is just something that is neither always true nor always false?

never heard of a separate word for that

[bleak spade]

ohh yeah, you just worded it better

may i ask something?

@stray reef

[stray reef]

uh i guess don't ask to ask?

what was it

[bleak spade]

so what are you good at?

like what type of math have you mastered?

[stray reef]

that... is vague as hell and i dont know how to answer you

like im good at most math up to and including highschool and ive completed a bachelors degree in applied math

and im good at basic uni-level analysis and measure/probability theory

[bleak spade]

sorry

that was a dumb question

[stray reef]

im better at stuff leaning the way of abstract algebra and the like

[quick folio]

actually, how much algebra does an applied math major see? im curious

[stray reef]

i am NOT going to extrapolate from a sample size of 1 i am sorry

[quick folio]

I would expect applied math to lean much more heavily on analysis, unless you're doing combinatorics or the like

then just speak on your own experience

[haughty garden]

there’s a decent amount of orbit and stabilisers stuff in dynamical systems

[stray reef]

well my own experience is that i changed tack rather drastically from bachelors into masters

i did do some analysis-flavored stuff in years 3 and 4 because i was working on an optimization problem of a certain kind

a continuous one

right now however im working on finite projective geometries

[bleak spade]

wow

[haughty garden]

my friend has to learn a bunch of group theory to understand some of the chaos theory stuff in her thesis

[bleak spade]

suddenly, i feel like dying

[stray reef]

why?

[quick folio]

ahhh, that's a cool connection

[stray reef]

yeah i know my way around that too somewhat

[bleak spade]

yeah

i dont understand anything

i

im sorry

[stray reef]

no like

why does that make you feel like dying

and is that literal or just a figure of speech?

[bleak spade]

i think it is very much literal

[stray reef]

uh then you should call up a crisis hotline

[bleak spade]

haha ye

[stray reef]

as much as im sorry youre feeling suicidal this server is not exactly the place to deal with that sort of distress

[lethal linden]

lol

💀

[wind robin]

getting ass kicked by this and seing it in "early University" not advanced math is humbling

[agile magnet]

Plenty of people who are taking classes listed under advanced mathematics had their ass kicked by their first intro to proofs course

Source: am in grad school now, had my ass handed to me when taking my first proof based course

[ruby valley]

Is graph theory questions allowed here?

[agile magnet]

Ya

[ruby valley]

Thank you

There are n participants in a meeting. Among any group of 4 participants, there is one who knows the other three members of the group. Prove that there is one participant who knows all other participants.

Is there a way to do this via graph theory? I think I can sort of managed to do it via induction

[haughty garden]

There is kind of a way to do it with graph theory but you don’t really use any standard graph theory tools

First, consider an arbitrary participant A. Try showing that A does not know at most 2 people; what happens if A does not know 3 people?

Then you can do a case analysis on the number of people that A does not know and show that in each case, there exist some person who knows everyone.

[shell jewel]

Let S be a finite set, p a prime, and f a function from S to S such that f^p(x) = x for all x.

Then, |S| = |F| (mod p), where F is the set of fixed points of f

Hints for proving this?

[quick folio]

if we look at one specific s inside S, think about all the possibe elements of S that you can reach via f

(I'm assuming you don't know what group actions are)

[shell jewel]

I can reach at most (p-1) other elements before cycling back to s

[quick folio]

you can do better, it's not just "at most"

there are two cases: either s is already a fixed point, or it is not

what happens in both cases

[shell jewel]

Well if s is already in F the orbit is trivial and I don't move. If s is not in F, I could have an orbit with p elements at most, but can't it happen that I hit some element in F at a step k with k < p ?

[quick folio]

yeah, why can't that happen?

hint: ||this is only true because p is a prime||

[shell jewel]

Oh I think I see what's happening

Struggling to formalize it but I get it

If there's an s such that f^k (s) = s with k < p, but also f^p (s) = s must hold, then it must mean that k divides p?

[quick folio]

not necessarily

but close

[shell jewel]

Is it an off-by-one kind of error?

[quick folio]

so, given any s, there must exist a smallest (positive) number m such that f^m(s) = s

what's the relationship between m and k, m and p

[shell jewel]

f^k (s) = s = f^p (s)

We can assume k, if it exists and is less than p, is that smallest m

[quick folio]

sure, but can you tell me what that relationship is

[shell jewel]

Between s and k?

Nothing apart from f^k (s) = s

s is some abstract element of a generic set and k is some positive integer

They have no relationship beside the fact that f^k (s) = s

?

s is not even a number

How can it be a divisor

[quick folio]

oh, typo

[quick folio]

here

[shell jewel]

Ok sure yeah there must exist some n such that k = nm

[quick folio]

why? and what about p?

[shell jewel]

Because if I get back to s in a minimum of m steps, then the next time I can get again to s must be in a multiple of m

Can't get there "in between"

[quick folio]

that's not a formal argument

[shell jewel]

Otherwise m wouldn't be the true smallest

[shell jewel]

Suppose k = nm + r for some n and r < m. Then, s = f^k(s) = f^r((f^(nm)(s)) = f^r(s)

But that can only hold if r = 0 otherwise m would not the the true smallest m

[quick folio]

ok good, so what now

[shell jewel]

I feel like I'm going to say the exact same thing I said before that you objected to

That the only way f^p(s) = s can hold now is if p is one of such k

So that p = mn and it would make it not prime

[quick folio]

ok sure, so what?

[shell jewel]

I think the difference from what I said before is that it's not that k necessarily divides p, it's that k and p share a common factor that is not 1

So that's the "not necessarily" part from before

[quick folio]

yep yep

[shell jewel]

Although I have to say that when I said that I was implicitly thinking of k as the smallest one

In my mental pic

[quick folio]

well not exactly, we know that that common factor has to exactly be 1 because p is a prime

but we also know that that common factor has to be a multiple of the "smallest one"

so what is that smallest one

[shell jewel]

p

[quick folio]

... it's 1

[shell jewel]

m = p

[quick folio]

or that, but we're assuming that k is strictly smaller than p remember

[shell jewel]

I thought we split the problem is "s is in F" and "s is not in F"

We are now in "s is not in F"

k = 1 would put us back in the other camp

[quick folio]

yes, exactly!

so, what do we conclude

if s is not in F, how many elements are in its orbit exactly

[shell jewel]

p

[quick folio]

see if you can figure out the rest of the problem from here

you're really close

[shell jewel]

So elements of S can be grouped in the ones belonging in F, and all the other ones forming p-cycles under f

Now all these cycles, or orbits, of lenght p must be disjoint

[quick folio]

that's also another good observation that I didn't notice (why is that true?)

once again, the lyncpin to this entire argument is the fact that there is no smaller number that divides a prime other than 1

[shell jewel]

Well I think that if there's an element that belongs to two different orbits then by applying f to it

I wouldn't know where to send it

So it must always send it to the same element therefore they're actually the same orbit?

[quick folio]

here's a concrete counterexample: let f(x) = x^2 on the complex numbers

then the orbit of i is {i, -1 , 1} but the orbit of -1 is {-1, 1}

so there are distinct orbits that are not disjoint

here's a pretty big hint: ||if two cycles are distinct but not disjoint, then one must be contained within the other||

[shell jewel]

Gotta go catch you tomorrow, thank you for your time and your help

I'll think about ti tomorrow and let you know

[quick folio]

ping me / dm if you need more help

[shell jewel]

But I think that the main result now is easy becasue basically |S| = |F| + pN where N is the number of p orbits (some finite number)

So |S| = |F| mod p

I'll think about the disjoint claim

Thanks again by catch you tomorrow

[idle badge]

Hi

I really need some math help

I’m new to discord

[quick folio]

just ask your question

[idle badge]

I’m having trouble with my homework, my professor has a 3 try policy and I’m on my last attempt of questions

It’s really confusing to me because missed a few classes

[quick folio]

do you know how or, and and not gates work? it's just plug and check in that question

[idle badge]

I don’t really understand

[quick folio]

which part

[idle badge]

How it’s 1, I asked her for help and she said it’s 1

Could you explain how to understand the picture in a few sentences

[quick folio]

a,b, or c

[idle badge]

A

[quick folio]

a is 1? that doesn't look right

[idle badge]

It’s not

?

Oh

Oh it’s 0

Is b 1

Because it is true and false so that would be false

[stray reef]

when in doubt, write down what signal goes down each and every individual wire

[ruby valley]

Ohh like case 1 and 2? I think I get what you are saying. Thank you👍

For part a, I drew this graph and had all the degree vertex = 3.

Is that correct?

For part b, should I use Cayley tree theorem or Kirchhoff theorem?

Both theorem finds spanning trees

Using Cayley gives 16 spanning trees? Idk if that’s correct

[weary tiger]

hello can someone help me out with this combinatorial probability problme

[lethal linden]

What have you tried?

[weary tiger]

stars and bars

idk if the people are indistinguishable or distinguishable

i emailed my prof

for the event space

sample space is easy

bro idk

or is it inclusion exclusion

idk when to use inclusion exclusion to be honest

is it when you’re trying to take the complement of the event not happening of

[astral wing]

I guess that you can solve this problem with inclusion-exclusion

[lethal linden]

Any time you've given a condition where you have "probability of nothing having property Q", look at

1 - P(at least one thing with property Q)

So, here it'd be

1 - P(at least 1 empty train car)

then inclusion-exclusion becomes more directly applicable.

[weary tiger]

my prof said theyre distinguisable he said i have to use the inclusion exclusion

okayyyyy

Show that q → p and ¬ q ˅ p are logically equivalent by using a truth table.

How do I do this without the truth table

[weary tiger]

that's where im having trouble because i thought i could use stars and bars to distribute the people between the cars so that at least one person is in a car

in each car

[lethal linden]

To prove something like that you must have been given some definition for q → p. What is that definition?

[lethal linden]

Well, now you know! I agree these word problems can be annoying in that way because the thought that "person" means "distinguishable" in this context is something you have to pick up.

That said, you can and should be able to answer it in both cases, so rather than sitting around wondering which one it is, do both and answer "If they're indistinguishable then.... Otherwise, if they're distinguishable then...."

[lethal linden]

But if we're talking people boarding a train then the picture is that each person picks their own car at random, so me picking Car 1 and you picking Car 3 is simply a different situation than me picking Car 3 and you picking Car 1.

It can sometimes help to abstract things away. Another way to phrase this question is:

Let A and B be sets with |A| = 10 and |B| = 5. If we pick a function f: A → B at random, what's the probability it's surjective?

i.e., what's the ratio of surjective functions f: A → B to all functions f: A → B?

[weary tiger]

i see

we have to take the intersection of A and B right

to find the probability of having and empty car

something like this to find the event that there is at least one empty car?

and the sample space is 5^10

[weary tiger]

tbh im a bit confused on how to do the calculations for the inclusion exclusion principle

[graceful shell]

I died from cringe

It was the first day and i already hate discrete math xd

[lethal linden]

Yep

So there's 5^10 minus that expression many assignments with at least one empty car

all over all possible assignments is the probability

If you're curious this is called the Stirling number of the second kind: https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

[graceful shell]

Can you tell me how not to get bored from listening discrete math?

[quick folio]

it gets better

[graceful shell]

How-

Btw if i have any problem then i can ask here right? :p

[quick folio]

yeah of course

[ruby valley]

Anyone please? 🙏🏼

[haughty garden]

you can use the contraction-deletion method; if ST(G) denotes the number of spanning trees of G, then ST(G) = ST(G - e) + ST(G \ e), where G - e denotes the graph generated by deleting the edge e and G \ e denotes the graph generated by contracting the edge e. To see why this is true, note that the first quantity counts the number of spanning trees that does not include e and the second quantity counts the number of spanning trees that includes e

oh actually, a simple graph on 4 vertices and 6 edges is a complete graph (since C(4, 2) = 6), so the number of spanning trees is simply n^(n - 2) according to cayley's formula where n is the number of vertices

[ruby valley]

So does that mean that there are 4^2=16 spanning trees?

[haughty garden]

yes

[ruby valley]

And is the graph I drew in part (a) valid?

[haughty garden]

you only have 5 edges

[ruby valley]

Oh so I can just add one more edge at the diagonal?

[haughty garden]

that's the only edge you can add

[ruby valley]

And make it so that all vertices have a degree 3?

[haughty garden]

there's only one possible graph you can make

and that's the complete graph on 4 vertices

[ruby valley]

Which is the square with an x in the middle right?

[haughty garden]

yea

[ruby valley]

I’m abit lost on the difference between Cayley formula and Kirchhoff formula

Can’t I always use Cayley? It’s a lot easier

[haughty garden]

cayley's formula is the number of spanning trees on a complete graph

kirchhoff's theorem is a generalisation

[ruby valley]

What does that mean? Both counts the number of spanning trees..

[ruby valley]

And how do I know it’s a complete graph?

[haughty garden]

cayley's formula can only be used when the graph is complete, whereas kirchhoff's theorem allows you to count the number of spanning trees on graphs that are not necessarily complete

[haughty garden]

a (simple) graph is complete if every pair of vertices in your graph has an edge

this means that there are C(n, 2) = n(n - 1)/2 edges on a complete graph

[ruby valley]

Ohhh let me write that down

I didn’t know that

Thank you!!

[haughty garden]

nws

[ruby valley]

I tried googling the contraction deletion formula and it’s showing me some chromatic polynomial

May I know why you suggested the contraction deletion formula over the Kirchhoff formula?

[haughty garden]

chromatic polynomials are examples of functions that satisfy the contraction deletion formula, but this is a bit of an overkill if you're dealing with relatively easy graphs

https://en.wikipedia.org/wiki/Deletion–contraction_formula

[haughty garden]

no reason, these are just different methods to solving the same problem

[ruby valley]

Ohhh is it applicable for an intro to graph theory course?

[haughty garden]

some might be easier than others depending on the nature of the graph

[ruby valley]

I was also ask to draw each spanning trees. Is there a way to immediately see what the spanning trees are?

[haughty garden]

i would check with your professor, you'd probably just want to use the techniques and tools that you've been taught in class

you just draw them one by one

a spanning tree is a tree that connects all of the vertices

so in your example, every spanning tree will have 3 edges

[ruby valley]

Clear! Let me draw each of the 16 spanning trees!

Many thanks🙏🏼😊

[haughty garden]

nws

[ruby valley]

I’m not sure about this question. I’m thinking can’t we just divide the 25 people into two groups consisting 13 and 12, and claim that their friends are on opposite sides. Thus they have at least half of their friends in each group?

[stray reef]

bruh the black space around this image was literally 12 times taller than the image itself 😭

[stray reef]

what are you trying to say with "claim that their friends are on opposite sides" tho?

[ruby valley]

Like can’t I claim that 13 people are in group A and 12 people are in group B and that the 13 people are friends with only the 12 people in group B. Thus this satisfies their condition of each person having at least half of their friends in a different group.

[stray reef]

you have no control over who is friends with whom

[ruby valley]

Sorry!! Idk how to make it bigger. Let me try

[stray reef]

i already processed the image for you, no need.

[ruby valley]

Thanks!! 🙏🏼

How do I proceed with this? I don’t see how this is testing graph theory

[stray reef]

you start with essentially an arbitrary graph on 25 nodes

the nodes are people and the edges are friendships

[ruby valley]

Is that an assumption based on the question? Or just how things work?

[stray reef]

it is how things work

you cannot dictate to the group of 25 who of them should or shouldn't be friends with whom

[ruby valley]

Ohhh.. ok clear! So I draw a graph with 25 vertices and how would I connect them?

[stray reef]

your goal here is to show the nodes of the graph can be colored red and blue in such a way that for each node, at least half of its neighbors have the opposite color to the node itself

[stray reef]

you do not draw one as such

[ruby valley]

Bipartite?

[ruby valley]

Let me try this. So basically I have to explain it?

Hmm..but it’s 25 so it’s not even…

[stray reef]

no, you are considering essentially all possible friendship graphs

for bipartite ones the problem is trivial

otherwise it is not so

[ruby valley]

Ohhh..I never heard of friendship graph yet

Hmmm ok let me give it a try

[stray reef]

that is not a formal math term

it is just convenient to call the graph that models your situation by this name

the one where the nodes are people and the edges are friendships

[ruby valley]

Hmmm so this wouldn’t work?

https://upload.wikimedia.org/wikipedia/commons/9/92/Friendship_graph_8.svg

[stray reef]

oh that looks like a different thing entirely

[ruby valley]

I was thinking maybe the Center is number 25

[stray reef]

it's irrelevant to your problem...

[ruby valley]

Ok ok sorry I misunderstood

[stray reef]

no you are just thinking in all the wrong directions at the moment

but actually i am not sure how best to proceed here myself

[ruby valley]

Yes I’m confuse as well..it seems to be easy if we could dictate the friendship but if we can’t…isn’t there too many possibilities to consider

[stray reef]

how much probability and statistics do you know

[ruby valley]

Hmm..only an introduction to it.

[stray reef]

there might actually be a really clever trick for this

do you know expected value

[ruby valley]

This question is part of the intro to graph theory class I’m taking

Hmm I think so

[stray reef]

ok so

this is going to sound crazy

[ruby valley]

I’m wondering if they are testing a graph theory concept that I never heard of

[stray reef]

but imagine splitting the people into groups completely at random

ie like

[ruby valley]

Let’s hear it!!

[stray reef]

ok it'll be convenient to label the groups with +1 and -1

assign to each person i (i=1, 2, ..., 25) a random variable C_i which takes values +1 and -1 with 50% probability each

then for each person $i$ define their ``score'' as $S_i := \sum_{(i,j)\in E} C_iC_j$

[vital dew]

ann.in.a.teacup

[stray reef]

wait... hold on i don't think this will work actually my bad

i was now gonna say S_i <= 0 if the "at least half of friends are in the opposite group" condition is satisfied for person i

[ruby valley]

No problem! I thought it was an innovative way to think about this

[stray reef]

but then we don't have any way to track the condition being true for everyone

adding all the S_i doesn't work...

[ruby valley]

Hmmmmmmm

[stray reef]

blech

[ruby valley]

I’m thinking about the colouring thing you said

[stray reef]

i know a similar technique worked for a similar graph coloring problem

but the problem was different and it looks like the technique doesn't carry over as i thought it would

so i didn't cook this time unfortunately

[ruby valley]

Alls good 👍

Do colouring of graph require Ramsay theorem?

I don’t think I learn that in my course…hmmm

[stray reef]

idk about ramsey here

[ruby valley]

Hmmmm..I only need to show it is possible so I only need to show one case

If I drew a 25 vertices graph with 13 on the right and 12 on the left, and connect the edge accordingly

It might work?

Idk if it’s reasonable to do that

[fossil mural]

well that gets you a graph, but it might not be a graph that has anything to do with which of these 25 people are friends with which other people

[ruby valley]

And colour the 13 in red and 12 in blue and claim that’s their friend pairing?

[fossil mural]

but what if it isn't

[ruby valley]

Do we have to consider that possibility?

[fossil mural]

yes

[ruby valley]

I only have to show that it’s possible?

😞

[fossil mural]

which means you don't have to consider every way of splitting the people into 2 groups, you only have to consider one way of splitting it

[ruby valley]

How do we show friendship without dictating it?

[fossil mural]

you don't "show friendship"

you're given a set of friendships

the thing you have to construct is how you split the people into 2 groups

[ruby valley]

But the question doesn’t say the configuration of the friendship of the 25 people.

[fossil mural]

well ok sure, you personally aren't

but you're "given" it in the sense that it's an input to your argument

[ruby valley]

Wouldn’t this just means putting 13 people into a group and 12 in another?

[fossil mural]

so if tomorrow you go to a party and there are 25 people there

the argument that you construct now must be able to apply to whatever friendships those 25 people have

[ruby valley]

A general solution?

[fossil mural]

yes

[ruby valley]

How can I even do that…

Is there a graph theory concept being tested here?

And what isit?

[fossil mural]

no

this isn't "a graph theory question" or something

it's just, a question

the thing being tested here is your ability at problem-solving

it just happens that a good way to phrase the problem is that it's about a graph

[ruby valley]

Hmmm…so I need to slot the friendships of the 25 people in a way that it works for every case..

[fossil mural]

...no

[ruby valley]

I can’t do it via pairings?

[fossil mural]

you don't construct the friendships

you construct a split of the group of people into 2 groups

[ruby valley]

Ok…so why can’t it just simply be 12 and 13?

That I don’t get…

[fossil mural]

because that might not work

[haughty garden]

ooo this is a pretty fun problem

i think i have an idea

[fossil mural]

if there's one person who's friends with everyone else and nobody else is friends with anyone except that person, then whichever group that person ends up in, everyone else in that group has none of their friends in the other group to them, which isn't at least half

[ruby valley]

So I have to come up with a sorting system?

With the condition being based on the number of friends they have? Then sort them respectively into groups A or B?

[ruby valley]

Yes?🙏🏼

[fossil mural]

well it can't just be based on the number of friends that they have, because it's possible that each of them has exactly two friends, but this is at least closer than everything else you've said

more precisely, what you have to come up with is, given a set of friendships between the 25 people, a way to split them into two groups so that for each person, at least half of their friends are in the other group

[ruby valley]

Hmmm…gosh this is hard

Adjacent?

Split based on their adjacent to the rest of the vertices?

[haughty garden]

if you look at an arbitrary partition, then either this is a correct partition or it's not

if it's a correct partition, then we're done

if it's not a correct partition, then there exist some person who has more than half of their friends in the same part of the partition

what happens if you move them to the other side of the partition

[ruby valley]

It should balance?

[haughty garden]

uh

well

[ruby valley]

In that it should fulfil the condition of” some person who has more than half of their friends”,

[haughty garden]

the issue might be that moving this person to the other side might cause other people to fail the condition

[ruby valley]

So what you are saying is that it’s not possible?

[haughty garden]

no

[ruby valley]

For a general solution?

Ohhhh

Idk why he asked this in a graph theory class😱

[haughty garden]

if you do this process over and over again until you can't make any more moves, this should give you the partition you're looking for

but you need to argue why this is the case

[ruby valley]

Hmmmm..what if he argued back of a special case that someone is not friends with anyone?

Wouldn’t this process be halted?

[haughty garden]

if someone is not friends with anyone, then by default, at least half of their friends are in the other group

[ruby valley]

Hmmmm..not sure why that’s the default

[haughty garden]

0/2 = 0

[ruby valley]

Hmmm…there’s a good arguement

Hmmm..so I just gotta explain the partition of a set process?

I was wondering if there might have been a graph theory solution

[haughty garden]

it would probably help if you think about it for a bit

and maybe try to convince yourself

time for me to go back to cleaning my apartment

goodbye

[ruby valley]

Thanks 🙏🏼

[ruby valley]

Thank you too!!🙏🏼

[ruby valley]

Thank you too!! 🙏🏼

[ruby valley]

So there’s a way to solve this via using a graph?

[merry storm]

weve solved something like this (probably)

one sec

upd: sorry it was another problem

[merry storm]

btw empty graph migt work

[merry storm]

and also vertex adjacent to all the others and no other edges

[lost apex]

What are some good resources for learning discrete mathematics?

[oblique pelican]

Discrete Mathematics and Its Applications by Kenneth Rosen is a pretty popular textbook

Also How To Prove It by Vellerman for logic/set theory/proof techniques

[cursive dew]

Help im so lost.
I have no idea how to tell which ones we star.
"Star premise letters that are distributed and conclusion**(?)** letters that arnt distributed
I dont have a clue what conclusion means, but anything distributed they underlined in the example. And they star the last b cause its not distributed. But...um...SO WASNT THE FIRST IN LINE 2?! XD
I get the distributed idea, but no this star thing.

i fail to see any difference with why the first b isnt stared while the second is just for the cause of "Its not distributed" which is the same for both.

[lethal linden]

You've gotta explain the syntax.

[cursive dew]

not sure what you mean

[lethal linden]

Whatever it is, it's not conventional.

The asterisk, the underline, what do the uppercase letters represent, etc

[cursive dew]

im not sure, im just hoping to have learned form the video. But maybe the video oversimplified.

[lethal linden]

Ah yes, the video.

[cursive dew]

the example is near the end https://www.youtube.com/watch?v=cJiLQnMXtxs

I understood most of it untill this weird valid check thing

[lethal linden]

That video is...I don't know.

Would not recommend, let's just put it that way after scanning it.

I've never seen this starring process to check for logical validity.

I'd have to think carefully about what it actually corresponds to.

[cursive dew]

yeah checking online, the most i find is some stackoverflow question, and nothing else

no other examples which makes it harder

ig it isnt important?

[lethal linden]

You picked a video that's using some idiosyncratic way of talking about logic. Look at something more standard. The Wikipedia page is better.

[cursive dew]

We shouldnt need some formulated check to see if something is valid or not right?

[lethal linden]

It's...uhh

You have to get specific about what counts as a logical formula

They're playing fast and loose, here.

[cursive dew]

Im just following the forallx book so far. they brought up asistotle out of no where which seems...complex

[lethal linden]

🤷‍♂️

The screenshot you posted is gobbledegook. Seems like it's some special notation use in the book the video referenced, which presumably isn't even the book you're using.

Find something that talks shiny the subject as your book does.

[lost apex]

Thank you 🙏🏻🙏🏻

[muted basin]

I'm confused on how to find a counter example when we aren't given any circumstances for what Q(x,y) is

Also, the flaw is hard to pinpoint for me. I'm inclined to say it's on line 3, where EI is used since it typically should be done before UI but there's x and y

so it should theoretically be fine

here are the rules in use for reference (also modus ponens, modus tollens, conjuction, simplification, addition and the other basic equivalence rules but none are used here)

But if UI is used on line 2, shouldn't y become a free variable, say 'b' ?

and EI would make 'a' giving Q(a,b) ?

I know a free variable is something that is outside of the scope of a quantifier

[cerulean wind]

not sure what interpretation means, but i think the flaw counter example has to do with the fact that there may not be any y’s?

most likely im wrong

[muted basin]

It's asking for a counter example I believe

I guess y could stay as the variable since it's free now but idk if it's incorrect or just improper to leave it as y instead of a new variable

[cerulean wind]

right, i think you pick the language to be empty

[muted basin]

also I have no fuckin clue what the rule for EG is. For somereason the pdf version is cut, but on the paper our prof gave it's: to go from P(a) to (Ex)(P(x), x must not appear in P(a) replaced with y, and y cannot have previously appeared anywhere within P

It seems like literally every step in this proof is wrong

[cerulean wind]

the flaw is from line 2 to 3.

Q(a,y) to for all y, Q(a,y). this is because Q(a,y) was deduced from a hypothesis in which y is a free variable

[muted basin]

UG doesn't work because on line 3, y is a free variable and the rule states that P(x) cannot be deduced by EI where x is a free variable, in this case y

in that case though is the wff just false overall?

cause I don't see any other way to create the other side of the wff

Discrete math is going to be the end of me

my textbook is full of chickenshit

[muted basin]

Besides my confusion with the rules, how does one find an interpretation for this thats false?

[lethal linden]

Interpret the symbols as something from everyday life and think of what a counterexample would look like. Translate that into a formal counter-model.

For example, let x,y be people and let Q(x,y) mean x loves y.

Then ∀y ∃x Q(x,y) means...what? And ∃x∀y Q(x,y) means...what?

[muted basin]

for every person, there exists somebody that loves them
there exists a person that loves everybody

[muted basin]

now stuck on this

this isn't possible using anything I have rule wise

I can use EI to get rid of quantifier

from there, nothing can be done i dont believe

I could do double negation and then demorgans law but that doesn't really do anything for me. I wouldnt be able to remove anything from the demorgans law application because there would be a lingering "not" that prevents me from applying simplification

[lethal linden]

What do your rules for quantifiers look like?

[muted basin]

Oh woops I sent same image twice

one sec

EI is valid since both are in the scope and 'a' doesn't exist yet

but after that none of these rules can handle the 'or'

[lethal linden]

Hmm. I agree. You normally have a disjunction elimination rule which looks like this:

Now...it's possbile there's some way to extract that rule (or equivalent) from what you've been given, I'm not sure.

But...unless you've been given some rule with disjunction as an antecedent or a relevant meta-logical principle not stated here, I'm not sure what to do.

Saying you can replace a sub-formula with something equivalent, assuming the free variable situation is fine, feels like begging the question, here.

[muted basin]

I know there’s technically a proof for disjunction or disjunction syllogism but there other half of the pre-reqs to derive that aren’t there

[lethal linden]

Like...I suppose you could say ∃x(Rx ∨ Sx) entails Ra ∨ Sa, which entails (∃x Rx) ∨ Sa

[muted basin]

we don’t have a not-P and if we made one with double negation or demorgans it doesn’t really work since we take the Q (in this case S) with us

[fossil mural]

using these equivalences we can get $P \lor R$ to $\neg (\neg P \land \neg R)$

[lethal linden]

Oh..

[vital dew]

bee [it/its]

[lethal linden]

I forgot to look over the first image, woops.

[muted basin]

right, but thats where im stuck is on this step

the not symbol in front of the parantheses prevents me from using any rules on the stuff inside

[fossil mural]

at that point i would be kind of stuck but i think we have implication introduction here, because otherwise we wouldn't even be able to get to the point of applying EI

so we take ¬Q as a hypothesis, derive ¬P and ¬R from this by modus tollens, and then use the conjunction rule to get ¬P \land ¬R as the result

meaning we have proven ¬Q -> (¬P \land ¬R)

by modus tollens again we obtain ¬¬Q, which by the equivalences is Q

[muted basin]

im so lost

[fossil mural]

that's understandable given that this is a ridiculously roundabout way to do it

[muted basin]

i understand temporary hypotheses when we have an implication on the conclusions side and discharging them

but not exactly how to apply it here

[fossil mural]

basically the idea is that we're just, proving the statement $\neg Q \to (\neg P \land \neg R)$, which is where the $\neg Q$ hypothesis came from

[muted basin]

I’d say I could look for a similar example on the textbook (odd numbers have solutions) but all of the odd problems are significantly easier

[vital dew]

bee [it/its]

[muted basin]

and none of them use “or”, they all use “and”

[fossil mural]

...i think the "intended" answer here is that they didn't think it through and/or just made a mistake, and expect you to use a rule like this that they haven't realised they forgot to actually give you

[muted basin]

I think my professor just didnt bother reading the problems himself or thinks too highly of beginners

We haven’t even mentioned disjunctions once in the class itself

[fossil mural]

first one, i think

[fossil mural]

...ok maybe both then

[fossil mural]

the thing is, if you read the setup here in detail (and already know the topic well), it doesn't just look unreasonably hard, it looks clearly set up wrong, it's only a coincidence that disjunction elimination is derivable at all, and even then my proof is a bit sketchy

[muted basin]

I will say the other option for this question was give an interpretation that’s false but I’m not sure how to identify when that’s appropriate

and the preceeding odd numbered questions are typically “similar” and 17 solves it out

so i assumed it would be something that i have to prove as well for 18

[fossil mural]

well this statement is actually provable (using a sensible proof system) so yeah there isn't going to be an interpretation where it's false

...to be honest
in terms of actually learning, these problems look fairly reasonable, but the proof system is so wacky that you might get more actually useful knowledge out if you just find a ...normal... presentation of natural deduction and try solving the problems in that instead

[muted basin]

I think we’re starting to lean into that

we just started learning about contrapositions / contradictions etc and written proofs using that

i guess the predicate stuff is a precursor but these proof sequences are awfully complicated for only using the rules we have

and especially for having no solutions present

[lethal linden]

My advice would be to telegraph your understanding as best you can.

I need a rule that lets me discharge disjunctions. If we had a rule like (descripton of the usual disjunction elimination) then we could prove this as follows: (proof assuming disjunction elimination)

It's not clear to me whether we can get such a rule from what we've been given. Some ideas I had were:

1. Using the fact that Ra∨Sa is equivalent to ¬Ra → Sa via imp and dn
2. Using the fact that Ra∨Sa is equivalent to ¬(¬Ra ∧ ¬Sa) via dm

Assuming the exercise is possible you won't get full credit, but that wasn't going to happen, regardless. But the professor/TA won't be left wondering whether you understand what you're being asked to do or whether you have a sense of how to navigate logical systems like this.

[muted basin]

nah theres no credit for it, just practice

but he put the even numbers as potential quiz/exam problems

[lethal linden]

I see. I'd still answer it like that. If you get feedback, that will help you get better feedback.

[fossil mural]

honestly i think possibly you should just like, ask how you're supposed to solve these

[lethal linden]

Unless these are just practice for yourself, no feedback.

[muted basin]

I'm guessing this problem is in the same suite of almost impossible for us

[lethal linden]

No, that one will be easier.

[fossil mural]

it's starting to feel like he doesn't know that there's something wrong here

[muted basin]

the first problem I'm recognizing is the implication

I know intuitively it should be fine to just use UI on P(x) and Q(x) but

[fossil mural]

which seems like an entirely plausible mistake tbh, if you just skim this set of rules it does all look reasonable and you have to look a bit closer to notice that some rules you'd expect to find are missing

[muted basin]

I was told we cannot do that on whole WFFs

[lethal linden]

Sure, you have to deal with the outer-most connective.

[muted basin]

I wouldn't be able to do anything with the hypothesis here though

Starting the proof sequence I have step 1: (Ax)P(x) -> (Ax)Q(x)

as the initial hypothesis

[fossil mural]

no this shouldn't be that bad actually

because it's false

so all you have to do is give an interpretation where it's false

[muted basin]

how am i supposed to differentiate when or when it isn't false though

[fossil mural]

which hopefully doesn't involve the broken proof system at all

[lethal linden]

I'd look at some worked examples because the professor has to have a way of smuggling in things like implication introduction, disjunction elimination, etc.

[muted basin]

for a false interpretation, am I able to choose a different x for P(x) and Q(x) or do I have to use the same for both

[lethal linden]

Oh, I see, they might be false and you have to supply a countermodel if so.

[muted basin]

cause these exams will be timed of course but i dont want to spend 30 mins trying to prove a wff just to find out oh it was false the whole time and i wasted my time

[lethal linden]

Again, translate the statements into everyday language and you'll see the two sides of the outermost implication are saying something pretty different.

[muted basin]

P(x) = x is even Q(x) = x is not prime
If any x is even, then any x is not prime. This implies that for any x, if it is even then it is not prime

Idk if i did this right

[lethal linden]

That's not quite everyday but...sure.

[fossil mural]

if you can't get the proof to work, for a reason that looks more like "the hypotheses just aren't strong enough" than "there isn't a rule i can use to deal with a disjunction", you should probably consider that it might be false

[muted basin]

it was just the first thing to come to mind my bad lololol

[fossil mural]

but also yeah the approach i'd take is more along the lines of "think about what it would actually mean if the statement was true"

[fossil mural]

...what does "divisible" mean here

[muted basin]

woops

i guess it would make more sense to say it is not prime

one sec

okie edited

but this is false cause 2 is prime

[fossil mural]

so yeah that works as a counterexample

well mostly

pedantically you should also specify which set you're talking about

but also it does kind of feel overly complicated

[muted basin]

yeah im not exactly sure how to do a false interpretation properly

we dont have any examples for it on our notes or lectures

[fossil mural]

(although also ``any'' is a slightly odd translation of $\forall$)

[vital dew]

bee [it/its]

[muted basin]

i just made up mine based off an odd number problem that used x is even and x is odd

[lethal linden]

Yes, "every" is usually more helpful.

[muted basin]

For every x that is even, every x is not prime.
This first line construction is what feels weird

not sure how else to word it

the conclusion makes more sense

[fossil mural]

...wow your professor is not very good at this apparently

[fossil mural]

if (for every x, x is even) then (for every x, x is not prime)

[lethal linden]

Make a model where ∀xPx is false and ∀x(Px → Qx) is false.

[fossil mural]

or phrased somewhat more naturally, "if every number is even then every number is not prime"

[lethal linden]

If ∀xPx is false then ∀xPx → ∀xQx is true.

[muted basin]

but thinking abt it the antecedent is false

which makes the WFF true

[fossil mural]

exactly

that's what we want

[muted basin]

wait huh?

but we want an interpretation where its false

[lethal linden]

I imagine a lot of these counter-models can be constructed on very small domains, like 1/2/3 elements. This allows you to rule out certain things.

Like, say that the domain is {0,1}. Well, if ∀xPx and ∀xQx are both true, i.e., if P={0,1} and Q={0,1}, then we have ∀x(Px → Qx).

So if there's a countermodel at least one of ∀xPx and ∀xQx must be false.

[fossil mural]

we want the overall statement, "if (if every number is even then every number is prime) then (every even number is not prime)", to be false

[muted basin]

if P is false then Q doesn’t matter and the overall statement is true

an implication wff is only false if the antecedent is true and the consequent is false

wait

sorry

youre tight

right

yeah the left side overall is true which leaves true -> ?

and ? is our statement If every x is even, then x is not prime ?

[fossil mural]

well it's the statement $\forall x (P(x) \to Q(x))$

[vital dew]

bee [it/its]

[fossil mural]

i honestly don't know what you mean by "if every x is even, then x is not prime"

[muted basin]

me either im struggling to construct this

[lethal linden]

You can make ∀xPx → ∀xQx true regardless of Q by making ∀xPx false. You now have free reign to make Q whatever you like, so long as ∀xPx is false.

That's a lot of wiggle room.

[muted basin]

For every x, if x is even then it is not prime

thats where im worried i chose a bad prompt lol

the antecedent WFF is true overall because I can choose x = 2 and that is even but IS prime

for the consequent how do i make P(x) true in the implication and the Q(x) false

[lethal linden]

No...

If P means "is even" and Q means "is prime" then ∀xPx → ∀xQx is true.

But ∀x(Px → Qx) is definitely not true.

Actually, no, scratch that.

Make P mean "equals 2", then ∀xPx → ∀xQx is true.

If every number equals 2 then every number is prime

[muted basin]

I guess I’m struggling to differentiate the quantifiers here

[lethal linden]

Write ∀xPx → ∀yQy instead if it helps keep your head straight.

[muted basin]

Intuitively the two sides both make up the same sentence in my head

oh so the left can use a different x for p and q?

[lethal linden]

The variables add noise. Forget about 2/even/prime. I'm not sure it will work.

"∀xPx" means "Every person here is happy"
"∀xQx" means "Every person here is tall"

For ∀xPx → ∀xQx to be true, one of two things must be the case:

1. Not everyone here is happy
2. Everyone here is happy and tall

[muted basin]

okay im with you so far

then the consequent is Every person that is happy is tall?

[lethal linden]

If everyone here is happy and tall then ∀x(Px→Qx) will also be true.

So, if there's a countermodel then we must have that not everyone is happy.

Say the domain is {a,b} and a is happy but b is not, i.e., P={a}.

Well, if P={a} then ∀xPx → ∀yQy is true.

Now can you find a Q such that ∀x(Px → Qx) is false?

There aren't many choices because there are only four possible things Q can be.

{}, {a}, {b}, or {a,b}

We need Qa to be false, which means Q must be either {} or {b}

And in fact both of those work

Another way to think of ∀x(Px → Qx) is that it's saying P must be a subset of Q.

And ∀xPx → ∀xQx is saying "If P is the whole domain then Q is the whole domain"

[muted basin]

Im not too sure of the usage of sets here

[lethal linden]

Well, that's what a countermodel is.

[muted basin]

we haven’t used anything with it yet unfortunately

[lethal linden]

What do countermodels look like, then?

Or what do interpretations look like in general?

[muted basin]

weve just had to make up arbitrary formulas for p(x) and q(x)

havent had to set a domain or values

it’s just been “we can pick any value”

let me see if i can find an example

[lethal linden]

Please

[muted basin]

cause i dont doubt you i just doubt my professor fully taught it

oh nvm lol we havent done any

this was closest thing

where f for example is false given x and y both are 3

sorry not f

I meant e

[muted basin]

I guess i'm confused on how the antecedent and consequent differ semantically

If every person is happy, then every person is tall

feels the same as: Every happy person is tall