@RoddyMacPhee - NOR and NAND should be easy. The rest you can get at by picking sentence letters to represent the arguments of the function (say p and q) and writing a disjunction made of all of the conjunctions of the conditions under which it comes out true.

For example, for implication you can write out (p & q) v (-p & q) v (-p & -q). Then you can do some distributing, or some plugging in truth values, to see how you can simplify.

Also a bunch of these will be sillier than you think. For example, a couple involve no logical operators.

← 6 messages moved from Logic

@RoddyMacPhee As MaliceVidrine said, this is trivial once you know how to express any arbitrary truth table using a propositional formula, in fact trivially in DNF (disjunctive normal form). The formula you gave for XOR is an example of DNF.

@LucasHenrique: Hello. If you have any questions about basic mathematics, you're welcome to inquire here.

room topic changed to Basic Mathematics: This room is meant for all basic mathematical discussion, including basic logical reasoning, simple properties about natural/rational/real/complex numbers, induction/recursion, elementary combinatorics, synthetic geometry, real analysis, ... (no tags)

@user21820 thank you. I was about to ask something about the algebraic closure of an arbitrary field, then I realized I was in the wrong room haha

@LucasHenrique If it's undergraduate material, I don't mind it here.

If it involves logic (such as "How much set theory do you need to prove the existence and uniqueness of an arbitrary field?"), then you can post in the Logic chat-room.

I’ve posted it in the standard Mathematics chat. If you could take a look I’d appreciate it very much.

Oops I made a typo above: "existence and uniqueness of the algebraic closure of an arbitrary field".

@LucasHenrique Well I don't know what "letters" means, nor why it's so unnecessarily complicated. Constructing the algebraic closure is done by a trivial transfinite recursion.

@LucasHenrique: Are you familiar with transfinite recursion?

@user21820 I just know Zorn’s lemma, and I’m not too good with cardinality/ordinals stuff

And the Axiom of Choice (which is the same thing)

Zorn's lemma is also fine. I can give you a few-line proof using that.

Okay, that’d be great.

Take any field K. Let S = { pair (f,i) : f is a polynomial over K and i∈N }. Let T = { field (M,+,×) : M⊆S and +,×∈(M^2→M) and ∀(f,i)∈M ( f applied to (f,i) in (M,+,×) equals 0 }. Define binary relation ≤ on T such that M ≤ N iff M is a subfield of N. Then (T,≤) is a partial order that we can apply Zorn's lemma to. It suffices to prove that every non-empty chain has an upper bound. Indeed, for any chain C in (T,≤), the union U of fields in C is also a field in T.

Hmm let me change the definition of T to make the rest of the proof easier.

Let T = { field (M,+,×) : K embeds into M and M⊆S and +,×∈(M^2→M) and ∀(f,i)∈M ( f applied to (f,i) in (M,+,×) equals 0 }.

What’s the logic behind this?

tbh I don’t understand where all this came from

That's why Zorn's lemma is actually less intuitive than a straightforward transfinite recursion.

Anyway let me finish the proof first.

Let K* be a maximal field in (T,≤). Now consider any polynomial g over K*. The coefficients of g are algebraic over the embedded copy of K in K*. If g does not split over K*, we can construct a field extension K' of K* where g splits, and we can do so in such a way that the additional elements of K' are all from S. This is because every additional element is also algebraic over K, and every polynomial f has finitely many roots in any extension.

This yields contradiction because K' is also a field in T but strictly larger than K*.

Therefore every polynomial g over K* splits over K*.

@LucasHenrique: That's it. I suggest you first understand the proof step by step, and then maybe you will understand why every step is needed (at least if you want to use Zorn's lemma). I personally prefer the transfinite recursion proof, as it very clearly shows exactly the logical structure underlying the theorem.

It seems that the proof you quote has omitted all the actual details. It is common for non-logicians to use non-rigorous arguments, and there are in fact some incorrect proofs of the algebraic closure existence that use Zorn's lemma wrongly.

If you've any clarification questions, feel free to ask. I'll be away for a while and then reply later.

@user21820 the biggest problem with Lang is that although he’s rigorous, everything is trivial

“Prove that $x^n + y^n = z^n$ has no integral solutions for $n>2$ (Tip: $1+1=2$)” (and there are no solutions or sketches in the book)

@user21820 so what’s T? And what is f applied to (f,i)? Is this N the set of natural numbers? How do we define subfields of $S$?

@LucasHenrique f is a polynomial over K, which is represented by coefficients from K. (f,i) is an element in the field (M,+,×), into which K embeds. To make it concrete for you, let's restrict it to the natural embedding, where each x∈K embeds into (M,+,×) as the pair ((t↦t−x),0), namely as if it's the 0th root of the linear polynomial over K with root x. Applying f to (f,i) then simply means to evaluate f on (f,i) according to the field operations +,× of the field (M,+,×).

Yes N is the set of natural numbers. We just want to have infinitely many pairs (f,i) for each polynomial f over K.

K is a subfield of M iff K,M are fields and the elements of K are elements of M and the field operations on M agree with the field operations on K for elements of K.

@LucasHenrique: Actually I don't know why you seem to be afraid of transfinite recursion. You do not need to know much about ordinals or cardinals to be able to use transfinite recursion in ordinary mathematics.

All you need is the well-ordering theorem, that states that every set can be well-ordered. And you'd be good to go.