discrete-math

[solemn mortar]

les element de 2Z\6Z et 6Z\2Z sont la solution?...

[opal crescent]

c'est un peu court là quand même

ok t'as la bonne réponse

mais ton argument il a cette tête "alors 2Z c'est 2Z, 6Z c'est 6Z, donc coup de baguette magique la réponse c'est ..."

je suis pas des masses convaincu

@solemn mortar

[solemn mortar]

c'est pouer cela je veux avoir les idee des autre pour que je peut mieux comprendre la chose et comment l'expliquer

ms maintenant j'ai les chose vagues

si tu prend des question specifique la baguette va disapretre

disparetre

@opal crescent

[opal crescent]

oui c'est bien pour ça que je t'ai sorti ces relations-là

c'est plus spécifique, plus simple

prends chacun de ces deux trucs indépendamment, qu'est-ce que ça te dit sur X ?

[solemn mortar]

que les deux solution sont un multiple de 6?

[opal crescent]

solutions de quoi

[solemn mortar]

X?

car2Z/X inclus danc 6z et le meme pour X\2Z

donc les deux sont des multiple de 6?

j'ai un petit cerveaux desoler si s'est faux T~T

[opal crescent]

ok donc les éléments de 2Z \ X et X \ 2Z sont des multiples de 6 d'accord

[solemn mortar]

oui

[opal crescent]

oui déjà on est moins sur de la baguette magique

le 2ème cas est assez intéressant à regarder

imagines tu prends un ensemble X et t'enlèves tous les multiples de 2 dedans, est-ce qu'il peut te rester des multiples de 6 ?

[solemn mortar]

6 est un multiple de 2

donc non

car chaque multiple de six et 6k = 2*3k

[opal crescent]

ok en effet

donc ça te dit que X \ 2Z inclus dans X \ 6Z (les pas multiples de 2 sont aussi pas multiples de 6)

mais en même temps on veut X \ 2Z inclus dans 6Z

X \ 6Z et 6Z ils ont aucun élément en commun donc c'est pas possible

sauf si X \ 2Z est vide

grosse info là

on sait que X \ 2Z est vide, dit autrement X contient que des multiples de 2

2Z\X U X\2Z = 6Z
donc ton équation de départ en réalité le X \ 2Z est vide

donc tu te retrouves avec 2Z \ X = 6Z

[solemn mortar]

qui ont les multiple de 6 si k = 3n ?

Donc il est vrai si le 2k|k ≠0 mod 2?

Non

[opal crescent]

mod 3

[solemn mortar]

Okey donc on a trouver cela

Et que X/2Z est vide

Qui nous done 2Z/X = 6Z

et puisque 6 est un multiple de deux si il y on a 3

On dit que X = { 2k|k ≠ 0 mod 3}

[pine bear]

Yo
Who can kindly teach me basics of discrete math?

Please

[opal crescent]

ouais

[solemn mortar]

Moins de baguette magic mais un vrai pain baguette

[opal crescent]

là tout ce qu'on a fait c'est la solution pas clean

[solemn mortar]

Tous cela n’est pas clean?!

[opal crescent]

ce que je voulais suggérer au début ça tient en 2 lignes

là on en a chié avec des tonnes de raisonnement ensembliste

[inland raft]

noone can, not through discord text, your best bet is to get a book, read it and try to do the exercises, if you can't solve then people here can help you work your way through it

[solemn mortar]

Vraimant?

[opal crescent]

oui

[pine bear]

Alright

[solemn mortar]

Pouvez vous me le dire svp

[opal crescent]

l'idée c'est de vraiment travailler comme si c'était une équation

tu pars de $2 \mathbb Z \Delta X = 6 \mathbb Z$

[vital dew]

aPlatypus

[opal crescent]

et t'appliques 2Z Delta des deux côtés en gros

[solemn mortar]

Avec cet truc? $A(\DeltaB\DeltaC) = (A/DeltaB)\DeltaC$

[opal crescent]

$2 \mathbb Z \Delta (2 \mathbb Z \Delta X) = 2 \mathbb Z \Delta 6 \mathbb Z$

[vital dew]

aPlatypus

Luci
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[opal crescent]

oui et ensuite t'utilises ça pour simplifier à gauche là

$(2 \mathbb Z \Delta 2 \mathbb Z) \Delta X = 2 \mathbb Z \Delta 6 \mathbb Z$

[vital dew]

aPlatypus

[opal crescent]

ça fait quoi 2Z Delta 2Z ?

[solemn mortar]

Z?

[opal crescent]

non

[solemn mortar]

2Z?

[opal crescent]

non plus

[solemn mortar]

Mon cerveau ve me tuer la 😭

[opal crescent]

eh reprends la définition si tu sais pas

[solemn mortar]

Okey je vais la chercher tt de suite

[opal crescent]

(2Z \ 2Z) U (2Z \ 2Z)

ça fait quoi

[solemn mortar]

Ah

…honestly je ne sais plus

A u A

Est A

[opal crescent]

non

A \ A c'est pas A de souvenir

l'ensemble vide ça existe aussi

[solemn mortar]

Il faut que je revise encore plus mes lesson

[opal crescent]

donc 2Z Delta 2Z = ensemble vide

et (vide) Delta X c'est X

la magie opère

donc au final X = 2Z Delta 6Z

finito

ce qui est exactement les multiples de 2 pas multiples de 6

[solemn mortar]

Merci beaucoup je vais essayer de la refers en plus regardant les definitions et les etape

Ms mntnt je vais avoir du cafe ma tete a fondu

[opal crescent]

pas une bonne idée le café le soir

mais bon je sais pas dans quelle timezone t'es

bon café I guess

[solemn mortar]

S’est 22 pour moi

10PM

Ms je dois travailler academic comeback

[opal crescent]

yep allez courage ^^

[solemn mortar]

15 janvier c est mes examen est j’ai Analyse algebre prog c algo et les langue que je n’ai rien fais dedant

On peut enlever prog c car je le connait un peut

En tout cas merci beaucoup <33

[versed oasis]

can i have functions in the alphabet of strings?

like f and g and some functions and i want to consider the set of all compositions of them, so i make the alphabet {f, g} and map each string in {f, g}* to a function like fgff --> f(g(f(f(x)))), but i'm not too sure if characters in a string can be functions

i considered using lists instead but it seems too computer-science-y

[sharp rose]

Aren't strings normally represented as lists/ordered sequences anyway

[versed oasis]

umm

so i can?

[weary tiger]

Can someone quickly help me understand how to solve math problems in discrete math??

[sharp rose]

I don't rlly get your question

You can have ordered sequences of functions

[versed oasis]

i mean, strings are sequences of characters, but can i make these characters whatever mathematical objects i want or can they just represent symbols?

if f and g are functions, i can have a tuple containing these functions: (f, g, f, f), but can i have a string containing these functions such as "fgff"?

or would i need to make placeholder characters to represent the functions, like "FGFF"

where F is character that represents the function f, and G is a character that represents the function g

[sharp rose]

How isn't this just this

I don't see the point in trying to collapse the semantics of functions and the letters of an alphabet into one

You can represent whatever you like in math, letters/formal languages are just a formalization of how you can display it in text form

[agile magnet]

what you've written is fine and defined but like

I guess what's the point?

what are you trying to model / do

[versed oasis]

i just need some notation to denote possible compositions, like f(f(x)), f(g(f(x))), etc., and prove things about them.

I could do this mapping like $fgf \to f(g(f(x))$ by defining $(\epsilon)^{\circ}$ as the identity function, and for all strings $S$ in ${f, g}^*$ i define $(fS)^{\circ} = f \circ S^{\circ}$ and $(gS)^{\circ} = g \circ S^{\circ}$ or something like that so I can do induction

[vital dew]

kaue

[agile magnet]

I think you can just define this recursively

Like fix $x$. Then you can define a function from ${f, g}^* \to Y$ recursively by $\varepsilon(x) = x$ and then for $w \neq \varepsilon$ so that $w = v \cdot c$ for some $c \in {f, g}$ and $v \in {f, g}^*$ define $w(x) = v(c(x))$

[vital dew]

Spamakin🎷

[novel ore]

If $\gamma \in \beta$ is it the case that $\gamma \cup {\gamma} \in \beta \cup {\beta}$

[vital dew]

okeyokay

[solemn badge]

they're gonna ask you to come with more specific questions or even practice problems on topics you{re struggling with that you wanna work through

[oblique pelican]

Let $\gamma={1}$ and $\beta={{1},2}$. Then $\gamma\in\beta$, but $\gamma\cup{\gamma}={1,{1}}\notin{{1},2,{{1},2}}=\beta\cup{\beta}$

[vital dew]

Dilly

[frosty tide]

what is a matroid ?

can anyone give me some ressources to learn more about them ?

[versed cairn]

does anyone has an idea on how approach this ?

[vestal bronze]

apparently you don't get to write i_n until there's no space

until it has to be 0

so it's some unknown amount of 0

[polar geode]

hey can someone help me with the induction step? i need to show that Fn < Fn+1 < 2Fn holds for all n ≥2.
it's the fibonacci sequence. my prof defines it a little different:
F0 = F1 = 1 and Fn+2 = Fn+1 + Fn
i did the base case and it holds for n = 2 . how do i proceed with the induction statement Fn+1 < Fn+2 < 2Fn+1 ?

i thought about splitting it into Fn+1 < Fn+2 and Fn+2 < 2Fn+1

but i don't know how to proceed from there

[haughty garden]

For n >= 2, you have that F(n + 1) = F(n) + F(n - 1) >= F(n) + F(1) > F(n). For the other inequality, you just apply the previous result. For n >= 2, you have that F(n) = F(n - 1) + F(n - 2) > F(n - 1). So you have that F(n + 1) = F(n) + F(n - 1) < F(n) + F(n) = 2F(n)

Induction seems a bit overkill here

[polar geode]

thank u !!

[last turtle]

please i need a step by step help or solution. If it can be solved on paper then snapped and posted it would be nice

[cursive nymph]

this is correct, right?

[neon harbor]

Yep, looks correct if this is an assignment I would expand on why the final line is a contradiction though

[cursive nymph]

nah, that ain't an assignment

just proved it much shorter than the lecturer so wanted to make sure it's also correct

[neon harbor]

I see 👍 just to be sure, b < x is not enough for a contradiction, you need b < x AND not phi(b), since x is a minimal element of S

I guess you know that, but the way you wrote it is somewhat unclear

[cursive nymph]

wait, why do we need not phi(b) tho?

by construction, x is minimal
yet we found an element that is comparable with it and which is smaller

[neon harbor]

x is a minimal element of S, but not necessarily a minimal element of A

[dry lotus]

Is this where I would talk about sets?

[solar marsh]

there is any probabilistic proof of the König/Hall theorem on bipartite graphs?

[dusky marsh]

Hola Kevin, ¿cuánto tiempo? Jaja.
The proof I know only uses graph theory related concepts, what do you mean by a probabilistic proof though?

[halcyon dock]

A matroid is a mathematical structure that generalizes the concept of independence found in linear algebra, graph theory, and other areas. It is defined as a set system that captures the essence of "independence" in a way that applies to a variety of problems, from geometry to optimization.

[solar marsh]

Hola Trivial!! Que bueno verte de nuevo por discord : )

