Proof by induction

[jolly vigil]

"Show by induction on k that for all k >= 1, if A has n members, then A^k has n^k members"

I watched two videos and read an article on proof by induction, but I'm still not sure how to craft an induction proof. I understand it at a certain level: it's like recursive programming. You decide a base case and an inductive/recursive step. However, in programming, I don't have to "prove" anything.

The problem itself seems ok: it's exponentiation using sets instead of numbers.

Does anyone have a decent resource for learning how to write a proof with induction? Thank you

[late ether]

In general for two sets $P$ and $Q$, $|P \times Q| = |P| \times |Q|$

This should immediately point you to the inductive step

[jolly vigil]

The "absolute value" of a set is a new concept for me

[soft hull]

zarakshr

[late ether]

I see, when talking about sets the '|' and '|' denote cardinality, not absolute value. So $|P|$ is the cardinality of the set $P$

[soft hull]

zarakshr

[late ether]

where, for your purposes, you can pretend that "cardinality" is "the number of elements" in a set

[real plover]

yes but does cardinality really prove what you're going for

[jolly vigil]

oh, cardinality. yes, number of elements! thank you

[real plover]

I think you need to construct the sets and if you're truly rigorous, you need induction in 2D (both n and k)

[jolly vigil]

I agree, this problem seems a little intense for a beginner like me. It seems like n and k are two important, separate variables.

[real plover]

nah, just a l;ittle odd

[late ether]

you won't need a set-construction if you assume $|P \times Q| = |P| \times |Q|$

[soft hull]

zarakshr

[jolly vigil]

Maybe I could only do single dimension, just k. But I agree, that to prove this completely, I'd need to handle n and k explicitly

[late ether]

also I don't immediately see why an induction on n is needed

[jolly vigil]

This is from the open logic project

[late ether]

try to solve it inductively, I think you can do it.

If you get stuck you can ask for more help

[jolly vigil]

thanks. I'll get to it

[jolly vigil]

My text has this proposition, so maybe I'm supposed to assume like you said |P x Q| = |P| x |Q|

[late ether]

yes, that proposition is true so you can assume it freely

[jolly vigil]

@late ether

It really looks like I've done nothing 😂 It's hard to say I've proven anything. I feel like this is not a great proof to solve with induction. Or rather that this proof is too... obvious to prove or something since the definition of a set product's cardinality is already clear

[jolly vigil]

Maybe I'm really not supposed to assume product cardinality

[late ether]

your induction hypothesis is wrong

you cannot, in the inductive step, assume P(k)
you can only assume P(k - 1) implies P(k)

since the proposition that you are proving is |A^k| = |A|^k, if you assume that during your induction, you get a circular (thus, invalid) proof

[jolly vigil]

thank you! I'll have to try this again

[late ether]

so your induction hyp. will be || |A^k-1| = |A| ^ k - 1 ||

oh my bad, I think your statement of the inductive hypothesis can still be made to work
although you will still have to change the actual induction step in that case

so you can get a proof by either assuming |A^k| = |A|^k and showing that that implies that |A^k+1| = |A|^k+1

or showing that |A^k-1| = |A|^k-1 implies |A^k| = |A|^k

[jolly vigil]

ok, but I've still run up against circular logic, right? the induction step is wrong? ok let me see what I can do

[late ether]

yes

hint: ||think about the algebraic identities that relate multiplication and exponentiation||

OK. anyways I have to go to sleep now, but if you have an interest in formal logic, try to think through the formula below and see if that helps you reason about how induction "should" work
The formula is a bit obtuse, but try and google things like implication,disjunction,conjuction and what they mean and it should help you understand why induction works

$(P(z) \land (\forall k \geq z.P(k) \implies P(k+1))) \implies \forall k \geq z.P(k)$ where $z,k \in \mathbb{N}$

[soft hull]

zarakshr

[jolly vigil]

i am interested in formal logic but i wonder if there's an easier open logic book to start with. I'll browse them and see

.solved

[quiet frost]

Solved

Post marked as solved by @jolly vigil.

Use .unsolved if this was a mistake.