-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathapisct_solutions.html
119 lines (118 loc) · 6.11 KB
/
apisct_solutions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2021-04-18, modified: 2021-04-21, language: english, status: on hold, importance: 2, confidence: likely</em></p>
<blockquote>
<p><strong>Solutions to the book “A Primer in Social Choice Theory” by
Wulf Gaertner.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#Chapter_1">Chapter 1</a><ul><li><a href="#11">1.1</a><ul></ul></li><li><a href="#12">1.2</a><ul></ul></li><li><a href="#13">1.3</a><ul></ul></li><li><a href="#17">1.7</a><ul></ul></li></ul></li></ul></div>
<h1 id="Solutions_to_A_Primer_in_Social_Choice_Theory"><a class="hanchor" href="#Solutions_to_A_Primer_in_Social_Choice_Theory">Solutions to “A Primer in Social Choice Theory”</a></h1>
<p>Note: Instead of using <code>$xIy, xRy$</code> and <code>$xPy$</code>, I will <em>sometimes</em>
write <code>$x \sim y, x \succeq y$</code> and <code>$x \succ y$</code>.</p>
<h2 id="Chapter_1"><a class="hanchor" href="#Chapter_1">Chapter 1</a></h2>
<h3 id="11"><a class="hanchor" href="#11">1.1</a></h3>
<blockquote>
<p>Show that if R is reflexive, complete, and transitive, then for all <code>$x, y, z \in X$</code>:<br/>
(a) <code>$(xIy \land yIz) \rightarrow xIz$</code>; </p>
</blockquote>
<p>We know that <code>$x \sim y \Leftrightarrow x \succeq y \land x \preceq y$</code>.</p>
<p>Then:</p>
<div>
$$(x \sim y \land y \sim z) \Leftrightarrow \\
x \succeq y \land x \preceq y \land y \succeq z \land z \succeq y \Rightarrow \\
x \succeq z \land x \preceq z \Rightarrow \\
x \sim y $$
</div>
<blockquote>
<p>(b) <code>$(xPy \land yRz) \rightarrow xPz$</code></p>
</blockquote>
<div>
$$ x \succ y \land y \succeq z \Leftrightarrow \\
x \succ y \land (y \succ z \lor y \sim z) \Leftrightarrow \\
(x \succ y \land y \succ z) \lor (x \succ y \land y \sim z) \Rightarrow \\
(x \succ z) \lor (x \succ z) \Rightarrow \\
x \succ z $$
</div>
<h3 id="12"><a class="hanchor" href="#12">1.2</a></h3>
<blockquote>
<p>Suppose that R is an ordering over the set <code>$X=\{x,y,z,w\}$</code> with
<code>$xIy$</code>, <code>$yPz$</code>, and <code>$zPw$</code>. Determine the choice set.</p>
</blockquote>
<p><code>$R$</code> is complete, reflexive and transitive. We therefore know:</p>
<p><code>$x \sim y \succ z \succ w$</code>. The choice set is the set of all best
elements, that is the set of all elements who at least as good as any
other element. So, here the choice set is <code>$\{x,y\}$</code>.</p>
<h3 id="13"><a class="hanchor" href="#13">1.3</a></h3>
<blockquote>
<p>Show that if <code>$S \subset X$</code> is finite and R is reflexive, complete,
and quasi-transitive over S, then <code>$C(S, R)$</code> is non-empty.</p>
</blockquote>
<p>If S contains exactly one element (<code>$S=\{x\}$</code>), then that element is
automatically the best element (due to reflexivity: <code>$xRx$</code>).</p>
<p>If S contains exactly two elements (<code>$S=\{x, y\}$</code>), then we have either
<code>$xPy, yPx \text{ or } xIy$</code> (due to completeness), with <code>$\{x\}, \{y\} \text{ and } \{x,y\}$</code>
being the choice sets.</p>
<p>If S contains three or more elements, due to completeness we know
that for an element <code>$x$</code>, there is a finite set <code>$g(x):=\{y: yRx\} \backslash \{x\}$</code>.
If <code>$g(x)=\emptyset$</code>, <code>$x$</code> is the best element. If <code>$g(x)$</code> is not
empty, we can pick an element <code>$y \in g(x)$</code> and generate <code>$g(y)$</code>. We
know that <code>$|g(y)|<g(x)|$</code> (because we're removing at least one element
from <code>$g(x)$</code>, namely <code>$y$</code>). If we repeat the procedure (finitely many
times, since <code>$g(x) \subset S$</code> is finite), we finally arrive at a set
<code>$g(z)$</code> with size <code>$|g(z)|=1$</code>. The element of <code>$g(z)$</code> is a chosen
element.</p>
<h3 id="17"><a class="hanchor" href="#17">1.7</a></h3>
<blockquote>
<p>Let F stand for Fahrenheit and C stand for Celsius. 32° in F are
the same as 0° in C; and 68° in F are the same as 20° in C. Please
specify the mapping F(C) and C(F). Do these mappings have the property
that F values are based on a positive affine transformation of C values,
and vice versa?</p>
</blockquote>
<p>I'm unsure what is asked here. The raw mapping given in set form is just
<code>$F(C)=\{(32, 0), (68, 20)\}$</code> and <code>$C(F)=\{(0, 32), (20, 68)\}$</code>.</p>
<p>The conversion formula for degrees Fahrenheit to Celsius, based on the
given values, can be determined easily from the set of linear equations</p>
<div>
$$ a+32b=0 \\
a+36b=20 $$
</div>
<p>Upon solving, one determines that
<code>$a=-32*\frac{5}{9} \approx -17.7778, b=\frac{5}{9} \approx 0.5556$</code>,
so <code>$F(C) \approx -17.7778+0.5556*C$</code>
and <code>$C(F)=-0.05625*C-1.8$</code>. Since <a href="https://en.wikipedia.org/wiki/Affine_transformation#Over_the_real_numbers">Wikipedia
says</a>
that a linear transformation in <code>$ℝ$</code> is an affine transformation,
this is an affine transformation.</p>
</body></html>