Estoy buscando relacionar el teorema de Gallai-Milgram y Gallai-Roy con algún teorema de matching, y me parecio interesante probar una ruta probabilística

muchas de las demostraciones de estos teoremas, son esencialmente encontrar alguna estructura con ciertas propiedades. Esta estructura quizás se pueda encontrar usando probabilidad. La idea seria considerar un espacio de probabilidad de estructuras y demostrar que con probabilidad positiva existe alguna con las propiedades que me permiten demostrar el teorema.

[cursive dew]

Quick terminology question.
The word extension, when refering to a set, that just means the elements inside that set? Reading Halmos's set theory book atm.

[prime steeple]

On the ordinal {0,1,...,n-2,n-1} of size n, the map acting as small shift
p_n(x) := (x+d) % n with d=1
not only has no fixed point, but indeed no cycle of length smaller than n. And ord(p_n)=n is its order.
What are the other d's for which this shift map has no small cycles and order n?
Is it the |d| < n that aren't factors of n? (And d=+1 like above and also d=-1)
(edit: counter-example to that conjecture is n=3*4=12 and d=3*3=9, where then the p_n has order 3. See below.)

[fossil mural]

it's the d that are coprime to n, meaning gcd(d, n) = 1

[agile magnet]

Can you send a screenshot with more context?

[digital parcel]

can somebody help i'm not sure why this is wrong

[vestal bronze]

non connected graph is a graph

maybe 1 is wrong

idk

[digital parcel]

ohh like two nonconnected graphs that have even vertices

[vestal bronze]

maybe they meant like that

[digital parcel]

yay it worke

[deft lynx]

Let $L_1, L_2$ be languages on $\Sigma$ Let's define: \
$L = { u \in \Sigma^* | \exists \sigma \in \Sigma : \sigma u \in L_1 \wedge u \sigma \in L_2}$ \
Prove by building an automat that if $L_1 and L_2$ are regular languages then L is regular

[vital dew]

prograce

[deft lynx]

I would appreciate any help ^^

[candid scarab]

Can I define relation R as R = {(a, b) in A * B | p(a, b)}, like, generally?

[coral island]

Could someone explain what this is trying to prove

I feel like this is just pointing out the obvious

Rearranging the formula of x in terms of y and subbing it back into y in terms of x

[lethal linden]

It's proving that the function defined in the example is surjective. Do you know the definition of surjective?

[final cliff]

If this way is obvious can you prove it in another way?

[coral island]

Every element in codomain is mapped to by an element in domain?

[final cliff]

Fwiw they aren't just solving. The part where they claim x in Q is important.

[lethal linden]

Yep.

y is an arbitrary element of the codomain. If x = (y-1)/3 then:

1. x is rational because y is rational, and
2. f(x) = y

therefore f is surjective

[final cliff]

If you had say f(x)=x^2 for example, 2 is in Q, but sqrt(2) is not. So even though you can solve in R and back sub the same argument fails.

[lethal linden]

If you took f: ℚ → ℝ defined by the same formula, would it still be surjective?

For any y ∈ ℝ, does there exist an x ∈ ℚ such that f(x) = y?

[coral island]

Nope

[lethal linden]

Well, then there's something to prove!

True
For any y ∈ ℚ, there exist an x ∈ ℚ such that f(x) = y

False
For any y ∈ ℝ, there exist an x ∈ ℚ such that f(x) = y

The example is proving the former

[coral island]

So for surjective questions, I need to prove that there is no situation where an element in codomain is left dangling if true

[lethal linden]

Uhh..

Say you have a function f: A → B

The negation of

For any y ∈ B, there exist an x ∈ A such that f(x) = y

is

There exists y ∈ B such that, for all x ∈ A, f(x) != y

Surjective says: if you give me a y, I can find an x such that f(x) = y

If a function isn't surjective then there's some y you can give me where I can't find any x with f(x) = y.

[coral island]

Oh I see. Thanks for clearing that up!

[lethal linden]

Cheers.

It's important here that the codomain is the rational numbers. The example would've been more effective if it made that explicit.

If the codomain were the reals then I could pick a number like y = 3*sqrt(2) + 1

There's no rational number x such that 3x + 1 = 3*sqrt(2) + 1, because sqrt(2) itself isn't rational.

Proving that isn't hard, but it's harder than proving f: ℚ → ℚ is surjective and the textbook author might not think it's appropriate for that textbook or chapter or whatever.

[lethal linden]

Sure, but how is this different than just saying R is a subset of A×B?

[buoyant yoke]

how the hell do you solve this

[lethal linden]

By understanding the difference between subgraph and induced subgraph.

[buoyant yoke]

what is the difference?

[lethal linden]

What does your book say?

[buoyant yoke]

i dont know it doesn't say

[lethal linden]

What book are you using?

[buoyant yoke]

nvm i got it

[lethal linden]

Guessing: the key to success

[deft lynx]

What subject is automata stuff ?

[inland raft]

some kind of intro cs, theory of computation

[deft lynx]

I seeee

I js need help bro

[agile magnet]

Ask your question then

[arctic hill]

yoo

i have my final exam tommorow

and i need help

can i dm someone?

basically i need help with these questions

for 2,5 (f), my answer is (C ^ D ^ R) -> H

where C : It is raining cat
D : It is raining Dog
R : I am going swimming
H : i will eat my hat

and please guide me on how to solve 2.6

[shrewd violet]

Hello

Nvm

[deft lynx]

This is my question btw

[distant estuary]

Hi everyone! I have a predicate logic question: Is the following statement true or false?

∀𝑥∀𝑦∃𝑧(𝑃(𝑥,𝑧)→𝑃(𝑦,𝑦))

[lethal linden]

Whether it's true or false depends on the model. Are you asking whether it's logically valid, i.e., true in every model?

[distant estuary]

True in every model or not?

[lethal linden]

You shouldn't expect it to be true in every model because the two parts of the implication don't share any variables. That gives you lots of control.

Two ways to find a countermodel, short of trying something systematic:

1. Think of an everyday two-place relations with a familiar domain and see if it holds there
2. Look at small domains like {0}, {0,1}, {0,1,2}, etc. and reason about what relations must be or must not be present

[distant estuary]

Thank you, I find model where it is false)

[arctic hill]

Can someone help me with this please?

@lethal linden

[twilit sundial]

how many hamiltonian paths are there from the southwestern corner to the northeastern corner of a 3xn grid (with 3(n-1) horizontal edges and 2n vertical edges) such that no edge is visited more than once?
is there a nice way to do this recursively?

there seem to be too many subcases to keep track of

[vestal bronze]

its the cat problem

each path corresponds to a subset of columns

you go right, and if the column is marked you switch to the middle go left, switch to the other side and go right

(and go through)

so it's 2^(n−1) / 2 when n is even

hm

because you want even number of marks for some reason

same for odd n apparently https://math.stackexchange.com/questions/4677579/combinatorics-how-many-paths

[twilit sundial]

icic

thank lmao

[vestal bronze]

right so when you do e.g. 7 choose k, you get equal amount of 0− and 7−subsets, 1 and 6 etc.

so half is even

and if you do 8 choose k, there's twice as many

i get it now

and here it looks like the last column outside is also marked (always marked)

that's why you want even and not odd

cool

[twilit sundial]

ah so it's like choosing where to break the "S" patterns

[vestal bronze]

it's where you switch to the opposite side, because you can't move horizontally on the middle row

i mean move to the right i guess

[twilit sundial]

ok i think i see it

[halcyon slate]

For any two sets $S$ and $T$, $S \triangle T$ is defined as the set of all elements that belong to either $S$ or $T$ but not both, that is, $S \triangle T = (S \cup T) \setminus (S \cap T)$. Let $A, B$ and $C$ be sets such that $A \cap B \cap C = \phi$, and the number of elements in each of $A \triangle B$, $B \triangle C$ and $C \triangle A$ equals 100. Then the number of elements in $A \cup B \cup C$ equals -

[vital dew]

James

[halcyon slate]

If I take explicit examples of this, then the intersection of any two of the three sets comes out to be half of the symmetric difference

The question is, how do I justify this claim?

[vestal bronze]

just say you add the three symmetric deifferences

then these get counted twice

idk

[lethal linden]

If you want to ping me either ask a specific question or make an earnest attempt yourself.

[distant estuary]

Hi friends, is it true for all model ∃X ∀Y ∃Z (P(Z, X) → P(Y, Y)) , I think, answer
is "YES" )

[fringe turret]

Why it didnt consider the same flag color? A signal is composed of two flags. lets say we use same color RED RED and GREEN GREEN, they are two different signals. Also since it didnt mention "repetition is not allowed", how can I decide and choose correct option in exams?

Also this example looks wrong to me
Here we should use 3 cases

Case 1: (2, 1, 1)

Case 2: (1, 1, 1)

Case 3: (1, 1, 2)

And then because its at least one keyword, we should add these cases. Am I right?

[fresh marten]

does it not say that the flags are all different colours?

[lethal linden]

No. Imagine you have space for 4 books somewhere. The first spot you pick a novel, second spot you pick a biography, third spot you pick a textbook, and fourth spot you pick one more from everything that remains.

[fossil mural]

my guess of the intended reading is that the flags are all physical objects, and so to display RED RED you would need two copies of the red flag, which you don't have

...but also yeah i don't like that phrasing

[fossil mural]

your strategy and their strategy are both reasonable approaches

as it happens their answer overcounts, because for instance if you choose two novels A and B, it will count that once with A as the novel and B as the extra book, and then again with B as the novel and A as the extra book

but that can be fixed by just dividing by 2, because it does end up counting every possibility exactly twice

[fringe turret]

It says different signal, not different flags on each signal

[fringe turret]

I see if thats the assumption then yes its without repetition.

[fringe turret]

So when I take 1 book from each category, I filled 3 places $5 \times 3 \times 4$. At least 1 book from each type is selected. But we need to fill 4th place also, and since there is no contraint. Any book can be used therefore, the leftover is $4 + 2 + 3 = 9$. Therefore we can say total arrangement count is $5 \times 3 \times 4 \times 9 = 540$.

Did I get it right now?

[vital dew]

ĐARK々MÁTTER

[light sinew]

https://www.youtube.com/watch?v=yWEZVVKwIME is this guy wrong, or is there actual credibility to what he's saying? I don't know enough to make a judgement, but it seems like bs to me.

Seems like all of his videos are some crazy claim

[sweet lava]

Well he's the self proclaimed greatest mathematician of all time, what do you expect?

He also said about Richard Courant "I wouldn't even call him the backside of a mathematician."

[lethal linden]

If you can't tell it's BS then get your BS detectors in for an emergency repair

[brave rock]

This guy is a very prolific and well-known crank, which is to say yes: he is full of shit.

[odd heart]

The utter bullshit known as The utter bullshit known as Cantor's Diagonal Argument

[lethal linden]

Fixed point of utter bullshit endofunctor

[graceful shell]

hi

should i worry about discrete math?

it will be in next year

[brave rock]

Yes you will literally die

No, just study as you would in any other class. It's just a class.

[tight hound]

No

[graceful shell]

ohk

is it worse or better than linear algebra?

[brave rock]

Depends on you and your prof

[graceful shell]

prof is bad

[light sinew]

I've been wrong so many times in the past, I've kind of given up trying to make judgement on stuff I have no clue about.I find it best to ask people who know more than me, at least for now. You are right though, there's like a billion red flags

[tight hound]

The guy in the video was using pretty abrasive language. This is not characteristic of someone who wants to engage in good faith scientific discourse.

[light sinew]

Yeah this guy is batshit crazy, he claims set theory is a jewish conspiracy to get them prizes and places in academia. Yikes

[lethal linden]

I have news for you: https://people.cs.uchicago.edu/~laci/babai-frankl-book2022.pdf

[lethal linden]

I mean, yeah, let's look at how the video opens. Who knows, maybe there is a Jewish conspiracy to suppress the fact that Cantor's diagonal argument is bullshit.

Who am I to say? I'm no expert in Jewish conspiracies. /s

No. Anyone who opens with that is obviously about to follow up with a river of nonsense, regardless of one's own expertise in the purported subject.

[graceful shell]

i dont need english math

[lethal linden]

I only meant to illustrate that linear algebra plays a non-trivial role in discrete math. You may or may not discuss the connections in your first discrete math course.

[cursive nymph]

I'm studying set theory on the undergrad level, and I don't quite understand where ZF axioms operate

So, for example, consider the pairing axiom. It says that given any two sets the "thing" that contains only those two sets is also a set

But it looks more like a 'deductive rule', that 'the starting positions of a formal game ≈ axioms'

Then why are they called 'axioms'?

I'm much more comfortable with calling the infinity axiom an axiom — something is assumed to be true, and we can use deductive rules of FOL to construct further propositions / theorems

[fossil mural]

...the axiom of pairing is also something that we assume to be true

i don't see how it's different at all to infinity

$\forall x \forall y \exists z (x \in z \land y \in z)$

[vital dew]

bee [it/its]

[fossil mural]

that's a statement, and we assume that the statement is true

or i guess to exactly match what you said it should be $$\forall x \forall y \exists z \forall w (w \in z \leftrightarrow (x = w \lor y = w))$$

[vital dew]

bee [it/its]

[fossil mural]

(the two are equivalent given separation, without that the second version is stronger)

[cursive nymph]

hmmm, I see

ig it's just a difference in perspective

I thought of that 'exists z' as a 'rule' on how to 'construct' it, given x and y

but if we just think of it without a specific 'construction'.... ig I can buy it

thanks

[grizzled storm]

Regarding graph theory, what is the eccentricity of a vertex if it has no path to one of the other vertices? Infinite?

[tight hound]

Yes, if a graph isn't connected then all of its vertices are said to have infinite eccentricity

[grizzled storm]

So the diameter is infinite as well?

[tight hound]

Yes

[grizzled storm]

Thanks!

[cursive dew]

Hello, trying to understand Logical Implication in propositional logic but not quite understanding it.
We're given just a "If P Then Q"
And i understand that if P is true and Q is true, the statement is true, and if Q is instead false, its false.
But im lost to the outcome of whenever P is false. Its always true, why?

Am i not understanding the scope / meaning of what implication is trying to convey?
Like we know for "and" its looking if both(all given) sides are true.
But im not sure what to make of Implication.

I heard some think of it as a promise.

[sharp rose]

"if it's raining, the ground is wet." aka Rain => Wet
In order to show the statement to be false, it would need to be raining but without the ground being wet, ie True => False

If it isn't raining, you cannot emphatically say that the statement is false, ie the statement is "not false" which is the same as "true" in classical logic

It isn't raining, and the ground isn't wet? Statement is not false.
It isn't raining, and the ground is wet anyway? Statement is not false

You can also think of <= , reads "if" (while => reads "only if")

"The ground is wet if it is raining." Would be Wet <= Rain which is equivalent

This statement can only be false when False <= True ie the ground is not wet but it is raining

[vestal bronze]

you should think of every statement as a promise

it's the same with "A and B"

[cursive dew]

I feel as though me and propositional logic have different intutitions on what true and false actually mean on a conceptual level, like im missing what its seeing

Or maybe im just looking at implication wrong. Maybe i shouldnt focus on Q of P -> Q?
Perhaps it's logic doesnt relate Q in any way

with it only "promising" that if P is true, then and only then, would it require Q to also be true

otherwise P being false, Q can be whatever it wants and still keep that promise that if otherwise P were true, then Q would require to be true as well

[vestal bronze]

i think of it as ≤

you can think of it as arithmetic, A or B means "A+B > 0"

A and B means "A × B = 1"

then implication is A ≤ B

it's not supposed to be complicated, and it is a lot like "if" in English, but many people struggle with this thing

[cursive dew]

Sorry not really understanding that xD

i understand conjunction, disjunction, and negation well enough, this implication thing tho is where the table turns

"wounderstand" might be my favorite word now

[sharp rose]

it is helpful if you think of the negation of implication

like ( \lnot (A \implies B) )

[vital dew]

qiuzlm

[sharp rose]

think of the truth table

it makes sense

[vestal bronze]

i don't think it's helpful to try to make sense of it even though it makes sense

[sharp rose]

it helped me at least

[vestal bronze]

it's more like you're lookng for a mnemonic device

"i don't want to just remember this rule, I want to know what it means"

but it's not actually important!

[sharp rose]

i mean it makes sense intuitively but it takes a bit of thought

[vestal bronze]

i agree

[agile magnet]

There's some intuition but also $\implies$ has a \textit{definition} which is its truth table, just like $\land, \lor, \oplus$ etc. There is no higher reason why that \textit{symbol} has that definition other than convention. Now everything above is about why we care abou that particular symbol, why its useful and models things we do in math. But that's separate from the \textit{definition}.

[vestal bronze]

but it all feels tangential somehow, while the point is that it's like ≤

[vital dew]

Spamakin🎷

[vestal bronze]

thank you

[cursive dew]

so, for me the first two rows of the truth table where P is true makes sense.
But the other 2 when its false is just convention? Just we chose to call them true?

[vital dew]

Spamakin🎷

[agile magnet]

it would not be useful for us to do mathmatics and say that statement is false

so yes that is convention but it's convention motivated by how we think about mathematics

if that makes sense

[vestal bronze]

"it rains → ground is wet" is like tautological, it doesn't have to be, a different example is "if it's wednesday, bob is at home"

then it's true when it's true when you should have trusted that advice

when the promise was kept

[agile magnet]

that last example IMO is only confusing. Trying to reason that is true or false is a thought exercise, it doesn't actually convey any intuition for why we define implication to have that specific truth table.

[vestal bronze]

i disagree

it's a real life statement that works as an implication. i'm probably failing to express the idea

you ask someone where's bob

[cursive dew]

so it seems like our less rigid speech/thought can just make the math inspired conventions to seem wonky in a out of math context right? Like saying `if 2 not a number then cats are also dragons"

[vestal bronze]

they don't know, and they don;t know what day it is but they can tell you something at least

they use the implication, everyone knows how to do it

that's why we associate the word "if" with implications

[sharp rose]

Maybe think of it as "Whenever A is true, B is true?"

(For A \implies B)

[cursive dew]

When A Then B does sound nice

wait i remember seeing a circuit like this before

!(P & !Q)

ig thats why they called it the Imply gate 😮

[vestal bronze]

@cursive dewwhe you say you understand the truth table for and, you misunderstand

you mean that the word "and" works as a mnemonic for you, you get the connection

but like that wasn't the point

the truth table is not there to explain the english word

to "mathematically prove and"

it's just there's 16 truth tables you could make, and that's one of them

the implication doesn't work mnemonically, and you don't get the connection, but you don't need to, it just exists, and there's a short way to refer to it

the → symbol

[cursive dew]

what do you mean by "connection"?

Im really lost in how we are meant to think about all this

in terms of logic i mean

[vestal bronze]

i thought i can explain but i'm discouraged because spamakin said that's bad

i'll explain i don't care

so this is "and" it just exists it's a table with letters

[cursive dew]

I think i like the current idea i have so far.
"Implication is a promise/claim that if P is true, than it implys the whole statement P->Q is true if Q is also true"
"With that, said, other than if P is true, and Q is false, than they're all true cause the above's claim still holds."

Thats worded better in my head xD

[vestal bronze]

not even close to what i wanted to say

[cursive dew]

So given that table. Is and just that table only? Like idk where i go wrong, to me it feels intuitive.

[vestal bronze]

if you say "P & Q" that's short for "P & Q is true" meaning the values of P and Q are in the first row

it's slang

[fossil mural]

yeah we decided to use "and" as an abbreviation for that table

(obviously there is a reason we did that, we didn't pick a string of letters at random, but that's more about linguistics/human intuition/etc. than about the mathematics itself)

[vestal bronze]

so here you're saying the values are in the 1st or 3rd or 4th row

it's very "low information"

[cursive dew]

so we shouldnt try to get a understanding of the tables?
Ig that would explain the "if the sun is a moon, then anything else i say after is ofc true" wackyness

[vestal bronze]

yes you shouldn't

that's not what they are for

[sharp rose]

we love classical logic

[cursive dew]

what is classical logic? xD

Just going by the table without adding human quoted intutiton that may break in some place?

[sharp rose]

Well it has law of excluded middle

[fossil mural]

...i mean i think it's a good idea to try to understand why we defined the tables like this, like in practice a good understanding of what the operations mean is useful for doing anything with them

[cursive dew]

law of excluded middle? Not sure what that means

[sharp rose]

[ \lnot \lnot A \equiv A ]

[vital dew]

qiuzlm

[cursive dew]

tbh i kinda had to do that just now for my brain to stop digging into what Implications meant. I saw the table but my brain kept trying to understand the idea behind.

[fossil mural]

just also yeah they're not... justified in terms of human intuition? they just exist

[vestal bronze]

in this framing the implication makes total sense

[cursive dew]

sry my palm hit the numpad enter before i could disable ping

[sharp rose]

rlly we can have any logic we want

[vestal bronze]

it is super justified

[sharp rose]

classical is just the most based 😎

[vestal bronze]

don;t interrupt k

[cursive dew]

thats the idea around abstract algebra right? Where we can make a random rule and see what that does to math?

[fossil mural]

there are some reasons why we're interested in these particular tables but at a certain point the answer to "why is it like this?" ends up being "well it just is", as if you were talking to someone who just really doesn't understand what the number 11 means and why it exists

[cursive dew]

So in math ig the rules we wanted was the axioms of math we use?

[sharp rose]

you could simulate logic in abstract algebra

[vestal bronze]

you ask me "where is Bob"
i don't know
i just woke up, i don't know what day it is
i know that he's at home on wednesdays
i say "If it's wednesday, bob is at home"

[sharp rose]

But logic is its own area of math

[vestal bronze]

i'm literally saying

that the values of "it's wednesday" and "bob is at home" are in one of those three rows, all but the second

that's all i can tell you

but it's useful

and it could be false

[cursive dew]

ig the trick here is to dont dig to deep in the thinking about the idea

[sharp rose]

viz Boolean algebra

[cursive dew]

I keep going down the "but why is it true when he's home while it isnt wednesday?" rabbit hole

[vestal bronze]

no no

[fossil mural]

well there is a direction that you can go with it that's productive, i think at this point i have a pretty good intuitive concept of what exactly -> is that's separate from my concept of the english word "if"

...but yeah if you try to reason about it as if it exactly corresponds to how normal humans use "if" then that's not going to help

[vestal bronze]

wtf

[cursive dew]

I have noticed a few times where the word if really doesnt seem like a proper fit

[sharp rose]

I think the English "if" is just <= but we don't think about the concept precisely, normally

[vestal bronze]

i completely disagree

[sharp rose]

in math we say "if" so

And I can't think of an example in English when it isn't the same logical connective as in math

Only misunderstandings

[fossil mural]

well the english "if" is a human concept

[vestal bronze]

no

[fossil mural]

i'm not really sure how meaningful it is to claim that you can separate out "what it means" from the fact that statements like "at a bar, there is some person such that, if that person is drinking, everyone is drinking" just sound so weird (if you're not used to material implication and explicitly interpreting "if" as that)

[sharp rose]

All "if" 's are human concepts

[sharp rose]

What would the equivalent in "normal" English be

I don't think anyone is expressing this exact idea but if they did, it would either be this or a more verbose version of this

[obtuse terrace]

🤓

[fossil mural]

"at a bar, either there is somebody who isn't drinking, or everyone is drinking" is the closest normal-sounding logically equivalent statement

(which also makes it sound like an obvious tautology)

[vestal bronze]

@sharp rosewhy did you say it's <=

[sharp rose]

"if" is <=
"only if" is =>

[vestal bronze]

no

[fossil mural]

there are things that you just wouldn't say in a natural language because they're weird things to say

[sharp rose]

"if it is raining, then the ground is wet"
"it is raining only if the ground is wet"

Equivalent semantics

[fossil mural]

specifically a lot of the weird cases are situations where there's some more concise way to express logically the same concept

[obtuse terrace]

@sharp rose we have a mutual lol

small world

[sharp rose]

That's crazy

[obtuse terrace]

are you from HK

[sharp rose]

No

[cursive dew]

Im getting quite lost, but i should just stick to the idea we chose our rules(the truth tables) for the logic we use, while making some thought/idea of what they represent to us is not nescessary, just helpful to understand, right?

[sharp rose]

I assumed nagisa was either Singapore or hk

[obtuse terrace]

bro just ask a TA for this

hes from HK

do you play tetris

[sharp rose]

no

[fossil mural]

"if this object is red, then it is blue", where "if" is read as material implication, is equivalent to "this object is blue", and we already have a way to say that, so nobody would use this longer representation for the same reason they wouldn't say "either this object is blue or it is blue"

[sharp rose]

I play(ed) chess

[obtuse terrace]

i see

[vestal bronze]

@sharp roseit's true if you mean the arithmetic less than or equal

[sharp rose]

What

[vestal bronze]

the arrows are thwe other way

[sharp rose]

"if" is ( \impliedby )
"only if" is ( \implies )

[vital dew]

qiuzlm

[vestal bronze]

yeah, you have them backwards idk why

[sharp rose]

What's backwards

[fossil mural]

yeah pretty much
as long as you're consistent about what truth table you're using, it's logically valid
the whole thing with naming them after words and mapping them to intuitive concepts etc. is just for intuition, i.e. to help us understand/deal with the concepts

[fossil mural]

if by if'' you mean if $P$ then $Q$'', which is far more common, then that's $\to$ \
``$P$ if $Q$'' does mean $Q \to P$ but is also honestly kind of a confusing way to write it

[vital dew]

bee [it/its]

[cursive dew]

Does direction matter? Or is it based on the order of the statements?
"If its raining {P}, then i have an umbrella {Q}"
We tend to say P->Q
But couldnt we also just do Q<-P?

[sharp rose]

yeah "if" meaning A if B

"if...then" would be ( \implies )

[vital dew]

qiuzlm

[fossil mural]

like i don't think i really see $P$ if $Q$'' anywhere outside of if and only if'' which effectively acts like one word by this point, it even has a single symbol $\leftrightarrow$

[vital dew]

bee [it/its]

[cursive dew]

woah! Such a slight symbol change! 😮
eh, ig its not negation versus subtraction

[sharp rose]

it is one word
iff 🗿

[cursive dew]

Lets make a new one, "However if" ~>

[sharp rose]

what would that mean

[cursive dew]

Eh i feel like its a secret negation actually

conditional negation?

[vestal bronze]

i see you mean there's no "then" when you say "if"

[sharp rose]

(petition to add iff to English dictionary)

[vestal bronze]

got it

[cursive dew]

would "however if" feel more like a xor?

[sharp rose]

I don't know what the term means semantically

[vestal bronze]

no

however is like "and"

"i'm 13 and John is 10"

[sharp rose]

so what's andif

[vestal bronze]

it corresponds to nothing

[cursive dew]

well im off to bed to dream of proposition(im scared) ty for the help guys 😄

[sharp rose]

yeah the binary connectives have been exhausted ig the best we can do is come up with new names for the same connectives

[fringe turret]

Isn't this a combination problem? I am doing 8C2, but the answer is 8P2

Why I think so? Because of choose keyword and we say n chooses r for nCr

I see, these two positions are distinct. For example lets say we have two person A and B, then two arrangements AB and BA are distince because roles are different. Therefore its a classic example of permutation.
How choose keyword got me wrong there 😄

[hard stone]

Yup exactly, it's a permutation bc the two positions are distinguishable

If it were just "choose two co-chairmen (where the order of the co-chairmen doesn't matter)" then it would be a combination problem

[lethal linden]

C(8,2) picks out two people, so you can imagine simultaneously summoning forth 2 people from the crowd of 8.

"Would Dark Matter and Cufflink please step forward."

And then you have two ways of assigning roles to those two people.

[fringe turret]

Oh yeah 2 . 8C2, this is nice logic

[weary tiger]

How do I get from {A} only A with ZFC set theory?
context: Im learning how to define ordered pairs without adding any other axioms

[cursive nymph]

u want to construct A given {A}?

or vice versa?

[weary tiger]

I have {A} and I want to construct A out of it

Ive seen that some people used U{A} but I dont understand which set your unioning A with

[weary tiger]

nvm my questions
ive found the answers

[hard stone]

If you already know that you have a set which has exactly one element in it, you don't need any axioms to name what the one element is.

However you are correct that U {A} is just A, and the existence of U {A} is guaranteed by the axiom of union.

[solar marsh]

Hi everyone! I’m researching Mader’s Theorem on S-Paths (Mader 1978) "Über die maximalzahl kreuzungsfreier", and I was wondering if anyone knows of any interesting applications or practical cases where this result has been used. Any references or ideas are greatly appreciated. Thanks in advance! 🤝

[agile magnet]

I have no idea about things about S-paths but just as a future reference, one place to start could be to look up the paper on Google Scholar. There, you'll get a list of papers which have cited that paper, which would be a good start of finding people who have used this theorem in some capacity in their work.

https://scholar.google.com/scholar?hl=en&as_sdt=0%2C14&q=Uber+die+Maximalzahl+kreuzungsfreier+H-Wege

[dry lotus]

I have a question about discrete mathematics. Would you say this is a course that's more of a preperation to the advanced maths we will see later on, kind of diving into multiple topics to prepare us?

[weary tiger]

Isn't ω^ω the same as ω because ω is infinite? (Context: ZFC ordinals)

[weary tiger]

Most of modern math is built upon axiomatic set theory which is afaik part of discrete math.

[odd heart]

Nope, it's greater: https://en.wikipedia.org/wiki/Ordinal_arithmetic#Properties_3

(in particular, since exponentiation is strictly increasing in the exponent, ω^ω > ω^1)

[dry lotus]

so discrete math kinda prepares for all those other topics

[hard stone]

I would say a lot of discrete math classes just package up all the math a CS student needs to know lol

That being said, some of the skills you learn in discrete math, like proofwriting, will be essential to everything math related you do later on

Some of the topics, like graph theory, are entire rich fields of study that you only touch on the surface of

So there's lots of ways you can take it afterwards!

[fossil mural]

...well, maths isn't "built on" axiomatic set theory in the sense of that being the order you should learn them in, it's more just that most of mathematics can be encoded in ZFC

so axiomatic set theory is a reasonable place to start if you're writing a computer program that checks proofs, but for humans, you don't really need to know how to encode objects as sets for most things, it mostly comes up in independence results

some basic concepts about sets like injections, surjections, intersection, union, cardinal arithmetic, etc., are very useful, but that's not really related to foundations stuff, it's just that sets come up a lot and it's useful to know how to work with them

[dry lotus]

I will apply what I learn to computer programming but I mostly just want to learn for the fun of it. In the end all of this is just for fun. So if there is some new math idk, I’m gonna learn it lol

[arctic berry]

Are cartesian products and outer products the same thing or is the cartesian a type of outer product?

[pale epoch]

whats an (the?) outer product?

[arctic berry]

The outer product of two vectors is $\vec{v} \otimes \vec{u} = \vec{v} \vec{u}^T$

[vital dew]

KySquared

[arctic berry]

Whereas the cartesian product is $A \times B = {(a,b) | a\in A \quad \text{and} \quad b\in B}$

@pale epoch

[vital dew]

KySquared

[pale epoch]

well, one of them is for vectors, the other is for sets

so no, they are not related

[arctic berry]

But sets can belong to vector spaces

[quick folio]

I can elaborate a little more on this

[pale epoch]

wdym

[quick folio]

set can belong to vector spaces, sure, but there are plenty of sets that aren't in vector spaces

it doesn't mean anything just to say that something is a set

[arctic berry]

I agree
But in what instance would the cartesian product not be equal to the outer product

[quick folio]

but the more important reason why the cartesian product is not in any way related to the outer product, is that the cartesian product does not respect the structure of a vector space, while the outer product does

[arctic berry]

Since from my understanding the outer seems like a generalization of cartesian

[quick folio]

no, it's not

it might seem like it superficially but it's not

let me explain

[quick folio]

what do I mean by this? well, v \otimes w is a matrix (for vectors at least). So we naturally get the very nice result that, for instance, v \otimes (w + u) = v \otimes w + v \otimes u

[arctic berry]

Mhmm

[quick folio]

but what even is v x w? it's not even a vector anymore, it's just some set. it doesn't meant anything to say v x w + v x u anymore, because v x w and v x u aren't in the original vector space anymore

but, and I think this is what you're confused on, this doesn't mean you can't make it make sense

[arctic berry]

v x w is a vector
Thats the cross product

[quick folio]

in here I'm writing the cartesian product with x, don't think about the cross product lol

in math there's a lot of notation clashing

[arctic berry]

I getcha

[quick folio]

but this:

[arctic berry]

Ok continue

[quick folio]

just because the sentence "v x w + v x u" doesn't make sense doesn't mean I can't introduce some sense to it

specifically, there's nothing stopping me from defining v x w + v x u = v x (w + u)

but you see, the difference between this and the outer product, is that here I have to go out of my way to define this nicely, while the outer product already comes with it built in

moreover, once I define the rule "v x w + v x u = v x (w + u)", the result I get is no longer just the cartesian product anymore. it's the cartesian product along with the added rule that it must satisfy "v x w + v x u = v x (w + u)"

but.

you aren't entirely incorrect in saying that they're related.

there is a certain sense in which the cartesian product and the outer product are special cases of the same thing

if you ever want to read deeper into this someday, they are in fact the categorical product in the category of sets and vector spaces

the idea of what's going on, is that the outer product is the "product" that "plays nice" with vectors, while the cartesian product is the "product" that "plays nice" with sets

that's the best I can describe it to you without getting deeper in the weeds

[quick folio]

if you just want the clean answer you can ignore everything after this message lol, it's just bonus info

[arctic berry]

So many layers of generalizations
The outer is a generalization of the cross, the categorical product is a generalization of the outer AND the cartesian

[quick folio]

the categorical product is a GIGANTIC generalization

it covers a lot, a lot, a lot of things

and you don't need to worry about it unless you really want to dive deep into pure math :D

[arctic berry]

I’m somewhat understanding what you’re saying
Since v otimes w isn’t within v or w, it belongs to some new space

[arctic berry]

Why do we choose to define it like this then?
We could have defined the cartesian product an million different ways

[quick folio]

a good metaphor might be that one is (outer) a crosshead screwdriver and the other is (cartesian) a flathead screwdriver
you can still use the flathead on crosshead screws, but you'll strip the head of that screw until it can't be used by a screwdriver anymore. and you certainly can't use a screwdriver on a flathead.
so if you ask a mechanic, they'll obviously tell you that they're completely unrelated
but it is still true, that they're kind of the same thing, just that one is for cross head screws and the other for flathead screws

image for reference, lol

[arctic berry]

I see

[quick folio]

and then in this analogy the categorical product would be the entire toolbox

probably more

[arctic berry]

Lol

[quick folio]

what do you mean?

[quick folio]

this is how the cartesian product is defined

[arctic berry]

You say here that we define v otimes (w+u) = v otimes w + v otimes u. However, as you mentioned, there is nothing within the structure of set theory which tells us this is the specific definition

[quick folio]

not my "v x (w + u)" thing

no no no that's not what I'm saying

because v otimes u is just a matrix, in fact vu^T,

we get the fact that v otimes (w+u) = v otimes w + v otimes u for free

and that's the core difference

with the cartesian product, you can still get something similar, but you have to force it to be like that, and you don't get it for free

[arctic berry]

One second, let me try and phrase this in my own words then

[quick folio]

moreover once you force it to be like that it's no longer just the cartesian product

[little prism]

hmm if you write subsets as their characteristic vectors over F_2 and then do the outer product of these vectors, the resulting matrix does essentially correspond to the cartesian product of the subsets. but that does feel more like a coincidence

(these vectors form a vector space and the addition corresponds to the symmetric difference of the subsets)

I've never thought about whether Ax(B Delta C)=AxB Delta AxC is true, maybe

[arctic berry]

Given vectors v, u and w
In LA: Since vu = some matrix A, we can immediately deduce and define v(u+w) = vu +vw. No other definition for this could exist within the lens of LA

In ST: because we already stated v and u to be vectors, we can pull from our definition of vu in LA to define v otimes u = vu, thus v otimes(w+u) = v otimes w + v otimes u.

Is this on the right track?

[quick folio]

yes

you can pull from the definition in LA to define v otimes u = vu, but because they're just sets you can pull from whereever else to define v otimes u to be whatever you want it to be

but that isn't the case for the outer product

[arctic berry]

Yeah, I forgot that last bit

So technically, the cartesian product could have been defined in some other manner however we settle on this one

Im basing that question off of my understanding of inner/outer products from LA

And how an infinite number of those products exist

But we have common ones like the dot in the case of inner and the cross for the outer

[quick folio]

I think you've got it, but here's one final way to look at it:
-vectors only care about two things: vector addition and scalar multiplication.
because the outer product is just vector multiplication, the outer product looks at that and goes "cool! I care about vector addition and scalar multiplication as well! we have so much in common let's be friends :)"

-sets only care about one thing: functions, of any kind.
because the outer product is just also a set, the outer product looks at that and goes "cool! I care about functions as well! we have so much in common let's be friends :)"

now, the cartesian product kind of cares about vectors as well, because vector addition and scalar multiplication are also functions, but they're only a tiny tiny corner of all possible functions so the cartesian product doesn't really like to play with the vectors.

however, the friendship between vectors + outer product, and sets + cartesian product, is the same friendship

[arctic berry]

OHHHHHHH okay I understand it now

Sets don’t care about what kind of function you give it, thus a cartesian product will exist for any two functions

Vectors DO care about the kind of function you give them (as only ones that are linear can exist w/i a vector space)

If the function(s) in question just so happen to exist within some vector space, then they also exist within a set

Thus the cartesian & the outer product are equivalent

[quick folio]

but they're still the same idea of multiplying things together in a way that plays nice with whatever you're originally using to multiply

[arctic berry]

Mhmm

[quick folio]

don't say they're equivalent. unless you're a category theorist that will make people angry

because they're really not unless you squint your eyes really hard

[arctic berry]

As another analogy, A square is a rectangle but a rectangle is not a square
An outer product is a cartesian product but a cartesian product is not an outer product

[quick folio]

an outer product isn't a cartesian product

they're neither each other

just vaguely related

[arctic berry]

I understand the vague relation part, but from my understanding this sounds correct
A cartesian product will always exist regardless of the two inputs. However an outer product only exists if the two inputs are elements within a vector space

[quick folio]

correct!

[arctic berry]

So, if the two inputs both belong to a vector space then the cartesian and outer product should be equivalent

As thats how we originally defined the caretesian prod

We just extrapolated its definition to cover more then just stuff w/i vector spaces

[quick folio]

they're still not equivalent. if both inputs are vectors, then you can force the cartesian product to be equivalent to the outer product. but it itself is not the same at all

and without that forcing, the cartesian product doesn't "want" to be like the outer product

[arctic berry]

What do you mean by “forcing” exactly?
Like I kinda get it, the cartesian is pretty much a set of sets, so by “forcing” are you saying we just represent it as a matrix?

[quick folio]

pretty much

I can define a bijective function from v x w to v otimes w

that just sends (v_i, w_j) to a_ij

and so if we force every v x w to have this bijective function, then the cartesian product would be the same

[arctic berry]

Okay I fully understand now

Ig my last question would be, in what instances would we prefer to keep everything as a set/in set notation versus using matrices/vectors?

[quick folio]

well.. if you're working with sets, lol

[arctic berry]

What about the inputs/outputs can we analyze using ST that we are unable to in LA?

[quick folio]

anything that isn't linear

[arctic berry]

Assuming they are lol
This kinda falls apart if they aren’t lol

[quick folio]

although ST is kinda boring and vanilla in and of itself. we usually can find some other branch of mathematics that the thing we're trying to understand is inside

and look at that branch instead

[arctic berry]

@quick folio

[quick folio]

?

[arctic berry]

^

[quick folio]

yeah

[arctic berry]

Assuming the inputs are linear, what can we analyze about them using ST which we can’t using LA?

And vise versa

[quick folio]

nothing

what's the vice versa

[arctic berry]

Idk
I brought that up just to cover all my bases

Im just now getting into ST so i was unsure if we could analyze anything in one framework but not the other (again assuming linear inputs)

[quick folio]

it really depends

you'll know it if you see it

that's the best answer I can give

[arctic berry]

I see
Alright then ill keep studying

[quick folio]

good luck!

[arctic berry]

Thanks so much for your time
Happy new years

[quick folio]

you too

[winter topaz]

Merry Christmas everyone!!

Im not asking for any answers, just a fun problem with funny numbers xD

[sharp rose]

bobs

[weary tiger]

does anyone know an easy way to raise a matrix to k-th power if it looks like this

I only need the last rows of the k-th powers

[vagrant chasm]

If you are doing this on a computer you can use binary lifting (calculate M^(2^i) by repeatedly squaring it), otherwise I'm not sure if there's a pattern. Maybe try some powers

At least it will be lower triangular

[little prism]

if you transpose it then the last column of M^k is just M^k*e_n. matrix vector multiplication is faster than matrix matrix multiplication so you could gain some speed from that (although you do need to calculate every step I think)

will depend on how big k is

[coral raven]

you can just treat it in blocks

each row is like 1 I 0

each column is like 0 I 1

actually i might be dumb

[vagrant chasm]

What are the possible sizes of k and your matrix? Where does this come from?

[weary tiger]

nvm I got my matrices incorrectly

they shouldn't look like this

[vapid depot]

Representation of a Hadamard matrix. Half of the entries in each row and column are 1 (represented by white squares) and half by -1 (black squares). All columns are mutually orthogonal, and all rows are as well.

[upper wraith]

What are some tips for discrete and what are some good videos to watch for the course so I can learn during break?

[lethal linden]

Do as many exercises as you can from a good textbook, get feedback on your answers/attempts, and compare your answers/attempts to other people's.

[coral island]

Could some explain how this counting method proves it is 1-1 and onto
I’m confused as to why one set isn’t being mapped to the other

[quick folio]

you seem to have said two opposite sentences...?

this counting method is 1-1 and onto, and so it's mapping Z to N

[coral island]

Forgive me I understand nothing about this chapter

Why does the counting method show that it is 1-1 and onto

Isn’t it just counting within one set

[quick folio]

it's a function from Z to N

not from Z to Z

the picture is just showing it as a series of arrows inside Z

[coral island]

Oh ok nvm I think I got it now

[arctic berry]

How does one handle unions when dealing w/ cardinality?

<@&268886789983436800> (noticed a spam account so i pinged mods, pls ignore this)

[arctic berry]

I have sets $A,B,C$ and I want $|A\cup B \cup C|$\
I managed to rewrite it as $|A-B\cup C| + |B-C| + |C|$ but idk how to deal w/ the union without expanding

[vital dew]

KySquared

[odd heart]

For finite sets that's basically what you need to do (something along the lines of the inclusion-exclusion principle); for infinite sets it sort of trivializes, because the cardinality of the union of finitely many infinite sets is just the largest of their cardinalities

[quick folio]

but I believe you're looking for this

https://en.wikipedia.org/wiki/Inclusion–exclusion_principle

[odd heart]

(unless you reject the Axiom of Choice)

[arctic berry]

I assume my prof wants me to rewrite it only in terms of base cardinalities & intersections(since thats what im given) but im moreso asking for general knowledge

[odd heart]

If we're talking finite sets, then in general there's nothing simpler than inclusion-exclusion principle (of course for specific finite sets it might simplify)

[arctic berry]

This is what i did @odd heart

But uhh, i dont feel like writing that out eacb & every time 💀

[arctic berry]

So i managed to simplify it to this^

[odd heart]

This is fairly clearly a problem that wants you to use the inclusion-exclusion principle and there isn't much in the way of shortcuts.

[arctic berry]

[odd heart]

My heart goes out to you at this difficult time

[arctic berry]

Thanks

How would the question need to be phrased in order to properly use the simplification?
Since the union immediately makes me want to add B & C

[odd heart]

What would "the simplification" be?

[arctic berry]

^ (assuming i even simplified correctly)

[odd heart]

That's correct, it just doesn't help you much if you don't know the cardinalities of the three sets you've reached

The first one is "tools used only by A", and the second one is "tools used by B but not by C"

[arctic berry]

As in: of the 8 used by A, |A-B U C| are the ones which B or C didn’t use
And: of the 10 used by B, |B-C| are the ones which C did not use

[odd heart]

Yes. Also note that $|B\setminus C| = |B|-|B\cap C|$

[vital dew]

Outsider

[arctic berry]

Wait, i think thats an “and” for the first one

Not or

[polar geode]

i can't wrap my head around what < is supposed to mean, is it a set of A but ordered? or how can i imagine it?

[hard stone]

≤ is a relation on A satisfying the poset axioms

so set theoretically, it's a subset of A × A

every element of ≤ is an ordered pair (a, b) where a and b are elements of A

if (a,b) is an element of ≤, then you can write that as a ≤ b

[polar geode]

i seee thank you so much

[hard stone]

you're welcome

[plain shoal]

is this a good proof for the transitive part?

[agile magnet]

Technically this seems correct but stylistic this needs a lot of work. You've seen proofs in the text you're reading yes? Write actual sentences, not just floating bits of math

Make it nicer to actually read and parse

You've got scratch work, now make it a written proof

[plain shoal]

okies, thank you

[agile magnet]

As an extra challenge, this relation is basically the relation for saying two fractions are equal right? So you can extend this claim to all integers

Now you have to worry about division by zero, so see if you can rewrite the proof without divisions

[plain shoal]

can't we do a 2 parts proof if we have zero and division, we do the first part by assuming that one of them or more equals 0 and solve it and then we can prove by proving that all the multiplications equal 0, and then we do the second part were we assume that all of them are different than zero and do this proof.

[agile magnet]

Yea sure you can

[plain shoal]

tysm 8)

[carmine bramble]

Hi why isn't my digraph correct for problem b?

[vestal bronze]

@carmine bramblethere's a 3 cycle

just use the right part

i don't know what it should be instead

oh you mean the leftmost vertex maybe

yeah that makes sense

so like, it's wrong because you didn't write v anywhere

lol

[carmine bramble]

gpt says it was wrong, but I don't why i listen to gpt

it said b) wasn't possible

[agile magnet]

Like you said, who cares what GPT / any other LLM has to say

Do you think your answer is correct, yes or no and why? In particular if you think your digraph is a sufficient example, then which vertex is the v in question?

[cursive dew]

guys somehow im failing to understand the inverse truth table and making it wrong

the internet seems to keep claiming the 3rd row is the false one

But i really just dont see how

If p is false, then Not q
But then claim its wrong when p is true? Thats now how implications work 😮

[brave rock]

The second line is incorrect. Ex falso quodlibet, False -> X for any proposition X is true

Maybe write out the truth table for X -> Y again and compare with what you have written

(In fact there is another incorrect line which you will need to correct)

[cursive dew]

what is x and y

[brave rock]

Some propositions, it doesn't matter what.

You have written P and Q, so I wanted to use different letters

[cursive dew]

I want to think the guides i seen they might not even use the columns for !P and !Q, and just negate P and Q mentally.
That way it makes sense

Was i not meant to actually use those columns?

[brave rock]

You can use whatever method you find easiest

[cursive dew]

Doing it the way I was doing, P column for P and !P column for !P is that why my table seems odd?

Cause i notice the condition and the contrapositive were ment to be the same, same for converse and inverse

Going to work, but the logic holds for me, im not sure how its appearing wrong

[fossil mural]

it doesn't matter whether you have columns for !P and !Q or not

if you get different results with the columns compared to without the columns, then that implies that you're doing something else wrong

[fossil mural]

although, uh, the exact text you wrote in for !P and !Q in this table is a bit odd and might be part of what's confusing you

[neat oasis]

Does someone have any counterexample to this algorithm to find the bridge edges of a graph?

Imagine we have an undirected graph G = (V,E), then you run a dfs search through the graph, and while doing so, you transform the undirected edges into directed edges. When finished you should have a graph G' = (V,E') (where E' is just E but with directed edges). Then we grab the inverted graph of graph G', G'^T and we run a dfs in the order that the last dfs was done (this means, if we started in node 0 in the creation of graph G', we will start here too by that, and then check the next unseen by the dfs node that follows the original order) and we remove any adjacent edges to a vertex that aren't accessible (through themselves or another path that starts on the same vertex). Finally the complementary graph to this graph where we removed edges from G'^T, while transforming it again into an undirected graph is the graph of every bridge edge in graph G.

[neat oasis]

Is there any better channel than this to ask this?

[cerulean wind]

can you do it with
3
/ |
0 — 1 — 2 |
\ |
4

and send sketches after each step?
i am a bit confused with your description

you should get 0 — 1 — 2 as a output

[terse wyvern]

one method you could use is to find cycles

[cursive dew]

I rewrote the two for conditional and contrapositive with a better statement.
Now I'm feeling the contrapositive is NOT the equivalence of the conditional, its just not making sense.

[quick folio]

oh, what are you confused about the contrapositive

[cursive dew]

At this point im not sure

im told its the same as the conditional?

[quick folio]

it is

[cursive dew]

But if you look at that truth table, its not

what was false for P->Q is magically true for !Q->!P

denoted with the "?!" in the photo

[quick folio]

$\begin{tabular}{c|c|c}
P & Q & P \rightarrow Q \
\hline T & T & T \
T & F & F \
F & T & T \
F & F & T \
\end{tabular}$

[vital dew]

HChan
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[quick folio]

jesus that was annoying lol

but anyways, here's the standard truth table for P -> Q

[cursive dew]

Woah you remembered that format first try 😮

[quick folio]

$\begin{tabular}{c|c|c}
\neg Q & \neg P & \neg Q \rightarrow \neg P \
\hline
F & F & T \
T & F & F \
F & T & T \
T & T & T \
\end{tabular}$

so here's the truth table for the contrapositive

[vital dew]

HChan
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[quick folio]

!Q and !P are now in reverse order

so that might be what's confusing you

[cursive dew]

I dont think so? When its like that i do understand it, but its when i use my truth table with those worded statements it seems to break somehow

[fossil mural]

yeah i think that's because the statements you put in the truth table are kind of just wrong

!P is the statement that it's not raining

so if !P is false, that doesn't mean it's not raining, it means that "it's not raining" is false, so it is raining

[cursive dew]

but the first row of !P is the negation of P right? raining -> not raining?

[fossil mural]

it's the negation of the truth value, so T becomes F

"raining" and "not raining" aren't the values of P

if P has the value T, then that does mean that it's raining

but then when we look at !P

we're still in the same row, so it's the same situation, it's still raining

and !P has the value !T = F

so !P being F means it's raining

[fossil mural]

so looking at what exactly the "wrong" result you got here is

[cursive dew]

sry trying to follow along

[fossil mural]

you've written at the bottom "if not wet, then no rain"

but what that really means in terms of the table the way you wrote it is "if Q is not wet, then P is not rain"

but then you took the boxes and wrote in the values that are in the !P and !Q columns

[fossil mural]

this is how "negation" works in the sense that like
P is true in the rows where it's raining
!P is true in the rows where it's not raining

but once you've picked what world you're in (i.e. which row of the table), P is either just "true" or just "false"

[cursive dew]

I think i see what you mean? Not sure tbh, the world of logic is somehow quite confusing.
I rewrote my table, and i noticed, I wrote just now !P, given it a basic FFTT table, but im looking at it as "Not raining"
Meaning the first value which should be the negation of P, is instead F for not raining which works out to be raining doesnt it, and not F

[quick folio]

so !Q -> !P is no longer a statement about whether if it's raining or if it is wet

they are now statements about the statements P and Q

[cursive dew]

idk how but it happened again XD

Do i need to rearrange !Q and !P rows?

[fossil mural]

...ok yeah now you've made a different mistake

if P is T then !P should be F

[cursive dew]

Somehow my chart doesn't make sense but this online one does

[fossil mural]

like if we focus on the first row of the table

then what you're claiming is

1. P is true, i.e. it's raining

2. Q is true, i.e. the ground is wet

3. !P is true, i.e. it's not raining

4. !Q is true, i.e. the ground is not wet

[cursive dew]

But then !P doesnt mean "is not raining'?

[fossil mural]

which doesn't make sense, is it raining or not lol

[fossil mural]

!P does mean "it's not raining"

if "it's raining" is true, then "it's not raining" is false

[cursive dew]

idk why my brain cant comprehend any of this

am i stupid or something? XD

[sharp rose]

Rather than "is not raining," it may be more precise to move the 'not' outside the quotes and say not "is raining"

[cursive dew]

Cant help but see that as being what negation is, is it wrong?

[sharp rose]

May help understand

[fossil mural]

well negation is "if !P is true, then it's not raining"

that's kind of my entire point

that, if it is raining, then !P must be false

because if !P is true, then that would mean it's not raining

like you've basically been claiming that if "it's raining" is true, then "it's not raining" is also true

[cursive dew]

SOMETHING HAPPENED!

[fossil mural]

yep that's the correct table

[cursive dew]

bee, after all this, im worried for what philosophers way back in the days of time must of gone through for this.

is this why i see a lot of them drawn as wizards? Or just people who gone insane

[fossil mural]

"the days of time" is an interesting way to phrase it

[sharp rose]

Honestly I find the !P and !Q columns confusing in terms of contributing to the semantics

[cursive dew]

I say that cause i dont know the timescale of this xD
I heard there was a historical "issue" with sets of all sets or something

[sharp rose]

I would cut them out

[fossil mural]

well more specifically the problem is the set of all sets that don't contain themselves

the problem being, does this set contain itself?

it contains itself iff it doesn't contain itself

[cursive dew]

A sort of mathethical "flucation in logic" right?
Doesnt contain itself, add it in, now contains it self, take it out, repeat"

[quick folio]

but that's the problem. in logic there can't be any fluctuations

[fossil mural]

well mathematics doesn't really change over time, so it's more just an issue of

yeah

[quick folio]

therefore, the set of all sets **[that don't contain themselves] can't be a set

[cursive dew]

these are my two options xD I doubt i was THAT far off to be uncorrectable

[fossil mural]

"if it contains itself, then it doesn't contain itself, that's a contradiction. so it doesn't contain itself, but then it does contain itself, that's also a contradiction. oh no"

[fossil mural]

no

the conclusion from this is that the set of all sets that don't contain themselves isn't a set

the more general conclusion is that you can't just run around saying "the set of all [whatever]" and expect nothing bad to happen

[cursive dew]

Wait so we cant say "the set of all numbers"? Or is that only sets of things

[quick folio]

what do you mean by numbers

[cursive dew]

I just chose something in general

lets say integers

[quick folio]

every time before you want to say something like "the set of all X", you need to double check that it is indeed a set

[fossil mural]

it turns out that you can have a set of all integers without any problems

[quick folio]

and the point was that you needed to do this double checking

[fossil mural]

but yeah you do have to prove that

[cursive dew]

for now before i delve too far into set theory im gonna continue my logic series xD

My end goal in all of this is to have a understanding of why (-A)*(-B) = +C

[quick folio]

you mean AB?

[cursive dew]

ig it would be the same as AB? I just used C to represent the result in a different name

I made "simple" proofs a while back for me to sleep with but people kept saying they wernt proofs, just intutitions

[quick folio]

well if you want a simple proof of that, (-A)(-B) = (-1)^2*AB = AB

[cursive dew]

more of a concept of negation turning positive once multiplied.

But i realize now thats steming more from subtraction of negatives

[neat oasis]

Well basically, you start at 0 and in this case creates the directed graph G' (0,1),(1,2),(2,3)(3,4),(4,2), then you grab the inverse graph G'^T with (1,0),(2,1),(3,2),(4,3),(2,4) and run dfs starting by 0, which makes you remove edge (1,0) as it is innaccessible and adjacent, then you go for 1, which makes you remove edge (2,1), because it is inaccessible and adjacent, you start on 2, which goes to (2,4), (4,3), (3,2) and so all these edges are accessible therefore none are removed.

Then the complementary undirected graph is the graph (0,1),(1,2) which is indeed the bridge edges of the original graph G

[neat oasis]

That's indeed the main idea of the algorithm, as there should always be a reversed path if there's a cycle when you run the dfs in the inversed graph in the order asked

[cerulean wind]

ah. this clears things up. my notion of inverse and complement was different

dfs creates a spanning tree, so you never get the edge (4, 2) in the digraph G’

if you can tweak that, then any edge that remains must be part of a cycle (can you argue why?) and so the complementary edges are bridge edges

i think it’s solid

[neat oasis]

Wdym by that?

[neat oasis]

Well mainly the edges that remain are from cycles because there exists at least two paths to reach the same starting point

Which is reflected by being able to reach every edge in the inverse graph

[cursive nymph]

i don't understand, how are:

1. Assume p is true, [...]. Contradiction. Hence p is false
2. Assume p is false, [...]. Contradiction. Hence p is true

different?

[quick folio]

functionally? not really

they're both just proofs by contradiction

[neon harbor]

Sometimes the former is just called proof by negation, since it isn't followed by double negation elimination. For the latter, you're actually proving (not (not p)), which is equivalent to p in classical logic

[tired gazelle]

main difference lies in the assumption and the ultimate conclusion tbh. Both are proof by contradiction, but they work with opposite assumptions to reach a conclusion about p

[lethal linden]

In what context were you told they were different? They are certainly formally different.

1. In the first case, you are allowed to conclude ¬P if you assume P and derive a contradiction.
2. In the second case, you are allowed to conclude P if you assume ¬P and derive a contradiction.

If you permit the first case then assuming ¬P and deriving a contradiction gets you a proof of ¬¬P.

Can we start with¬¬P and deduce P? This is called double-negation elimination. Some logical systems have it and others don't.

So you still need "something more" for (1) and (2) to be substantively equivalent.

[cursive nymph]

so, in classical logic they are equivalent, right?

and in IPL they aren't, right?

[tired gazelle]

^ the process of reaching the conclusion about p is equivalent (proof by contradiction)

[lethal linden]

Classical logic has double-negation elimination, yes.

[tired gazelle]

the statements themselves aren't 100% equivalent unless stated

[cursive nymph]

but proof by contradiction doesn't work in all logics tho

when u don't accept LEM for example

[tired gazelle]

yes, but here it clearly says contradiction

so it should work in this case

[lethal linden]

I think you're over-interpreting what's going on.

[cursive nymph]

I think I heard there is a way to make a 'contradiction' in constructive mathematics. I didn't get what the lecturer meant by that tho xD

[tired gazelle]

yeah i don't quite understand what they mean, i'm just trying to explain to them the main difference between the two

[lethal linden]

Replace "contradiction" with "absurdity" if you take the mere use of the word "contradiction" to imply proof by contradiction is permitted.

In IPL, ⊥ is usually given as a primitive and ¬P is an abbreviation for P → ⊥.

[cerulean wind]

if dfs gets caught in a cycle, it will loop forever. so it can’t ever close a cycle. the graph traced out by a dfs is a tree

[neat oasis]

I just have to do a "seen" vector

Which indicates if a vertex was already seen by the algorithm and if it was, ignore it

[cerulean wind]

yes, of course, but you won’t ever get the edge (4,2) traversed

[neat oasis]

I get you now

[cerulean wind]

it’s a small issue

but if you can maintain some other information about the state of the dfs, you should be able to fix it

[neat oasis]

Err then I guess I can use something like kruskal's with every edge being of cost 1 or some shit

But the algorithm does seem solid right?

[cerulean wind]

yes!

[neat oasis]

Or instead of "unvisited vertexes" I could keep a vector of unvisited edges

[neat oasis]

Does it seem efficient enough? I think it's O(V+E) (where V is the number of vertices and E the number of edges)

As I'm just running two dfs

[neat oasis]

Which would be the same complexity as tarjan's algorithm if I'm not wrong

[cerulean wind]

yea

[neat oasis]

P sure this should work

[cerulean wind]

not familiar with tarjans, but it does run in O(V + E) time

[cerulean wind]

you need to visit every edge anyways, so that makes sense

[neat oasis]

Ok cool, I was practicing some algorithms past exams, and a question to find bridge edges appeared and the solution mentioned tarjan's algorithm but I didn't know about it so I just kind of thought of my way to do it

[cerulean wind]

but now your dfs complexity may change

i haven’t given it any thought tho

just a consideration

[neat oasis]

It doesn't seem like it would increase in a significant manner in terms of visiting vertexes in the worst case

[cerulean wind]

also, you need to take into account disconnected graphs as input

[neat oasis]

Yeah yeah, obviously

When I run the initial dfs I start from somewhere but if there are any unseen vertices I start a dfs from them too

From a "seen" (now yes) vertices vector

[cerulean wind]

yea

[neat oasis]

Which any normal dfs already does

Ok cool

Anyway, thanks

I may end up programming it if I have time

It doesn't seem really hard to do tbh

[cerulean wind]

it seems like a cool one to do

i’m also brushing up on algorithms for interview prep. might do this one and tarjans now for fun

[neat oasis]

Haha, cool, have fun testing it out, if you end up programming it, may I see it?

[cerulean wind]

yea. would love to see yours if you end up programming it too

[neat oasis]

What do you program in?

[cerulean wind]

C, C++, or Python

wbu?

[neat oasis]

Great, I usually do C++, but I know a little bit of python from a course

[cerulean wind]

great opportunity to learn some more python

[neat oasis]

Maybe when I get to numerical calculus

Next semester

(Mainly because numerical linear algebra was an all-python course)

[shadow cobalt]

python is easy rigth

especially for people new to coding

[neat oasis]

It is intuitive

I preferred starting with C++ tho as you really have to do everything on your own and not rely on 300 libraries, but yeah to grasp coding it is good to start with python

[cerulean wind]

you only begin to appreciate the stl once you try to do anything in C

[shadow cobalt]

anybody do comepetitive coding

[agile magnet]

This is not the server to ask about programming and competitive programming

[neat oasis]

Yeah it was previously related to some algorithms about graphs, sorry

[night magnet]

is "Discrete Math and its applications" a good book to learn?

[arctic berry]

Yeah, lots of people recommend it

[shell yew]

what is the sequence S: N/{0} -> N/{0} such that
x<y->S(x)<S(y)
|{x:S(x)=y}| = S(y)
proportional to? (the first few terms are 1,2,2,3,3,4,4,4,5,5,5,6,6,6,6....)

I thought of the fact that S(sum from n = 1 to y of S(y)) = y
and compared it to the integral of x = 0 to y of f(x) = f^-1(y) and got f(x) = (phi^(1/phi^2))*(x^(1/phi)), but when I tested their ratios on python it was clearly getting smaller and smaller (S(x)/f(x)), and even if that's not a formal proof it does make me doubt that it's proportional to f(x) in any way

[shell yew]

It seems the sequence I mentioned here is basically a not-only 1 and 2 version of this sequence

[polar geode]

what does a ̸≡0 mod 4 mean?

[shell yew]

Without that slash it would mean that 4 divides a. I'm not sure what that slash is doing here but perhaps it means that 4 doesn't divide a?

[polar geode]

and what does the zero mean?

[shell yew]

so this sequence is called Golomb's sequence huh

[shell yew]

a ≡ b mod c means: (these are all the same)
the remainder you get when dividing by c is the same for a and b
c divides b-a
these are the same because if c divides b-a that means that it also divides the difference between the remainders, but the only way that's possible if that difference is 0 so the remainders are the same

a ≡ 0 mod c means that c divides a-0, so basically a

to visualise it you can image a 12-hour clock as being mod 12

if you add the seventh hour and the 6th hour, for example, you get the 1st hour

[shell yew]

apparently it is proportional to x^(phi-1) so now I'm confused

did I do something wrong in python

[vivid osprey]

Basic question. If $I$ is a countable set, is it true that we can find an increasing sequence $(I_n)$ of finite subsets of $I$ such that there union is $I$? I struggle with how to construct such a sequence for an arbitrary countable set $I$? (With the naturals it is immediate.)

[vital dew]

psie

[lethal linden]

If it's countable then it's in bijection with the natural numbers, so use that bijection along with the "immediate" construction in the naturals.

[vivid osprey]

Ok. So suppose we have our finite, increasing subsets of the naturals A1, A2, ... The image or the preimage of a function preserves inclusion, so they'll be increasing in the countable set I too. However, and I feel silly for asking, what property is it that preserves that the sets will be finite in I too?

[lethal linden]

The bijective preimage of a finite set had better be finite.

[vivid osprey]

yes, ok 😅

[hard stone]

Yeah, finite by definition means there's a bijection with some set of the form {0,1,...,n-1}

So if you pick A1 = {0}, A2 = {0,1}, ..., etc., then this guarantees that the corresponding subsets of I will be finite, by definition

[cursive dew]

Learning contradictions for propoisitional logic.
So far i heard 2 sides of the coin.
It is considered a contradictory IF all truth values of both propositions are not logically equivlant. No F - F and no T - T.
The other side i heard elsewhere is that we dont care for F - F, that if F-F we can still consider it a contradiction?
Im hoping we can lean more towards the first one.

[cursive dew]

This claims c and p are contradictions. Yet other info online says they're not cause the bottom row

[true parcel]

It is a contradiction if all possible truth values are false

Meaning, every column of c ^ p must be F

[cursive dew]

is there a single thing explaining this? Im still seeing different things be said. Been only finding bits and pieces around the internet

"Heres a contradiction" shows one example type of stuff

[true parcel]

It's simple